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

Cápsula 05: IVF - Inverted File Index

Siguiente →

🎯 Objetivo de la cápsula

Entender CÓMO funciona IVF (clustering de vectores), por qué es mejor que HNSW para >1M vectores, y cuándo usarlo en RAG systems.

Al finalizar esta cápsula:

  • ✅ Explicarás qué es IVF y cómo usa clustering (k-means)
  • ✅ Entenderás trade-off: accuracy menor + memoria menor
  • ✅ Conocerás parámetros clave (nlist, nprobe)
  • ✅ Decidirás cuándo migrar de HNSW a IVF

Tiempo estimado: 8-10 minutos

🗂️ ¿Qué es IVF?

Definición

IVF = Inverted File Index

Es algoritmo que divide vectores en clusters usando k-means, luego busca solo en clusters más cercanos al query (no en todos).

Analogía: Biblioteca organizada

Sin IVF (brute force):

  • Libros desordenados en pila gigante
  • Buscar libro X = revisar TODOS los libros
  • O(n) = 1,000,000 libros

Con IVF:

  • Libros organizados en estantes por categoría
    • Estante 1: Ciencia (10K libros)
    • Estante 2: Historia (15K libros)
    • Estante 3: Ficción (20K libros)
    • ... (100 estantes total)
  • Buscar libro de ciencia = revisar SOLO estante de ciencia
  • O(n/k) donde k = número de clusters = 10K libros (no 1M)

Speedup: 100x (1M → 10K búsquedas)

🏗️ Arquitectura de IVF

Step 1: Construcción (Build Index)

1. Clustering con k-means

# Conceptual
def build_ivf_index(vectors, nlist=100):
    # 1. Ejecutar k-means para encontrar centroids
    centroids = kmeans(vectors, k=nlist)
    # Resultado: 100 centroids (representan clusters)
    
    # 2. Asignar cada vector a cluster más cercano
    for vector in vectors:
        cluster_id = find_nearest_centroid(vector, centroids)
        inverted_index[cluster_id].append(vector)
    
    # Resultado: Diccionario {cluster_id: [vectores]}
    # Ejemplo: {0: [v1, v2, ...], 1: [v100, v101, ...], ...}

Visualización:

1M vectores                    100 clusters
──────────────────────────────────────────
v1, v2, v3, ..., v1M   →      Cluster 0: [v1, v5, v12, ...] (10K vectores)
                              Cluster 1: [v2, v8, v20, ...] (9K vectores)
                              Cluster 2: [v3, v7, v15, ...] (11K vectores)
                              ...
                              Cluster 99: [v4, v9, v18, ...] (10K vectores)

Parámetro clave: nlist = número de clusters

2. Almacenar inverted index

inverted_index = {
    0: [v1, v5, v12, ...],  # Cluster 0
    1: [v2, v8, v20, ...],  # Cluster 1
    ...
    99: [v4, v9, v18, ...],  # Cluster 99
}

centroids = [c0, c1, c2, ..., c99]  # Centroids de k-means

Step 2: Búsqueda (Query)

1. Encontrar clusters más cercanos

def query_ivf(query, nprobe=10):
    # 1. Encontrar nprobe clusters más cercanos a query
    nearest_clusters = find_nearest_centroids(query, centroids, k=nprobe)
    # Ejemplo: [5, 12, 23, 45, ...] (10 clusters)
    
    # 2. Buscar solo en esos clusters
    candidates = []
    for cluster_id in nearest_clusters:
        candidates.extend(inverted_index[cluster_id])
    
    # 3. Calcular similitud con candidates (no con todos)
    results = []
    for candidate in candidates:
        sim = cosine_similarity(query, candidate)
        results.append((sim, candidate))
    
    # 4. Ordenar y devolver top-k
    results.sort(reverse=True)
    return results[:10]

Parámetro clave: nprobe = número de clusters a explorar

Visualización:

Query: "Python asyncio tutorial"
           ↓ (embedding)
   [0.1, 0.5, 0.8, ...]
           ↓
   Find nearest centroids
           ↓
   Clusters: [5, 12, 23, 45, 67, 78, 81, 92, 95, 99]
           ↓
   Search only in these 10 clusters (100K vectores, no 1M)
           ↓
   Top-10 results

Speedup: 10x (buscar en 100K vs 1M vectores)

📊 Por qué IVF es O(sqrt(n))

Análisis de complejidad

Brute force:

for vector in database:  # n = 1M
    compare(query, vector)

→ O(n)

IVF:

# Step 1: Find nearest centroids
for centroid in centroids:  # nlist = 100
    compare(query, centroid)

# Step 2: Search in nprobe clusters
for cluster in top_nprobe_clusters:  # nprobe = 10
    for vector in cluster:  # ~n/nlist per cluster
        compare(query, vector)

→ O(nlist + nprobe * (n/nlist))
→ Optimal when nlist ≈ sqrt(n) → O(sqrt(n))

Benchmark: Comparaciones reales

