Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

Kejing Lu, Zhenpeng Pan, Jianbin Qin, Yoshiharu Ishikawa, Chuan Xiao · 2026

Read Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach by Kejing Lu, Zhenpeng Pan, Jianbin Qin, Yoshiharu Ishikawa, Chuan Xiao (2026) 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-2603-06660.txt.

Introduction

Lu and team outline six demands of approximate nearest neighbor search: query efficiency, fast indexing, low memory, high-dimensional reach, retrieval-size robustness, and online-insertion support. They bring Projection-Augmented Graph (PAG), fitting projection tricks into a graph index to cut exact distance maths via one-sided comparisons guided by projection-based statistical tests. On six modern datasets, PAG beats HNSW on queries-per-second-recall by up to 5x. It offers fast setup, moderate memory, toughness as size and fetch size grow, and online-add support.

Catalog record

CREATORKejing Lu, Zhenpeng Pan, Jianbin Qin, Yoshiharu Ishikawa, Chuan Xiao
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68808
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.06660

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach Kejing Lu, Zhenpeng Pan, Jianbin Qin, Yoshiharu Ishikawa, Chuan Xiao Abstract Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper, we outline six critical demands of modern AI applications: high query efficiency, fast indexing, low memory footprint, scalability to high dimensionality, robustness across varying retrieval sizes, and support for online insertions. To satisfy all these demands, we introduce Projection-Augmented Graph (PAG), a new ANNS framework that integrates projection techniques into a graph index. PAG reduces unnecessary exact distance computations through asymmetric comparisons between exact and approximate distances as guided by projection-based statistical tests. Three key components are designed and unified to the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior query per second (QPS)-recall performance—up to 5 × \times faster than HNSW—while offering fast indexing speed and moderate memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions. Our source code is available at: https://github.com/KejingLu-810/PAG/ . 1 Introduction Given a dataset \mathcal{D}\subset\mathbb{R}^{d} with size n and a query \bm{q}\in\mathbb{R}^{d} , Approximate Nearest Neighbor Search (ANNS) aims to find K approximate nearest neighbors of \bm{q} as accurately and efficiently as possible. Due to its crucial role in many applications such as image search, recommender systems, and retrieval-augmented-generation (RAG), we have witnessed the rapid proliferation of ANNS solvers. Whereas the ANN-Benchmarks ( 8 ) has been developed to compare these methods in a unified environment, many datasets in the ANN-Benchmarks, as pointed out by 13 , are derived from outdated models such as SIFT and GIST, which are image descriptors developed more than 20 years ago ( 32 ; 39 ) . In addition, its evaluation metric is limited to query per second (QPS)-recall under K=10 . Seeing the fast development of AI technology, we argue that a well-designed ANNS solver should perform well on modern datasets, and beyond (D1) QPS-recall performance, several demands must also be considered: (D2) indexing time , for which graph indexes such as HNSW ( 37 ) are often criticized ( 31 ; 30 ) , compromising their use in applications that require instant deployment; (D3) memory footprint , where moderate and adjustable consumption, mostly caused by the index size, is desired for the memory vs accuracy trade-off ( 14 ; 55 ) ; (D4) scalability to high dimensionality , as motivated by the increasing dimensionality of modern embedding models such as CLIP ( 49 ) 1 1 1 Despite the availability of dimensionality reduction techniques, 60 proved that for embedding-based retrieval with dimensionality d , there exists a dataset size n (e.g., n\approx 4M for d=1024 ) beyond which it is theoretically impossible to represent all possible top-2 document combinations, showcasing the necessity for higher dimensionality on large datasets. ; (D5) robustness against the retrieval size K , due to the needs in various applications (e.g., K is typically 10 for RAG ( 15 ; 28 ) but can be up to hundreds in image retrieval ( 54 ) and thousands in recommender systems ( 66 ) ); (D6) support of online insertions , which is essential for emergent applications such as self-evolving agents that continually accumulate and reuse experience through interaction ( 42 ; 65 ; 67 ) . Graph-Based Quantization-Based QG PG PAG Criteria HNSW Vamana IVFPQFS 1 ScaNN 1 RaBitQ+ SymQG HNSW+KS2 PAG-Base PAG-Lite D1. QPS-recall Tier-2 Tier-2 Tier-1 Tier-1 Tier-1 Tier-3 Tier-3 Tier-4 Tier-3 D2. Indexing time Tier-1 Tier-1 Tier-3 Tier-3 Tier-3 Tier-2 Tier-1 Tier-2 Tier-4 D3. Memory footprint 2 Tier-3 Tier-3 Tier-4 Tier-4 Tier-4 Tier-1 Tier-2 Tier-3 Tier-4 D4. High-dim. scalability ✓ ✓ ✓ ✓ ✓ ✗ ✓ ✓ ✓ D5. Retrieval size robustness ✓ ✓ ✓ ✓ ✓ ✗ ✓ ✓ ✓ D6. Online insertion support 3 ✓ ✓ ✓ ✓ ✓ ✗ ✗ ✓ ✓ 1 Reranking is enabled for IVFPQFS and ScaNN. 2 Memory footprint for searching, rather than indexing, is compared. 3 For any streaming workload Q composed of search and insertion queries, we say an algorithm supports online insertion, if the amortized cost of processing a query in Q is O(1) times the cost of a search. In other words, the index can be incrementally updated with minimal cost. See Sec. 4.3 for the analysis of PAG. Table 1: Summary of empirical performance comparison of notable ANNS solvers, HNSW ( 37 ) , Vamana (in-memory DiskANN ( 51 ) ), IVFPQFS (fast scan IVFPQ ( 26 ) ), ScaNN ( 23 ) , RaBitQ+ ( 18 ) , SymQG ( 22 ) , HNSW+KS2 ( 35 ) , and our solutions PAG-Base (for high QPS) and PAG-Lite (for fast indexing and small index size). Detailed results are available in Sec. 5.2 . The evaluation of D1 – D3 is clustered into tiers, where Tier-4 is the best. D4 – D6 are evaluated in yes/no (✓/✗). 1.1 Prior Works We review representative ANNS solvers based on D1 – D6. More discussions on literature can be found in Appendix C . Graph-Based Methods. These methods construct a similarity graph connecting nearby vectors and hop towards the neighborhood of \bm{q} . Notable methods are HNSW ( 37 ) , NSG ( 17 ) , and DiskANN ( 51 ) . They are generally competitive in QPS-recall but slow in building indexes. Quantization-Based Methods. These methods compress vectors and rank them using approximate (i.e., quantized) distances to \bm{q} in pursuit of efficiency. Representative methods are IVFPQ ( 26 ) and ScaNN ( 23 ) . They are fast in building indexes and save memory, but their QPS-recall is generally inferior to graph-based methods. Projection-Based Methods. These methods use random (e.g., E2LSH ( 3 ) , Falconn ( 2 ) , and CEOs ( 45 ) ) or data-dependent (e.g., learning to hash ( 57 ) ) projections of the original vectors for indexing. Although many of them enjoy theoretical guarantees, they are less competitive than graph- and quantization-based methods in QPS-recall performance, hence becoming less popular in modern top- K ANNS. Tree-Based Methods. They utilize tree indexes. Notable methods include k-d tree ( 7 ) , cover tree ( 10 ) , and Annoy ( 9 ) . Like projection-based methods, they are less widely used for modern ANNS due to limited QPS-recall performance. As discussed above, graph-based methods are good at QPS-recall. But they compute exact distances between vectors, which is computationally costly. To address this weakness, recent advancements attempt to integrate other techniques, in particular, quantization or projection, into graphs. Quantized Graph (QG) Methods. They construct a similarity graph based on quantized vectors instead of the original ones, thereby replacing exact distances with approximate values. Representative methods are NGT-QG ( 63 ) , LVQ ( 1 ) , and SymphonyQG ( 22 ) . QG methods can achieve very high QPS-recall performance, yet they are sensitive to the data distribution and many of them do not perform very well in D3 – D6. Projection + Graph (PG) Methods. Unlike QG, they operate on original vectors and reduce unnecessary exact

Read the complete text