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

Kejing Lu; Zhenpeng Pan; Jianbin Qin; Yoshiharu Ishikawa; Chuan Xiao

cs.IRMar 1, 2026

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

Authors: Kejing Lu, Zhenpeng Pan, Jianbin Qin, Yoshiharu Ishikawa, Chuan Xiao

Organizations: University of Yamanashi · Beijing Institute of Technology, Zhuhai · Shenzhen University · Nagoya University ·

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 integrated into the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior queries per second (QPS)-recall performance -- up to 5x 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.

Figures & tables

	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	✓	✓	✓	✓	✓	✗	✓	✓	✓

Table 1: Summary of empirical performance comparison of notable ANNS solvers, HNSW ( Malkov and Yashunin, 2020 ) , Vamana (in-memory DiskANN ( Subramanya et al., 2019 ) ), IVFPQFS (fast scan IVFPQ ( Jégou et al., 2011 ) ), ScaNN ( Guo et al., 2020a ) , RaBitQ+ ( Gao et al., 2025 ) , SymQG ( Gou et al., 2025b ) , HNSW+KS2 ( Lu et al., 2025 ) , 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 (✓/✗).

Figure 1: An overview of PAG. In this example,

\bm{u}

has 7 out-neighbors

\{\bm{w_{i}}\}^{7}_{i=1}

. Let

\{\bm{e_{i}}\}^{7}_{i=1}

denote the edges between

\bm{u}

and

\{\bm{w_{i}}\}^{7}_{i=1}

, which are sent to PRT, where the threshold is determined by

\bm{z_{\max}}

. As a result, only

\bm{w_{3}}

and

\bm{w_{5}}

pass PRT, and their exact distances to

\bm{v}

are computed. By distance comparison, node

\bm{w_{5}}

is identified as a false positive, not added to

W

, and thus sent to

R_{F}

. Node

\bm{w_{3}}

is inserted into

W

, causing

\bm{z_{\max}}

to be ejected from

W

and sent to

R_{T}

. The two rings

R_{F}

and

R_{T}

are merged and refilled into

W

. On the other route, by a left shift, the signs of both

\bm{w_{3}}

and

\bm{w_{5}}

are reversed, and all signs become negative, indicating that no witness is detected by PES. Consequently,

\vec{\bm{uv}}

is treated as a candidate edge and added to the PES set.

Figure 2: Illustration of PES (left: the role of PES; right: geometric illustration). Let

\bm{v}

be the node to be inserted. The four green nodes are out-neighbors of

\bm{v}

. Without PES, we can obtain only a single in-neighbor via RobustPrune. By taking all other visited nodes (the blue ones) into account, we apply PES, followed by RobustPrune. As such, we can identify three additional promising in-neighbors, thereby strengthening the connectivity of the neighborhood of

\bm{v}

Name/Source	Dataset Size	Query Size	Dim.	OOD	Type	Embedding Model	Distance Measure
Modern Datasets
DBpedia1536	999,000	1,000	1,536	No	Text	text-embedding-3-large ( OpenAI, 2024 )	Euclidean
DBpedia3072	999,000	1,000	3,072	No	Text	text-embedding-3-large ( OpenAI, 2024 )	Euclidean
WoltFood	1,719,611	1,000	512	No	Image	clip-ViT-B-32 ( Radford et al., 2021 )	Euclidean
DataCompDr	12,779,520	1,000	1,536	Yes	Text-to-Image	coca_ViT-L-14 ( Yu et al., 2022 )	Euclidean
AmazonBooks	15,928,208	1,000	384	No	Text	all-MiniLM-L12-v2 ( Wang et al., 2020 )	Euclidean

Table 2: Dataset statistics.

Figure 3: QPS-recall,

K=100

. SymQG runs out of memory on MajorTOM. Recall is plotted on a logarithmic scale.

Figure 4: Indexing time and peak memory usage. SymQG runs out of memory on MajorTOM.

Figure 5: QPS-recall of query workloads with online insertions,

K=100

Figure 6: Ablation study, QPS-recall. PRT only is the re-implementation of KS2 in PAG.

Figure 7: Ablation study, indexing time. PRT only is the re-implementation of KS2 in PAG.

Appendix figures & tables22 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
$\mathcal{D}$	Dataset of vectors
$d$	Dimension of vectors
$n$	Dataset size
$\bm{q}$	Query vector
$K$	Retrieval size
$\bm{v}$	Node to be inserted to a graph index

Appendix

Table 3: Frequently used notations.

Figure 8: DataCompDr data (sampled 50,000 vectors) and query (1,000 vectors) distributions.

Figure 9: QPS-recall of PAG-Base under varying space partition size

L

K=100

M

and

efC

values are given in Table 4 , PAG-Base.

