CertEx: Exact Visual Retrieval at Scale by Certified Exclusion

1 Introduction

• Missed neighbors can remove relevant images, preserve duplicate pairs in training corpora, affect representation evaluation, and drop relevant memories.Exhaustive GPU search computes every distance at full precision, while approximate indexes trade recall for speed and require index construction and repair as datasets change.Source: §1 · p. 1
• Certified exclusion tests every vector at low precision but excludes it only when a conservative test proves it cannot be within the neighbor threshold.CertEx folds a rounding and accumulation error certificate into a half-precision tensor-core dot product, avoiding a false dismissal.Source: §1 · p. 1
• On one H100 GPU, CertEx returns exact results across sixteen datasets at 7.1× to 18.0× the throughput of the fastest cuVS fp32 configuration, outperforming GPU indexes when every query must be exact.Source: §1 · p. 2
• Figure 1 contrasts CertEx text-to-image retrieval with exact and CAGRA top-5 rankings; CAGRA loses the best matching image for both prompts.The figure covers retrieval over 1.28M ImageNet images.Source: §1 · p. 2, Figure 1 · p. 2
• CertEx replaces ranking all N vectors with one certified keep-or-exclude decision per vector, then verifies the kept vectors exactly; its retina examines every vector rather than choosing where to look.The method also answers range queries and similarity self-joins exactly.Source: §1 · p. 2
• On DataComp’s 12.8M web images, CertEx is exact for every query and finds all 31.4 billion duplicate pairs.The paper presents this as making exact deduplication practical at web scale.Source: §1 · p. 2

2 Related Work

• Exact lower-bound methods such as k-d trees, cover trees, AESA, GEMINI, and the VA-file prune candidates, but their bounds or survivor ranking differ from CertEx’s half-precision tensor-core test.Random projections preserve distances only up to a distortion factor and support approximate hashing.Source: §2 · p. 2
• Quantization methods [28] and graph indexes reduce examined vectors, while CertEx examines every vector and returns exact results.Benchmarks rank approximate methods by recall at a given throughput.Source: §2 · pp. 2–3
• Visual recognition pipelines use nearest neighbors for object retrieval [3], copy detection [17], dataset curation [1] [21], representation evaluation [12] [61], and retrieval-augmented classification [41].In practice, these pipelines obtain neighbors from approximate indexes, cluster-restricted comparisons, or fixed-degree kNN graphs.Source: §2 · p. 3
• Foveation allocates visual resolution unevenly [45], and floating-point filters pair fast arithmetic with error bounds; CertEx combines these ideas in a half-precision product with a no-false-dismissal proof.This distinguishes CertEx from approximate foveation.Source: §2 · p. 3

3.1 Overview

• CertEx divides exact search into a retina pass over all vectors and full-precision foveal verification of survivors.The fovea returns the k survivors with the smallest exact distances.Source: §3.1 · pp. 3–4

3.2 Certified Exclusion

• A certified exclusion test keeps every vector within threshold U, so exact reranking of its survivors yields the exact k nearest neighbors when U ≥ r_k(q).It may keep vectors farther than U, but cannot exclude a vector within U.Source: §3.2 · p. 4

3.3 Lifted Lower Bound

• The lifted projection retains m principal coordinates and summarizes the residual by its norm, giving a lower bound on the original distance.CertEx rewrites the resulting exclusion test as one inner product and comparison per vector.Source: §3.3 · pp. 4–5

3.4 Certified Half-Precision Retina

• Four appended half-precision certificate coordinates bound projection-rounding and tensor-core accumulation errors within the same dot product.The no-false-dismissal result ensures that vectors within the lifted-distance threshold are kept.Source: §3.4 · pp. 5–6

3.5 Foveal Verification and Exactness

• CertEx chooses U from sampled anchors and exactly reranks survivors; every query returns its exact k nearest neighbors.Survivors lie within squared distance U^2 + η(q) + 4ρ(q)ρ(x), and their number approaches ks when the width captures most data variance.Source: §3.5 · p. 7

3.6 Certified Exclusion at Any Threshold

• For a fixed-radius range query, CertEx uses the radius directly without anchors; similarity self-joins test each pair once, while a kNN graph can miss duplicates beyond k.The self-join is defined by a radius rather than a neighbor count.Source: §3.6 · pp. 7–8

Datasets and encoders

