Rinha de Backend 2026: o VP-Tree exato que saiu do piso

Começando

Recapitulando os dois posts anteriores em uma frase: o brute force tirou último lugar com -6000, 0 falso positivo e 0 falso negativo, porque escanear 3 milhões de vetores por request num núcleo de 2014 estoura o relógio — não porque erra. O classificador sempre esteve certo. Faltava caber no tempo.

Esse post é sobre fazer caber. E o requisito que define tudo o que vem a seguir: a busca otimizada tem que devolver exatamente o mesmo resultado do brute force. Não “quase”. Não “erro pequeno”. Idêntico, byte a byte, para qualquer query — inclusive as que a Engine manda e eu nunca vi.

Por que exato, e não aproximado

A escolha óbvia de quem quer velocidade em busca vetorial é ANN — Approximate Nearest Neighbors, tipo HNSW. É o que a maior parte do mundo usa. E é exatamente o que eu não podia usar aqui.

A fórmula da Rinha pune erro de detecção com peso real: falso positivo peso 1, falso negativo peso 3, e um corte rígido em 15% de falhas que trava o detection_score em -3000. Um índice aproximado troca exatidão por velocidade — ele às vezes devolve o 6º vizinho no lugar do 5º. Na maioria dos domínios isso é irrelevante. Aqui, cada vizinho trocado pode virar um fraud_score diferente, que vira uma decisão diferente, que vira um FP ou FN que o brute force não cometia. Eu já tinha provado 0/0 com brute force. Trocar isso por “0.3% de erro de recall” seria jogar fora a única coisa que estava perfeita.

Então: busca exata, sublinear. O candidato é o VP-Tree (Vantage Point Tree) — uma BSP métrica que particiona o espaço por distância a um ponto-pivô. No post 5 eu mesmo escrevi que 14 dimensões é território perigoso pra árvores métricas (elas degeneram em alta dimensão, o crossover com brute force fica na faixa 10–20 dim e depende do dataset). Era um risco real. A forma de lidar com risco é medir, não torcer.

O VP-Tree em 14 dimensões i16

A ideia do VP-Tree: cada nó escolhe um ponto (o vantage point), calcula a distância dele para todos os outros do subconjunto, pega a mediana dessas distâncias como threshold, e particiona — os mais próximos que a mediana vão pra subárvore esquerda, os mais distantes pra direita. Recursivamente. A árvore fica balanceada por construção (split pela mediana de contagem), profundidade O(log n).

Cada nó serializa em 20 bytes fixos:

struct VpNode {
    point_index: u32,    // índice da referência (o vantage point)
    threshold_sq: u64,   // distância² mediana
    left: u32,           // índice do nó filho (ou u32::MAX = vazio)
    right: u32,
}

threshold_sq é u64 porque a distância euclidiana ao quadrado em 14 dimensões de i16 chega a 5.6 × 10⁹ — não cabe em i32, e eu nunca tiro a raiz no caminho de dados (já volto nisso). Três milhões de nós × 20 bytes = 60 MB de índice, mmap’do como os refs, com checksum FNV-1a validado na carga (ADR-0003). A árvore é construída no preprocess, no build da imagem — zero custo de startup, igual aos refs.

A busca é a recursão métrica clássica: visita o nó, calcula a distância da query ao vantage point, atualiza os 5 melhores (tau = distância do 5º melhor atual), e decide quais subárvores ainda podem conter um vizinho melhor usando a desigualdade triangular. É aqui que mora o post inteiro.

A poda que parecia exata — e não era

A regra de poda do VP-Tree, em distância euclidiana, é direta. Com d = distância da query ao vantage point, threshold = raio do nó, tau = raio da busca atual (distância do 5º melhor):

• Pode existir vizinho à esquerda (dentro) se d - tau ≤ threshold, ou seja d ≤ threshold + tau.
• Pode existir vizinho à direita (fora) se d + tau ≥ threshold, ou seja threshold ≤ d + tau.

Se a condição falha, a subárvore inteira é podada — não visito, não comparo. É daí que vem o sublinear. Mas se eu podar uma subárvore que continha um vizinho verdadeiro, o resultado diverge do brute force. Em qualquer outro domínio isso é “recall 99.9%”. Aqui é um FP ou FN que eu jurei que não existiria.

A primeira implementação fazia a poda assim:

let threshold = (node.threshold_sq as f64).sqrt();
let d   = (distance as f64).sqrt();
let tau = (top.tau_sq() as f64).sqrt();
let may_need_left  = d - tau <= threshold + f64::EPSILON;
let may_need_right = d + tau >= threshold - f64::EPSILON;

