HNSW: el algoritmo que hace posible la búsqueda vectorial instantánea

⏱️ Lectura: 15 min

Comparar un vector de embeddings contra mil millones de vectores, uno por uno, puede tardar minutos incluso en un servidor potente. HNSW (Hierarchical Navigable Small World) resuelve ese cuello de botella con un grafo organizado en capas que responde la misma consulta en milisegundos, a cambio de sacrificar un poco de precisión.

📑 En este artículo

1. TL;DR
2. Qué es la búsqueda vectorial aproximada y por qué importa
3. Cómo funciona HNSW por dentro
4. Ejemplos prácticos con hnswlib
   1. Un índice mínimo
   2. Un índice con embeddings reales
5. Cómo empezar: instalación y configuración paso a paso
6. Casos de uso reales
7. Errores comunes y buenas prácticas
8. HNSW frente a otras estrategias de búsqueda vectorial
9. Profundizando: el diseño detrás de las capas
10. Preguntas frecuentes
    1. ¿HNSW da resultados exactos?
    2. ¿Cuánta memoria necesita un índice HNSW?
    3. ¿Puedo eliminar vectores de un índice HNSW ya construido?
    4. ¿Qué distancia debería usar, coseno o L2?
    5. ¿HNSW funciona con miles de millones de vectores?
    6. ¿Dónde se usa HNSW en producción hoy?
11. Referencias

Este algoritmo sostiene la búsqueda vectorial detrás de sistemas de recomendación, buscadores semánticos y la recuperación de contexto en RAG. Faiss, hnswlib, pgvector, Qdrant, Weaviate y Elasticsearch lo usan como motor de índice por defecto.

TL;DR

• Vas a entender por qué la búsqueda exacta de vecinos más cercanos colapsa al llegar a millones de vectores.
• Vas a poder describir la estructura de grafo en capas de HNSW y su parecido con una skip list.
• Vas a saber ajustar M, ef_construction y ef_search para mover el balance entre velocidad y precisión.
• Vas a poder montar un índice HNSW en Python con hnswlib en menos de 15 líneas.
• Vas a saber medir el recall@10 de tu índice comparándolo contra una búsqueda por fuerza bruta.
• Vas a poder decidir cuándo conviene HNSW frente a IVF, LSH o un índice plano.
• Vas a conocer por qué borrar vectores de un índice HNSW no es una operación barata.

Qué es la búsqueda vectorial aproximada y por qué importa

La búsqueda vectorial convierte texto, imágenes o audio en listas de números (embeddings) y busca los vectores más parecidos según una distancia matemática, casi siempre coseno o distancia euclidiana. El problema aparece cuando esa colección crece: comparar una consulta contra cada vector, la llamada búsqueda por fuerza bruta o flat search, tiene costo lineal respecto al tamaño de la colección.

Con mil vectores la fuerza bruta es instantánea. Con cien millones, cada consulta implica cien millones de productos punto, antes de sumar la latencia de red o de disco. HNSW ataca ese costo con una estructura que descarta la mayor parte del espacio de búsqueda sin comparar contra todos los vectores.

El problema de fondo se conoce como la maldición de la dimensionalidad: a medida que sube el número de dimensiones de cada vector (768, 1536, hasta 4096 en algunos modelos), las distancias entre puntos se vuelven cada vez más parecidas entre sí. Estructuras clásicas como los árboles k-d, eficientes en 2 o 3 dimensiones, dejan de aportar ventaja frente a la fuerza bruta en espacios de alta dimensión.

La idea central de HNSW no es nueva: viene de las skip lists, una estructura de listas enlazadas con niveles de atajos. HNSW aplica ese mismo principio a un grafo de vecinos en un espacio de alta dimensión, publicado en 2016 por Malkov y Yashunin en un paper de arXiv que hoy es la referencia estándar del campo.

Cómo funciona HNSW por dentro

HNSW construye varias capas de un mismo grafo. La capa superior tiene pocos nodos y conexiones largas, pensadas para saltar rápido entre regiones lejanas del espacio. Cada capa inferior agrega más nodos y conexiones más cortas, hasta llegar a la capa base, que contiene todos los vectores del índice.

Cada vector nuevo recibe, al insertarse, un nivel máximo asignado al azar con una probabilidad que decae exponencialmente: la mayoría de los nodos solo viven en la capa base, y muy pocos alcanzan las capas superiores. Ese desbalance le da al grafo su forma de small world: pocos saltos largos bastan para recorrer todo el espacio.

Buscar un vecino cercano empieza en un punto de entrada fijo de la capa más alta. El algoritmo avanza de forma golosa hacia el vecino más cercano a la consulta dentro de esa capa, y cuando ya no puede mejorar, baja una capa y repite el proceso, cada vez con un vecindario más denso.

