arXiv:2607.02338 · v3

Graph-Based Nearest-Neighbor Search with Recall Guarantees Using Graph Spanners

首次提交 2026-07-02 23:44

版本更新 2026-11-12 04:06

雷达观测 2026-11-13 14:16

摘要

Graph-based indexes such as Hierarchical Navigable Small World (HNSW) graphs make nearest-neighbor retrieval efficient, but a high average recall can hide queries whose results fall below an application's quality requirement. We introduce Certify-then-Rectify (CTR), which returns an initial graph-search result when a calibrated rule accepts it and searches for missing neighbors otherwise. The recovery search reuses the existing graph and the distances already evaluated by the initial search. To determine how far this search should proceed, we relate metric distances to graph-path lengths through graph stretch. We develop Stretch-Bounded Expansion from Query (SBE-Q), together with Metric Bound Verification (MBV) to prune unnecessary work, and estimate its budget from paths to the fraction of true neighbors needed for the requested recall. Finite-sample tolerance bounds support this recall-aligned estimate; paths recorded during proposal recovery offer a conservative alternative to separate shortest-path computations. Independent tests certify initial acceptance and recovery outcomes, giving an end-to-end population recall guarantee even when the estimated stretch does not cover every relevant path. If recovery cannot be certified, rejected queries use exact scan. Experiments on HNSW compare five stretch estimators, assess recovery efficiency, and evaluate compliance and throughput on databases of up to 100 million vectors. CTR is not specific to HNSW, and we also evaluate it on another graph index.

作者备注：21 pages, 8 figures