Vectores (n)nlistnprobeComparacionesvs Brute Force
100K10010~10K10x faster
1M31610~31K32x faster
10M100010~100K100x faster

Clave: IVF gana más a medida que n crece (mejor para >1M vectores).

⚙️ Parámetros clave de IVF

1. nlist (Número de clusters)

Definición: Número de clusters en los que dividir vectores (k en k-means).

Impacto:

  • nlist alto (1000, 5000):

    • ✅ Mayor accuracy (clusters más específicos)
    • ❌ Build time más lento (k-means con más clusters)
    • ❌ Query ligeramente más lento (más centroids que comparar)

  • nlist bajo (50, 100):

    • ✅ Build rápido
    • ✅ Query rápido
    • ❌ Accuracy menor (clusters muy amplios)

Regla óptima: nlist ≈ sqrt(n)

Vectoresnlist recomendado
100K316
1M1000
10M3162
100M10000

2. nprobe (Clusters a explorar)

Definición: Número de clusters más cercanos a explorar durante query.

Impacto:

  • nprobe alto (50, 100):

    • ✅ Mayor accuracy (explora más clusters)
    • ❌ Query más lento (más vectores que comparar)

  • nprobe bajo (5, 10):

    • ✅ Query rápido
    • ❌ Accuracy menor (puede saltarse cluster correcto)

Regla práctica: nprobe = nlist / 10 (10% de clusters)

Trade-off visualizado:

Accuracy vs Query Speed

High Accuracy    nprobe=100 (explora 100 clusters)
(95%)           ▲  ❌ Slow (100ms)
                │
Medium          │  nprobe=20 (explora 20 clusters)
Accuracy        │  ⚖️ Balanced (30ms)
(92%)           │
                │  nprobe=5 (explora 5 clusters)
Low Accuracy    │  ✅ Fast (10ms)
(88%)           └──────────────────────
                  Fast ← Speed → Slow

3. Metric (Distance)

IVF soporta diferentes métricas de similitud:

MetricFormulaUsado para
Cosine1 - dot(a,b) / (norm(a)*norm(b))Text embeddings (default)
L2sqrt(sum((a-b)^2))Image embeddings
Dot Productdot(a,b)Pre-normalized embeddings

Para RAG: Usa cosine (estándar para text embeddings).

🆚 HNSW vs IVF: Comparación directa

Tabla comparativa

DimensiónHNSWIVF
ComplejidadO(log n)O(sqrt(n))
Accuracy95-99%90-95%
Latency (1M vecs)15-20 ms30-50 ms
Latency (10M vecs)20-30 ms40-60 ms
Memoria (1M vecs)4-8 GB1-2 GB
Build time (1M vecs)5-10 min2-3 min
Incremental updates✅ Sí❌ No (rebuild clusters)
Mejor para<1M vectores>1M vectores

Cuándo usar IVF

Usa IVF cuando:

  • ✅ Tienes >1M vectores (IVF escala mejor)
  • ✅ Accuracy 90-95% es suficiente (no necesitas 98%)
  • ✅ Memoria es limitada (<4 GB disponible)
  • ✅ Batch updates (rebuild nightly OK)

Ejemplo RAG: E-commerce product search con 5M productos.

Cuándo usar HNSW

Usa HNSW cuando:

  • ✅ Accuracy crítica (>95% requerido)
  • ✅ Tienes RAM suficiente (4-8 GB)
  • ✅ <1M vectores
  • ✅ Incremental updates (agregar docs diariamente)

Ejemplo RAG: Customer support chatbot con 100K articles.

🏭 IVF en la práctica: Faiss

Faiss (Facebook AI Similarity Search) es librería optimizada para IVF.

Setup básico

import faiss
import numpy as np

# 1. Crear índice IVF
dimension = 1536  # OpenAI embedding dimension
nlist = 1000  # Número de clusters
quantizer = faiss.IndexFlatL2(dimension)  # Quantizer para centroids
index = faiss.IndexIVFFlat(quantizer, dimension, nlist, faiss.METRIC_L2)

# 2. Train (construir clusters con k-means)
vectors = np.random.random((1_000_000, dimension)).astype('float32')
index.train(vectors)  # ← Esto ejecuta k-means

# 3. Add vectors al índice
index.add(vectors)

# 4. Query
query = np.random.random((1, dimension)).astype('float32')
index.nprobe = 10  # Explorar 10 clusters
distances, indices = index.search(query, k=10)

IVF + PQ (Compresión adicional)

Puedes combinar IVF con PQ para reducir memoria 4-8x:

# IVF + PQ (Product Quantization)
nlist = 1000
m = 8  # Sub-vectores
bits = 8  # Bits per sub-vector

index = faiss.IndexIVFPQ(quantizer, dimension, nlist, m, bits)
index.train(vectors)
index.add(vectors)

# Resultado: 4-8x menos memoria con accuracy 85-90%

Trade-off: IVF solo = 90-95% accuracy. IVF+PQ = 85-90% accuracy.

📊 Benchmark: IVF vs HNSW en producción