El descenso goloso se detiene en cada capa cuando ningún vecino candidato mejora la distancia a la consulta respecto al mejor candidato actual. En ese punto el algoritmo pasa ese mejor candidato como punto de entrada a la capa inferior, y repite la búsqueda con un conjunto de candidatos mantenidos en una cola de prioridad.

Dos parámetros controlan la forma del grafo: M fija cuántas conexiones mantiene cada nodo (más M significa más memoria y mejor recall, con retornos decrecientes pasado cierto punto), y ef_construction fija cuántos candidatos se evalúan al insertar cada nodo nuevo, lo que afecta la calidad del grafo final.

flowchart TD
subgraph "Capa 2 (dispersa)"
A2["nodo A"] --- B2["nodo B"]
end
subgraph "Capa 1"
A1["nodo A"] --- B1["nodo B"]
B1 --- C1["nodo C"]
end
subgraph "Capa 0 (base, todos los nodos)"
A0["nodo A"] --- B0["nodo B"]
B0 --- C0["nodo C"]
C0 --- D0["nodo D"]
D0 --- E0["nodo E"]
end
A2 -.-> A1
B2 -.-> B1
A1 -.-> A0
B1 -.-> B0
C1 -.-> C0

En consulta aparece un tercer parámetro, ef_search (a veces solo ef), que controla cuántos candidatos mantiene abiertos el algoritmo mientras busca en la capa base. Subir ef_search mejora el recall a costa de latencia; bajarlo hace la consulta más rápida pero puede perder al vecino real.

Ejemplos prácticos con hnswlib

Un índice mínimo

hnswlib es la implementación de referencia en C++ con bindings de Python, y es la base de muchos motores de búsqueda vectorial. Este primer ejemplo crea un índice diminuto de 5 vectores de 4 dimensiones y busca los 2 más parecidos al primero:

import hnswlib
import numpy as np

dim = 4
num_elements = 5

data = np.array([
    [0.1, 0.2, 0.3, 0.4],
    [0.9, 0.8, 0.7, 0.6],
    [0.15, 0.25, 0.35, 0.45],
    [0.5, 0.5, 0.5, 0.5],
    [0.05, 0.1, 0.2, 0.3],
], dtype=np.float32)

index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=num_elements, ef_construction=100, M=16)
index.add_items(data, ids=np.arange(num_elements))
index.set_ef(50)

labels, distances = index.knn_query(data[0], k=2)
print(labels, distances)

init_index reserva espacio para 5 elementos con M=16 y ef_construction=100 (valores generosos para un índice tan pequeño). knn_query devuelve las etiquetas (ids) y las distancias de los 2 vecinos más cercanos al vector 0; el resultado esperado incluye al propio vector 0 (distancia 0) y al vector 2, el más parecido en el espacio de coseno.

Un índice con embeddings reales

El caso realista cambia de escala: 200.000 embeddings de 384 dimensiones, el tamaño típico de un modelo tipo sentence-transformers. Este ejemplo construye el índice, lo guarda en disco y calcula el recall@10 comparando contra una búsqueda exacta:

import hnswlib
import numpy as np

dim = 384
num_embeddings = 200_000

embeddings = np.random.default_rng(42).random((num_embeddings, dim)).astype(np.float32)
query_vectors = embeddings[:100]

index = hnswlib.Index(space='cosine', dim=dim)
index.init_index(max_elements=num_embeddings, ef_construction=200, M=32)
index.add_items(embeddings, ids=np.arange(num_embeddings))
index.save_index("catalogo_productos.hnsw")

index.set_ef(100)
approx_labels, _ = index.knn_query(query_vectors, k=10)

exact_labels = np.argsort(1 - (query_vectors @ embeddings.T), axis=1)[:, :10]

recall = np.mean([
    len(set(approx_labels[i]) & set(exact_labels[i])) / 10
    for i in range(len(query_vectors))
])
print(f"recall@10: {recall:.3f}")

El bloque calcula el top-10 aproximado con knn_query y el top-10 exacto ordenando la matriz completa de similitudes con np.argsort. recall@10 mide qué fracción de los 10 vecinos exactos aparece también en el resultado aproximado: si da 0.95, el índice acierta el 95% de los vecinos reales; si cae por debajo de 0.8, conviene subir ef_search o M.

💡 Tip: normalizá los vectores antes de indexarlos si tu modelo fue entrenado para similitud coseno. Con space='cosine', hnswlib ya normaliza internamente, pero con 'ip' (producto interno) no lo hace por vos.

Cómo empezar: instalación y configuración paso a paso

