🤖 machine learning

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions

Este artigo apresenta uma análise sistemática da busca ANN baseada em grade de múltiplas sondas, revelando sua escalabilidade superior em altas dimensões e custos de indexação mais baixos em comparação com métodos de grafo, árvore e particionamento, sugerindo, assim, seu potencial para otimizar aplicações com reconstrução intensa e arquiteturas de transformadores eficientes.

Autores originais: Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

Publicado 2026-07-03

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Matthew J Liu, Wei Hang Zheng, Vidhan Purohit, Siqi Xie, Chieh-En Li, Jerry Li, Noah Flynn

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

A Visão Geral: Encontrando uma Agulha em um Palheiro Crescente e Mutável

Imagine que você está procurando uma agulha específica em um palheiro.

A Agulha: A resposta exata que você está procurando (o "vizinho mais próximo").
O Palheiro: Uma coleção massiva de pontos de dados (como milhões de palavras ou imagens).
O Problema: À medida que o palheiro fica maior (mais dados) ou as agulhas ficam mais complexas (dimensções mais altas), encontrar essa agulha específica torna-se incrivelmente lento e difícil.

Este artigo apresenta uma nova forma "da velha guarda" de encontrar agulhas chamada "Multiprobe Grid Search" (Busca em Grade Multiprobe). Os autores testaram este método contra as ferramentas modernas e de alta tecnologia que todos os outros estão usando (como sistemas baseados em grafos e árvores) e descobriram algo surpreendente: Métodos baseados em grades são, na verdade, muito fortes quando os dados se tornam enormes ou muito complexos.

A Analogia: O Supermercado vs. O Labirinto

Para entender a diferença entre os métodos, vamos usar duas analogias:

1. Os Métodos Modernos (Grafos e Árvores): O Labirinto Complexo
Os métodos populares atuais são como um labirinto complexo e de várias camadas. Para encontrar uma agulha, você tem um que seguir um caminho sinuoso através do labirinto.

O Problema: À medida que o labirinto fica maior (mais dados) ou as paredes ficam mais confusas (mais dimensões), o caminho fica mais longo e emaranhado. Você gasta muito tempo voltando atrás e se perdendo. O artigo descobriu que, conforme os dados ficam mais complexos, esses "caminhantes de labirinto" ficam significativamente mais lentos.

2. O Novo Método (Multiprobe Grid): O Supermercado Organizado
O método deste artigo é como um supermercado perfeitamente organizado.

Como funciona: Em vez de um labirinto, a loja é dividida em corredores quadrados simples (uma grade).
O Truque: Quando você quer encontrar um item, você não verifica apenas o corredor onde acha que ele está. Você verifica esse corredor, mais os corredores imediatamente ao lado, e os que estão ao lado desses. Isso é chamado de "multiprobe".
O Ingrediente Secreto: Para decidir quais corredores verificar, o sistema usa um mapa simplificado (uma "projeção PCA") que ignora alguns detalhes confusos. Ele olha apenas para o layout principal. Assim que escolhe os corredores certos, ele faz uma verificação final rápida no mundo real detalhado.

O Que o Artigo Descobriu

Os autores realizaram experimentos para ver quão rápidos esses métodos se tornam à medida que alteram duas coisas: o tamanho dos dados e a complexidade dos dados.

1. O Teste de "Tamanho" (Mais Palheiros)

A Configuração: Eles dobraram e triplicaram a quantidade de dados.
O Resultado: O método do "Supermercado" (Grade) desacelerou de forma quase perfeita em linha com o tamanho. Se você dobra os dados, leva aproximadamente o dobro do tempo. Isso é chamado de escalonamento quase linear.
Os Competidores: Os métodos do "Labirinto" desaceleraram muito menos do que o esperado no início, mas, conforme os dados ficaram enormes, começaram a ter mais dificuldades do que o método de Grade.
Conclusão: O método de Grade é muito previsível e honesto sobre quanto tempo precisa conforme os dados crescem.