Figure 10: Indexing time and peak memory usage of PAG-Base under varying space partition size

L

M

and

efC

values are given in Table 4 , PAG-Base.

Figure 11: QPS-recall of PAG-Base under varying

(M,efC)

K=100

L

values are given in Table 4 , PAG-Base.

Figure 12: Indexing time and peak memory usage of PAG-Base under varying

(M,efC)

L

values are given in Table 4 , PAG-Base.

Modern Datasets
Dataset	PAG-Base $(efC,M,L)$	PAG-Lite $(efC,M,L)$
DBpedia1536	$(1000,32,128)$	$(100,32,128)$
DBpedia3072	$(1000,32,64)$	$(100,32,64)$
WoltFood	$(2000,128,64)$	$(100,64,32)$
DataCompDr	$(1000,32,64)$	$(100,32,64)$
AmazonBooks	$(2000,64,64)$	$(100,64,32)$

Appendix

Table 4: PAG parameter settings.

Figure 13: QPS-recall,

K=10

Figure 14: QPS-recall,

K=1000

Figure 15: QPS-recall comparison of PAG-Base and SymQG under varying retrieval size

K

Figure 16: QPS-recall on additional legacy datasets,

K=10

Figure 17: QPS-recall on additional legacy datasets,

K=100

Figure 18: QPS-recall on additional legacy datasets,

K=1000

Figure 19: Indexing time and peak memory usage on additional legacy datasets.

Figure 20: Peak memory usage breakdown in the indexing phase, modern datasets.

Figure 21: Peak memory usage breakdown in the indexing phase, legacy datasets.

Figure 22: Peak memory usage breakdown in the searching phase, modern datasets.

Figure 23: Peak memory usage breakdown in the searching phase, legacy datasets.

Figure 24: QPS-recall comparison of PAG-Base, HNSW, and Vamana under the same sets of

efC

L_{\mathrm{vam}}

Figure 25: Indexing time comparison of PAG-Base, HNSW, and Vamana under the same sets of

efC

L_{\mathrm{vam}}

Figure 26: Peak memory usage breakdown of PAG-Base, HNSW, and Vamana under the same sets of

efC

L_{\mathrm{vam}}

, indexing phase.

Figure 27: Peak memory usage breakdown of PAG-Base, HNSW, and Vamana under the same sets of

efC

L_{\mathrm{vam}}

, searching phase.

Approximate Nearest Neighbor Search

Approximate nearest neighbor search finds close vectors without exhaustive comparisons, enabling scalable retrieval in high-dimensional datasets.

See all 42 papers

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search
Jul 20, 2026Zheqi Shen, Jingbo Su, Zijin Wan +2Exact Nearest Neighbor Search Graph-Based Retrieval
UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA
Panorama: Fast-Track Nearest Neighbors
Oct 1, 2025Vansh Ramani, Alexis Schlomer, Akash Nayar +3Product Quantization Approximate Nearest Neighbor Search
IIT Delhi & CMU & UCPH · Carnegie Mellon University · Indian Institute of Technology Delhi +1
Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning
Sep 28, 2026Fangzhou Wu, Haike Xu, Sandeep SilwalSemantic Search Graph-Based Retrieval
University of Wisconsin–Madison · MIT

Jul 20, 2026J/K move · Enter open · S save

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

Zheqi Shen, Jingbo Su, Zijin Wan, Yan Gu+1

UC Riverside Riverside CA, USA · W&M Williamsburg VA, USA

Exact Nearest Neighbor Search Graph-Based Retrieval Approximate Nearest Neighbor Search

Open paper AskPDF arXiv

Approximate Nearest Neighbor Search (ANNS) plays a pivotal role in modern deep learning pipelines. Recently, many ANNS systems have been proposed to either provide broad functionality or reach high performance. However, it is yet difficult to achieve both with minimal programming efforts. We propose ANNLib to address the gap. ANNLib is a library that provides a programming framework for achieving high performance and flexible functionality in ANNS systems, based on popular graph-based ANNS algorithms. We carefully decouple and independently optimize both the algorithm and the data structure components of an ANNS system. In addition, we integrate state-of-the-art algorithms and data structures into ANNLib as modules, along with our new designs. Users can choose combinations of components to implement sophisticated settings with high performance, such as filter search, fully dynamic updates, and historical queries on snapshots. Our experiments show that our new solution provides a simple interface for various applications and achieves comparable or even better performance than previous work, specifically for each application.

Abstract

Approximate Nearest Neighbor Search

Explore similar work

ANNLib: A Development Framework for Efficient Approximate Nearest Neighbor Search

Panorama: Fast-Track Nearest Neighbors

Better Nearest Neighbor Graph Indices via (Efficient) LLM-Guided Pruning