Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization
Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, Zhiming Ma · 2025
Read Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization by Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, Zhiming Ma (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15531.txt.
Introduction
Xinran Ma leads a team that speeds up nearest neighbor search on huge vector sets. Graph based search is fast and accurate at billion scale. One popular graph trims links by a rule set by a parameter that is costly to tune. The team wanted theory to replace that trial and error.
They model the trimming as a fair game process that evolves by chance. With that model they bound the graph's largest link count and its expected search path length. From the bounds they derive a closed form rule for the best trim value. On real data sets, their tuned graph builds far faster on average, with peaks well above that. Search quality holds or improves.
Catalog record
| CREATOR | Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, Zhiming Ma |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-15531
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Graph-Based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis and Optimization Xinran Ma, Zhaoqi Zhou, Chuan Zhou, Qi Meng, Zaijiu Shang, Guoliang Li, Zhiming Ma Abstract Graph-based approaches to approximate nearest neighbor search (ANNS) have achieved remarkable success in enabling fast, high-recall retrieval on billion-scale vector datasets. Among them, the Sparse Neighborhood Graph (SNG) has emerged as a widely adopted graph structure due to its superior search performance. However, the theoretical understanding of SNG remains limited, leading to reliance on heuristic-based and often suboptimal truncation strategies. In this work, we aim to bridge the gap between theory and practice by providing formal guarantees for graph-based ANNS methods and proposing principled optimization strategies for the truncation parameter. By characterizing the index construction process through martingale-based analysis, we show that the degree of the index graph is O ( n 2 / 3 + ϵ ) O(n^{2/3+\epsilon}) , where ϵ \epsilon is an arbitrarily small constant. Furthermore, we prove that the expected search path length during query processing is O ( log n ) O(\log n) . Based on these theoretical insights, we introduce a novel and principled method for selecting the truncation parameter R R in SNG. Experimental results demonstrate that our method achieves comparable or superior performance in terms of query latency and Recall@10 compared to commonly used binary search heuristics, while yielding 2x to 9x speedups in overall index construction. 1 Introduction NNS-ANNS Problems. Nearest neighbor search (NNS) is a fundamental problem in computer science KNN1 ; KNN2 and has become a fundamental research topic across various fields such as information retrieval IRTV ; image , machine learning ICDEML ; RAG and data mining Dataminingsig2017 . Formally, given a dataset P=\{p_{1},\ldots,p_{n}\}\subset\mathbb{R}^{d} of cardinality n and query point q\in\mathbb{R}^{d} , the NNS problem requires finding the k closest points to q under an appropriate distance metric \|\cdot\| . The computational complexity of exact NNS grows prohibitively with both dimensionality d due to the well-documented curse of dimensionality Curse and the expanding dataset size n . This fundamental limitation has motivated the development of Approximate Nearest Neighbor Search (ANNS) algorithms, which achieve significant efficiency improvements while sacrificing minimal accuracy. Graph-Based ANNS. Modern ANNS approaches achieve remarkable efficiency-accuracy tradeoffs and can be categorized into four categories: tree-based approaches tree1 ; KD-TREE , hashing-based approaches LSHarshing ; hash2 ; hash3 ; hash4 , vector quantization-based approaches quantti1 ; RabitQ , and graph-based approaches Graph4 ; Graph3 ; Graph1 ; UNI1 . Among these, graph-based approaches have demonstrated particular success in practical applications Graph2024VLDB ; Graph1 , owing to their ability to capture local neighborhood structures. The graph-based ANNS framework operates through two sequential phases: an index construction phase that builds a graph preserving neighborhood relationships, followed by an query processing phase that employs the GreedySearch algorithm NSG19 ; NEURIPS2019 ; HNSW2020 to iteratively traverse the graph along paths until convergence to the query point. Numerous graph construction strategies have been proposed, each differing in how neighbors are selected and edges are formed. Theoretical Limitations. Despite their empirical success, graph-based ANNS methods remain theoretically underexplored, primarily due to the stochastic nature of high-dimensional data and the combinatorial complexity of graph construction. Existing theoretical studies often rely on simplified assumptions and focus on analyzing key structural properties such as degree, query complexity, and search path length. For instance, sublinear query complexity has been established for threshold-based nearest neighbor graphs 1 1 1 A threshold-based nearest neighbor graph connects two nodes if the distance between them is below a specified threshold value. under spherical data models ICML2020 , while navigable graphs 2 2 2 A graph is navigable if the search algorithm can find a path from any starting vertex to any target vertex in the dataset. constructed under a binomial distribution exhibit an average degree of O(n^{\beta}) for \beta<1/2 Haya24 , although such assumptions are often unrealistic in practical settings. The Monotonic Search Network (MSNET) 3 3 3 The Monotonic Search Network is a navigable graph where the path between any two nodes follows a monotonic trajectory. is known to achieve a logarithmic search path length NSG19 . The Sparse Neighborhood Graph (SNG) Arya93 is a variant designed to further reduce graph density while preserving search quality in practice. It has been broadly adopted in modern ANNS systems, including DiskANN NEURIPS2019 , HNSW HNSW2020 , and NSG NSG19 . The worst-case search analysis of SNG indyk2023worst relies on dataset aspect ratios 4 4 4 The aspect ratio is the ratio of the maximum to minimum distance between any pair of points in the dataset. , yielding bounds that are less interpretable compared to those based on cardinality. Practical Limitations and Parameter Tuning. To reduce index construction time, a common practice in SNG construction is to impose a maximum degree of node through a truncation parameter R . However, existing methods typically rely on parameter sweeping NEURIPS2019 , most commonly implemented as a binary search guided by the downstream search performance of the constructed graph. This tuning process for R is computationally expensive, highlighting the need for a theoretically grounded approach to its selection—one that ensures high search performance while reducing tuning overhead. 1.1 Main Results To address the dual challenges of theoretical understanding and practical parameter tuning in SNG-based approximate nearest neighbor search, this study develops a rigorous theoretical framework for graph construction under realistic random data assumptions, with a focus on the SNG. Building on this foundation, we further derive a marginal optimal principle-based strategy for parameter optimization. Specifically, we provide tighter bounds for both the indexing and query processes and offer an analytical expression for the key graph truncation parameter in SNG, enabling direct performance gains during index construction. Degree Bound of the SNG Graph. We establish a tighter degree bound for SNG, improving upon the prior rough bound of O(n) from NEURIPS2019 : Theorem 1 . Given a dataset P of n points in d -dimensional space, with probability 1 , the maximum out-degree in the constructed SNG is bounded by O(n^{2/3+\epsilon}) for any small constant \epsilon>0 . This result highlights the sparsity of the graph and the effectiveness of pruning during index construction. It implies that the SNG remains sparser than a complete graph. The proof idea and sketch are provided in Section 3 , and the full proof is deferred to Appendix C.4 . Search Path Length on SNG. Building on the degree bound, we further demonstrate that the expected search path length in SNG is logarithmic in the dataset size: Theorem 2 . Given a dataset P with n points in d -dimensional space, with probability 1 , the SNG search converges in O(\log n) steps. The sketch of the proof is provided in Section 4 , and the full argument appears in Appendix C.5 . Optimizing Parameter R. Based on these findings, we analyze the graph construction complexity under the truncated setting and derive an analytical expression for the optimal truncation parameter R , as presented in Section 5.2 . This theoretically grounded formulation enables principled and efficient parameter selection, removing the need for manual tuning. Empirically, in the search phase, our optimized R achieves comparable or improved latency and Recall @ 10 compared to traditional