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
Every edge carries a method, confidence, and the source snippet that justified it — so bad links are debuggable.
- PossiblePossibly related (embedding) · 47%Benchmarked Graph-RAG vs. Graph-Free Multi-Hop RAG: The graph mostly bought us a massive rebuild bill, not accuracy. →
- PossiblePossibly related (embedding) · 46%New benchmark exposes reasoning gaps in top models →
- LinkedLinked via arxiv author · 85%Minghao Li →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”
- LinkedLinked via arxiv author · 85%Raghav Mittal →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”
- LinkedLinked via arxiv author · 85%Sanjivni Rana →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”
- LinkedLinked via arxiv author · 85%Suraj Shetiya →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”
- LinkedLinked via arxiv author · 85%Gautam Das →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”
- LinkedLinked via arxiv author · 85%Nick Koudas →
“HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report”