2. O Teste de "Complexidade" (O Cruzamento de Dimensões)

A Configuração: Eles tornaram os dados mais complexos (adicionando mais características, como passar de um desenho 2D para um modelo 3D, depois para um modelo 100D).
A Surpresa: Esta é a maior descoberta do artigo.
- Os métodos de "Labirinto" (Grafos/Árvores) ficaram muito mais lentos conforme a complexidade aumentava. Quanto mais complexos os dados, mais difícil era para eles podarem (ignorar) os caminhos errados.
- O método do "Supermercado" (Grade) permaneceu estável. Como utiliza um mapa simplificado para decidir quais corredores verificar, ele não se confunde com a complexidade extra.
O Cruzamento: Em determinado ponto de complexidade, o método de Grade tornou-se mais rápido do que os modernos métodos de Labirinto. O artigo chama isso de "crossover" (ponto de cruzamento).

3. O Custo de Configuração (Construindo a Loja)

A Configuração: Quanto tempo leva para construir o índice (organizar as prateleiras) antes de começar a busca?
O Resultado: O método de Grade é incrivelmente rápido de configurar. Levou de 4 a 36 segundos para organizar um milhão de itens. Os métodos modernos de Labirinto levaram de minutos a mais de 25 minutos.
Por que importa: Se você tem um sistema onde descarta constantemente dados antigos e constrói um novo índice do zero (como um sistema de recomendação que atualiza a cada hora), o método de Grade é o vencedor porque constrói muito rápido.

A Equação do "Custo Total"

O artigo argumenta que você não deve olhar apenas para a velocidade de uma busca durante a pesquisa. Você deve olhar para o Custo Total:

Custo Total = (Tempo para Construir) + (Tempo para Buscar × Frequência de Busca)

Cenário A: Você constrói o índice uma vez e faz uma milhão de buscas. Os métodos de Labirinto, que são lentos para construir, podem vencer por serem rápidos na busca.
Cenário B: Você constrói o índice com frequência (reconstrução intensa) ou faz poucas buscas. O método de Grade vence porque é muito barato e rápido de construir.

Por Que Isso Importa para a IA (A Conexão com a "Atenção")

O artigo menciona que a IA moderna (Transformers) funciona realizando buscas de "Vizinho Mais Próximo Aproximado" para decidir em quais palavras prestar atenção.

Se um modelo de IA precisa atualizar constantemente sua memória (índice) conforme novas palavras entram, o baixo custo de configuração do método de Grade e sua capacidade de lidar com dados complexos sem perder velocidade podem tornar a IA mais rápida e barata de operar.

Resumo

O artigo diz: "Não ignore a grade simples."
Enquanto todos estavam obcecados com métodos de busca complexos e semelhantes a labirintos, a abordagem simples e organizada do "Supermercado" (Multiprobe Grid) é, na verdade, melhor para lidar com:

Conjuntos de dados enormes (velocidade previsível).
Dados muito complexos (não se confunde com altas dimensões).
Reconstrução frequente (configura-se em segundos, não em minutos).

É um lembrete de que, às vezes, o método "da velha guarda", quando ajustado corretamente, é a ferramenta mais eficiente para o trabalho.

Resumo Técnico: Leis de Escala para Busca de Vizinho Mais Próximo Aproximado Baseada em Grade em Altas Dimensões

Declaração do Problema

A busca de Vizinho Mais Próximo Aproximado (ANN) é um primitivo fundamental na aprendizagem de máquina moderna, servindo tanto para tarefas de recuperação tradicionais quanto para papéis emergentes como um bloco de construção computacional para arquiteturas transformer (onde a auto-atenção é formalizada como uma operação de ANN). Embora leis de escala empíricas guiem o design de modelos de grande escala, o comportamento de escala dos algoritmos de ANN com relação ao tamanho do conjunto de dados ( $N$ ) e à dimensionalidade ( $d$ ) permanece uma área de estudo crítica, porém subcaracterizada.

