Resumo Técnico: Busca ANN: Relembrando o que Importa

Problema

A busca por Vizinhos Próximos Aproximados (ANN - Approximate Nearest Neighbor) é um primitivo fundamental na recuperação de informações moderna e no aprendizado de máquina, particularmente para tarefas como classificação e Geração Aumentada de Recuperação (RAG). A comunidade padronizou o Recall@k (a fração dos $k$-vizinhos exatos verdadeiros recuperados) como a métrica primária para avaliar e ajustar algoritmos de ANN. Pesquisadores otimizam para o rendimento (throughput, Queries-Per-Second, QPS) em limiares de Recall fixos.

Os autores argumentam que essa convenção está desalinhada com a utilidade real dos sistemas de ANN. Em espaços de alta dimensionalidade (comuns em embeddings modernos), as distâncias para vizinhos sucessivos se concentram, levando a muitos candidatos "quase equidistantes". Um algoritmo de ANN pode recuperar pontos que são geometricamente tão próximos da consulta quanto os vizinhos verdadeiros, mas que carregam identificadores diferentes. Sob o Recall@k, esses resultados geometricamente precisos são penalizados como falhas, forçando os sistemas a incorrer em um custo computacional desnecessário para alcançar uma alta sobreposição de identificadores. O artigo postula que o Recall@k superestima a dificuldade da tarefa e o custo da aproximação, podendo levar a configurações de sistema subótimas.

Metodologia

O artigo propõe substituir o Recall@k pelo 1/Ratio@k, o inverso da razão de aproximação. Diferente do Recall, que conta correspondências de identificadores, o 1/Ratio@k mede a qualidade dos resultados recuperados com base nas distâncias dos vizinhos retornados em relação aos $k$-vizinhos verdadeiros.

Definições Chave:

• Recall@k: $\frac{| \tilde{N}_k(q) \cap N_k(q) |}{k}$, onde $\tilde{N}_k$ é o conjunto recuperado e $N_k$ é o conjunto verdadeiro.
• Ratio@k: A média das razões de distância por posição: $\frac{1}{k} \sum_{i=1}^k \frac{\tilde{d}_i(q)}{d_i(q)}$, onde $\tilde{d}_i$ e $d_i$ são as distâncias para o $i$-ésimo vizinho retornado e verdadeiro, respectivamente.
• 1/Ratio@k: O inverso da razão acima, variando de 0 a 1 (1 indicando recuperação perfeita).

Configuração Experimental:
Os autores testaram cinco algoritmos de ANN de última geração em diversos conjuntos de dados com variadas dimensionalidades intrínsecas (LID):

1. Annoy (Baseado em Árvores)
2. SuCo (Baseado em Colisão)
3. HNSW (Baseado em Grafos, padrão da indústria)
4. RaBitQ (Baseado em Quantização)
5. SymphonyQG (Híbrido Grafo-Quantização)

A avaliação cobriu seis conjuntos de dados (Gist, SimpleWiki, ImageNet, AGNews, MNIST, Fashion-MNIST) e estendeu-se para tarefas subsequentes (downstream) incluindo classificação de imagens (MNIST, Fashion-MNIST, CIFAR-10, SVHN) e RAG (SciFact, NFCorpus, HotpotQA, MS-MARCO, PubMedQA).

Estratégia de Avaliação:

1. Análise de Eficiência: Mediu o custo computacional (QPS, computações de distância, tempo de construção, memória) necessário para atingir limiares de qualidade específicos ($T \in \{0.90, 0.95, 0.99\}$) sob ambas as métricas.
2. Validação de Tarefas Subsequentes (Downstream): Utilizou controle de recall sintético para degradar artificialmente os níveis de recall ($r \in [0.4, 1.0]$) enquanto mantinha a qualidade geométrica. Eles mediram o desempenho da tarefa subsequente (Precisão de Rótulo para classificação; BERTScore, Similaridade Semântica e notas de LLM para RAG) para determinar se o baixo Recall realmente degrada a utilidade.
3. Comparação de Métricas: Calculou o Desvio Absoluto Médio (MAD) entre as métricas (Recall vs. 1/Ratio) para avaliar qual métrica é um melhor proxy.

Principais Contribuições

1. Proposta do 1/Ratio@k: Introduziu uma métrica de qualidade que é isenta de juiz, isenta de hiperparâmetros e computável apenas a partir de entradas padrão de benchmark de ANN (embeddings e identificadores de verdade fundamental). Ao contrário de alternativas como Semantic Recall ou Tolerant Recall, não requer juízes externos de LLM ou parâmetros de tolerância ajustáveis.
2. Demonstração de Sobrecarga Computacional: Mostrou que otimizar para o Recall@k impõe uma penalidade computacional substancial em comparação com a otimização para o 1/Ratio@k.
3. Evidência de Estabilidade Subsequente: Forneceu evidência empírica de que o desempenho da tarefa subsequente (precisão de classificação e qualidade de resposta em RAG) permanece estável mesmo quando o Recall cai significativamente (ex: para 0,4), desde que a qualidade geométrica (1/Ratio) permaneça alta.
4. Explicação Geométrica: Vinculou a divergência entre Recall e 1/Ratio à Dimensionalidade Intrínseca Local (LID) e ao tamanho do vizinhança $k$. À medida que a LID e $k$ aumentam, a probabilidade de recuperar vizinhos geometricamente próximos, mas com identificadores divergentes, aumenta, fazendo com que o Recall degrade enquanto o 1/Ratio permanece alto.

