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.
There is no recall SLA on the market. 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 |
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.
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 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.