A literatura existente analisou extensivamente métodos baseados em grafos (ex: HNSW), árvores e particionamento. No entanto, abordagens baseadas em grade, apesar de seu papel fundamental na teoria de ANN inicial, têm sido amplamente ausentes das análises de escala modernas. Este artigo aborda essa lacuna caracterizando sistematicamente a dinâmica de escala de um algoritmo de grade multiprobe, investigando especificamente como seu desempenho escala com $N$ e $d$ em comparação com competidores de estado da arte.

Metodologia

O Algoritmo de Grade Multiprobe

Os autores propõem um algoritmo de grade multiprobe que desacopla a seleção de células da dimensionalidade total $d$ . O fluxo de trabalho envolve:

Projeção PCA: Os pontos de dados são projetados de $\mathbb{R}^d$ para um subespaço de menor dimensão $\mathbb{R}^m$ ( $m \ll d$ ).
Particionamento de Grade: O subespaço é particionado em uma grade uniforme de $G^m$ células.
Seleção Multiprobe: No momento da consulta, o algoritmo identifica a célula "lar" e sonda até $2^m - 1$ células vizinhas, ordenadas por sua distância de parede ao quadrado ( $w_i^2$ ) em relação à consulta.
Re-ranking: Os candidatos coletados das células sondadas são reclassificados no espaço original de alta dimensão $\mathbb{R}^d$ .

Modelo Teórico

Os autores derivam uma relação de forma fechada entre o custo de consulta (Queries Per Second, QPS) e o recall ( $R$ ).

Modelo de Custo: O custo de consulta é linear no número de células sondadas ( $n_{probe}$ ) e no número de pontos por célula ( $N/G^m$ ).
Modelo de Recall: Assumindo uma distribuição uniforme, a probabilidade de o verdadeiro vizinho mais próximo estar em uma célula sondada decai exponencialmente com a distância de parede.
Relação Resultante: O modelo prevê uma relação log-linear entre QPS e recall: $\log(\text{QPS}) \approx \log(\text{const}) - \log(R)$ . Isso surge do decaimento exponencial da probabilidade de pertencimento através das células e do crescimento linear do tamanho do conjunto de candidatos.

Avaliação Empírica

O estudo avalia a grade multiprobe contra quatro baselines que representam as principais famílias de ANN:

Baseados em Grafos: Voyager, PyNNDescent.
Baseados em Árvores: Annoy.
Particionamento/Quantização: FAISS-IVF.

Os experimentos foram conduzidos usando o framework ann-benchmarks em dois conjuntos de dados:

GloVe-200-angular (Embeddings de palavras, $d=200$ , $N \approx 1.18 \times 10^6$ ).
SIFT-128-euclidean (Descritores de imagem, $d=128$ ).

A avaliação focou nos expoentes de escala para $N$ ( $\alpha_N$ ) e $d$ ( $\alpha_d$ ), frentes de Pareto (throughput vs. recall) e análise de custo total (indexação + tempo de consulta).

Principais Resultados

1. Relação Throughput-Recall Log-Linear

A análise da frente de Pareto no GloVe-200 confirma a previsão teórica: a grade multiprobe exibe uma diminuição log-linear no throughput conforme o recall aumenta. Este comportamento é distinto dos baselines e é impulsionado pela geometria da grade e pelo decaimento exponencial da probabilidade de vizinho mais próximo através das células.

2. Escala de $N$ : Degradação Quase-Linear

A grade multiprobe escala de forma quase-linear com o tamanho do conjunto de dados ( $N$ ).

No recall@10 = 0.80, o expoente de escala é $\alpha_N \approx -0.94$ (GloVe) e $-0.83$ (SIFT).
Em contraste, os baselines baseados em grafos e árvores exibem escala sub-linear ( $\alpha_N$ variando de $-0.44 $a$ -0.59$).
Implicação: Embora o throughput da grade multiprobe degrade mais rápido conforme $N$ cresce em comparação com métodos de grafo, isso é uma consequência mecanística do design do algoritmo (a contagem de candidatos cresce linearmente com $N$ ).

