Certified search & aggregation
A similarity-search primitive that proves it never drops a true neighbor — and a ladder that extends the proof from the computation to the data and the model.
Every production approximate nearest-neighbor (ANN) index — the HNSW behind Qdrant, Weaviate, pgvector, Milvus, Pinecone — is approximate and silent: at a typical speed setting it returns results with recall below 1 and tells you nothing about the miss rate. On real hnswlib (40k vectors, 128 dimensions) we measured recall@10 between 0.56 and 0.97 depending on the search parameter — with no signal of the error. In recommendation that is tolerable. In audit, compliance, fraud detection, deduplication and prior-art search, a silent “not found” is a risk you cannot sign your name to.
Until September 2026 there was no recall SLA on the market. On October 1st, SOLO (Chávez, CICESE) appeared: the first approximate index with a computable recall certificate — and we measured it, confirmed it, and put it next to our contract in section 3. The frontier moved from “no guarantee” to “a guarantee over the query distribution”. Ours remains the other one: proof per query.
Our thesis is simple: where the state of the art delivers confidence, one can declare a signable contract — a guarantee by construction — and beat the installed incumbents adversarially, honestly documenting what holds and what is refuted.
SIEVE's contract: given a query q and a radius r, return every point within distance ≤ r — zero false negatives, by construction — or the exact k-NN. Brute force is the guaranteed worst case; deterministic pruning speeds up the common case without ever weakening the guarantee.
Pruning uses provable lower bounds on the true distance, so none of them can ever exclude a real neighbor. Over compressed data, the mechanism yields the central trichotomy of the whole stack:
Where the search wins and where it does not, measured: for cheap L2 in RAM a brute-force loop is unbeatable and pruning only ties — we refute the “faster in RAM” claim and report it. The guarantee pays off in three regimes: out of RAM (compression becomes an I/O win), expensive metrics (a saved exact distance is worth a lot), and when completeness must be auditable (the value is not speed, it is the proof).
| Regime | Data (real) | Result |
|---|---|---|
| Out-of-core | SIFT1M (1M×128, ANN benchmark) | 1215× less I/O · 3.0× faster · recall 1.000 vs ground truth |
| Expensive metric (DTW) | UCR Archive (canonical 1-NN DTW) | 2–6.6× faster · accuracy identical to brute (within published range) |
| Expensive metric (edit) | OFAC SDN (43k names) | 18–26× faster · zero false negatives |
| L2 in RAM | 128-d vectors, synthetic + real | ties with brute — speed claim refuted, reported · SIMD with a proven margin: 1.25–1.39× over scalar, bit-identical result (section 7) |
SOLO makes the sample the vocabulary: 2 % of the base, drawn at random, become “terms”; every object is posted to its b nearest terms; a query goes to its ks nearest lists and scans everything with the true distance. No vote, no beam, no pruning. Recall is therefore an identity: recall = coverage probability, computable from the stored signatures with one ground-truth pass over a sample of queries.
We reimplemented the core in Go and measured it on the same files that judge SIEVE — SIFT1M and GIST1M — on the same machine.
| What the paper claims | What we measured | Verdict |
|---|---|---|
| recall = coverage | SIFT 100 K→1 M: 96 of 96 points; GIST 100 K→500 K: 3 grids | difference 0.0000 everywhere — the identity holds in an independent implementation |
| work ∝ N0.4–0.6 | candidates at fixed recall | N0.46–0.52 on SIFT, N0.54–0.59 on GIST · exact SIEVE: N0.94 and N1.00 |
| “equal-work law” | coverage depends on b·ks only | mass 512 → 0.9956–0.9980 for b from 2 to 16; mass 1024 → 0.9998 for b from 4 to 16 |
| cost at 0.998 coverage | SIFT 1 M · GIST 200 K | 8.9 ms vs 38.4 ms exact · 22 ms vs 205 ms exact |
Two contracts, not one winner. SIEVE proves, for this query, that no true neighbor was left out — an inequality. SOLO certifies an expectation: the mean recall over the query distribution the certificate was computed on. The paper itself says where that stops: the triangle-inequality proof certifies under 0.1 % of queries, and an out-of-distribution query (text against images) is served uncertified. On high-dimensional data, where exact search becomes certified brute force, the second contract costs 4 to 9× less. The natural next rung is to offer both over the same cells.
Limits of this measurement: Go without SIMD, exhaustive router, one seed, queries from the base distribution, 500 queries on SIFT and 200 on GIST; the SIEVE baseline is from another session. Nothing here is a systems benchmark against the author’s binary.
A certificate answers the question “correct with respect to what?”. A certified search guarantees the computation — given the metric and the data as they are. But choosing the metric, the radius and the model is a leap of faith. The central contribution of this work is a ladder that shrinks that leap, rung by rung, without ever pretending to remove it.
With n observations, the true distribution F lies in a proven band F̂ ± εₙ, with εₙ = √(ln(2/α)/2n) — with no shape assumption. The band widens with scarcity. Measured on 3,391 plant species (temperature niche, GBIF+WorldClim): with 15 records only ~20% of the central mass is certifiable; with 300, ~74%. On a species-recommendation task, 39% of the point-model recommendations do not hold at 95% — and the analysis says which species need more data.
From a labeled calibration set, conformal prediction chooses a radius r_α with the guarantee P(true match ∈ radius) ≥ 1−α — distribution-free coverage against reality. Together, SIEVE guarantees completeness within the radius and conformal guarantees the radius covers reality: certified recall of the model's decision. The residual premise is exchangeability between calibration and deployment — nameable and mitigable (adversarial calibration), not “the model is right”.
CLAMP and SIEVE are the same engine in dual operators: CLAMP certifies a reduction (many data → one value, as an interval [Lo,Hi]); SIEVE certifies a selection (a set → In/Possible). They are the two halves of any query, and they use the same trichotomy. So they compose without glue:
Validated on real climate data (3,263 species, 5-D niche): the certified mean of an attribute over the species climatically adapted to a site fell inside the bracket in 327 of 327 queries (zero violations); the width (2.26 °C) decomposes cleanly into measurement error (1.00 °C) plus search uncertainty (1.26 °C). The composition is always sound; its usefulness tracks the compression quality — when the bracket is too wide, one refines the Possible members on the exact data.
AML screening is the strong fit: a missed true match is enforcement risk, and the whole market delivers confidence, not proof. We stack the three layers over the real OFAC SDN list (OpenSanctions).
Prefix “blocking”, common in production, trades recall for speed silently: we measured it dropping 24% of name variants; SIEVE catches 100% (verified, 26× faster than brute). And the 3,667 Cyrillic names in OFAC are invisible to a Latin-only screen (0% recall); canonical Cyrillic→Latin transliteration recovers them to 96%, with a certified floor.
Over real data-entry variants, conformal delivers a signable floor: α=0.05 → recall ≥ 95% (measured 96.1%), α=0.01 → ≥ 99% (measured 99.1%), with the recall×volume trade explicit in the same table — the number a Chief Compliance Officer puts into the Model Risk Management file.
The principle: exclude only by proof, never by uncertainty. A date of birth disjoint from all recorded dates (OFAC lists several per target, by evasion) proves a different person and suppresses with certainty; a missing or uncertain field never drops an alert; nationality and ID only confirm (they never exclude — dual nationality, multiple IDs). Measured on 7,379 persons with a date of birth: alert volume falls 78% overall and 96% on common names, with recall preserved at 100%. Real example: a client with 14 name-similar entities collapses to 1 after certified date suppression — and the true one remains.
What we knew about exact SIEVE on SIFT1M: the ball bound forces a visit to 54 % of the points, while the real floor (the cells of the 10 neighbors) is 0.22 %. The slack of the bound is the problem. We tried three things under one protocol (k-NN k=10, 200 queries, median of 6 runs, same session, Apple M2, Go 1.27).
For x in cell j and any other centroid c′, d(q,x) ≥ (d(q,cj)² − d(q,c′)²) / 2·d(cj,c′). It holds in any inner-product space and the inequality is proved point by point in a test. With one witness it prunes 13 % of the points considered and 14 % of the cells the ball let through. Wall-clock: −0.5 %, inside the noise; with 8 witnesses, +10 %. The points it removes are the ones the local pivot already removed at a few nanoseconds each. It stays in the code, opt-in, off.
The profile charged 26 % (PQ) and 40 % (projection) of the time to memclr of a
64 KB table allocated per query. We removed the allocation: memclr vanished from the
profile and the clock did not move. It stays, because it is correct and avoids
garbage under concurrency; it is not booked as a gain anywhere.
Three float32 kernels — the pivot bound, the projection sum of squares and a screen for the exact distance — subtract a proven rounding margin before returning, so they never exceed the exact value (20,000 trials per build). A candidate that survives the screen pays the exact float64 distance: the result is bit-identical to the scalar path. The bits of the intermediate bounds are not, and need not be.
| Configuration (SIFT) | N | Scalar | SIMD | Gain |
|---|---|---|---|---|
| 8 pivots + PQ m=32 + IVF | 200 K | 8.52 ms | 6.83 ms | 1.25× |
| IVF + projection k=32 | 200 K | 4.14 ms | 3.15 ms | 1.32× |
| 8 pivots + projection k=32 + IVF | 200 K | 6.47 ms | 4.66 ms | 1.39× |
| 8 pivots + PQ m=32 + IVF | 1 M | 35.1 ms | 28.2 ms | 1.24× |
| IVF + projection k=32 | 1 M | 15.7 ms | 12.2 ms | 1.29× |
The PQ bound (37 % of the time in the PQ configuration) is a table gather; the portable SIMD package has neither gather nor byte shuffle. The way out is still 4-bit FastScan, which loosens the bound — scoped, not faked. And the rule that made the three kernels safe is the same one that forbids SIMD in any sum that becomes a byte, a hash or a seal: SIMD only where the result is still a bound.
The claim “certified search faster than brute in RAM for L2” is false — the brute-force loop is unbeatable in that regime, and we say so with numbers. SIEVE's gain is in out-of-core, expensive metrics and auditable completeness, not in-RAM search.
The certified Voronoi half-space pruning removes 13 % of the points and 0 % of the time; the profile that blamed 26–40 % on allocation did not move the clock. Both are in section 7, with the numbers.
The certificate covers the computation and, with rungs 2–3, the sample and the model's decision — not the model class itself. Conformal coverage assumes exchangeability between calibration and reality; date-of-birth suppression assumes correct records (a tolerance absorbs error). Each premise is shrunk to the minimum and named — never zeroed.
The pattern repeats all the way down: you do not eliminate the leap of faith; you push it to the weakest possible point, give it a name and a number, and certify everything downstream.
All numbers are measured on real public data and reproducible; the certificate is verified in tests (containment vs brute force, property tests over thousands of cases) at every layer.
Research/2026-10-05-sieve-solo; kernels and half-space bound: sieve
(kernels_simd.go, ivf_hyper_test.go), built with
GOEXPERIMENT=simd, Go 1.27.