Búsqueda vectorial sin fuerza bruta: cómo funcionan IVF y HNSW

Búsqueda Vectorial Sin Fuerza Bruta: Cómo Funcionan IVF y HNSW

Cuando una base de datos vectorial contiene millones de embeddings, buscar vectores similares mediante fuerza bruta se vuelve imposible. Dos algoritmos — IVF y HNSW — resuelven esta tarea mediante búsqueda aproximada, encontrando respuestas en milisegundos en lugar de minutos. Un nuevo artículo detallado en Habr analiza ambos enfoques desde la teoría matemática hasta la implementación en Python.

Por Qué la Búsqueda Exacta No Funciona

En dimensiones bajas (2D, 3D), puede construir índices espaciales — árboles k-d, árboles R. Utilizan geometría: si una consulta está lejos de una parte del espacio, puede excluirse de la búsqueda sin perder resultados. Pero en dimensiones altas (768D para BERT, 3072D para GPT-4 Turbo), esta idea se quiebra. Las distancias se vuelven no-locales — casi todos los puntos están a casi la misma distancia entre sí. Este fenómeno se llama la maldición de la dimensionalidad. Los índices tradicionales pierden eficiencia, dejan de reducir el espacio de búsqueda, y volvemos a la fuerza bruta — comparar la consulta con todos los millones de vectores en la base de datos.

IVF: La Agrupación Viene al Rescate

IVF (Inverted File Index) resuelve la tarea mediante agrupación preliminar. El algoritmo utiliza k-means clásico para dividir el espacio en "cubo"-clusters condicionales. La intuición es simple: si los vectores están cerca en el espacio, deben estar en el mismo cluster, y durante la búsqueda solo necesitamos verificar algunos clusters relevantes, no toda la base de datos.

El proceso funciona en dos etapas. Durante la indexación, cada vector en la base de datos se asigna a su cluster más cercano (su centroide). Durante la búsqueda, el sistema primero encuentra K clusters más cercanos a la consulta mediante búsqueda rápida, luego busca coincidencias exactas solo dentro de ellos.

Esto reduce drásticamente el número de comparaciones — en lugar de millones de comparaciones, necesitamos solo unos pocos miles.

• Primera etapa: k-means divide el espacio en cientos o miles de clusters
• Segunda etapa: cada vector de la base de datos se indexa en su cluster (se guarda el ID del centroide)
• Durante la búsqueda: encontrar K clusters más cercanos, luego búsqueda completa solo dentro de ellos

IVF escala bien a miles de millones de vectores y requiere relativamente poca memoria. Habr presenta la implementación en Python con ejemplos de código concretos y métricas de desempeño.

HNSW: Mundo Pequeño Navegable Jerárquico

HNSW (Hierarchical Navigable Small World) utiliza un enfoque completamente diferente — construyendo un grafo de vecindad en lugar de clusters. Cada vector se convierte en un nodo en el grafo, las aristas conectan vectores vecinos (cercanos). El grafo se construye jerárquicamente: en niveles inferiores hay un vecindario local denso de cada vector, en niveles superiores hay conexiones dispersas de larga distancia para descenso aproximado global rápido.

Durante la búsqueda, el algoritmo comienza desde un punto de entrada en el nivel superior y desciende a través de la jerarquía, seleccionando en cada paso vecinos que están más cerca de la consulta objetivo. Esto es como navegar en una ciudad grande: primero viaja por autopistas principales, luego cambia a calles locales hasta encontrar la dirección que busca.

"HNSW funciona como un navegador en una ciudad desconocida: comienza en las autopistas principales, luego desciende a las calles locales", explican los autores del artículo en

Habr.

En la práctica, HNSW es generalmente más rápido que IVF para búsqueda de baja latencia, pero requiere más memoria para almacenar la estructura del grafo y las conexiones entre nodos.

Qué Significa Esto

Ambos algoritmos se utilizan en bases de datos vectoriales modernas: Pinecone, Weaviate, Qdrant, Milvus. Para aplicaciones LLM — sistemas RAG, búsqueda de documentos, recomendaciones semánticas, chatbots inteligentes — la elección del algoritmo de búsqueda afecta directamente la velocidad de respuesta y la experiencia del usuario. IVF es mejor elegir para enormes bases de datos con memoria limitada, HNSW proporciona una ventaja cuando se requiere latencia mínima y al trabajar con conjuntos de datos más compactos.