Standard graph searches face a worst-case speed limit
Standard graph methods could not guarantee search times growing more slowly than the dataset’s size, even with arbitrarily loose approximations.
Edited by Boris Djordjevic · Paperfoot
The paper proved a worst-case limit for standard graph-based methods for finding approximate nearest neighbors: data points close to a query, measured by straight-line distance. These methods searched a network of linked points using greedy search, choosing a promising next step locally, through either a single layer or a hierarchy of layers.
No such method could guarantee search times that grew more slowly than the number of data points, even with an arbitrarily loose approximation to the closest point. The authors also proved that such guarantees became possible when the graph included Steiner points: extra locations beyond the data points being searched. Their bounds were comparable to those for locality-sensitive hashing, an established method for finding similar items. They complemented the proofs with initial experiments exploring how to add these points to practical graph-based methods.
Why it matters
The proofs established a limit on what standard graph-based search can guarantee, while showing that adding extra search points can change that limit. They did not establish how much those extra points help in practice.
Caveats
The limit concerned worst-case searches using straight-line distance, not a measured slowdown in practical systems. The abstract reported no numerical results from the initial practical experiments; the paper is a preprint.
In this paper
graph-based nearest neighbor search
- Methods
- graph-based search with Steiner points (this paper)HNSW (baseline)DiskANN (baseline)NSG (baseline)Locality Sensitive Hashing (LSH) (baseline)
What it shows
- No standard graph-based method running 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.
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.
Abstract
- Graph-based search with Steiner points can achieve sublinear query time, solving c-approximate nearest neighbor search in Euclidean space with query time O(n^(1/(c-1))).
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 O(n^(1/(c-1))).
Abstract
Quoted word for word from the abstract on arXiv.
The paper
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
arXiv, Oct 28, 2026, Open access, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.38133
arXiv:2610.38133v1 in cs.DS, also cs.LG
Cite as BibTeX
@misc{daliri2026worstcase,
title = {On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search},
author = {Daliri, Majid and Daneshvaramoli, Mohammadreza and Dutta, Purna and Liberty, Edo and Musco, Cameron and Musco, Christopher and Suel, Torsten},
year = {2026},
eprint = {2610.38133},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arxiv.2610.38133},
url = {https://arxiv.org/abs/2610.38133}
}