CertEx: Exact Visual Retrieval at Scale by Certified Exclusion

arXiv:2610.21325v1 Announce Type: new Abstract: Exact k-nearest-neighbor (kNN) search over image descriptors and embeddings underlies visual retrieval, near-duplicate detection, the evaluation of learned representations, and increasingly the memory of LLM agents. However, exhaustive search computes every distance at full precision, whereas approximate indexes return recall below one. We observe that exact search only needs a proof that each excluded vector cannot be a neighbor. Because such a proof only has to be conservative, it can be checked in low precision, much as the retina examines the whole scene at low resolution. We call this principle certified exclusion and realize it in an exact kNN method for GPUs, which we call ertex. Specifically, ertex stores a lower-bounding projection of each vector in half precision and folds a rounding certificate into the same tensor-core dot product, so that only the few vectors that the test keeps need exact distances. We prove that ertex returns the exact kNN of every query. On sixteen datasets with up to 100M vectors, ertex is exact for every query at 7.1imes to 18.0imes the throughput of the fastest cuVS search on one H100 and outperforms quantized and graph indexes whenever every query must be exact.

Source: arXiv cs.CV | 2026-10-16