# HNSW with Accuracy Guarantees Using Graph Spanners

arXiv: https://arxiv.org/abs/2607.02338 · HTML: https://mlsanity.com/paper/2607.02338/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 52 references that are in the map.
- First posted on arXiv 2 Jul 2026.

## Builds on (most cited first, 22 of 22)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [π*0.6: a VLA That Learns From Experience](https://mlsanity.com/paper/2511.14759/) (2025)
- [Distribution-Free, Risk-Controlling Prediction Sets](https://mlsanity.com/paper/2101.02703/) (2021)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data](https://mlsanity.com/paper/2403.04871/) (2024)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [UNIFY: Unified Index for Range Filtered Approximate Nearest Neighbors Search](https://mlsanity.com/paper/2412.02448/) (2024)
- [boldsymbolSteiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes](https://mlsanity.com/paper/2408.13899/) (2024)
- [Quake: Adaptive Indexing for Vector Search](https://mlsanity.com/paper/2506.03437/) (2025)
- [Navigable Proximity Graph-Driven Native Hybrid Queries with Structured and Unstructured Constraints](https://mlsanity.com/paper/2203.13601/) (2022)
- [SIEVE: Effective Filtered Vector Search with Collection of Indexes](https://mlsanity.com/paper/2507.11907/) (2025)
- [Early Exit Strategies for Approximate k-NN Search in Dense Retrieval](https://mlsanity.com/paper/2408.04981/) (2024)
- [TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning](https://mlsanity.com/paper/2508.17828/) (2025)
- [PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs](https://mlsanity.com/paper/2508.17886/) (2025)
- [Tao: A Learning Framework for Adaptive Nearest Neighbor Search using Static Features Only](https://mlsanity.com/paper/2110.00696/) (2021)
- [Proxy-based Zero-Shot Entity Linking by Effective Candidate Retrieval](https://mlsanity.com/paper/2301.13318/) (2023)
- [Improving Biomedical Entity Linking with Retrieval-enhanced Learning](https://mlsanity.com/paper/2312.09806/) (2023)
- [Evaluating and Generating Query Workloads for High Dimensional Vector Similarity Search](https://mlsanity.com/paper/2606.14511/) (2026)
- [CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2509.00365/) (2025)

## Abstract (arXiv)

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.