HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
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 o
Lineage graph
Paper → model → repo connections mined from source citations (Tier-1 exact match).
Why these links exist
- Linked via arxiv authorMinghao Li →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
- Linked via arxiv authorRaghav Mittal →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
- Linked via arxiv authorSanjivni Rana →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
- Linked via arxiv authorSuraj Shetiya →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
- Linked via arxiv authorGautam Das →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
- Linked via arxiv authorNick Koudas →
HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report