HNSW Explorer: Mundo Pequeno Hierárquico Navegável, Visualizado

Observe o percurso de uma pesquisa pelo gráfico em camadas — desde a camada superior esparsa (autoestradas) até à camada inferior densa (estradas locais). Arraste o ponto de consulta na Camada 0 e ajuste M / ef para ver como o gráfico se altera.

Número máximo de vizinhos por nó

ef8

Conjunto de candidatos da Camada 0

Velocidade450ms

Por etapa

Passo atual

14 / 14

Pesquisa concluída. Top-3: [3, 10, 4].

Estatísticas de pesquisa

Visitado

17 / 30

Camadas

Entrada

Nó 0

Top-3

[3, 10, 4]

Distribuição de camadas

Como funciona o « HNSW »

Gráfico em camadas: a cada nó é atribuída aleatoriamente uma camada máxima utilizando uma distribuição exponencial. A maioria dos nós permanece apenas na Camada 0; muito poucos chegam ao topo.
Dentro de cada camada: cada nó liga-se aos seus vizinhos mais próximos M. As camadas superiores são esparsas (poucos nós, arestas longas = «autoestradas»). A camada 0 é densa (todos os nós, arestas curtas = «estradas locais»).
A pesquisa começa no topo: a partir de um ponto de entrada fixo, avança-se de forma gananciosa até ao vizinho mais próximo da consulta, repetindo-se o processo até não haver melhorias.
Desça uma camada e repita: a posição da camada anterior torna-se o início do percurso da camada seguinte. Cada descida refina o resultado com arestas mais detalhadas.
Camada 0 com « ef »: na camada inferior, em vez de parar no primeiro mínimo local, o « HNSW » mantém um conjunto dos ef melhores candidatos e expande as suas vizinhanças. Maior ef → mais preciso, mas mais lento.

Por que é rápido: as camadas superiores funcionam como um índice sobre o índice — percorre-se enormes distâncias em apenas alguns saltos e, em seguida, amplia-se a imagem. Para N pontos, a pesquisa visita aproximadamente O(log N) nós, em vez de N.

O que é « HNSW »?

HNSW (Hierarchical Navigable Small World) é um algoritmo aproximado de vizinho mais próximo baseado em grafos. Organiza os vetores numa pilha de grafos «small-world» navegáveis: camadas superiores esparsas com arestas de longo alcance para o encaminhamento grosseiro e uma camada inferior densa com arestas curtas para o percurso final de alta resolução. Uma pesquisa avança avidamente em direção à consulta em cada camada e, em seguida, desce — visitando aproximadamente O(log N) nós, em vez de analisar todos os N.

HNSW é o índice de vetores em memória mais utilizado e o índice de grafos predefinido no Milvus. O Milvus também oferece HNSW_SQ e HNSW_PQ variantes que quantizam os vetores armazenados para reduzir o consumo de memória com um pequeno custo em termos de recall.

HNSW parâmetros em Milvus

M (tempo de construção): o número máximo de arestas por nó, o mesmo controlador que o cursor acima. Os valores típicos situam-se entre 8 e 64. Um valor M mais elevado melhora a recuperação e a conectividade do grafo, mas aumenta a memória de forma linear e retarda a construção.
efConstruction (tempo de construção): o tamanho do conjunto de candidatos utilizado durante a inserção de nós. Valores mais elevados resultam num gráfico de melhor qualidade (maior recall alcançável) à custa de uma construção mais lenta do índice. Os valores típicos situam-se entre 100 e 500.
ef / ef_search (tempo de consulta): o conjunto de candidatos mantido durante a percorrida da Camada-0 — o principal regulador de recall/latência no momento da pesquisa. Deve ser, no mínimo, o seu top-K. Aumente-o até que o recall atinja um patamar; a latência aumenta de forma aproximadamente linear com ele.

HNSW vs IVF vs DiskANN

HNSW normalmente proporciona a melhor latência de consulta com elevada precisão de recuperação para pesquisas na memória — é por isso que é a escolha predefinida quando o conjunto de dados (mais a sobrecarga do gráfico) cabe em RAM. Os seus custos são a memória e o tempo de construção: o gráfico adiciona uma sobrecarga percetível por vetor, e as inserções são mais lentas do que a atribuição k-means de IVF. Escolha IVF quando precisar de construções rápidas de índices ou de quantização agressiva, e DiskANN quando o conjunto de dados for demasiado grande para RAM, mas ainda assim precisar de um elevado recall.

Perguntas frequentes

O que controla o parâmetro M em « HNSW »?

M limita o número de arestas que cada nó mantém por camada. Um valor maior de M torna o grafo mais bem conectado — maior recall e encaminhamento mais robusto —, mas a memória cresce linearmente com M e a construção do índice fica mais lenta. Valores entre 8 e 64 cobrem a maioria das cargas de trabalho; 16–32 é um ponto ideal comum.

Qual é a diferença entre ef e efConstruction?

Ambos são tamanhos do conjunto de candidatos, aplicados em momentos diferentes. O « efConstruction » é utilizado durante a construção do índice: determina com que rigor cada nó inserido procura vizinhos, controlando assim a qualidade do grafo. O « ef » (ef_search) é utilizado no momento da consulta: controla a amplitude da pesquisa na Camada 0, trocando latência por recall em cada consulta.

Quanta memória necessita um índice « HNSW »?

Aproximadamente os vetores brutos mais o grafo: cerca de d × 4 bytes por vetor para dados float32, mais da ordem de M × 2 × 8 bytes de arestas por nó. Para implementações com restrições de memória, Milvus disponibiliza HNSW_SQ e HNSW_PQ, que quantizam os vetores armazenados, ou DiskANN, que transfere vetores completos para SSD.

Quando devo usar « HNSW » em vez de « IVF »?

Utilize « HNSW » quando a latência da consulta com elevada precisão de recuperação for a prioridade e o índice couber na memória — normalmente é a melhor opção. Prefira « IVF » quando reconstruir índices com frequência (construções muito mais rápidas) ou quando combinado com a quantização « SQ8 » / «PQ » para se adequar a um orçamento de memória restrito.

Aprofunde-se: leia a documentação «HNSW » para conhecer os parâmetros exatos do índice, ou consulte «Index Explained» para obter o guia de decisão completo.