Parece defensivo. Tem f64::EPSILON dos dois lados pra “ser conservador no arredondamento”. Os testes locais passavam — todas as 54.100 entradas do test-data.json, byte a byte com o brute force. Eu quase segui em frente.

O problema é a escala. Distância² chega a 5.6 × 10⁹; a raiz disso é ~74.833. O erro de arredondamento de um f64::sqrt nessa magnitude é da ordem de 1.6 × 10⁻¹¹. E f64::EPSILON vale 2.2 × 10⁻¹⁶. O padding “conservador” era cinco ordens de grandeza menor que o erro que ele deveria cobrir. Ele não fazia nada — era cosmético.

Isso abre uma janela de ~5 × 10⁻¹¹ em que d - tau calculado em f64 cai do lado errado da comparação e a poda descarta uma subárvore que tinha o vizinho verdadeiro. Para o dataset fixo e as queries do test-data.json, essa janela nunca foi tocada — por isso os testes passavam. Mas a Engine não manda as queries do meu fixture. Ela manda transações que eu nunca vi. A exatidão não estava provada; estava não-refutada pela amostra que eu por acaso testei. São coisas diferentes, e a diferença é a nota.

A poda inteira que prova exatidão

A saída é não ter ponto flutuante no caminho de decisão. As três grandezas que eu comparo são raízes de inteiros (d², threshold², tau² são todos u64 exatos). A pergunta “√a² ≤ √b² + √c²?” pode ser respondida só com inteiros, sem nunca tirar raiz.

A álgebra, com a, b, c ≥ 0 e seus quadrados conhecidos:

• Se a ≤ b, então a ≤ b ≤ b + c → verdadeiro. Testo a² ≤ b².
• Senão a > b. a ≤ b + c ⟺ (a - b) ≤ c ⟺ (a - b)² ≤ c² (ambos os lados ≥ 0).
  • (a - b)² = a² + b² - 2ab, então a condição vira a² + b² - c² ≤ 2ab.
  • Seja L = a² + b² - c². Se L ≤ 0, verdadeiro (2ab ≥ 0 ≥ L).
  • Senão, ambos os lados positivos: elevo ao quadrado de novo → L² ≤ 4·a²·b².

Tudo isso é aritmética inteira. Em Rust, com i128/u128 para não estourar (4·a²·b² no pior caso ≈ 1.25 × 10²⁰, dentro de u128):

/// Decide √a2 ≤ √b2 + √c2 exatamente, só com inteiros.
fn sqrt_le_sum(a2: u64, b2: u64, c2: u64) -> bool {
    if a2 <= b2 {
        return true; // a ≤ b ≤ b + c
    }
    // a > b: a ≤ b + c  ⟺  (a-b)² ≤ c²  ⟺  a²+b²-c² ≤ 2ab
    let lhs = a2 as i128 + b2 as i128 - c2 as i128;
    if lhs <= 0 {
        return true; // 2ab ≥ 0 ≥ lhs
    }
    let lhs = lhs as u128;
    lhs * lhs <= 4u128 * a2 as u128 * b2 as u128
}

E a poda vira duas chamadas, sem um único f64:

let d2  = distance;          // u64
let th2 = node.threshold_sq; // u64
let t2  = top.tau_sq();      // u64, ou u64::MAX enquanto < 5 vizinhos
let may_need_left  = sqrt_le_sum(d2, th2, t2);  // d ≤ threshold + tau
let may_need_right = sqrt_le_sum(th2, d2, t2);  // threshold ≤ d + tau

O sentinela cai de graça: enquanto não juntei 5 vizinhos, tau² é u64::MAX; lhs = a² + b² - c² fica enorme e negativo, sqrt_le_sum devolve true, e os dois ramos são visitados — exatamente o que se quer antes do conjunto de candidatos encher. Agora a poda é a desigualdade triangular verdadeira, não uma aproximação com um epsilon pequeno demais. Não existe janela de erro porque não existe arredondamento. A exatidão vale para qualquer query — inclusive as que eu nunca vou ver.

Como se prova que está exato

Provar a álgebra no papel é metade. A outra metade é não confiar em mim mesmo. Três camadas de validação, todas comparando contra o brute force como verdade:

1. Todas as 54.100 saídas oficiais. Cada entrada do test-data.json passa pelo VP-Tree e o approved/fraud_score tem que bater com o esperado oficial. 0 divergências.