Para llevar HNSW a un proyecto real, estos son los pasos concretos, sin atajos:

1. Instalar la librería: pip install hnswlib (o faiss-cpu si preferís Faiss con soporte HNSW integrado).
2. Elegir la métrica de espacio según tu modelo de embeddings: cosine, l2 o ip.
3. Definir M (16 a 48 es un rango típico) y ef_construction (100 a 200) al llamar a init_index.
4. Agregar los vectores con add_items(vectores, ids), en lotes si la colección es grande.
5. Guardar el índice con index.save_index("ruta.hnsw") y cargarlo después con load_index.
6. En cada consulta, fijar ef_search por encima de k (por ejemplo, ef_search=100 para k=10).
7. Medir el recall@10 contra fuerza bruta en una muestra antes de pasar a producción.

Si tu stack ya usa PostgreSQL, pgvector agrega un índice HNSW nativo sin salir de SQL:

CREATE INDEX ON productos
USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);

SET hnsw.ef_search = 100;

EXPLAIN ANALYZE
SELECT id FROM productos
ORDER BY embedding <=> '[0.12, 0.04, 0.31]'
LIMIT 10;

El EXPLAIN ANALYZE confirma que Postgres usa el índice: si en el plan aparece Index Scan using sobre el índice HNSW en lugar de un Seq Scan, la consulta está aprovechando el grafo en vez de comparar contra toda la tabla.

Casos de uso reales

El uso más común hoy es RAG (retrieval-augmented generation): un asistente basado en un LLM necesita recuperar los fragmentos de documentación más relevantes para una pregunta, y hace esa búsqueda contra un índice HNSW en vez de leer todo el corpus.

Un caso concreto: un catálogo de e-commerce con millones de productos genera un embedding de imagen y descripción para cada uno. Ante una búsqueda por foto, el sistema convierte la imagen en un vector y consulta el índice HNSW para traer los productos visualmente más parecidos, en el tiempo de respuesta de una request HTTP normal.

Motores de búsqueda semántica y sistemas de recomendación usan la misma técnica para encontrar productos, canciones o artículos parecidos a partir de su representación vectorial. Faiss, la librería de Meta, expone HNSW como uno de sus tipos de índice desde hace años.

Bases de datos como Qdrant, Weaviate y Milvus, y motores de búsqueda como Elasticsearch y OpenSearch (a través del tipo dense_vector), integran HNSW como su índice vectorial por defecto o principal.

Errores comunes y buenas prácticas

⚠️ Ojo: HNSW no soporta eliminar un vector de forma barata. hnswlib permite marcarlo con mark_deleted para excluirlo de futuras búsquedas, pero el nodo sigue ocupando espacio en el grafo hasta que reconstruyas el índice.

index.mark_deleted(id_producto_descontinuado)

# el vector sigue ocupando espacio en el grafo
# hasta reconstruir el indice con save_index() y load_index()

• ef_search igual a k: si pedís los 10 vecinos más cercanos con ef_search=10, el recall suele ser pobre. Dejá margen: ef_search de 50 a 200 según cuánta latencia tolerás.
• Mezclar métricas: indexar con ‘ip’ vectores que no normalizaste rompe la relación entre distancia y similitud real. Si tu modelo asume coseno, normalizá antes de insertar o usá directamente space=’cosine’.
• M excesivo: subir M de 16 a 64 no duplica el recall; duplica la memoria y el tiempo de construcción. Medí el recall real antes de subir M a ciegas.
• Todo en RAM: HNSW mantiene el grafo completo en memoria. Para catálogos de decenas de millones de vectores de alta dimensión, la RAM suele ser el cuello de botella antes que la CPU.
• Subestimar el tiempo de construcción: indexar millones de vectores con M y ef_construction altos puede tardar minutos u horas; probá primero con un subconjunto antes de lanzar la construcción completa en producción.

HNSW frente a otras estrategias de búsqueda vectorial

Ninguna de estas opciones es universalmente mejor: la elección depende del tamaño de la colección, la memoria disponible y cuánta pérdida de recall estás dispuesto a aceptar.

Opción	Cuándo usarla	Ventaja	Limitación
HNSW	Latencia baja y buen recall sin reentrenar el índice	Mejor balance velocidad/precisión de las opciones aproximadas	Todo el grafo vive en RAM; borrar vectores es costoso
IVF (Faiss)	Colecciones enormes con presupuesto de memoria ajustado	Divide el espacio en clusters y solo busca en los más cercanos	Necesita reentrenar los clusters si la distribución de datos cambia mucho
Flat / fuerza bruta	Colecciones pequeñas o cuando el recall debe ser 100%	Resultado exacto, sin aproximación	Costo lineal: se vuelve lento a partir de unos pocos millones de vectores
LSH	Memoria muy limitada y recall aproximado aceptable	Estructura simple basada en funciones hash	Recall generalmente peor que HNSW en la práctica