• Sixteen datasets span SIFT/GIST descriptors, CNN descriptors, word embeddings, seven ImageNet vision encoders, cross-modal CLIP queries, and web-scale DataComp embeddings.The dataset sizes range up to 100M vectors; ImageNet uses 1.28M training images and 10,000 validation queries.Source: §4.1 · p. 8

Platform, metrics, and baselines

• Experiments use one NVIDIA H100 with CertEx implemented in Triton on PyTorch; four datasets are repeated on an A100.On A100, CertEx is 8.8× to 11.8× faster than cuVS.Source: §4.1 · p. 8
• Throughput measures queries per second at k = 10, and exactness compares returned squared distances with fp64 ground truth at relative 10^-12.The benchmark compares exhaustive cuVS fp32 and fp16 search plus IVF-Flat, IVF-PQ, IVF-RaBitQ, and CAGRA, with configurations selected from a grid.Source: §4.1 · p. 8

4.2 Exact Search Throughput

• 7.1× to 18.0× faster than the fastest cuVS fp32 configuration, CertEx is exact on all sixteen datasets; half-precision exhaustive search remains 1.8× to 12.9× slower.Exhaustive fp32 search leaves 1 to 108 of 10,000 queries inexact on ten datasets; ImageNet embeddings yield 139 to 327 survivors per query.Source: §4.2 · p. 8
• 11.0× to 18.0× speedup over cuVS fp32 as BIGANN grows from 1M to 100M vectors; at 99.9% exact queries, CertEx is 27.2× to 84.9× faster than IVF-Flat, 3.7× to 124× faster than IVF-PQ, and 2.3× to 10.7× faster than IVF-RaBitQ.CertEx is exact for every query on every dataset, while CAGRA reaches this level only on SIFT1M among the thirteen datasets where it builds; the retina takes 0.03 to 2.47 seconds to build versus 2.2 to 29.7 seconds for CAGRA graphs. The figure compares scaling with N, methods at 99.9% exact queries, and survivors against ks.Source: §4.2 · p. 9, Figure 3 · p. 9
• Survivors lie at most 1.15× above ks where width approaches dimension, and farther above it for narrow widths.The BIGANN scaling comparison attributes the growing speedup to the retina pass scaling with N while anchor and fovea costs remain nearly constant.Source: §4.2 · pp. 8–9

4.3 Ablation of the Design Elements

• 5.0 ms versus 37.2 ms for exhaustive search on SIFT1M, and 170 ms versus 3.6 s on BIGANN-100M, for batches of 2048 queries.Anchors and fovea together take 2.2 ms and 22 ms, respectively.Source: §4.3 · p. 9
• 2.3 ms versus 4.1 ms on SIFT1M and 148 ms versus 289 ms on BIGANN-100M: the retina pass is faster than plain fp16 GEMM by comparing each product with its threshold inside one kernel.Exhaustive search's top-100 selection costs 3.3× to 12.5× the GEMM alone.Source: §4.3 · p. 9
• 5.6× to 24.3× slower with top-k selection; TF32 instead of fp16 slows the pass by 1.2× to 1.5×, and width D instead of m by 1.1× to 2.1×.The ablation isolates these elements on the same kernel and threshold.Source: §4.3 · p. 9
• 0.4% to 2.7% throughput cost for the certificate, which keeps every pair at the decision boundary while the uncertified retina excludes 1.996M to 2.007M of 4M pairs.The largest measured accumulation error is 0.42% to 0.76% of the certified bound; without the certificate, the exact DINOv2 self-join misses 299, 50, and 1 duplicate pairs at τ = 0.90, 0.95, and 0.98.Source: §4.3 · pp. 9–10
• CertEx remains faster than exhaustive search for k from 1 to 100 and batches of 1 to 4096 queries.The supplied figure captions identify ImageNet encoders and DINOv2 duplicates and kNN classification as additional figure topics.Source: §4.3 · p. 10, Figure 5 · p. 10, Figure 6 · p. 10

4.4 Vision Encoders

• Across all seven ImageNet encoders, CertEx is exact for every query and faster than every baseline at 99.9% exact queries.The figure covers seven encoders and varies retina width.Source: §4.4 · p. 10
• 10.3k to 671 survivors per query on DINOv2 as width increases from m = 507 to m = 763.A larger width tightens the bound.Source: §4.4 · p. 10
• 41× the throughput of IVF-Flat, CertEx is exact for every CLIP text query, while IVF-Flat alone among indexes reaches 99.9% exact text queries.The text embeddings occupy a different region of the joint embedding space than the image embeddings.Source: §4.4 · p. 10