2. Top-5 canônico, não só a decisão. Comparo os 5 vizinhos exatos (índice e distância), não só o booleano final — incluindo o desempate. Empate de distância resolve por (distância, índice_original), determinístico e idêntico nos dois caminhos. Duas decisões iguais podem esconder vizinhos diferentes; essa camada não deixa.

3. Fuzz diferencial determinístico. Um PRNG SplitMix64 de semente fixa gera 5.000 queries contra os 3 milhões de referências reais: derivadas de referências (exatas, perturbadas de perto, perturbadas de longe) e uniformemente aleatórias. Para cada uma, o top-5 do VP-Tree tem que ser igual ao do brute force. Semente fixa = reproduz bit a bit em qualquer máquina. 0 divergências.

Com a poda inteira, essa terceira camada deixou de ser a prova de exatidão (a álgebra já é) e virou rede de segurança contra regressão. Mas ela é o que me deixa dormir: 5.000 queries adversariais no dataset real, zero diferença.

Sem fallback silencioso

Um detalhe que parece paranoia e não é. O VP-Tree carrega de um artefato mmap’do com checksum. O que acontece se o arquivo faltar, ou o checksum não bater?

A resposta tentadora é “cai pro brute force”. É a resposta errada. Brute force silencioso é voltar pro -6000 sem ninguém ver — a API responderia, o healthcheck passaria, e a nota despencaria sem um único erro no log. O comportamento certo é falhar alto: artefato ausente ou corrompido faz a carga do índice retornar erro, o processo não sobe, o HEALTHCHECK do container nunca fica verde, e o compose não promove a API. Testes garantem isso explicitamente — carregar com artefato faltando ou com um byte trocado tem que dar erro, nunca degradar escondido. Um modo SEARCH_MODE=bruteforce existe, mas só explícito, pra validação. O default nunca cai pra trás sozinho.

O número real — a Engine oficial

Empacotei v0.5.0, atualizei a submission, abri a issue rinha/test. A Engine rodou o test/test.js completo no mesmo Mac Mini Late 2014 de sempre. O resultado, lado a lado com o brute force:

Os dois cortes que mataram o brute force — p99 ≥ 2000 ms e falhas ≥ 15% — sumiram. O p99 caiu de 2002 ms para 162 ms; as falhas, de 89% para zero. E as duas linhas que importam continuam 0 / 0: a classificação não regrediu nem um caso. Não podia regredir — é a mesma busca, exata, só que sem escanear 3 milhões por request.

Olha o contraste com cuidado: logo abaixo de mim no filtro tem um gpu-bruteforce e um java-brute-force, ambos cravados em -6000. GPU não salvou o brute force. Trocar de linguagem não salvou. O que tirou do piso não foi força bruta nem hardware — foi parar de fazer trabalho O(n) por request. Estrutura de busca, não músculo.

Uma nota honesta, porque a série é sobre a jornada real: o p99 local oscilou feio entre execuções na minha máquina — 3 ms numa run, 31 ms em outra, ambas do mesmo binário, porque é um laptop compartilhado sob carga durante a medição. Por isso eu nunca tratei o número local como verdade. O único juiz é a Engine oficial, no hardware padrão, e ela cravou 162,80 ms com 0% de falha. O número local serve de sanidade; a nota vem de fora.

O que ainda falta

3.788 é a saída do piso, não o teto. A fórmula de latência satura em +3000 só quando o p99 chega perto de 1 ms — estou em 162. Ainda tem distância:

• Quantização para u8 — metade da banda de memória no scan que o VP-Tree ainda faz nas folhas, mais vetores por linha de cache.
• SIMD explícito (_mm256_*) no lugar da auto-vetorização, agora que tem alvo medido.
• Afinar o VP-Tree — escolha de vantage point, profundidade de corte para folha, layout dos nós para localidade de cache.

Cada um entra um de cada vez, medido contra esse 3.788 exatamente como o VP-Tree foi medido contra o -6000. A regra da série não muda: medir antes de otimizar, e nunca trocar exatidão por velocidade sem prova.

O gancho que abriu a série fechou aqui: o algoritmo estava certo o tempo todo. Faltava caber no relógio. Agora ele cabe — e a prova de que continua certo é matemática inteira, não um teste que por sorte não caiu na janela de erro.

Código: github.com/obrunogonzaga/rinha-backend-2026-rust. PR do Slice 5 mergeada em 20d0ffc; submissão v0.5.0 medida na issue #4880 da Rinha. A poda inteira (sqrt_le_sum) e o fuzz diferencial estão na PR #12.