# Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 40 references that are in the map.
- First posted on arXiv 17 Feb 2024.

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

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [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)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [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)
- [Norm-Explicit Quantization: Improving Vector Quantization for Maximum Inner Product Search](https://mlsanity.com/paper/1911.04654/) (2019)
- [Learning to Route in Similarity Graphs](https://mlsanity.com/paper/1905.10987/) (2019)
- [Learning to Hash Robustly, Guaranteed](https://mlsanity.com/paper/2108.05433/) (2021)
- [Automating Nearest Neighbor Search Configuration with Constrained Optimization](https://mlsanity.com/paper/2301.01702/) (2023)
- [Falconn++: A Locality-sensitive Filtering Approach for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.01382/) (2022)
- [FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.11408/) (2022)

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

- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Graph-based Nearest Neighbors with Dynamic Updates via Random Walks](https://mlsanity.com/paper/2512.18060/) (2025)
- [Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach](https://mlsanity.com/paper/2603.06660/) (2026)

## Abstract (arXiv)

Approximate nearest neighbor search (ANNS) in high-dimensional spaces is a pivotal challenge in the field of machine learning. In recent years, graph-based methods have emerged as the superior approach to ANNS, establishing a new state of the art. Although various optimizations for graph-based ANNS have been introduced, they predominantly rely on heuristic methods that lack formal theoretical backing. This paper aims to enhance routing within graph-based ANNS by introducing a method that offers a probabilistic guarantee when exploring a node's neighbors in the graph. We formulate the problem as probabilistic routing and develop two baseline strategies by incorporating locality-sensitive techniques. Subsequently, we introduce PEOs, a novel approach that efficiently identifies which neighbors in the graph should be considered for exact distance calculation, thus significantly improving efficiency in practice. Our experiments demonstrate that equipping PEOs can increase throughput on commonly utilized graph indexes (HNSW and NSSG) by a factor of 1.6 to 2.5, and its efficiency consistently outperforms the leading-edge routing technique by 1.1 to 1.4 times.