On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Abstract
Graph-based nearest neighbor search algorithms like HNSW, DiskANN, NSG, and others have surged in popularity in recent years due to their excellent empirical performance in comparison to space-partitioning methods like IVF data structures and Locality Sensitive Hashing (LSH). However, in contrast to LSH and related methods, obtaining strong worst-case theoretical guarantees for graph-based search has proven challenging. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. We show that no standard graph-based method (any that runs a variant of greedy search on a flat or hierarchical graph) can achieve sublinear query time for approximate nearest neighbor search in Euclidean space, even for an arbitrarily large approximation factor. On the other hand, we prove that sublinear query time is possible if we allow for Steiner points in the search graph. We obtain bounds comparable to LSH, showing e.g., that graph-based search with Steiner points can solve $c$-approximate nearest neighbor search in Euclidean space with query time $\tilde{O}(n^{1/(c-1)})$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper establishes a fundamental lower bound for graph-based nearest neighbor search and demonstrates that Steiner points can restore sublinear query time guarantees comparable to LSH. It rigorously explains the theoretical limitations of current popular algorithms like HNSW and DiskANN while providing a constructive path forward through graph augmentation, bridging a significant gap between empirical success and theoretical understanding in high-dimensional search.
Methodology
The paper presents a rigorous theoretical framework for analyzing graph-based nearest neighbor search (NNS) algorithms like HNSW and DiskANN. The core methodological contribution is the formalization of a "flat search graph" model that captures generalized greedy search, allowing for the derivation of strong lower bounds. The authors prove that without Steiner points, no such method can achieve sublinear query time in worst-case Euclidean high-dimensional settings, effectively explaining the long-standing gap between empirical performance and theoretical guarantees. Conversely, they introduce a novel construction using Steiner points to simulate Locality Sensitive Hashing (LSH) within the graph search framework, achieving query times comparable to LSH ($\tilde{O}(n^{1/(c-1)})$). The proof techniques involve constructing hard instances of orthogonal vectors and leveraging geometric properties of Steiner nodes to implement hash table lookups via greedy traversal.
Results & evaluation
The experimental section is limited but sufficient for an initial exploration. The authors augment the ParlayANN implementation of DiskANN with simple $k$-means cluster centroids as Steiner points. They evaluate this on standard benchmarks (GloVe-200, NYTimes) using cosine similarity. The results show consistent improvements in recall vs. distance computations compared to the baseline, validating the theoretical potential of Steiner points. However, the experiments are preliminary, using a very simple heuristic for Steiner point generation rather than the optimal theoretical construction, and the datasets are relatively small compared to industrial scale.
Reproducibility
The paper provides clear pseudocode for the generalized greedy search and detailed descriptions of the theoretical constructions. The experimental setup specifies the use of ParlayANN and specific hyperparameters (degree bound, pruning parameter, beam width). While the code for the specific Steiner-point augmentation is not explicitly linked in the text provided, the reliance on the open-source ParlayANN library and standard $k$-means clustering makes the experimental results highly reproducible.
Limitations
The primary limitation is the gap between the theoretical upper bound (which requires a complex, specific construction of Steiner points to simulate LSH) and the experimental lower bound (which uses simple $k$-means centroids). The experiments do not demonstrate that the simple heuristic achieves the theoretical $O(n^{1/(c-1)})$ bound, only that it improves over the baseline. Additionally, the lower bound for the high-dimensional case requires $d=n$, leaving the low-dimensional worst-case complexity (for $d \ll n$) partially open, though a weaker bound is provided. The paper also ignores preprocessing time, focusing solely on query time.
Broader impact
This paper has significant implications for the vector database and search engine community. By proving that standard graph-based methods cannot theoretically match LSH in worst-case high-dimensional settings, it redirects research focus toward hybrid methods or Steiner-point-augmented graphs. The introduction of Steiner points as a mechanism to bridge the gap between empirical graph search and theoretical LSH guarantees offers a new design space for next-generation ANN algorithms. This could lead to more robust search systems with provable performance guarantees, which is critical for safety-critical applications. The paper establishes a fundamental lower bound for graph-based nearest neighbor search and demonstrates that Steiner points can restore sublinear query time guarantees comparable to LSH. It rigorously explains the theoretical limitations of current popular algorithms like HNSW and DiskANN while providing a constructive path forward through graph augmentation, bridging a significant gap between empirical success and theoretical understanding in high-dimensional search.
Author of this paper? Send a correction.