Módulo 2: Cómo funcionan Vector Databases (Conceptual)

Cápsula 04: HNSW - Hierarchical Navigable Small World

Entender CÓMO funciona HNSW (grafo navegable jerárquico) conceptualmente, por qué logra O(log n), y cuándo usarlo en RAG systems.

Al finalizar esta cápsula:

✅ Explicarás qué es grafo navegable jerárquico
✅ Entenderás por qué HNSW es O(log n) (no O(n))
✅ Conocerás parámetros clave (M, efConstruction, efSearch)
✅ Decidirás cuándo usar HNSW vs otros algoritmos

Tiempo estimado: 10-12 minutos

🧩 ¿Qué es HNSW?

Definición

HNSW = Hierarchical Navigable Small World

Es un grafo navegable organizado en capas jerárquicas, donde cada capa tiene subset de nodos y conexiones de largo alcance (small world property).

Small World Graph (concepto previo)

Small World es propiedad de grafos donde:

Mayoría de nodos NO están directamente conectados
Pero cualquier par de nodos está a pocos saltos de distancia

Ejemplo: Red social (6 grados de separación)

No conoces a todos directamente
Pero puedes llegar a cualquier persona en ~6 saltos (friend of friend of friend...)

Aplicado a vectores:

Cada vector es nodo
Nodos similares están conectados
Puedes llegar a cualquier vector similar en pocos saltos (O(log n))

🏗️ Arquitectura de HNSW

Capas jerárquicas

HNSW organiza vectores en múltiples capas (levels), donde:

Capa superior (Layer 2+): Pocos nodos, conexiones largas (saltos grandes)
Capa media (Layer 1): Más nodos, conexiones medianas
Capa base (Layer 0): TODOS los nodos, conexiones cortas

Visualización:

Layer 2 (Top):    A ←─────────→ B
                  │             │
                  │             │
Layer 1:          A ←─→ C ←─→ D ←─→ B
                  │    │     │     │
                  │    │     │     │
Layer 0 (Base):   A→C→E→F→G→D→H→I→B
                  (todos los vectores)

Clave:

Layer 2: Solo A y B (salto largo A→B)
Layer 1: A, B, C, D (saltos medianos)
Layer 0: Todos los vectores (saltos cortos)

¿Por qué jerárquico?

Analogía: Sistema de transporte

Sin jerarquía (brute force):

Solo caminas (no autopistas)
De A a B = 100 km caminando = 20 horas

Con jerarquía (HNSW):

Camina a estación tren (1 km = 15 min)
Tren a ciudad cercana (90 km = 1 hora)
Camina a destino final (1 km = 15 min)
Total: 1h 30min (vs 20 horas)

Aplicado a búsqueda:

Layer 2: Saltos largos (encuentra región correcta)
Layer 1: Saltos medianos (refina región)
Layer 0: Saltos cortos (encuentra vecino exacto)

🔍 Cómo funciona: Búsqueda en HNSW

Algoritmo de navegación (conceptual)

def search_hnsw(query, graph, k=10):
    # Step 1: Empezar en capa superior con nodo aleatorio
    current_layer = max_layer
    current_node = entry_point  # Nodo inicial
    
    # Step 2: Navegar hacia abajo
    while current_layer > 0:
        # Encontrar vecino más cercano al query en capa actual
        current_node = greedy_search(query, current_node, current_layer)
        
        # Bajar a capa inferior
        current_layer -= 1
    
    # Step 3: Búsqueda final en capa base (Layer 0)
    candidates = greedy_search(query, current_node, layer=0)
    
    # Step 4: Devolver top-k más similares
    return top_k(candidates, k)

Ejemplo paso a paso

Escenario: Buscar documento similar a query "Python asyncio tutorial"

Database: 1,000,000 vectores en HNSW con 3 layers

Step 1: Empezar en Layer 2 (Top)

Query embedding: [0.1, 0.5, 0.8, ...]

Layer 2:  A ←─────────→ B
         (entry_point)

Comparar query con A y B:
- Similarity(query, A) = 0.3
- Similarity(query, B) = 0.7  ← Más cercano

→ Moverse a B

Step 2: Bajar a Layer 1

Layer 1:  A ←─→ C ←─→ D ←─→ B
                          (current)

Vecinos de B en Layer 1: C, D
Comparar query con vecinos:
- Similarity(query, C) = 0.6
- Similarity(query, D) = 0.8  ← Más cercano

→ Moverse a D

Step 3: Bajar a Layer 0 (Base)

Layer 0:  ... → D → H → I → J → ...
                (current)

Vecinos de D en Layer 0: H, I, J, K, ...
Comparar query con vecinos:
- Similarity(query, H) = 0.75
- Similarity(query, I) = 0.85  ← Top 1
- Similarity(query, J) = 0.82  ← Top 2
- ...

→ Devolver top-10: [I, J, K, ...]

Total de comparaciones: ~50-100 (vs 1,000,000 en brute force)

Speedup: 10,000x - 20,000x

📊 Por qué HNSW es O(log n)

Análisis de complejidad

Brute force:

for vector in database:  # n iteraciones
    compare(query, vector)

→ O(n)

HNSW:

# Layer 2: ~10 nodos, ~5 comparaciones
# Layer 1: ~100 nodos, ~10 comparaciones
# Layer 0: ~1000 nodos, ~20 comparaciones

Total comparaciones ≈ log2(n) * M
→ O(log n)

Donde:

n = total de vectores
M = número de conexiones por nodo (parámetro configurable)

Benchmark: Comparaciones reales

Vectores (n)	Brute Force	HNSW	Speedup
10K	10,000	50	200x
100K	100,000	75	1,333x
1M	1,000,000	100	10,000x
10M	10,000,000	150	66,666x

Clave: HNSW crece logarítmicamente (100→150 comparaciones cuando n crece 10x).

⚙️ Parámetros clave de HNSW

1. M (Conexiones por nodo)

Definición: Número máximo de conexiones bidireccionales por nodo en cada layer.

Impacto:

M alto (64, 128):
- ✅ Mayor accuracy (más caminos alternativos)
- ❌ Más memoria (más conexiones almacenadas)
- ❌ Build time más lento
M bajo (4, 8):
- ✅ Menos memoria
- ✅ Build más rápido
- ❌ Accuracy menor (menos caminos)

Recomendado:

M = 16 (default ChromaDB, Weaviate) → Balance accuracy/memoria
M = 32 (high accuracy) → Casos donde accuracy crítica
M = 8 (low memory) → Casos con memoria limitada

2. efConstruction (Effort Construction)

Definición: Número de candidatos explorados durante construcción del índice.

Impacto:

efConstruction alto (200, 400):
- ✅ Índice de mayor calidad (mejor accuracy)
- ❌ Build time más lento
efConstruction bajo (50, 100):
- ✅ Build rápido
- ❌ Accuracy menor

Recomendado:

efConstruction = 200 (default) → Balance
efConstruction = 400 (high accuracy) → Production crítica
efConstruction = 100 (fast build) → Desarrollo/testing

3. efSearch (Effort Search)

Definición: Número de candidatos explorados durante búsqueda (query time).

Impacto:

efSearch alto (200, 500):
- ✅ Mayor accuracy (explora más vecinos)
- ❌ Latencia mayor (más comparaciones)
efSearch bajo (50, 100):
- ✅ Latencia menor
- ❌ Accuracy menor

Recomendado:

efSearch = 100 (default) → Balance
efSearch = 200 (high accuracy) → RAG crítico
efSearch = 50 (fast query) → Performance crítico

Trade-offs visualizados

Accuracy vs Speed vs Memory

                  efConstruction=400
High Accuracy     M=32, efSearch=200
(98%)            ▲
                 │  ← High Memory (8 GB)
                 │     Slow Build (10 min)
Medium           │     Fast Query (15ms)
Accuracy         │
(95%)            │  efConstruction=200
                 │  M=16, efSearch=100
                 │  ← Medium Memory (4 GB)
Low Accuracy     │     Medium Build (5 min)
(92%)            │     Medium Query (25ms)
                 │
                 └──────────────────────
                   Low ← Resources → High

🏭 HNSW en la práctica

ChromaDB configuración

ChromaDB usa HNSW por default. Puedes configurar parámetros:

import chromadb

# Crear collection con HNSW custom
collection = client.create_collection(
    name="my_docs",
    metadata={
        "hnsw:space": "cosine",  # Distance metric
        "hnsw:M": 32,  # Más conexiones (mayor accuracy)
        "hnsw:construction_ef": 200,  # Build quality
        "hnsw:search_ef": 100,  # Query quality
    }
)

Cuándo ajustar:

Accuracy <90% → Aumentar M y efSearch
Build time muy lento → Reducir efConstruction
Query latency >100ms → Reducir efSearch

Weaviate configuración

collection_config = {
    "vectorIndexType": "hnsw",
    "vectorIndexConfig": {
        "maxConnections": 64,  # M parameter
        "efConstruction": 128,
        "ef": 100,  # efSearch
    }
}

Pinecone (HNSW-like custom)

Pinecone usa algoritmo similar a HNSW (no expone parámetros directamente):

# Pinecone maneja tuning automáticamente
index.query(
    vector=query_embedding,
    top_k=10,
    # No configuras M, ef (managed service)
)

✅ Ventajas y desventajas de HNSW

Ventajas

Alta accuracy (95-99%)
- Mejor que IVF (90-95%) y PQ (85-90%)
- Casi perfecto vs brute force
Latencia predecible
- O(log n) garantizado
- 15-20ms para 1M vectores (consistente)
Incremental updates
- Puedes agregar vectores uno a uno
- No requiere rebuild completo (vs IVF)
Open source maduro
- hnswlib (C++ library)
- Integrado en ChromaDB, Weaviate, Qdrant

Desventajas

Memoria alta
- 4-8 GB para 1M vectores (1536-dim)
- Conexiones (edges) almacenadas en RAM
Build time lento
- 5-10 min para 1M vectores
- Trade-off: Mejor calidad de índice
No comprime vectores
- Full dimensionality stored
- Para comprimir, combinar con PQ
Delete operations costosas
- Requiere rebuild de conexiones
- Mejor usar soft deletes (metadata filter)

🔗 Conexión con RAG

¿Por qué HNSW es ideal para RAG?

Requisitos típicos de RAG:

Accuracy crítica (>95%) → HNSW cumple (98%)
Latencia <500ms → HNSW cumple (15-20ms)
Incremental updates (agregar documentos diariamente) → HNSW soporta
Scale moderado (100K-1M documentos MVP) → HNSW maneja bien

Trade-off aceptable:

Memoria alta (4-8 GB) es OK para MVP/mid-size RAG

Casos de uso RAG + HNSW

Caso A: Customer Support Chatbot

Documents: 50K support articles
Requisito: Accuracy >95%, Latency <500ms
Solución: ChromaDB con HNSW (default config)
Resultado: 98% accuracy, 15ms latency, 2 GB RAM

Caso B: Internal Knowledge Base

Documents: 500K Confluence pages + Slack messages
Requisito: Accuracy >90%, Latency <1s
Solución: Weaviate con HNSW (M=32, efSearch=200)
Resultado: 97% accuracy, 50ms latency, 16 GB RAM

Caso C: Legal Document Search

Documents: 1M legal cases
Requisito: Accuracy >98% (crítico)
Solución: Pinecone (HNSW-like, managed)
Resultado: 99% accuracy, 30ms latency, managed RAM

✅ Checklist de comprensión

Verifica que entendiste esta cápsula:

¿Qué es HNSW?
- Respuesta: Grafo navegable organizado en capas jerárquicas, donde navegas desde capa superior (saltos largos) a capa inferior (saltos cortos).
¿Por qué HNSW es O(log n)?
- Respuesta: No visitas todos los nodos (n), solo navegas ~log2(n) * M nodos usando jerarquía.
¿Qué hace parámetro M?
- Respuesta: Número de conexiones por nodo. M alto = mayor accuracy + más memoria. M bajo = menos memoria + accuracy menor.
¿Cuándo usar HNSW vs IVF?
- Respuesta: HNSW cuando accuracy crítica (>95%), tienes RAM suficiente, y updates incrementales. IVF cuando >1M vectores y accuracy 90% OK.
¿Por qué ChromaDB usa HNSW?
- Respuesta: Balance perfecto para RAG: Alta accuracy (98%), latencia baja (15ms), incremental updates, setup simple.

Si respondiste 4-5/5 correctamente → ✅ Listo para Cápsula 05 (IVF)

🚀 Siguiente paso

Ahora que entiendes HNSW profundamente, aprenderás IVF (Inverted File Index).

Próxima cápsula: 05 - IVF (Inverted File Index)

Aprenderás:

Cómo funciona clustering de vectores (k-means)
Por qué IVF es mejor que HNSW para >1M vectores
Trade-off accuracy vs memory
Cuándo migrar de HNSW a IVF

Clave: IVF sacrifica accuracy (93% vs 98% HNSW) pero gana en memoria y scale.

Tiempo de lectura: 10-12 minutos
Siguiente: 05-ivf-clustering.md

← AnteriorCápsula 03: Indexing Algorithms - Overview Siguiente →Cápsula 05: IVF - Inverted File Index

Cápsula 04: HNSW - Hierarchical Navigable Small World

🎯 Objetivo de la cápsula

🧩 ¿Qué es HNSW?

Definición

Small World Graph (concepto previo)

🏗️ Arquitectura de HNSW

Capas jerárquicas

¿Por qué jerárquico?

🔍 Cómo funciona: Búsqueda en HNSW

Algoritmo de navegación (conceptual)

Ejemplo paso a paso

Step 1: Empezar en Layer 2 (Top)

Step 2: Bajar a Layer 1

Step 3: Bajar a Layer 0 (Base)

📊 Por qué HNSW es O(log n)

Análisis de complejidad

Benchmark: Comparaciones reales

⚙️ Parámetros clave de HNSW

1. M (Conexiones por nodo)

2. efConstruction (Effort Construction)

3. efSearch (Effort Search)

Trade-offs visualizados

🏭 HNSW en la práctica

ChromaDB configuración

Weaviate configuración

Pinecone (HNSW-like custom)

✅ Ventajas y desventajas de HNSW

Ventajas

Desventajas

🔗 Conexión con RAG

¿Por qué HNSW es ideal para RAG?

Casos de uso RAG + HNSW

✅ Checklist de comprensión

🚀 Siguiente paso