Terminação adaptativa precoce para HNSW no Elasticsearch

O Elasticsearch utiliza o algoritmo Hierarchical Navigable Small World (HNSW) para realizar buscas vetoriais em um gráfico de proximidade. O HNSW é conhecido por oferecer uma boa compensação entre a qualidade dos resultados do k-nearest neighbor (KNN) e o custo associado.

No HNSW, a busca prossegue expandindo iterativamente os nós candidatos no gráfico, mantendo um conjunto limitado de vizinhos mais próximos descobertos até então. Cada expansão tem um custo (operações vetoriais, acessos aleatórios ao disco, e mais), e o benefício marginal desse custo tende a diminuir conforme a busca avança.

Uma forma de otimizar a travessia de gráficos HNSW é parar de buscar quando a probabilidade marginal de encontrar novos vizinhos verdadeiros não aumenta. Por essa razão, no Elasticsearch 9.2 introduzimos um novo mecanismo de terminação antecipada. Isso interrompe o processo de busca quando visitar nós do gráfico não fornece vizinhos novos mais próximos suficientes, consecutivamente, por um número fixo de vezes.

Este artigo mostra como aprimoramos o mecanismo de terminação antecipada mencionado no HNSW para torná-lo mais adequado para diferentes conjuntos de dados e distribuições de dados.

Terminação antecipada no HNSW

No HNSW, a busca prossegue expandindo iterativamente os nós candidatos no gráfico de proximidade, mantendo um conjunto limitado de vizinhos mais próximos descobertos até então, até que tenha visitado todo o gráfico ou atenda a alguns critérios iniciais de parada.

Portanto, a terminação antecipada nem sempre é necessariamente uma otimização, faz parte do próprio algoritmo de busca. O momento em que decidimos parar determina o equilíbrio entre eficiência e recall. No Elasticsearch, já existem várias maneiras de uma consulta no HNSW terminar antecipadamente:

• Um número máximo fixo de nós é visitado.
• Um tempo limite fixo é atingido.

Embora simples e previsíveis, essas regras são em grande parte agnósticas em relação ao que a busca realmente está fazendo. Além disso, elas são usadas principalmente para garantir que a consulta seja concluída em um tempo razoável para o usuário final.

Em uma postagem anterior do blog, apresentamos o conceito de redundância no HNSW. Em resumo, cálculos redundantes ocorrem quando o HNSW continua a avaliar novos nós candidatos que não resultam em encontrar mais vizinhos mais próximos.

Paciência: Medindo progresso em vez de esforço

A noção de paciência reformula a terminação antecipada, focando no progresso em vez do esforço.

Em vez de perguntar:

"Quantos passos já demos?"

A nova pergunta passa a ser:

“Qual é a quantidade de computação que aceitamos desperdiçar até perdermos a esperança?”

Durante a busca HNSW, a exploração precoce normalmente produz melhorias de pico no conjunto de candidatos top-k. Durante as primeiras etapas da exploração do gráfico HNSW, o conjunto de vizinhos é continuamente atualizado à medida que o algoritmo continua descobrindo vizinhos cada vez mais próximos do vetor de consulta. Com o tempo, essas melhorias se tornam mais raras à medida que a busca converge. A terminação antecipada baseada em paciência monitora esse padrão e finaliza a busca assim que as melhorias cessarem por um período prolongado.

Na prática, ao visitar o gráfico HNSW, também calculamos a razão de saturação da fila ao pular entre os nós candidatos. Isso mede a porcentagem de vizinhos mais próximos que permaneceram inalterados ao visitar o nó mais recente do gráfico (ou o inverso do número de novos vizinhos introduzidos na última iteração). Quando essa proporção se torna grande demais para muitas iterações consecutivas, paramos de visitar o gráfico.

Conceitualmente, a paciência trata a busca HNSW como um processo de retornos decrescentes. Quando os retornos se estabilizam, continuar explorando o gráfico traz pouco benefício.

Esse enquadramento é poderoso porque vincula a interrupção diretamente a resultados observáveis, e não a limites fixos arbitrários.

