# Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 56 references that are in the map.
- First posted on arXiv 1 Mar 2026.

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

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers](https://mlsanity.com/paper/2002.10957/) (2020)
- [CoCa: Contrastive Captioners are Image-Text Foundation Models](https://mlsanity.com/paper/2205.01917/) (2022)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [ReasoningBank: Scaling Agent Self-Evolving with Reasoning Memory](https://mlsanity.com/paper/2509.25140/) (2025)
- [MemRL: Self-Evolving Agents via Runtime Reinforcement Learning on Episodic Memory](https://mlsanity.com/paper/2601.03192/) (2026)
- [A Survey on Learning to Hash](https://mlsanity.com/paper/1606.00185/) (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)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [AgentEvolver: Towards Efficient Self-Evolving Agent System](https://mlsanity.com/paper/2511.10395/) (2025)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [INQUIRE: A Natural World Text-to-Image Retrieval Benchmark](https://mlsanity.com/paper/2411.02537/) (2024)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [Similarity search in the blink of an eye with compressed indices](https://mlsanity.com/paper/2304.04759/) (2023)
- [Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2409.09913/) (2024)
- [SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2411.12229/) (2024)
- [Characterizing the Dilemma of Performance and Index Size in Billion-Scale Vector Search and Breaking It with Second-Tier Memory](https://mlsanity.com/paper/2405.03267/) (2024)
- [Probabilistic Routing for Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2402.11354/) (2024)
- [Optimizing Recall or Relevance? A Multi-Task Multi-Head Approach for Item-to-Item Retrieval in Recommendation](https://mlsanity.com/paper/2506.06239/) (2025)
- [Evaluating Hybrid Retrieval Augmented Generation using Dynamic Test Sets: LiveRAG Challenge](https://mlsanity.com/paper/2506.22644/) (2025)
- [Reveal Hidden Pitfalls and Navigate Next Generation of Vector Similarity Search from Task-Centric Views](https://mlsanity.com/paper/2512.12980/) (2025)
- [Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes?](https://mlsanity.com/paper/2409.06464/) (2024)
- [Probabilistic Kernel Function for Fast Angle Testing](https://mlsanity.com/paper/2505.20274/) (2025)
- [Accelerating Graph Indexing for ANNS on Modern CPUs](https://mlsanity.com/paper/2502.18113/) (2025)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper, we outline six critical demands of modern AI applications: high query efficiency, fast indexing, low memory footprint, scalability to high dimensionality, robustness across varying retrieval sizes, and support for online insertions. To satisfy all these demands, we introduce Projection-Augmented Graph (PAG), a new ANNS framework that integrates projection techniques into a graph index. PAG reduces unnecessary exact distance computations through asymmetric comparisons between exact and approximate distances as guided by projection-based statistical tests. Three key components are designed and integrated into the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior queries per second (QPS)-recall performance -- up to 5x faster than HNSW -- while offering fast indexing speed and moderate memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions.