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

Cápsula 03: Indexing Algorithms - Overview

Entender POR QUÉ indexing algorithms (HNSW, IVF, PQ) logran búsqueda O(log n) vs brute force O(n), y CUÁNDO usar cada algoritmo según trade-offs.

Al finalizar esta cápsula:

✅ Explicarás diferencia entre brute force O(n) y indexing O(log n)
✅ Compararás HNSW, IVF, PQ (accuracy, speed, memory)
✅ Decidirás cuál algoritmo usar según requisitos de tu RAG system

Tiempo estimado: 8-10 minutos

🧮 Problema: Brute Force O(n) no escala

¿Qué es brute force search?

Definición: Calcular similitud entre query y TODOS los vectores en database, luego ordenar y devolver top-k.

Código conceptual:

def brute_force_search(query, database, k=10):
    similarities = []
    for vector in database:  # ❌ Itera TODOS los vectores
        sim = cosine_similarity(query, vector)
        similarities.append((sim, vector))
    
    # Ordenar y devolver top-k
    similarities.sort(reverse=True)
    return similarities[:k]

Complejidad: O(n) donde n = número de vectores en database.

¿Por qué es problema en RAG?

Escenario típico de RAG production:

Database: 1,000,000 vectores (documentación de producto)
Vector dimension: 1536 (OpenAI text-embedding-3-small)
Requisito: Latencia < 500ms para chatbot

Benchmark brute force con numpy:

Vectores	Latency (numpy)	¿Cumple requisito?
10K	15 ms	✅ Si
100K	150 ms	✅ Si
500K	750 ms	❌ No (>500ms)
1M	1500 ms	❌ No (3x límite)
10M	15000 ms	❌ No (30x límite)

Conclusión: Brute force falla en >100K vectores con requisito <500ms.

¿Solución? Indexing algorithms que evitan comparar con TODOS los vectores.

🎯 Solución: Indexing Algorithms

¿Qué es indexing?

Definición: Construir estructura de datos especializada que organiza vectores de forma que búsqueda sea O(log n) o mejor.

Analogía:

Sin índice (brute force):

Como buscar nombre en lista telefónica desordenada
Debes leer TODAS las páginas (O(n))

Con índice (HNSW, IVF):

Como buscar en lista telefónica ordenada alfabéticamente
Saltas a sección correcta directamente (O(log n))

Principales algoritmos de indexing

Algoritmo	Tipo	Complejidad	Usado por
HNSW	Grafo navegable jerárquico	O(log n)	ChromaDB, Weaviate, Qdrant
IVF	Clustering (k-means)	O(sqrt(n))	Faiss, Milvus
PQ	Compresión de vectores	O(n) compressed	Faiss, Milvus (addon)
ScaNN	Learned quantization	O(log n)	Google Research
NSW	Grafo navegable (no jerárquico)	O(n^(1/2))	Predecessor de HNSW

En esta guía nos enfocamos en: HNSW, IVF, PQ (los más usados en production).

🔍 Algoritmo 1: HNSW (Hierarchical Navigable Small World)

¿Qué es?

Definición: Grafo navegable organizado en capas jerárquicas, donde navegas desde capa superior (saltos largos) a capa inferior (saltos cortos).

Cómo funciona (conceptual)

Analogía: Sistema de autopistas

Capa superior (autopistas): Pocos nodos, saltos largos (100 km)
Capa media (carreteras): Más nodos, saltos medianos (10 km)
Capa inferior (calles): Todos los nodos, saltos cortos (1 km)

Navegación:

Empiezas en capa superior (autopista)
Bajas a capa media cuando estás cerca
Bajas a capa inferior para precisión final

Ventaja: No visitas todos los nodos (O(log n) en lugar de O(n)).

Trade-offs

Ventajas:

✅ Alta accuracy: 95-99% (casi perfecto)
✅ Latencia baja: 10-20ms para 1M vectores
✅ Incremental updates: Puedes agregar vectores uno a uno

Desventajas:

❌ Memoria alta: 4-8 GB para 1M vectores (1536-dim)
❌ Build time lento: 5-10 min para 1M vectores

Usado por

ChromaDB (default)
Weaviate
Qdrant
Milvus (opción)

Cuándo usar HNSW

Usa HNSW cuando:

✅ Accuracy es crítica (>95% requerido)
✅ Tienes RAM suficiente (4-8 GB por 1M vectores)
✅ Latencia debe ser <50ms
✅ Dataset crece incrementalmente (no batch)

Ejemplo RAG: Customer support chatbot (accuracy crítica, <100K vectores, latencia <500ms).

🗂️ Algoritmo 2: IVF (Inverted File Index)

¿Qué es?

Definición: Divide vectores en clusters usando k-means, luego busca solo en clusters más cercanos al query.

Cómo funciona (conceptual)

Analogía: Biblioteca organizada por categorías

