# Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits

arXiv: https://arxiv.org/abs/2405.18680 · HTML: https://mlsanity.com/paper/2405.18680/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 29 May 2024.

## Builds on (most cited first, 8 of 8)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [Graph-based time-space trade-offs for approximate near neighbors](https://mlsanity.com/paper/1712.03158/) (2017)
- [Greedy Heuristics and Linear Relaxations for the Random Hitting Set Problem](https://mlsanity.com/paper/2305.05565/) (2023)

## Built on by (most cited first, 7 of 7)

- [Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2505.15636/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search](https://mlsanity.com/paper/2601.01930/) (2026)
- [Graph-Based Nearest-Neighbor Search without the Spread](https://mlsanity.com/paper/2602.06633/) (2026)
- [EGA: Adapting Frozen Encoders for Vector Search with Bounded Out-of-Distribution Degradation](https://mlsanity.com/paper/2605.05674/) (2026)
- [Learning Partition Trees for Nearest Neighbor Search](https://mlsanity.com/paper/2607.09909/) (2026)
- [A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search](https://mlsanity.com/paper/2609.02143/) (2026)

## Abstract (arXiv)

There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to a given distance function. The complete graph is navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree O(√n log n ) for any set of n points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in O(log n) dimensions, a random point set has no navigable graph with average degree O(nα) for any α < 1/2. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use to show that the near-neighborhoods of a set of random points do not overlap significantly, forcing any navigable graph to have many edges.