16 · Vecinos más cercanos aproximados
La búsqueda por fuerza bruta es O(N) por consulta — bien para miles, imposible para millones. Los índices ANN (IVF, HNSW) cambian una pizca de recall por una aceleración enorme al buscar solo una fracción de los vectores.
La búsqueda de vecinos más cercanos aproximados (ANN) supera a la fuerza bruta al NO comparar la consulta con cada vector. IVF agrupa los datos y busca solo en los pocos clústeres más cercanos; HNSW recorre con avidez un grafo navegable. Cedes un poco de recall (puedes perder un vecino verdadero) por una aceleración de un orden de magnitud.
Sin esto:
Sin ANN, cada consulta escanea los N vectores. Está bien en una demo pero se siente cuadrático a escala: con 10M de vectores una consulta por fuerza bruta es demasiado lenta y consume demasiada CPU, así que la latencia y las facturas explotan.
La lección pasada nuestro query corría un bucle de coseno sobre cada registro. Eso es búsqueda exacta / por fuerza bruta: O(N) comparaciones por consulta. Con 5 documentos es instantáneo; con 10 millones es inviable — no puedes hacer el producto punto de 10M de vectores por cada tecla del usuario.
La solución es la búsqueda de Vecinos Más Cercanos Aproximados (ANN). La palabra "aproximados" es el trato: aceptas una pequeña probabilidad de perder un vecino verdadero a cambio de buscar solo una fracción de los datos. Dominan dos familias:
IVF — Índice de Archivo Invertido (agrupar y luego sondear). Pre-agrupa todos los vectores en, digamos, 100 buckets (con k-means). Cada bucket tiene un centroide (su vector promedio). En la consulta tú (1) comparas la consulta con los ~100 centroides, (2) eliges los nprobe buckets más cercanos y (3) corres la búsqueda exacta de coseno solo dentro de esos buckets. Si cada bucket tiene N/100 vectores y sondeas 3 buckets, comparas contra ~3N/100 vectores en vez de N — un recorte de ~30×. El riesgo: un vecino verdadero que esté en un bucket que no sondeaste se pierde.
HNSW — Mundo Pequeño Navegable Jerárquico (recorrido ávido por grafo). Construye un grafo multicapa donde cada vector enlaza con unos pocos vecinos cercanos. La búsqueda empieza en un punto de entrada de la capa superior (dispersa) y salta con avidez al vecino que esté más cerca de la consulta, descendiendo capas hasta converger — como hacer zoom en un mapa. Visita solo un número logarítmico de nodos, nunca los N. Es el predeterminado en la mayoría de BD vectoriales modernas porque el recall se mantiene alto con latencia muy baja.
Ambos mandos intercambian la misma moneda: recall@k vs velocidad. Recall@k = (verdaderos top-k vecinos que el ANN realmente devolvió) / k. Sondea más buckets (IVF) o ensancha el haz de búsqueda (HNSW) → más recall, más lento. Sondea menos → más rápido, menos recall. ¡Construyamos IVF y midamos ese tradeoff!
Abajo implementamos IVF de principio a fin con un k-means diminuto inline (RNG con semilla, así es reproducible). Agrupamos ~200 vectores aleatorios en buckets, luego para una consulta comparamos dos estrategias:
- Fuerza bruta — coseno contra los 200 (la verdad exacta).
- IVF — encontrar los
nprobecentroides más cercanos y buscar solo en esos buckets.
Reportamos cuántas comparaciones hizo cada uno y el recall@k de IVF contra la respuesta exacta. Luego barremos nprobe para ver el recall subir hacia 1.0 a medida que sondeamos más buckets — el dial velocidad/recall en acción.
Python (in browser)
IVF busca solo en los clústeres más cercanos: con nprobe=2 hace una fracción de las comparaciones y aun recupera la mayoría del top-k verdadero. Sondear más cambia velocidad por recall.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Los números cuentan toda la historia. Con nprobe=1 IVF compara contra una pequeña porción y corre más rápido, pero el recall está por debajo de 1.0 — a veces pierde un vecino verdadero que vivía en un bucket no sondeado. A medida que nprobe sube, más comparaciones recuperan más del top-k verdadero, hasta que sondear todos los buckets vuelve a ser fuerza bruta (recall 1.0, sin ahorro). El punto óptimo es el menor nprobe que da un recall aceptable para tu tarea.
En producción nunca construyes esto a mano — pero el read-along te muestra que los mandos son las mismas palabras que acabas de implementar. Faiss expone nlist (número de buckets IVF) y nprobe; HNSW expone M (grado del grafo) y efSearch (ancho del haz de búsqueda). Cada uno de ellos es el dial recall/velocidad que acabas de girar.
Faiss IVF (nlist/nprobe) y HNSW (M/efSearch) son las versiones de producción del dial que afinaste a mano — el mismo tradeoff recall-vs-velocidad, implementado a velocidad nativa.
Un índice IVF divide 1.000.000 de vectores en 1.000 buckets. Pones nprobe=5. ¿Contra cuántos vectores compara aproximadamente cada consulta, y cuál es el truco?
- La búsqueda exacta por fuerza bruta es O(N) por consulta — bien para miles de vectores, demasiado lenta para millones.
- IVF agrupa vectores con k-means y sondea solo los pocos buckets más cercanos; HNSW recorre un grafo navegable con avidez — ambos visitan una fracción de los datos.
- ANN cambia recall por velocidad: nprobe (IVF) y efSearch (HNSW) regulan cuántos vectores revisas, así que mide siempre recall@k en tus datos al afinar.
Toda BD vectorial a gran escala (Pinecone, Qdrant, Milvus, pgvector con HNSW) usa índices ANN; Faiss impulsa muchas de ellas por debajo con los mandos nlist/nprobe y M/efSearch que acabas de usar.
Si lo quitas: Sin ANN, la latencia de recuperación crece linealmente con el corpus; pasados unos millones de vectores cada consulta se vuelve demasiado lenta y costosa para servir en tiempo real.