Módulo 4: Búsqueda por Proximidad
4. HNSW: Grafos Navegables Jerárquicos
Descripción
HNSW (Hierarchical Navigable Small World) es el índice más usado en vector databases modernas (Pinecone, Weaviate, Qdrant). Aquí entenderás cómo funciona conceptualmente: es un grafo de múltiples capas donde "navegas" saltando de nodo cercano en nodo cercano hasta llegar a la región correcta.
La idea central
Analogía: Buscar una casa en una ciudad grande:
Método lento (brute force):
- Visitar TODAS las casas, medir distancia a cada una
- Retornar la más cercana
Método rápido (HNSW):
- Empezar en autopista (capa alta: saltos grandes)
- Tomar salida más cercana a destino
- Bajar a calles locales (capa baja: saltos pequeños)
- Navegar calle por calle hasta casa específica
HNSW hace lo mismo con vectores: Múltiples capas de "autopistas" a "calles" a "casas".
Estructura de capas
Capa 2 (Autopista):
•────────────────•────────────────•
(Pocos nodos, saltos grandes)
Capa 1 (Avenidas):
•─────•─────•─────•─────•─────•─────•
(Más nodos, saltos medianos)
Capa 0 (Calles):
•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•─•
(Todos los vectores, saltos pequeños)
Cada nodo = un vector del dataset
Aristas = conexiones a vecinos cercanos
Algoritmo de búsqueda (simplificado)
1. Empezar en capa más alta (autopista)
- Punto de entrada: nodo aleatorio
2. Para cada capa (de alta a baja):
- Navegar al vecino más cercano a la query
- Repetir hasta que no haya vecino más cercano
- Bajar a capa siguiente
3. En capa 0 (todos los vectores):
- Navegar buscando K vecinos más cercanos
- Retornar top-K
Ejemplo visual (simplificado en 2D)
Query: ⭐
Capa 2 (autopista):
A•─────────────•B
╱
╱
Entrada→ •C
Navegas: C → B (B está más cerca de ⭐)
Capa 1 (avenidas):
A•───•D───•E───•B
│ │
•F───•G
↑ ⭐ está cerca de G
Navegas: B → E → G (G está más cerca de ⭐)
Capa 0 (calles - todos los vectores):
•D───•H───•E───•I
│ │ │ │
•F───•J───•G───•K
│ ↑│ │
•L───⭐•M─•N
Desde G, encuentras M (vecino más cercano a ⭐) → ¡Resultado! ✅
Ventajas de HNSW
1. Muy rápido:
- Complejidad: O(log N) en lugar de O(N)
- Con 1M vectores: ~20 saltos vs 1M cálculos
2. Alta precisión:
- Típicamente ~98-99% de los verdaderos top-K
3. Escalable:
- Funciona con millones/miles de millones de vectores
4. Sin necesidad de reentrenamiento:
- Puedes agregar vectores dinámicamente (aunque rebuild periódico mejora calidad)
Desventajas de HNSW
1. Uso de memoria:
- Cada nodo guarda conexiones a vecinos (aristas del grafo)
- Típicamente 2-3x más memoria que solo guardar vectores
2. Build time:
- Construir el grafo toma tiempo (horas para miles de millones)
- Trade-off: construcción lenta una vez, búsquedas muy rápidas después
3. No óptimo para inserciones masivas:
- Agregar 1M vectores nuevos → Mejor rebuild completo que insertar uno por uno
Parámetros de configuración
ef_construction (construcción):
ef_construction = 100 → Grafo de menor calidad, build rápido
ef_construction = 400 → Grafo de alta calidad, build lento
ef_search (búsqueda):
ef_search = 50 → Búsqueda rápida, ~95% precisión
ef_search = 200 → Búsqueda lenta, ~99% precisión
M (número de conexiones por nodo):
M = 16 → Menos memoria, menor precisión
M = 64 → Más memoria, mayor precisión
Trade-off típico: ef_construction=200, ef_search=100, M=32
HNSW en producción
Pinecone:
- HNSW por defecto
- Parámetros optimizados automáticamente
Weaviate:
- HNSW con configuración manual (ef_construction, M)
- Recomendación: ef_construction=128, M=32
Qdrant:
- HNSW optimizado con opción de quantization
- Recomendación: ef_construct=200, M=16
Resumen
Puntos clave:
- HNSW: Grafo de múltiples capas (autopistas → calles)
- Navegación: Saltar de vecino en vecino hasta encontrar región correcta
- Ventajas: Muy rápido (O(log N)), alta precisión (~99%)
- Desventajas: Más memoria, build time inicial
- Uso: Estándar en vector databases modernas
Próxima cápsula: 05-ivf-and-clustering.md — Alternativa: IVF (clustering + búsqueda).