# CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 41 references that are in the map.
- First posted on arXiv 29 Aug 2023.

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

- [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)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [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)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2205.03763/) (2022)
- [Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)](https://mlsanity.com/paper/1610.02455/) (2016)
- [Why do Nearest Neighbor Language Models Work?](https://mlsanity.com/paper/2301.02828/) (2023)
- [Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data](https://mlsanity.com/paper/1810.07355/) (2018)
- [Bringing UMAP Closer to the Speed of Light with GPU Acceleration](https://mlsanity.com/paper/2008.00325/) (2020)
- [Approximate Nearest Neighbor Search under Neural Similarity Metric for Large-Scale Recommendation](https://mlsanity.com/paper/2202.10226/) (2022)
- [GGNN: Graph-based GPU Nearest Neighbor Search](https://mlsanity.com/paper/1912.01059/) (2019)
- [LANNS: A Web-Scale Approximate Nearest Neighbor Lookup System](https://mlsanity.com/paper/2010.09426/) (2020)
- [GPU Semiring Primitives for Sparse Neighborhood Methods](https://mlsanity.com/paper/2104.06357/) (2021)
- [Practice with Graph-based ANN Algorithms on Sparse Data: Chi-square Two-tower model, HNSW, Sign Cauchy Projections](https://mlsanity.com/paper/2306.07607/) (2023)
- [cuSLINK: Single-linkage Agglomerative Clustering on the GPU](https://mlsanity.com/paper/2306.16354/) (2023)
- [View management for lifelong visual maps](https://mlsanity.com/paper/1908.03605/) (2019)

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

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Personal LLM Agents: Insights and Survey about the Capability, Efficiency and Security](https://mlsanity.com/paper/2401.05459/) (2024)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2410.18926/) (2024)
- [REIS: A High-Performance and Energy-Efficient Retrieval System with In-Storage Processing](https://mlsanity.com/paper/2506.16444/) (2025)
- [Retrieval with Learned Similarities](https://mlsanity.com/paper/2407.15462/) (2024)
- [LiNR: Model Based Neural Retrieval on GPUs at LinkedIn](https://mlsanity.com/paper/2407.13218/) (2024)
- [Lossless Compression of Vector IDs for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2501.10479/) (2025)
- [GPU-Accelerated ANNS: Quantized for Speed, Built for Change](https://mlsanity.com/paper/2601.07048/) (2026)
- [LEMUR: Learned Multi-Vector Retrieval](https://mlsanity.com/paper/2601.21853/) (2026)
- [GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions](https://mlsanity.com/paper/2602.16719/) (2026)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [GPU-accelerated Multi-relational Parallel Graph Retrieval for Web-scale Recommendations](https://mlsanity.com/paper/2502.11490/) (2025)
- [All-in-one Graph-based Indexing for Hybrid Search on GPUs](https://mlsanity.com/paper/2511.00855/) (2025)
- [FaTRQ: Tiered Residual Quantization for LLM Vector Search in Far-Memory-Aware ANNS Systems](https://mlsanity.com/paper/2601.09985/) (2026)
- [FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2603.21710/) (2026)
- [NasZip: Software and Hardware Co-Design to Accelerate Approximate Nearest Neighbor Search with DIMM-Based Near-Data Processing](https://mlsanity.com/paper/2605.21952/) (2026)
- [NBQ: Next-Best-Question for Dynamic Profiling](https://mlsanity.com/paper/2606.00809/) (2026)
- [D-NOVA: In-Storage Retrieval Accelerator via Dual-Bound 3D NAND-Optimized Similarity Search with Vector Adaptation](https://mlsanity.com/paper/2607.17538/) (2026)
- [NeuRoute: Logit-Guided Neural Routing for Billion-Scale Vector Search with Sub-Hour Index Construction](https://mlsanity.com/paper/2608.15438/) (2026)
- [Accelerating LLM Inference via Vector Index Based Output Embeddings](https://mlsanity.com/paper/2608.27460/) (2026)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) plays a critical role in various disciplines spanning data mining and artificial intelligence, from information retrieval and computer vision to natural language processing and recommender systems. Data volumes have soared in recent years and the computational cost of an exhaustive exact nearest neighbor search is often prohibitive, necessitating the adoption of approximate techniques. The balanced performance and recall of graph-based approaches have more recently garnered significant attention in ANNS algorithms, however, only a few studies have explored harnessing the power of GPUs and multi-core processors despite the widespread use of massively parallel and general-purpose computing. To bridge this gap, we introduce a novel parallel computing hardware-based proximity graph and search algorithm. By leveraging the high-performance capabilities of modern hardware, our approach achieves remarkable efficiency gains. In particular, our method surpasses existing CPU and GPU-based methods in constructing the proximity graph, demonstrating higher throughput in both large- and small-batch searches while maintaining compatible accuracy. In graph construction time, our method, CAGRA, is 2.2~27x faster than HNSW, which is one of the CPU SOTA implementations. In large-batch query throughput in the 90% to 95% recall range, our method is 33~77x faster than HNSW, and is 3.8~8.8x faster than the SOTA implementations for GPU. For a single query, our method is 3.4~53x faster than HNSW at 95% recall.