# FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 56 references that are in the map.
- First posted on arXiv 22 Jun 2022.

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

- [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)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Neural Nearest Neighbors Networks](https://mlsanity.com/paper/1810.12575/) (2018)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Security and Privacy on Blockchain](https://mlsanity.com/paper/1903.07602/) (2019)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [Unsupervised Neural Quantization for Compressed-Domain Similarity Search](https://mlsanity.com/paper/1908.03883/) (2019)
- [A Greedy Approach for Budgeted Maximum Inner Product Search](https://mlsanity.com/paper/1610.03317/) (2016)
- [An Introduction to Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2103.00564/) (2021)
- [Learning to Screen for Fast Softmax Inference on Large Vocabulary Neural Networks](https://mlsanity.com/paper/1810.12406/) (2018)
- [Link and code: Fast indexing with graphs and compact regression codes](https://mlsanity.com/paper/1804.09996/) (2018)
- [A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1612.07545/) (2016)
- [Word2Bits - Quantized Word Vectors](https://mlsanity.com/paper/1803.05651/) (2018)
- [A Note on Graph-Based Nearest Neighbor Search](https://mlsanity.com/paper/2012.11083/) (2020)

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

- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Trading Vector Data in Vector Databases](https://mlsanity.com/paper/2511.07139/) (2025)

## Abstract (arXiv)

Approximate K-Nearest Neighbor Search (AKNNS) has now become ubiquitous in modern applications, for example, as a fast search procedure with two tower deep learning models. Graph-based methods for AKNNS in particular have received great attention due to their superior performance. These methods rely on greedy graph search to traverse the data points as embedding vectors in a database. Under this greedy search scheme, we make a key observation: many distance computations do not influence search updates so these computations can be approximated without hurting performance. As a result, we propose FINGER, a fast inference method to achieve efficient graph search. FINGER approximates the distance function by estimating angles between neighboring residual vectors with low-rank bases and distribution matching. The approximated distance can be used to bypass unnecessary computations, which leads to faster searches. Empirically, accelerating a popular graph-based method named HNSW by FINGER is shown to outperform existing graph-based methods by 20%-60% across different benchmark datasets.