Step 1: Agrupa libros en categorías (ciencia, historia, ficción) → Clustering
Step 2: Cuando buscas libro de ciencia, solo buscas en estante de ciencia (no todos) → Query en subset

Búsqueda:

Encuentra cluster más cercano al query (usando centroids)
Busca solo dentro de ese cluster
Devuelve top-k resultados

Ventaja: Buscas en 1-10 clusters (no en 1M vectores).

Trade-offs

Ventajas:

✅ Memoria menor: 1-2 GB para 1M vectores (vs 4-8 GB HNSW)
✅ Build time rápido: 2-3 min para 1M vectores
✅ Bueno para batch updates: Rebuild clusters periódicamente

Desventajas:

❌ Accuracy menor: 90-95% (vs 98% HNSW)
❌ Latencia mayor con pocos clusters: 30-50ms
❌ Requiere tuning: Número de clusters (nlist) afecta mucho

Usado por

Faiss (Facebook AI Research)
Milvus (opción)

Cuándo usar IVF

Usa IVF cuando:

✅ Tienes >1M vectores (IVF escala mejor que HNSW)
✅ Accuracy 90-95% es aceptable
✅ Memoria es limitada (< 4 GB disponible)
✅ Batch updates (rebuild clusters cada día)

Ejemplo RAG: E-commerce search (1M+ productos, accuracy 90% OK, batch updates nocturnos).

📦 Algoritmo 3: PQ (Product Quantization)

¿Qué es?

Definición: Comprime vectores dividiendo en sub-vectores y reemplazando con códigos (codebook), reduciendo memoria 4-8x.

Cómo funciona (conceptual)

Analogía: Compresión de imágenes (JPEG)

Original: Imagen sin comprimir (10 MB)
Comprimida: Imagen JPEG (1 MB)
Trade-off: Calidad ligeramente menor

Para vectores:

Original: Vector de 1536 dims (6 KB)
Comprimido: Vector de 384 dims (1.5 KB)
Trade-off: Accuracy 85-90% (vs 100% original)

Proceso:

Divide vector en sub-vectores (1536 dims → 8 sub-vectores de 192 dims)
Encuentra centroid más cercano para cada sub-vector (codebook)
Reemplaza sub-vector con código (8 bits en lugar de 768 bytes)

Trade-offs

Ventajas:

✅ Memoria 4-8x menor: 500 MB para 1M vectores (vs 4 GB HNSW)
✅ Latencia aceptable: 20-40ms
✅ Económico: Puedes tener 10M+ vectores en RAM

Desventajas:

❌ Accuracy menor: 85-90% (vs 98% HNSW)
❌ Build time lento: Calcular codebook tarda tiempo
❌ Requiere tuning: Número de sub-vectores afecta accuracy

Usado por

Faiss (IVF + PQ combinado)
Milvus (PQ addon)

Cuándo usar PQ

Usa PQ cuando:

✅ Tienes >5M vectores y RAM limitado
✅ Accuracy 85-90% es suficiente
✅ Costo de memoria es crítico
✅ Puedes tolerar latencia 30-50ms

Ejemplo RAG: Knowledge base interno (10M documentos, accuracy 85% OK, RAM limitado).

📊 Comparación: HNSW vs IVF vs PQ

Tabla comparativa

Dimensión	HNSW	IVF	PQ
Complejidad	O(log n)	O(sqrt(n))	O(n) compressed
Accuracy	95-99%	90-95%	85-90%
Latencia (1M vecs)	15-20 ms	30-50 ms	20-40 ms
Memoria (1M vecs)	4-8 GB	1-2 GB	0.5-1 GB
Build time (1M vecs)	5-10 min	2-3 min	10-15 min
Incremental updates	✅ Sí	❌ No (rebuild)	❌ No (rebuild)
Usado por	ChromaDB, Weaviate	Faiss, Milvus	Faiss, Milvus

Visualización de trade-offs

Accuracy vs Memory

High Accuracy (98%) ┤  HNSW
                    │    │
                    │    │
Medium Accuracy     │      IVF
(93%)               │        │
                    │        │
Low Accuracy (88%)  │          PQ
                    │
                    └──────────────────
                      Low ← Memory → High
                      0.5GB  2GB  8GB

¿Cuál elegir?

Decision tree:

¿Accuracy > 95% requerida?
│
├─ Sí → HNSW
│       (ChromaDB, Weaviate)
│
└─ No → ¿Memoria limitada?
        │
        ├─ Sí → PQ
        │       (Faiss IVF+PQ)
        │
        └─ No → ¿>1M vectores?
                │
                ├─ Sí → IVF
                │       (Faiss, Milvus)
                │
                └─ No → HNSW
                        (ChromaDB)

🏭 Algoritmo 4: ScaNN (Bonus)

¿Qué es?

ScaNN (Scalable Nearest Neighbors) es algoritmo de Google Research que usa learned quantization + anisotropic vector quantization.

