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.
Não existe SLA de recall no mercado. 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 |
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.
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.
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.