5. IVF: Inverted File Index y Clustering

Descripción

IVF (Inverted File Index) es una alternativa a HNSW basada en clustering: divide el espacio en regiones (clusters), asigna cada vector a un cluster, y al buscar solo revisa clusters cercanos a la query. Usa menos memoria que HNSW pero típicamente menor precisión.

---

La idea central

Analogía: Biblioteca con secciones temáticas:

Método lento (brute force):

• Revisar TODOS los libros en toda la biblioteca

Método rápido (IVF):

1. Dividir biblioteca en secciones (Ficción, Ciencia, Historia, etc.)
2. Query: "libro de ciencia sobre física"
3. Ir directamente a sección Ciencia
4. Buscar solo en esa sección (no revisar Ficción ni Historia)

IVF hace lo mismo con vectores: Divide el espacio en clusters, busca solo en clusters relevantes.

---

Algoritmo de IVF

Fase 1: Construcción (offline)

1. Tomar todos los vectores del dataset
2. Aplicar clustering (ej: k-means) para crear N clusters
   - Típicamente N = √(tamaño_dataset)
   - Ej: 1M vectores → 1000 clusters
3. Asignar cada vector a su cluster más cercano
4. Guardar índice invertido:
   - Cluster 1 → [vector_23, vector_891, ...]
   - Cluster 2 → [vector_45, vector_102, ...]
   - ...

---

Fase 2: Búsqueda (online)

Query: Vector query

1. Encontrar los nprobe clusters más cercanos a la query
   - nprobe = 1: Solo el cluster más cercano
   - nprobe = 10: Los 10 clusters más cercanos
   
2. Buscar exhaustivamente solo en esos clusters
   - Calcular similaridad(query, vector) para vectores en clusters seleccionados
   
3. Retornar top-K vectores con mayor similaridad

---

Visualización (2D simplificado)

Espacio dividido en 4 clusters:

        |         
  C1    |    C2   
   •  • | • •  •  
  •  •  |  • •    
────────────────── Query ⭐
  • •   |     •   
   •  • | •  •  • 
  C3    |    C4   
        |         

Query ⭐ está cerca del límite entre C2 y C4

Con nprobe=1:

• Solo buscar en C4 (cluster más cercano)
• Puede perder resultados en C2 ❌

Con nprobe=2:

• Buscar en C2 y C4
• Mayor probabilidad de encontrar todos los top-K ✅

---

Ventajas de IVF

1. Menos memoria que HNSW:

• Solo necesita guardar: vectores + asignación a clusters + centroides
• HNSW necesita: vectores + grafo completo (más conexiones)

2. Rápido para búsquedas:

• Con nprobe pequeño, revisa solo una fracción del dataset
• Ej: nprobe=10 de 1000 clusters → Revisa ~1% de vectores

3. Simple de entender e implementar:

• Clustering estándar (k-means)
• Sin estructuras complejas como grafos

---

Desventajas de IVF

1. Menor precisión que HNSW:

• Típicamente ~95-98% vs ~98-99% de HNSW
• Puede perder resultados si están en "cluster incorrecto"

2. Sensible a calidad de clustering:

• Si clusters mal formados → Peor precisión
• Requiere re-clustering periódico al agregar muchos vectores

3. Trade-off más marcado:

• nprobe pequeño → Rápido pero impreciso
• nprobe grande → Lento, acercándose a brute force

---

Parámetros de configuración

nlist (número de clusters):

nlist = sqrt(N)  → Regla general
Ej: 1M vectores → 1000 clusters

nprobe (clusters a buscar):

nprobe = 1   → Muy rápido, ~90% precisión
nprobe = 10  → Rápido, ~95% precisión
nprobe = 100 → Lento, ~98% precisión

Trade-off típico: nlist=1000, nprobe=10 (95% precisión, rápido)

---

IVF vs HNSW

Aspecto	HNSW	IVF
Precisión	~98-99% ✅	~95-98% ⚠️
Velocidad	Muy rápido ✅	Rápido ✅
Memoria	Alta (2-3x vectores) ⚠️	Media (1.2-1.5x vectores) ✅
Escalabilidad	Millones ✅	Miles de millones ✅
Inserciones	Más costoso ⚠️	Más fácil (reasignar a cluster) ✅
Uso típico	Producción general	Datasets masivos con budget memoria

---

Variantes de IVF

IVF-Flat:

• Básico: Clustering + búsqueda exacta en clusters
• Alta precisión dentro de clusters

IVF-PQ (Product Quantization):

• IVF + compresión de vectores
• Mucho menos memoria (~10-20x compresión)
• Menor precisión pero escala a miles de millones

IVF-HNSW (híbrido):

• IVF para primera etapa (encontrar clusters)
• HNSW para segunda etapa (buscar en clusters)
• Combina ventajas de ambos

---

IVF en producción

FAISS (Facebook):

• IVF es uno de los índices principales
• Múltiples variantes (IVF-Flat, IVF-PQ, IVF-HNSW)
• Configuración manual requerida

Weaviate:

• Soporte para IVF como alternativa a HNSW
• Menos común (HNSW por defecto)

Milvus:

• Soporte completo para IVF y variantes
• Recomendado para datasets > 10M vectores con constraints de memoria

---

Cuándo usar IVF

Usa IVF cuando:

• Dataset muy grande (> 10M vectores)
• Memoria es limitada
• Precisión ~95% es aceptable
• Inserciones frecuentes (más fácil que HNSW)

Usa HNSW cuando:

• Precisión crítica (~99% requerida)
• Memoria disponible
• Dataset < 10M vectores
• Pocas inserciones (batches periódicos)

---

Resumen

Puntos clave:

• IVF: Clustering + búsqueda en clusters relevantes
• nprobe: Controla trade-off precisión vs velocidad
• Ventajas: Menos memoria, más simple
• Desventajas: Menor precisión que HNSW
• Uso: Datasets masivos con constraints de memoria

---

Próxima cápsula: 06-tradeoffs-and-decisions.md — Cuándo usar cada índice.