Trade-offs

Ventajas:

✅ Accuracy similar a HNSW (97-99%)
✅ Latencia 2-3x mejor que HNSW con >5M vectores
✅ Memoria comparable a HNSW

Desventajas:

❌ Complejidad de implementación alta
❌ Requiere TensorFlow (no standalone)
❌ Build time muy lento (research-grade)

Usado por

Google Vertex AI Matching Engine
Research projects (no mainstream en OSS)

Recomendación: Para AI Engineer, enfócate en HNSW/IVF/PQ. ScaNN es para casos edge.

✅ Checklist de comprensión

Verifica que entendiste esta cápsula:

¿Por qué brute force O(n) no escala?
- Respuesta: Con 1M vectores tarda 1500ms. Requisito típico es <500ms. No cumple.
¿Qué es indexing?
- Respuesta: Construir estructura de datos (grafo, clusters, codebook) para búsqueda O(log n) vs O(n).
¿Cuál es trade-off de HNSW vs IVF?
- Respuesta: HNSW = mayor accuracy (98%) + más memoria (8 GB). IVF = menor accuracy (93%) + menos memoria (2 GB).
¿Cuándo usar PQ?
- Respuesta: Cuando tienes >5M vectores, RAM limitado, y accuracy 85-90% es suficiente.
¿Cuál algoritmo usa ChromaDB?
- Respuesta: HNSW (default). Alta accuracy, buena latencia, setup simple.

Si respondiste 4-5/5 correctamente → ✅ Listo para Cápsula 04 (HNSW profundo)

🔗 Conexión con RAG

¿Cómo esto ayuda en RAG?

Elegir vector database según algoritmo

Escenario A: MVP de RAG (10K documentos)

Algoritmo: HNSW (ChromaDB)
Razón: Alta accuracy, setup simple, suficiente memoria
Latencia: <20ms

Escenario B: Production RAG (1M documentos)

Algoritmo: HNSW (Pinecone, Weaviate)
Razón: Accuracy crítica, managed service escala automáticamente
Latencia: <50ms

Escenario C: Massive RAG (10M documentos, budget limitado)

Algoritmo: IVF + PQ (Faiss self-hosted)
Razón: Memoria limitada, accuracy 90% OK
Latencia: <100ms (aceptable para batch)

Debuggear accuracy issues

Problema: "Mi RAG devuelve resultados irrelevantes."

Diagnóstico con conocimiento de algoritmos:

Verificar accuracy del índice:
- HNSW → 98% accuracy esperado
- IVF → 93% accuracy esperado
- PQ → 88% accuracy esperado
Si accuracy es lower than expected → Problema de embeddings (no indexing)
Si accuracy es expected → Problema de prompt/chunking

🚀 Siguiente paso

En cápsula 03 viste overview de algoritmos. Ahora profundizaremos en HNSW (el más usado).

Próxima cápsula: 04 - HNSW (Hierarchical Navigable Small World)

Aprenderás:

Cómo funciona grafo navegable jerárquico (conceptual)
Por qué es O(log n) (navegación vs visita completa)
Parámetros clave (efConstruction, M)
Por qué ChromaDB usa HNSW

Clave: Entenderás arquitectura de HNSW suficientemente para configurar y debuggear (sin implementar desde cero).

Tiempo de lectura: 8-10 minutos
Siguiente: 04-hnsw-profundo.md

← AnteriorCápsula 02: Arquitectura de Vector Databases (3 Capas)Siguiente →Cápsula 04: HNSW - Hierarchical Navigable Small World

Cápsula 03: Indexing Algorithms - Overview

🎯 Objetivo de la cápsula

🧮 Problema: Brute Force O(n) no escala

¿Qué es brute force search?

¿Por qué es problema en RAG?

🎯 Solución: Indexing Algorithms

¿Qué es indexing?

Principales algoritmos de indexing

🔍 Algoritmo 1: HNSW (Hierarchical Navigable Small World)

¿Qué es?

Cómo funciona (conceptual)

Trade-offs

Usado por

Cuándo usar HNSW

🗂️ Algoritmo 2: IVF (Inverted File Index)

¿Qué es?

Cómo funciona (conceptual)

Trade-offs

Usado por

Cuándo usar IVF

📦 Algoritmo 3: PQ (Product Quantization)

¿Qué es?

Cómo funciona (conceptual)

Trade-offs

Usado por

Cuándo usar PQ

📊 Comparación: HNSW vs IVF vs PQ

Tabla comparativa

Visualización de trade-offs

¿Cuál elegir?

🏭 Algoritmo 4: ScaNN (Bonus)

¿Qué es?

Trade-offs

Usado por

✅ Checklist de comprensión

🔗 Conexión con RAG

Elegir vector database según algoritmo

Debuggear accuracy issues

🚀 Siguiente paso