Escenario A: 1M vectores

MétricaHNSW (ChromaDB)IVF (Faiss)Ganador
Accuracy98%93%HNSW
Latency18 ms35 msHNSW
Memoria6 GB2 GBIVF
Build time8 min3 minIVF

Conclusión: HNSW mejor para 1M vectores (accuracy + latency).

Escenario B: 10M vectores

MétricaHNSW (Weaviate)IVF (Faiss)Ganador
Accuracy98%92%HNSW
Latency45 ms55 msHNSW
Memoria48 GB12 GBIVF (4x menos)
Build time120 min25 minIVF (5x rápido)

Conclusión: IVF competitivo para 10M vectores (memoria crítica).

Escenario C: 100M vectores

MétricaHNSWIVF (Faiss)Ganador
Accuracy97%91%HNSW
Latency80 ms75 msIVF
Memoria400 GB ❌80 GB ✅IVF (5x menos)
Build time1200 min180 minIVF (6x rápido)

Conclusión: IVF mejor para 100M vectores (HNSW impracticable en RAM).

✅ Ventajas y desventajas de IVF

Ventajas

  1. Memoria eficiente

    • 2-4x menos memoria que HNSW
    • Permite manejar >10M vectores

  2. Build time rápido

    • 2-3x más rápido que HNSW
    • Rebuild clusters es rápido (batch updates)

  3. Escalabilidad lineal

    • Performance predecible con n grande
    • O(sqrt(n)) garantizado

  4. Fácil tuning

    • Solo 2 parámetros: nlist, nprobe
    • Reglas simples (nlist≈sqrt(n), nprobe≈nlist/10)

Desventajas

  1. Accuracy menor (90-95%)

    • vs 98% HNSW
    • Puede ser problema si accuracy crítica

  2. Latency mayor

    • 30-50ms vs 15-20ms HNSW
    • Especialmente con nprobe alto

  3. No incremental updates

    • Agregar vectores requiere rebuild clusters
    • Mejor para batch updates (nightly)

  4. Requiere training

    • k-means necesita dataset representativo
    • Si distribution cambia → rebuild index

🔗 Conexión con RAG

Cuándo migrar de HNSW a IVF en RAG

Señales que necesitas IVF:

  1. Memoria insuficiente

    • HNSW consume >64 GB RAM
    • IVF reduce a 16 GB

  2. Dataset >1M vectores

    • HNSW latencia aumenta significativamente
    • IVF mantiene latencia estable

  3. Accuracy 90-95% es OK

    • No es customer-facing crítico
    • Internal search/analytics

  4. Batch updates

    • Agregar documentos nightly (no real-time)
    • Rebuild clusters es rápido (30 min)

Ejemplo: Knowledge base interno con 5M Confluence pages + Slack messages.

Arquitectura hybrid (HNSW + IVF)

Algunos sistemas combinan ambos:

Hot data (recent, <100K vectores):

  • HNSW para accuracy alta + latency baja
  • Últimos 30 días de documentos

Cold data (old, >1M vectores):

  • IVF para memoria eficiente
  • Historical data (>30 días)

Query strategy:

  • Search HNSW first (recent docs)
  • If not enough results → Search IVF (historical)

✅ Checklist de comprensión

Verifica que entendiste esta cápsula:

  • ¿Qué es IVF?

    • Respuesta: Algoritmo que divide vectores en clusters (k-means), luego busca solo en clusters más cercanos al query.

  • ¿Por qué IVF usa menos memoria que HNSW?

    • Respuesta: No almacena grafo de conexiones (edges). Solo almacena inverted index (cluster_id → vectores).

  • ¿Qué hace parámetro nprobe?

    • Respuesta: Número de clusters a explorar durante query. nprobe alto = mayor accuracy + latency mayor.

  • ¿Cuándo usar IVF vs HNSW?

    • Respuesta: IVF cuando >1M vectores, memoria limitada, accuracy 90% OK, batch updates. HNSW cuando accuracy crítica (>95%), <1M vectores, incremental updates.

  • ¿Por qué IVF no soporta incremental updates?

    • Respuesta: Agregar vectores requiere recalcular clusters (k-means). Rebuild completo es necesario.

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

🚀 Siguiente paso

Ahora que entiendes IVF (clustering), aprenderás PQ (Product Quantization) para compresión extrema.

Próxima cápsula: 06 - PQ (Product Quantization)

Aprenderás:

  • Cómo comprimir vectores 4-8x (1536 dims → 384 dims)
  • Trade-off accuracy vs memory (85% vs 98%)
  • Cuándo usar PQ (>5M vectores, RAM crítico)
  • Combinar IVF + PQ para scale extremo

Clave: PQ sacrifica accuracy (85-90%) pero gana memoria masivamente (10M vectores en 5 GB).

Tiempo de lectura: 8-10 minutos
Siguiente: 06-pq-compresion.md

← AnteriorCápsula 04: HNSW - Hierarchical Navigable Small WorldSiguiente →Cápsula 06: PQ - Product Quantization