3. Escala de $d$ : Um Crossover Crítico

Um crossover de escala de $d$ anteriormente não relatado é observado na família de embeddings GloVe.

Baselines: À medida que a dimensionalidade $d$ aumenta, o throughput dos métodos de grafos, árvores e particionamento degrada significativamente ( $\alpha_d$ íngreme), refletindo a "maldição da dimensionalidade" e a falha da poda geométrica em altas dimensões.
Grade Multiprobe: O expoente de escala $\alpha_d$ permanece relativamente plano e favorável conforme $d$ aumenta.
Mecanismo: Ao realizar a seleção de células em um subespaço PCA de baixa dimensão ( $m \ll d$ ) e adaptar os parâmetros da grade ( $m, G$ ) com base em $d$ e no recall alvo, o algoritmo evita percorrer todo o espaço de alta dimensão. Os custos de re-ranking crescem apenas linearmente com a contagem de candidatos, o que é menos agressivo do que o crescimento de custo dos métodos que percorrem o espaço completo de $d$ dimensões.

4. Custo Total e Eficiência de Indexação

O artigo analisa o custo total $J(N) = f_I \cdot I(N) + f_C \cdot C(N) + M(N)$ , onde $I$ é o custo de indexação, $C$ é o custo de computação e $M$ é a pegada de memória.

Velocidade de Indexação: A grade multiprobe é significativamente mais rápida para construir do que os baselines. Em $N = 1.18 \times 10^6$ , ela constrói um índice em 4–36 segundos, comparado a 1.569 segundos para o Voyager.
Latência de Consulta: A grade multiprobe tem maior latência por consulta (aproximadamente 120 $\times$ mais lenta que o Voyager em alto recall).
Regime Competitivo: O método torna-se competitivo quando a razão de reconstrução-para-consulta ( $f_I/f_C$ ) é alta. Especificamente, se um índice é reconstruído aproximadamente uma vez a cada 2.600–20.400 consultas, a grade multiprobe oferece um custo total menor. Isso a torna adequada para cenários de "reconstrução intensa".

Significância e Alegações

O artigo alega que métodos baseados em grade, frequentemente negligenciados em análises de escala modernas, oferecem um conjunto distinto e competitivo de trade-offs em cenários específicos:

Robustez Dimensional: A grade multiprobe é unicamente robusta ao aumento da dimensionalidade ( $d$ ), superando métodos de grafos e árvores em configurações de alta dimensão onde a poda geométrica falha.
Baixo Overhead de Indexação: O algoritmo oferece indexação quase instantânea em comparação com métodos baseados em grafos que exigem construções de grafos complexas e dependentes de dados.
Relevância para Transformers: Dada a formalização da auto-atenção como uma operação de ANN, as propriedades de escala de $N$ $N$ e $d$ $d$ dos algoritmos de ANN são diretamente relevantes para a eficiência de transformers. Os autores sugerem que a grade multiprobe pode ser vantajosa em arquiteturas transformer onde:
- O comprimento do contexto ( $N$ ) ou a dimensão da cabeça ( $d$ ) varia.
- Atualizações incrementais são frequentes (ex: estendendo o KV-cache), pois anexar um token a uma grade requer apenas uma atribuição de célula única, em vez de uma reconstrução completa do grafo.
Perspectiva de Custo Total: O artigo argumenta que a seleção de métodos de ANN não deve basear-se apenas na latência de consulta, mas deve considerar a função de custo total, incluindo frequência de indexação e custos de reconstrução. Em cenários de reconstrução frequente, o baixo custo de indexação dos métodos de grade pode compensar sua maior latência de consulta.

Em resumo, o trabalho reestabelece os métodos baseados em grade como uma opção viável para sistemas de aprendizagem de alta dimensão, particularmente onde o custo de indexação, a frequência de reconstrução e a robustez dimensional são as restrições primárias.