Busca vetorial sem força bruta: como funcionam IVF e HNSW

Busca Vetorial Sem Força Bruta: Como Funcionam IVF e HNSW

Quando um banco de dados vetorial contém milhões de embeddings, buscar vetores semelhantes usando força bruta se torna impossível. Dois algoritmos — IVF e HNSW — resolvem essa tarefa por busca aproximada, encontrando respostas em milissegundos em vez de minutos. Um novo artigo detalhado no Habr decompõe ambas as abordagens da teoria matemática à implementação em Python.

Por Que a Busca Exata Não Funciona

Em baixas dimensões (2D, 3D), você pode construir índices espaciais — árvores k-d, árvores R. Eles usam geometria: se uma consulta está longe de uma parte do espaço, ela pode ser excluída da busca sem perder resultados. Mas em altas dimensões (768D para BERT, 3072D para GPT-4 Turbo), essa ideia quebra. As distâncias se tornam não-locais — quase todos os pontos estão a quase a mesma distância um do outro. Esse fenômeno é chamado de maldição da dimensionalidade. Os índices tradicionais perdem eficiência, param de reduzir o espaço de busca, e voltamos à força bruta — comparar a consulta com todos os milhões de vetores no banco de dados.

IVF: Clustering Vem em Auxílio

IVF (Inverted File Index) resolve a tarefa por clusterização preliminar. O algoritmo usa k-means clássico para dividir o espaço em "balde"-clusters condicionais. A intuição é simples: se vetores estão próximos no espaço, devem estar no mesmo cluster, e durante a busca precisamos verificar apenas alguns clusters relevantes, não todo o banco de dados. O processo funciona em dois estágios. Durante a indexação, cada vetor no banco de dados é atribuído ao seu cluster mais próximo (seu centroide). Durante a busca, o sistema primeiro encontra K clusters mais próximos à consulta por busca rápida, depois busca correspondências exatas apenas dentro deles. Isso reduz dramaticamente o número de comparações — em vez de milhões de comparações, precisamos apenas de alguns milhares.

• Primeiro estágio: k-means divide o espaço em centenas ou milhares de clusters
• Segundo estágio: cada vetor do banco de dados é indexado em seu cluster (ID do centroide é salvo)
• Durante a busca: encontre K clusters mais próximos, depois busca completa apenas dentro deles

IVF escala bem para bilhões de vetores e requer relativamente pouca memória. Habr apresenta a implementação em Python com exemplos de código concretos e métricas de desempenho.

HNSW: Mundo Pequeno Navegável Hierárquico

HNSW (Hierarchical Navigable Small World) usa uma abordagem completamente diferente — construindo um grafo de vizinhança em vez de clusters. Cada vetor se torna um nó no grafo, arestas conectam vetores vizinhos (próximos). O grafo é construído hierarquicamente: em níveis inferiores há uma vizinhança local densa de cada vetor, em níveis superiores há conexões esparsa de longa distância para descida aproximada global rápida. Durante a busca, o algoritmo começa de um ponto de entrada no nível superior e desce pela hierarquia, selecionando em cada passo vizinhos que estão mais próximos da consulta alvo. Isso é como navegar em uma grande cidade: primeiro você viaja em rodovias principais, depois muda para ruas locais até encontrar o endereço que procura.

"HNSW funciona como um navegador em uma cidade desconhecida: você começa nas rodovias principais, depois desce para ruas locais", explicam os autores do artigo no

Habr.

Na prática, HNSW é geralmente mais rápido que IVF para busca de baixa latência, mas requer mais memória para armazenar a estrutura do grafo e conexões entre nós.

O Que Isso Significa

Ambos os algoritmos são usados em bancos de dados vetoriais modernos: Pinecone, Weaviate, Qdrant, Milvus. Para aplicações LLM — sistemas RAG, busca de documentos, recomendações semânticas, chatbots inteligentes — a escolha do algoritmo de busca afeta diretamente a velocidade de resposta e a experiência do usuário. IVF é melhor para enormes bancos de dados com memória limitada, HNSW oferece vantagem quando latência mínima é necessária e ao trabalhar com conjuntos de dados mais compactos.