# Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2025.

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

- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search](https://mlsanity.com/paper/2508.01405/) (2025)
- [Machine learning and high dimensional vector search](https://mlsanity.com/paper/2502.16931/) (2025)
- [TAIJI: MCP-based Multi-Modal Data Analytics on Data Lakes](https://mlsanity.com/paper/2505.11270/) (2025)
- [GPU-Accelerated ANNS: Quantized for Speed, Built for Change](https://mlsanity.com/paper/2601.07048/) (2026)
- [GPU-Accelerated Algorithms for Graph Vector Search: Taxonomy, Empirical Study, and Research Directions](https://mlsanity.com/paper/2602.16719/) (2026)
- [An In-Depth Study of Filter-Agnostic Vector Search on a PostgreSQL Database System: [Experiments and Analysis]](https://mlsanity.com/paper/2603.23710/) (2026)
- [Mandol: An Agglomerative Agent Memory System for Long-Term Conversations](https://mlsanity.com/paper/2606.29778/) (2026)
- [PLASMA: A Layout-Aware Benchmark Reveals Memory Layout Matters for Graph-based ANNS on GPU](https://mlsanity.com/paper/2508.15436/) (2025)
- [Adaptive Prefiltering for High-Dimensional Similarity Search: A Frequency-Aware Approach](https://mlsanity.com/paper/2602.22214/) (2025)
- [FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2603.21710/) (2026)

## Abstract (arXiv)

Vector data is prevalent across business and scientific applications, and its popularity is growing with the proliferation of learned embeddings. Vector data collections often reach billions of vectors with thousands of dimensions, thus, increasing the complexity of their analysis. Vector search is the backbone of many critical analytical tasks, and graph-based methods have become the best choice for analytical tasks that do not require guarantees on the quality of the answers. We briefly survey in-memory graph-based vector search, outline the chronology of the different methods and classify them according to five main design paradigms: seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, and divide-and-conquer. We conduct an exhaustive experimental evaluation of twelve state-of-the-art methods on seven real data collections, with sizes up to 1 billion vectors. We share key insights about the strengths and limitations of these methods; e.g., the best approaches are typically based on incremental insertion and neighborhood diversification, and the choice of the base graph can hurt scalability. Finally, we discuss open research directions, such as the importance of devising more sophisticated data-adaptive seed selection and diversification strategies.