# GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 56 references that are in the map.
- First posted on arXiv 10 Feb 2026.

## 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)
- [ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms](https://mlsanity.com/paper/1807.05614/) (2018)
- [HashNet: Deep Learning to Hash by Continuation](https://mlsanity.com/paper/1702.00758/) (2017)
- [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)
- [A Survey on Deep Hashing Methods](https://mlsanity.com/paper/2003.03369/) (2020)
- [Supervised Discrete Hashing](https://mlsanity.com/paper/1503.01557/) (2015)
- [SPANN: Highly-efficient Billion-scale Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2111.08566/) (2021)
- [SPFresh: Incremental In-Place Update for Billion-Scale Vector Search](https://mlsanity.com/paper/2410.14452/) (2024)
- [CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPUs](https://mlsanity.com/paper/2308.15136/) (2023)
- [EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph](https://mlsanity.com/paper/1609.07228/) (2016)
- [BANG: Billion-Scale Approximate Nearest Neighbor Search using a Single GPU](https://mlsanity.com/paper/2401.11324/) (2024)
- [Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art](https://mlsanity.com/paper/2502.05575/) (2025)
- [Breaking the Storage-Compute Bottleneck in Billion-Scale ANNS: A GPU-Driven Asynchronous I/O Framework](https://mlsanity.com/paper/2507.10070/) (2025)
- [PilotANN: Memory-Bounded GPU Acceleration for Vector Search](https://mlsanity.com/paper/2503.21206/) (2025)
- [GRNND: A GPU-Parallel Relative NN-Descent Algorithm for Efficient Approximate Nearest Neighbor Graph Construction](https://mlsanity.com/paper/2510.02774/) (2025)

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

- [StructSAM: Structure- and Spectrum-Preserving Token Merging for Segment Anything Models](https://mlsanity.com/paper/2603.07307/) (2026)

## Abstract (arXiv)

Approximate Nearest Neighbor Search (ANNS) underpins many large-scale data mining and machine learning applications, with efficient retrieval increasingly hinging on GPU acceleration as dataset sizes grow. Although graph-based approaches represent the state of the art in approximate nearest neighbor search, there is a lack of systematic understanding regarding their optimization for modern GPU architectures and their end-to-end effectiveness in practical scenarios. In this work, we present a comprehensive survey and experimental study of GPU-accelerated graph-based vector search algorithms. We establish a detailed taxonomy of GPU optimization strategies and clarify the mapping between algorithmic tasks and hardware execution units within GPUs. Through a thorough evaluation of six leading algorithms on eight large-scale benchmark datasets, we assess both graph index construction and query search performance. Our analysis reveals that distance computation remains the primary computational bottleneck, while data transfer between the host CPU and GPU emerges as the dominant factor influencing real-world latency at large scale. We also highlight key trade-offs in scalability and memory usage across different system designs. Our findings offer clear guidelines for designing scalable and robust GPU-powered approximate nearest neighbor search systems, and provide a comprehensive benchmark for the knowledge discovery and data mining community.