This technical report introduces a "Certify-then-Rectify" framework that combines the speed of Hierarchical Navigable Small World (HNSW) graphs with theoretical correctness guarantees. The method dynamically evaluates search quality and escalates to an exact recovery algorithm if needed, ensuring worst-case accuracy.
- Uses a distribution-free statistical certifier to assess HNSW search quality with minimal overhead.
- Reinterprets the HNSW graph as a geometric spanner to bound the maximum distance of true nearest neighbors.
- Applies Extreme Value Theory to stochastically estimate the maximum empirical stretch factor.
- Delivers average-case speed of HNSW while maintaining the worst-case correctness of exact search.
This approach bridges the gap between heuristic search and rigorous retrieval, outperforming other applicable approaches on benchmark datasets.