Search papers, labs, and topics across Lattice.
This paper introduces a "Certify-then-Rectify" framework that enhances the Hierarchical Navigable Small World (HNSW) graph algorithm by combining heuristic search speed with theoretical correctness guarantees. By employing a distribution-free statistical certifier, the method dynamically assesses the quality of HNSW search results and escalates to a rigorous exact recovery algorithm when necessary, ensuring both efficiency and accuracy. Extensive evaluations show that this approach maintains the average-case speed of HNSW while providing worst-case correctness, outperforming existing methods in benchmark tests.
HNSW can now deliver both speed and accuracy, ensuring that even the fastest graph searches come with theoretical correctness guarantees.
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.
