O preço da garantia.

Na busca por parecido, cada item (uma imagem, um trecho de texto, um cadastro) vira uma lista de números, e "parecido" quer dizer "perto" nessa lista. Achar os mais perto exige comparar a pergunta com muitos itens. Para não fazer a conta inteira em todos, os sistemas guardam um resumo de cada item e descartam pelo resumo o que já está claramente longe.

O resumo mais usado hoje se chama RaBitQ (2024). Ele gira a lista de números ao acaso e guarda, de cada número, só o sinal: positivo ou negativo, 1 bit. Junto, guarda uma nota de quanto esse resumo aponta na mesma direção que o item original. É como anotar só o rumo aproximado de cada casa em vez do endereço, mais o quanto o rumo anotado pode estar torto.

Com o resumo, o sistema estima a distância até a pergunta. Como a estimativa erra, ele só descarta um item se, mesmo descontando uma margem, o item continua longe. Tudo depende do tamanho dessa margem.

O artigo original prova que o erro da estimativa fica dentro de uma margem com alta probabilidade, sobre o sorteio do giro. Para a margem, os autores escolhem um número, 1,9, e todo mundo copiou. Lemos o código de 13 sistemas que usam esse atalho: a biblioteca oficial, o Faiss (Meta), o Milvus, o LanceDB, o VectorChord, o VSAG, o pg_vectorsearch e outros. Todos usam uma margem estatística fixa (1,9, ou 2,5 num deles) ou nem isso, só buscam itens a mais e conferem. Três escrevem no próprio código que a margem não é uma garantia.

Medimos o "quase". Em 5 milhões de comparações no conjunto SIFT, 2,74% passam da margem. Na maioria das vezes isso não muda nada, porque o item estava longe mesmo. Mas em 1 milhão de imagens, com 500 buscas pelos 10 mais parecidos, 12 buscas voltaram com vizinho faltando, sem aviso nenhum.

Para recomendar um filme, isso não importa. Para conferir um nome contra uma lista de sanções, achar todos os documentos parecidos num processo ou provar que uma imagem não está numa base, um "não achei" errado e silencioso é exatamente o defeito que não pode ter.

A nota de confiança do resumo é, na verdade, um ângulo: o quanto o rumo anotado se desvia do rumo verdadeiro do item. E ângulos obedecem a uma regra simples, a mesma do triângulo, só que sobre uma esfera: o ângulo entre a pergunta e o item não pode diferir do ângulo entre a pergunta e o resumo mais do que o desvio do próprio resumo.

Isso dá uma margem que não depende de sorte, de sorteio nem do tipo de dado. Vale para todo par de pergunta e item. Com ela, o SIEVE, o nosso índice de busca, descarta pelo resumo sem nunca descartar um vizinho de verdade. Testamos em 20 milhões de pares: zero exceções.

Não é matemática nova, e dizemos isso. A regra dos ângulos foi escrita para busca por parecido em 2021 (Schubert), a ideia de comparar com um resumo sem perder ninguém aparece em teoria da informação desde 2013 (Ingber e colegas), e a nossa margem está escondida num lema do próprio artigo do RaBitQ, que preferiu a versão estatística. O que não achamos em lugar nenhum, nem nos 13 códigos que lemos, é alguém usar essa margem para descartar com garantia, com as contas em 32 bits provadas, e medir quanto ela custa.

A margem garantida é mais larga, então descarta menos e sobra mais conta completa. Comparamos as duas no mesmo motor, com o mesmo dado e as mesmas buscas.

No SIFT (1 milhão de imagens, 128 números cada), a margem estatística é 1,36× mais rápida que a garantida: 16,5 contra 22,5 milésimos de segundo por busca. É esse o preço inteiro de não perder ninguém. E a garantia ainda acelera o SIEVE: sem o resumo de 1 bit, a mesma busca leva 29,9 ms; com ele, 22,5 ms, 1,33× mais rápido, por 32 bytes a mais por imagem.

No GIST (960 números por imagem, um dado conhecido por ser difícil), a conta muda: a margem estatística é 2,5× mais rápida (13,7 contra 34,7 ms, com 100 mil imagens). Com muitos números, ela aperta muito e a garantida aperta pouco: no limiar ideal, a estatística descarta 99,6% dos itens, a garantida 59,8%.

Com um resumo de 4 bits por número em vez de 1, a garantida passa a descartar 99,8%, quase o mesmo que a estatística, e a busca cai para 26,6 ms. O preço vai para 2,0×, e não mais para baixo: as contas completas já são da mesma ordem (551 contra 262 por busca); o que sobra é ler 4 bits por número em vez de 1. E não é só no GIST: medimos 1 bit contra 4 bits em nove conjuntos de dados, de 64 a 960 números por item, incluindo embeddings de texto reais (GloVe, NYTimes, OpenAI, InstructorXL). O de 4 bits nunca foi mais lento: de 1,03× no SIFT a 3,03× nos embeddings da OpenAI. O ganho não segue o tamanho do item, segue quanto o resumo de 1 bit deixava passar. Por isso o SIEVE passou a usar 4 bits sempre, ao custo de uns 19% a mais de memória.

Depois trocamos a leitura. Em vez de consultar, para cada número de cada item, uma tabela que mora na memória, o SIEVE passou a somar 32 itens de uma vez com uma tabela que cabe dentro do registrador do processador (a técnica se chama FastScan e os bancos de vetores já a usam). A novidade é que o erro de arredondar essa tabela entra na margem: a garantia não muda, e a versão de 16 bits descarta exatamente o mesmo que a conta cheia. No GIST, a busca garantida cai de 26,0 para 12,9 ms em 100 mil imagens e de 48 para 22 ms em 200 mil. Com a mesma leitura dos dois lados, a garantia passa a custar 1,7×, e a garantida com a leitura nova fica mais rápida que a estatística com a leitura antiga (12,9 contra 13,2 ms; 22 contra 24). O que sobra do preço são as contas completas: 551 contra 262 por busca.

E não basta aumentar a folga da margem estatística até ela nunca falhar. Com folga máxima ela também vira garantia, mas outra, bem mais frouxa: deixa 2,9× mais itens para a conta completa no SIFT e 1,7× no GIST. Dá para ver isso no espécime, arrastando a folga até o fim.