Busca e agregação certificadas
Uma primitiva de busca por similaridade que prova não deixar passar nenhum vizinho verdadeiro — e uma escada que estende a prova da conta ao dado e ao modelo.
Todo índice de vizinho mais próximo aproximado (ANN) em produção — o HNSW por trás de Qdrant, Weaviate, pgvector, Milvus, Pinecone — é aproximado e silencioso: no ajuste de velocidade típico ele devolve resultados com recall abaixo de 1 e não informa quanto. Medimos, no hnswlib real (40k vetores, 128 dimensões), recall@10 entre 0,56 e 0,97 conforme o parâmetro de busca — sem nenhum sinal do erro. Em recomendação isso é tolerável. Em auditoria, compliance, detecção de fraude, deduplicação e busca de patentes, um “não achei” silencioso é um risco que não se pode assinar.
Até setembro de 2026 não existia SLA de recall no mercado. Em 1º de outubro saiu o SOLO (Chávez, CICESE), o primeiro índice aproximado com um certificado de recall calculável — e nós o medimos, confirmamos e colocamos ao lado do nosso contrato na seção 3. A fronteira moveu-se de “não há garantia” para “há uma garantia sobre a distribuição das consultas”. A nossa continua sendo a outra: prova por consulta.
Nossa tese é simples: onde o estado da arte entrega confiança, é possível declarar um contrato assinável — uma garantia por construção — e vencer os incumbentes instalados de forma adversarial, documentando honestamente o que se confirma e o que se refuta.
O contrato do SIEVE: dada uma consulta q e um raio r, devolver todos os pontos com distância ≤ r — zero falso negativo, por construção — ou o k-NN exato. O brute-force é o pior caso garantido; a poda determinística acelera o caso comum sem nunca enfraquecer a garantia.
A poda usa cotas inferiores provadas da distância verdadeira, de modo que nenhuma delas pode excluir um vizinho real. Sobre dado comprimido, o mecanismo produz a tricotomia central de toda a pilha:
Onde a busca vence e onde não vence, medido: para L2 barata em RAM, um laço brute-force é imbatível e a poda apenas empata — nós refutamos a claim de “mais rápido em RAM” e reportamos. A garantia paga em três regimes: fora da RAM (compressão vira ganho de I/O), métrica cara (uma distância exata poupada vale muito), e quando a completude é auditável (o valor não é velocidade, é a prova).
| Regime | Dado (real) | Resultado |
|---|---|---|
| Out-of-core | SIFT1M (1M×128, benchmark ANN) | 1215× menos I/O · 3,0× mais rápido · recall 1,000 vs ground-truth |
| Métrica cara (DTW) | UCR Archive (1-NN DTW canônico) | 2–6,6× mais rápido · acurácia idêntica ao brute (na faixa publicada) |
| Métrica cara (edit) | OFAC SDN (43k nomes) | 18–26× mais rápido · zero falso negativo |
| L2 em RAM | vetores 128-d, sintético + real | empate com brute — claim de velocidade refutada, reportada · SIMD com margem provada: 1,25–1,39× sobre o escalar, resultado bit-idêntico (seção 7) |
O SOLO faz da amostra o vocabulário: 2 % da base, sorteados, viram “termos”; cada objeto entra nas listas dos seus b termos mais próximos; a consulta vai às ks listas mais próximas e varre tudo com a distância verdadeira. Sem voto, sem feixe, sem poda. Por isso o recall é uma identidade: recall = probabilidade de cobertura, calculável das assinaturas guardadas com uma única passagem de verdade-terreno sobre uma amostra de consultas.
Reimplementamos o núcleo em Go e medimos nos mesmos arquivos que julgam o SIEVE — SIFT1M e GIST1M — na mesma máquina.
| O que o paper afirma | O que medimos | Veredito |
|---|---|---|
| recall = cobertura | SIFT 100 K→1 M: 96 de 96 pontos; GIST 100 K→500 K: 3 grades | diferença 0,0000 em todos — a identidade se sustenta em implementação independente |
| trabalho ∝ N0,4–0,6 | candidatos a recall fixo | N0,46–0,52 em SIFT, N0,54–0,59 em GIST · SIEVE exato: N0,94 e N1,00 |
| “lei do trabalho igual” | cobertura depende só de b·ks | massa 512 → 0,9956–0,9980 para b de 2 a 16; massa 1024 → 0,9998 para b de 4 a 16 |
| custo a 0,998 de cobertura | SIFT 1 M · GIST 200 K | 8,9 ms vs 38,4 ms do exato · 22 ms vs 205 ms do exato |
Dois contratos, não um vencedor. O SIEVE prova, nesta consulta, que nenhum vizinho verdadeiro ficou de fora — uma desigualdade. O SOLO certifica uma expectativa: a média do recall sobre a distribuição das consultas em que o certificado foi calculado. O próprio paper diz onde isso para: a prova por desigualdade triangular certifica menos de 0,1 % das consultas, e uma consulta fora da distribuição (texto contra imagem) fica sem certificado. Em dado de dimensão alta, onde o exato vira brute-force certificado, o segundo contrato custa 4 a 9× menos. O degrau natural é oferecer os dois sobre as mesmas células.
Limites desta medição: Go sem SIMD, roteador exaustivo, uma semente, consultas da mesma distribuição da base, 500 consultas em SIFT e 200 em GIST; a linha de base do SIEVE é de outra sessão. Nada aqui é benchmark de sistema contra o binário do autor.
Um certificado responde à pergunta “correto em relação a quê?”. Uma busca certificada garante a computação — dada a métrica e os dados como estão. Mas escolher a métrica, o raio e o modelo é um salto de fé. A contribuição central deste trabalho é uma escada que encolhe esse salto, degrau a degrau, sem nunca fingir eliminá-lo.
Com n observações, a distribuição verdadeira F fica numa faixa provada F̂ ± εₙ, com εₙ = √(ln(2/α)/2n) — sem hipótese de forma. A faixa alarga com a escassez. Medido em 3.391 espécies de plantas (nicho de temperatura, GBIF+WorldClim): de 15 registros, só ~20% da massa central é certificável; de 300, ~74%. Sobre uma tarefa de recomendação de espécies, 39% das recomendações do modelo de ponto não se sustentam a 95% — e a análise diz quais espécies precisam de mais dado.
A partir de um conjunto de calibração rotulado, a predição conforme escolhe um raio r_α com garantia P(match verdadeiro ∈ raio) ≥ 1−α — cobertura distribution-free contra a realidade. Juntos, SIEVE garante completude dentro do raio e o conformal garante que o raio cobre a realidade: recall certificado da decisão do modelo. A premissa residual é trocabilidade entre calibração e deploy — nomeável e mitigável (calibração adversarial), não “o modelo está certo”.
CLAMP e SIEVE são o mesmo motor em operadores duais: CLAMP certifica uma redução (muitos dados → um valor, num intervalo [Lo,Hi]); SIEVE certifica uma seleção (um conjunto → In/Possible). São as duas metades de qualquer consulta, e usam a mesma tricotomia. Por isso compõem sem cola:
Validado em dado climático real (3.263 espécies, nicho 5-D): a média certificada de um atributo sobre as espécies climaticamente adaptadas a um sítio ficou dentro do bracket em 327 de 327 consultas (zero violação); a largura (2,26 °C) decompõe-se limpa em erro de medição (1,00 °C) mais incerteza de busca (1,26 °C). A composição é sempre sã; sua utilidade acompanha a qualidade da compressão — quando o bracket é largo demais, refinam-se os membros Possible no dado exato.
A triagem AML é o encaixe forte: um match verdadeiro perdido é risco de enforcement, e o mercado inteiro entrega confiança, não prova. Empilhamos as três camadas sobre a lista real do OFAC SDN (OpenSanctions).
O “blocking” por prefixo, comum em produção, troca recall por velocidade em silêncio: medimos que ele perde 24% das variantes de nome; o SIEVE pega 100% (verificado, 26× mais rápido que o brute). E os 3.667 nomes cirílicos do OFAC são invisíveis a uma triagem só-latina (recall 0%); a transliteração canônica cirílico→latino os recupera a 96%, com piso certificado.
Sobre variantes reais de data-entry, o conformal entrega um piso assinável: α=0,05 → recall ≥ 95% (medido 96,1%), α=0,01 → ≥ 99% (medido 99,1%), com o trade recall×volume explícito na mesma tabela — o número que um Chief Compliance Officer põe no dossiê de Model Risk Management.
O princípio: excluir só por prova, nunca por incerteza. Uma data de nascimento disjunta de todas as datas registradas (o OFAC lista várias por evasão) prova pessoa diferente e suprime com certeza; campo ausente ou incerto nunca derruba um alerta; nacionalidade e ID só confirmam (não excluem — dupla nacionalidade, múltiplos IDs). Medido em 7.379 pessoas com data de nascimento: o volume de alertas cai 78% no geral e 96% nos nomes comuns, com recall preservado em 100%. Exemplo real: um cliente com 14 entidades de nome parecido colapsa para 1 após a supressão certificada por data — e a verdadeira permanece.
O que sabíamos sobre o SIEVE exato em SIFT1M: o limite de bola obriga a visitar 54 % dos pontos, o piso real (as células dos 10 vizinhos) é 0,22 %. A folga do limite é o problema. Tentamos três coisas, no mesmo protocolo (k-NN k=10, 200 consultas, mediana de 6 repetições, mesma sessão, Apple M2, Go 1.27).
Para x na célula j e qualquer outro centróide c′, d(q,x) ≥ (d(q,cj)² − d(q,c′)²) / 2·d(cj,c′). Vale em qualquer espaço com produto interno e a desigualdade é provada ponto a ponto em teste. Com uma testemunha, poda 13 % dos pontos considerados e 14 % das células que a bola deixava passar. O relógio: −0,5 %, dentro do ruído; com 8 testemunhas, +10 %. Os pontos que ele remove são os que o pivô local já removia a poucos nanossegundos cada. Fica no código, opt-in, desligado.
O perfil atribuía 26 % (PQ) e 40 % (projeção) do tempo a memclr de uma tabela de
64 KB alocada por consulta. Tiramos a alocação: o memclr sumiu do perfil e o relógio
não mudou. Fica, porque é correto e evita lixo sob concorrência; não entra como
ganho em lugar nenhum.
Três kernels em float32 — o limite de pivô, a soma de quadrados da projeção e um crivo da distância exata — descontam uma margem de arredondamento demonstrada antes de devolver, de modo que nunca excedem o valor exato (20 mil tentativas por build). O candidato que sobrevive ao crivo paga a distância exata em float64: o resultado é bit-idêntico ao escalar. Os bits dos limites intermediários não são, e não precisam ser.
| Configuração (SIFT) | N | Escalar | SIMD | Ganho |
|---|---|---|---|---|
| 8 pivôs + PQ m=32 + IVF | 200 K | 8,52 ms | 6,83 ms | 1,25× |
| IVF + projeção k=32 | 200 K | 4,14 ms | 3,15 ms | 1,32× |
| 8 pivôs + projeção k=32 + IVF | 200 K | 6,47 ms | 4,66 ms | 1,39× |
| 8 pivôs + PQ m=32 + IVF | 1 M | 35,1 ms | 28,2 ms | 1,24× |
| IVF + projeção k=32 | 1 M | 15,7 ms | 12,2 ms | 1,29× |
O bound do PQ (37 % do tempo na configuração PQ) é gather em tabela; o pacote SIMD portátil não tem gather nem shuffle de bytes. A saída continua sendo o FastScan de 4 bits, que afrouxa o bound — escopado, não fingido. E a regra que fez os três kernels serem seguros é a mesma que impede usar SIMD em qualquer soma que vire byte, hash ou selo: SIMD só onde o resultado continua sendo um limite.
A claim “busca certificada mais rápida que brute em RAM para L2” é falsa — o laço brute-force é imbatível nesse regime, e nós dizemos com número. O ganho do SIEVE está no out-of-core, na métrica cara e na completude auditável, não na busca em RAM.
A poda certificada pelo hiperplano de Voronoi remove 13 % dos pontos e 0 % do tempo; o perfil que acusava 26–40 % em alocação não mexeu no relógio. Os dois estão na seção 7, com os números.
O certificado cobre a computação e, com os degraus 2–3, a amostra e a decisão do modelo — não a classe do modelo em si. A cobertura conforme assume trocabilidade entre calibração e realidade; a supressão por data de nascimento assume registro correto (uma tolerância absorve erro). Cada premissa é encolhida ao mínimo e nomeada — nunca zerada.
O padrão se repete até o fim: você não elimina a fé; empurra-a ao ponto mais fraco possível, dá um nome e um número a ela, e certifica tudo o que está a jusante.
Todos os números são medidos em dado público real e reproduzíveis; o certificado é verificado em teste (contenção vs brute-force, propriedade sobre milhares de casos) a cada camada.
Research/2026-10-05-sieve-solo; kernels e hiperplano: sieve
(kernels_simd.go, ivf_hyper_test.go), build com
GOEXPERIMENT=simd, Go 1.27.