Source-linked AI summary
Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art
Ilias Azizi, Karima Echihabi, Themis Palpanas
TL;DR
The paper addresses how graph-based vector search methods should be organized and compared as vector collections grow to billion-scale sizes. It surveys and classifies these methods into five design paradigms, then evaluates twelve state-of-the-art approaches across datasets reaching 1 billion vectors. The study finds that incremental insertion, effective seed selection, and neighborhood diversification are central to scalable and efficient search, while many methods still face indexing scalability limits.
Problem
Growing vector collections make search increasingly challenging, while prior graph-based evaluations did not establish how methods and design choices behave at larger scales.
Method
The paper surveys graph-based vector search, proposes a five-paradigm taxonomy, and experimentally evaluates twelve state-of-the-art methods on datasets reaching 1 billion vectors.
Results
Incremental insertion methods show the best scalability beyond 100GB, while lightweight seed-selection structures and neighborhood diversification improve search on billion-scale datasets.
Takeaways & Limitations
Seed selection and neighborhood diversification are key design choices, with RND and MOND producing the best overall search performance in the experiments.
Takeaways & Limitations
Most graph-based methods face significant indexing scalability challenges, and several methods that perform well on small datasets cannot scale to 100GB and billion-scale collections.
Abstract
from arXiv · showhide
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.
1 Introduction
Vector search is essential for analyzing increasingly large and high-dimensional vector collections, while graph-based approximate methods offer efficient empirical search without quality guarantees. The paper surveys and classifies these methods, then evaluates their design choices and scalability across datasets reaching one billion vectors.
- Vector collections can exceed multiple terabytes and thousands of dimensions, making their analysis challenging across recommendation, retrieval, clustering, classification, and other applications.
- Approximate vector search trades accuracy for efficiency through scans, trees, graphs, inverted indexes, hashing, and hybrid structures.
- Graph-based search structures vectors as proximity graphs and answers queries by traversing from seed nodes using approximate beam search.
- Prior graph-based evaluation used datasets no larger than 1M vectors, whereas this study examines size-dependent behavior and real collections reaching one billion vectors.
- The paper classifies state-of-the-art methods into five paradigms: seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, and divide-and-conquer.
- The evaluation covers twelve state-of-the-art methods on synthetic and real datasets from neuroscience, computer vision, and seismology, including collections reaching 1 billion vectors.
2 Preliminaries
The paper formulates approximate vector search as heuristic nearest-neighbor retrieval over high-dimensional vectors and contrasts graph-based search with other indexing families. Graph methods use proximity structures and beam search to obtain efficient approximate answers, but lack theoretical quality guarantees.
- An exact k-NN query retrieves the k vectors closest to a query under the chosen distance function.
- An ng-approximate k-NN query retrieves k vectors heuristically, without theoretical guarantees about answer quality.
- Vector search methods use scans, trees, graphs, inverted indexes, hashing, or combinations of these structures to trade accuracy against efficiency.
- Graph-based search represents data as a proximity graph and uses initial seeds, an entry node, and greedy beam traversal to produce approximate neighbors.
- Graph-based approaches can require substantial indexing time and memory, yet achieve strong empirical query accuracy and efficiency without query-accuracy guarantees.
3 Graph-Based Vector Search
Graph-based vector search methods organize approximate nearest-neighbor indexing around five paradigms: seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, and divide-and-conquer. The section introduces their graph structures, search process, diversification strategies, and taxonomy.
- The taxonomy classifies state-of-the-art graph-based vector search methods by seed selection, neighborhood propagation, incremental insertion, neighborhood diversification, and divide-and-conquer.It also traces their chronological development and influence relationships.
- 3.1 A Primer: A proximity graph connects data points according to geometric neighborhood requirements, but Delaunay graphs become impractical in high dimensions because they approach full connectivity.State-of-the-art methods therefore use alternative graph structures with beam search for efficient query answering.
- 3.3 Seed Selection: Seed selection chooses initial search nodes, while beam search traverses graph edges to identify approximate nearest neighbors.Seed structures include hierarchical graphs, K-D trees, and other indexes used to warm up candidate answers.
- 3.2 Main Paradigms: Neighborhood propagation refines an existing graph by exchanging neighbor lists, whereas incremental insertion builds the graph one vertex at a time with short and long links.Incremental insertion uses beam search over already inserted vertices and preserves early connections as long-range links.
- 3.6 State-of-the-Art Approaches: NSW incrementally inserts vertices and connects them to selected neighbors, producing a graph whose hop count grows logarithmically with graph size.Its early edges serve as long-range links that support navigation toward nearest neighbors.
- 3.6 State-of-the-Art Approaches: SPTAG combines divide-and-conquer clustering, local exact k-NN graphs, and neighborhood diversification before merging the graphs into one index.Vamana instead starts from a connected random graph and refines neighborhoods using relaxed and standard diversification.
4 Experimental Evaluation
The evaluation studies twelve state-of-the-art graph-based vector search methods across varied datasets, sizes, query workloads, seed-selection strategies, and neighborhood-diversification strategies. It measures search, indexing, memory, and dataset-complexity effects, finding that incremental insertion, neighborhood diversification, and seed-selection choices substantially affect performance and scalability.
- Experimental setup: Local Intrinsic Dimensionality and Local Relative Contrast characterize dataset complexity, with lower LID and higher LRC indicating easier search.LID captures intrinsic dimensionality, while LRC measures nearest-neighbor separability from the rest of the dataset.
- Neighborhood diversification: RND and MOND consistently outperform NoND in search, while the performance gap widens as dataset size increases, especially at high recall.The comparison uses Deep and Sift datasets at 25GB, 100GB, and 1B scales, measuring recall against distance calculations.
- Neighborhood diversification: RND produces the highest pruning ratios and smallest graph sizes, MOND provides moderate pruning, and RRND produces the least pruning and larger graphs.Pruning ratios quantify candidate-list reduction and directly affect graph size and memory usage.
- Seed selection: SN and KS are the most efficient seed-selection strategies for query answering, whereas SF and MD perform worst overall and KD deteriorates on billion-scale datasets.The comparison targets 0.99 accuracy across Deep and Sift datasets from 25GB to 1B vectors.
- Experimental setup: The study evaluates twelve vector search methods on datasets ranging from 1 million to 1 billion vectors, using indexing and query experiments.The evaluation includes synthetic and real-world settings, with queries sampled sequentially and hardness varied for Deep workloads.
- Indexing performance: Incremental-insertion approaches have the lowest indexing time, with ELPIS 2.7x faster than HNSW and 4x faster than NSG on 1M and 25GB datasets.Several methods fail to scale because index construction exceeds time limits or memory requirements on larger datasets.
Disk Footprint
Search-time resource requirements vary across graph-based methods, with Vamana and ELPIS showing the lowest memory footprint and ELPIS requiring the smallest beam width for similar accuracy. At higher recall, ELPIS maintains a performance lead while optimized implementations improve scalability.
- Memory Footprint: Vamana, followed by ELPIS, has the lowest search-time memory footprint.ELPIS’s contiguous search-time storage increases its loaded-memory footprint despite its smaller index size.
- Beam Width: ELPIS requires the smallest beam width to reach similar query accuracy.A high beam width indicates that beam search must visit a wider area.
- Query Performance: At higher recall, HCNNG_Opt is competitive with Vamana and HNSW, while ELPIS maintains a performance lead.The advantage of optimized implementations over their original counterparts diminishes as distance computations dominate.
5 Discussion
The evaluation compares graph-based vector search methods across efficiency, accuracy, tuning, memory, and scalability criteria. It finds that method performance depends on dataset size, workload hardness, graph construction choices, and implementation optimization, while several approaches face large-scale indexing limits.
- Evaluation Criteria: The evaluation assesses search efficiency, accuracy, tunable parameters, indexing efficiency at high recall, memory footprint, and tuning complexity.These criteria span both query processing and index construction.
- Comparative Results: HNSW, VAMANA, and ELPIS provide the best combined search performance and index efficiency.ELPIS and VAMANA require additional parameters to tune, while HNSW does not have those stated extra parameters.
- Unexpected Results: K-random sampling can outperform stacked NSW on smaller and medium-sized datasets.The result contrasts with the reported promise of hierarchical NSW layers on billion-scale datasets.
- Scalability: Most graph-based approaches face significant scalability challenges despite building indexes efficiently on small datasets.SPTAG, NGT, NSG, and SSG show strong search performance on smaller datasets but cannot construct indexes at 100GB and billion-vector scales.
- Neighborhood Diversification: Neighborhood diversification improves search performance, especially as dataset size grows.The discussion also identifies RND and MOND as having the best overall search performance.
- Seed Selection: Seed selection affects both search performance and indexing efficiency.The paper identifies lightweight seed-selection strategies as an open research direction, particularly for large datasets and out-of-distribution queries.
- Optimized Libraries: ParlayNN makes HCNNG_Opt scalable to 1B datasets, whereas the non-optimized version does not scale beyond 25GB.The comparison motivates broader adoption of optimized libraries for large-scale graph search.
6 Conclusions
The paper surveys and classifies state-of-the-art in-memory graph-based approximate vector-search methods, then evaluates their scalability and key design choices experimentally. Its findings identify incremental insertion, seed selection, and neighborhood diversification as important directions for large-scale search.
- The survey organizes graph-based approximate vector-search methods into five design paradigms and traces their chronological development and inter-method influence.
- Experiments on datasets with up to 1B vectors reveal scalability challenges for most methods, while incremental insertion scales best beyond 100GB.
- Light-weight hierarchical structures select better initial search seeds on billion-scale datasets.
- Neighborhood diversification improves query-answering performance, with RND and MOND identified as the best techniques.