4.5 Downstream Tasks

• At web scale, the exact self-join found all 31.4 billion DataComp duplicate pairs, while cluster restriction missed duplicates for 41,875 to 56,416 images.The pair count covers 1.97M of 12.79M images at τ = 0.95.Source: §4.5 · p. 10
• An exact 10-NN graph contained only 24.6% of the 4.0M pairs at τ = 0.90, while the exact self-join was 22× to 37× faster than an exhaustive fp32 join.SemDeDup missed up to 26% of the pairs of the worst ImageNet classes and up to 66% of all pairs with 50,000 clusters.Source: §4.5 · p. 10
• CertEx found exact neighbors for 50,000 DINO validation images in 0.40 seconds, 6.4× faster than the fastest cuVS fp32 configuration.IVF-RaBitQ lowered top-1 accuracy from 82.07% by up to 0.42 points, turning 463 correct predictions wrong and 259 wrong ones correct.Source: §4.5 · p. 10

4.6 Integer Retina

• The integer retina stores projected coordinates as scaled integer codes, keeps the residual coordinate in fp32, and evaluates a certified lower bound to decide which vectors to retain.Its proof assumes 127^2m < 2^24; the integer tensor-core code product is exact before the remaining fp32 arithmetic is bounded.Source: §4.6 · p. 11
• On DINOv2, the integer retina was exact at 53.5k queries per second with 660 bytes per vector, where the half-precision retina overflowed its survivor list at 644 bytes per vector.The integer configuration was 2.7× the throughput of the fastest cuVS search.Source: §4.6 · p. 11
• At the same width, the integer retina roughly halves memory but increases survivors, from 327 to 452 per DINOv2 query and from 178 to 641 per BIGANN-10M query.At the same memory, it can retain fewer survivors than the half-precision retina.Source: §4.6 · p. 11
• At m = 635 on DINOv2, the integer retina ran at 53.5k queries per second versus 152k for half precision, and its kernel was neither persistent nor tuned.The integer format is suited to datasets that would otherwise exceed device memory.Source: §4.6 · p. 11

4.7 Certified Screening in Inverted Lists

• Certified screening followed by ordered verification returns the exact k nearest neighbors among the probed lists, matching exhaustive search over those same lists.CertEx and IVF-Flat share list centers, and the reported test uses k = 10 and 1,024 lists.Source: §4.7 · p. 12
• On BIGANN-10M’s uint8 vectors, differing cuVS list placement made the methods’ answers differ at some probe settings, while recall stayed within 0.02.Their answers coincided on every query of SIFT1M and DINOv2.Source: §4.7 · p. 12
• At 200 probed lists, where CertEx recall exceeded 0.999, it was 4.7, 3.6, and 23.7 times faster than IVF-Flat on three datasets; on DINOv2 it was 40.1 times faster at 500 lists.Figure 9 plots throughput against probed lists and shows CertEx recall@10 at three settings.Source: §4.7 · p. 12
• At one to five probed lists, IVF-Flat is faster because CertEx’s anchor stage costs 51 to 63 ms per 10,000 queries regardless of probe count.CertEx verifies an almost constant number of vectors per query as the number of probed lists grows.Source: §4.7 · p. 12

4.8 Exact Search on an A100

• The A100 tests used one 7g.80gb MIG instance, and CertEx was compared with the fastest cuVS fp32 configuration on that same instance.The experiments covered SIFT1M, GIST1M, GloVe, and BIGANN-10M.Source: §4.8 · p. 13
• 8.8× to 11.8×: CertEx was exact for every query on all four datasets and achieved this throughput advantage over the fastest cuVS fp32 configuration on an A100.The corresponding H100 speedups were 7.7× to 15.5×.Source: §4.8 · p. 13
• Moving from H100 to A100, CertEx lost 2.3× to 2.5× throughput, while exhaustive search lost 1.9× on three datasets and 2.75× on GIST1M’s 960 dimensions.Consequently, the GIST1M speedup rose from 7.7× to 9.3×.Source: §4.8 · p. 13

• Up to 18.0× the throughput of the fastest exhaustive GPU search, CertEx is exact for every query across sixteen datasets of up to 100M vectors.Source: §5 · p. 13
• A lifted lower bound with a rounding-error certificate excludes almost every vector in one half-precision tensor-core pass without false dismissal.Source: §5 · p. 13
• The conclusion argues that exact search can become a practical default for visual retrieval, deduplication, and representation evaluation.Source: §5 · p. 13