Profundizando: el diseño detrás de las capas

La asignación de capa de cada nodo sigue la fórmula nivel = floor(-ln(uniform(0,1)) * mL), donde mL es un factor de normalización relacionado con M. Esa distribución exponencial es la misma idea que usan las skip lists para decidir cuántos niveles de atajo recibe cada elemento insertado.

En la capa base cada nodo suele mantener hasta 2×M conexiones (el doble que en las capas superiores), porque ahí ocurre la mayor parte del trabajo real de la búsqueda. Esa asimetría explica por qué la memoria de un índice HNSW crece más rápido que solo dim × num_vectores × 4 bytes: hay que sumar el costo de las listas de adyacencia.

sequenceDiagram
participant Q as Consulta
participant L2 as Capa superior
participant L1 as Capa media
participant L0 as Capa base
Q->>L2: entra por el punto de entrada
L2-->>Q: mejor candidato en esta capa
Q->>L1: desciende con ese candidato
L1-->>Q: candidato refinado
Q->>L0: desciende a la capa base
L0-->>Q: top-k vecinos finales

Construir un índice HNSW es más costoso en tiempo que construir un índice IVF, porque cada inserción hace varias búsquedas golosas para encontrar a quién conectar. A cambio, no exige una fase de entrenamiento previa sobre una muestra de datos, algo que sí necesita IVF para definir sus centroides.

Para reducir la huella de memoria, Faiss combina HNSW con product quantization (PQ): usa el grafo HNSW como capa gruesa de navegación y comprime los vectores reales con códigos cuantizados de unos pocos bytes en vez de guardar el float32 completo, el mismo patrón que usan índices como IVF-PQ, pero con HNSW organizando el grafo en lugar de clusters.

💭 Clave: pgvector no soportó HNSW desde el inicio: sumó ese tipo de índice como alternativa a IVFFlat en una versión posterior de su repositorio, precisamente porque HNSW no exige un paso de entrenamiento previo como sí lo exige IVFFlat.

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: instalá hnswlib con pip install hnswlib, generá 10.000 vectores aleatorios de 128 dimensiones con NumPy, construí un índice y comparate el recall@10 contra fuerza bruta cambiando solo ef_search entre 10, 50 y 200.

Preguntas frecuentes

¿HNSW da resultados exactos?

No. Es un algoritmo de búsqueda aproximada: prioriza velocidad sobre precisión perfecta. El recall, qué tan seguido encuentra al vecino real, se controla ajustando ef_search en el momento de la consulta.

¿Cuánta memoria necesita un índice HNSW?

Como piso, dim × número de vectores × 4 bytes si usás float32, más el costo de las listas de adyacencia de cada nodo, proporcional a M. Un índice de 10 millones de vectores de 768 dimensiones ronda decenas de gigabytes solo en los vectores, sin contar el grafo.

¿Puedo eliminar vectores de un índice HNSW ya construido?

hnswlib permite marcarlos con mark_deleted para excluirlos de futuras búsquedas, pero el nodo sigue ocupando espacio en el grafo. Para liberar memoria de verdad hay que reconstruir el índice desde cero.

¿Qué distancia debería usar, coseno o L2?

Depende de cómo se entrenó el modelo que generó los embeddings. Si el modelo optimiza similitud coseno, normalizá los vectores antes de indexarlos o usá directamente space='cosine' en hnswlib.

¿HNSW funciona con miles de millones de vectores?

Sí, pero al vivir enteramente en RAM conviene combinarlo con cuantización, como hace Faiss con product quantization, o distribuirlo entre varios nodos, en vez de intentar meter todo en una sola máquina.

¿Dónde se usa HNSW en producción hoy?

En Faiss, hnswlib, pgvector, Qdrant, Weaviate, Milvus y en el tipo dense_vector de Elasticsearch y OpenSearch. Es el índice aproximado más extendido del ecosistema de bases de datos vectoriales.

Referencias

• Malkov y Yashunin, arXiv 1603.09320: el paper original que describe HNSW y su relación con las skip lists.
• nmslib/hnswlib en GitHub: la implementación de referencia en C++ con bindings de Python usada en los ejemplos de este artículo.
• facebookresearch/faiss en GitHub: la librería de Meta que combina HNSW con cuantización de producto para índices más compactos.
• pgvector/pgvector en GitHub: la extensión de PostgreSQL que agrega índices HNSW nativos sobre la columna vector.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de A Chosen Soul en Unsplash