A vantagem de usar essa técnica inteligente de terminação antecipada é que as explorações do gráfico HNSW tendem a visitar um número menor de nós gráficos, mantendo uma taxa de recall quase perfeita.

Para visualizar isso, podemos visualizar em um gráfico a quantidade de recall por nó visitado que obtivemos com a terminação antecipada baseada em paciência (rotulada como et=static), quando comparada ao comportamento padrão do HNSW (rotulado como et=no) em alguns conjuntos de dados, FinancialQA e Quora, e modelos, JinaV3 e E5-small.

Limiares estáticos e dinâmicas do HNSW

Na prática, no Elasticsearch, isso é implementado usando limites estáticos. Um limite refere-se ao limite de saturação, ou seja, a proporção de saturação que consideramos abaixo do ideal. O outro limite refere-se ao número de nós de gráfico consecutivos que permitimos serem visitados enquanto ainda mantêm uma saturação de fila abaixo do ideal: ou seja, o limiar de paciência.

Quando introduzimos essa estratégia de terminação antecipada no Elasticsearch 9.2, decidimos optar por padrões conservadores, de modo a preservar o recall o máximo possível, enquanto ainda obtemos ganhos em termos de latência e consumo de memória. Por esse motivo, definimos o limiar de saturação para 100% e o limiar de paciência para ser definido como 30% (limitado) do num_candidates na consulta KNN.

Em muitos cenários, essas configurações funcionaram bem; no entanto, duas consultas que solicitam o mesmo número de vizinhos podem ter comportamentos de convergência radicalmente diferentes. Algumas consultas encontram vizinhanças locais densas e saturam rapidamente; outras precisam percorrer caminhos longos e esparsos antes de encontrar candidatos competitivos. Este último mostrou-se o mais difícil de lidar de forma eficaz.

Como resultado, por vezes notamos:

• Exploração excessiva para consultas fáceis.
• Encerramento prematuro para consultas complexas.

Portanto, descobrimos que valores de limite fixos codificam suposições globais sobre convergência, enquanto poderíamos fazer com que o HNSW se adaptasse melhor a diferentes dinâmicas.

Tornando o HNSW adaptativo à terminação antecipada

A terminação antecipada adaptativa aborda esse problema de um ângulo diferente. Em vez de impor limiares de parada pré-definidos, o algoritmo infere quando parar a partir da própria dinâmica da busca.

Então, em vez de comparar a taxa de saturação da fila entre dois candidatos consecutivos, decidimos introduzir uma taxa de descoberta instantânea suavizada $d_{q,i}$ (quantos novos vizinhos foram introduzidos para uma consulta q,na última visita i) junto com a média móvel $\ mu_{q,i}$ e o desvio padrão $\sigma_{q,i}$ dessa taxa de descoberta durante a visita ao gráfico (usando o algoritmo de Welford). Essas estatísticas sobre a taxa de descoberta são calculadas por consulta, de modo que essas informações podem ser usadas para determinar diferentes níveis de paciência para cada consulta.

Os limites anteriormente estáticos se tornam adaptáveis às estatísticas da taxa de descoberta: o limite de saturação se torna a média contínua mais o desvio padrão; enquanto fazemos com que a paciência se adapte e redimensione inversamente com o desvio padrão.

As regras de saída antecipada permanecem as mesmas; a saturação ocorre quando a taxa de descoberta instantânea é menor que o limite de saturação adaptativa. A visita ao gráfico é interrompida se a saturação persistir por um número consecutivo de visitas candidatas maior que a paciência adaptativa.

Dessa forma, obtemos um comportamento que não depende do parâmetro num_candidates na consulta KNN (que pode estar sempre definido ou deixado como padrão, independentemente de sair cedo) e que se adapta melhor a cada consulta e distribuição vetorial de forma dinâmica.

O recall por nó visitado no FinancialQA e Quora com a estratégia adaptativa (rotulada como et=adaptive) apresenta um recall maior por nó visitado, quando comparado à estratégia estática (et=static) e ao comportamento padrão do HNSW (et=no).

A terminação antecipada adaptativa está ativada por padrão no Elasticsearch 9.3 para campos vetoriais densos HNSW (e pode ser desativada posteriormente por meio da mesma configuração no nível do índice).