On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search

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 previously successful ``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 remained a challenging open problem. In this paper, we prove a strong lower bound that helps explain the lack of progress towards such guarantees. In particular, we show that no standard graph-based method (i.e., any method that runs a variant of greedy search on a flat or hierarchical search 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 \emph{is possible} if we allow for the use of \emph{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}\left(n^{1/c}\right)$. We complement this result with initial experiments exploring how Steiner points can be incorporated into practical graph-based methods, showing modest but meaningful improvements in recall versus query-time tradeoffs.