HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
For practitioners relying on approximate nearest neighbor search, this work provides a way to maintain HNSW's speed while offering theoretical correctness guarantees, addressing a key limitation of heuristic search.
The paper introduces a 'Certify-then-Rectify' framework that enhances HNSW graph search with correctness guarantees by dynamically certifying search quality and, when needed, escalating to exact recovery using geometric spanner theory and Extreme Value Theory. The method achieves average-case speed of HNSW while ensuring worst-case correctness, outperforming other approaches on benchmarks.
Hierarchical Navigable Small World (HNSW) graphs serve as the industry standard due to their logarithmic complexity and strong empirical performance. However, HNSW relies on greedy graph traversal, a heuristic that provides no theoretical guarantees of correctness. In this paper, we propose a novel "Certify-then-Rectify" framework that bridges the gap between the speed of heuristic search and the rigor of exact retrieval. Rather than discarding HNSW, our approach first employs a distribution-free statistical certifier to dynamically evaluate the quality of a standard HNSW search with minimal overhead. If certification indicates that the retrieved neighbors are of low quality, the framework safely escalates to a rigorous exact recovery algorithm. To make this exact recovery computationally feasible, we reinterpret the HNSW graph as a geometric spanner and utilize Extreme Value Theory to stochastically estimate its maximum empirical stretch factor. This allows us to mathematically bound the maximum distance of true nearest neighbors. Extensive evaluations on benchmark datasets demonstrate that our tiered framework delivers the average-case speed of HNSW while ensuring the worst-case correctness of exact search and outperforming other applicable approaches.