Resultados Experimentais

1. Eficiência e Custo (RQ1 & RQ2)

• Rendimento (QPS): Otimizar para 1/Ratio@k produz um rendimento significativamente maior do que otimizar para Recall@k. Em um limiar de qualidade de $T=0.95$ e $k=100$, o aumento de velocidade varia de 1,86× a 9,36× em computações de distância e de 2× a 10× em QPS, dependendo do algoritmo e do conjunto de dados.
  • Exemplo: No conjunto de dados ImageNet com HNSW, atingir 1/Ratio@100 $\ge$ 0,95 é 9,98× mais rápido do que atingir Recall@100 $\ge$ 0,95.
• Tempo de Construção: O custo para construir índices para alto Recall é frequentemente maior. Para HNSW no Gist, atingir Recall $\ge$ 0,90 exigiu 18,39× mais tempo de construção do que atingir 1/Ratio $\ge$ 0,90.
• Memória: As diferenças na pegada de memória são mínimas. O gap é geralmente próximo de 1,0×, pois a memória é dominada pelo armazenamento de vetores, não pelos parâmetros usados para ajustar para alto Recall.
• Classificação de Algoritmos: O ranking relativo dos algoritmos (qual é o mais rápido/barato) permanece amplamente estável entre as duas métricas. A mudança de métrica afeta o custo absoluto para atingir um limiar, não o desempenho relativo dos algoritmos.

2. Divergência Geométrica (RQ3)

• O gap entre Recall e 1/Ratio aumenta conforme $k$ aumenta e conforme a LID aumenta.
• Em espaços de alta LID, os vizinhos são quase equidistantes. Um algoritmo de ANN que retorna um vetor com um ID diferente, mas com distância quase idêntica, é severamente penalizado pelo Recall, mas recebe uma pontuação alta pelo 1/Ratio.
• O Recall degrada substancialmente conforme $k$ cresce (ex: caindo significativamente de $k=1$ para $k=100$), enquanto o 1/Ratio permanece relativamente estável.

3. Qualidade de Tarefas Subsequentes (RQ4)

• Classificação de Imagens: Conforme o Recall caiu de 1,0 para 0,4, a Precisão de Rótulo (LP@100) permaneceu notavelmente estável (ex: caindo de apenas 1,0 para ~0,94 no SVHN).
  • Análise MAD: O Recall teve um Desvio Absoluto Médio (erro de previsão) de ~26% da qualidade real. Em contraste, o 1/Ratio teve um erro de < 3% (frequentemente < 1%).
• Tarefas de RAG: A qualidade da resposta (medida por BERTScore, Similaridade Semântica e notas de LLM) mostrou degradação negligenciável conforme o Recall caiu para 0,4.
  • Em benchmarks anotados por humanos, as métricas de qualidade de texto variaram menos de 1,2%, apesar de uma queda de 60% no Recall.
  • O 1/Ratio acompanhou essa estabilidade de perto, enquanto o Recall sinalizou falsamente uma queda massiva na qualidade.
  • Análise MAD: Para RAG, o erro de previsão do Recall foi de ~30%, enquanto o do /1/Ratio foi de < 3% (frequentemente < 1%).

Significância e Alegações

O artigo alega que a dependência da comunidade em relação ao Recall@k levou a um superdimensionamento desnecessário de sistemas de ANN. Ao ajustar para alto Recall, os praticantes incorrem em custos computacionais substanciais (tempo, energia, latência) para recuperar resultados que são geometricamente indistinguíveis da verdade fundamental, mas que falham em um teste de correspondência de identificadores.

Os autores concluem que:

1. O 1/Ratio@k é um proxy superior para a utilidade real subsequente, refletindo com precisão a estabilidade da qualidade de recuperação mesmo quando o Recall é baixo.
2. A adoção do 1/Ratio@k permite implantações de ANN mais rápidas, baratas e eficientes sem sacrificar a qualidade da aplicação final (classificação ou geração).
3. Configurações atualmente descartadas como "inadequadas" devido ao baixo Recall são frequentemente operacionalmente suficientes e podem ser implantadas para alcançar ganhos de eficiência significativos.

O estudo defende uma mudança no paradigma de avaliação da comunidade de ANN: movendo-se da otimização para sobreposição de identificadores (Recall) para a otimização de proximidade geométrica (1/Ratio), alinhando assim o ajuste do sistema com os requisitos reais das tarefas de aprendizado de máquina subsequentes.