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 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×faster than HNSW---while offering fast indexing speed and small memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions. Our source code is available at: https://anonymous.4open.science/r/PAG-A73D/ .
BibTeX
@inproceedings{
lu2026approximate,
title={Approximate Nearest Neighbor Search for Modern {AI}: A Projection-Augmented Graph Approach},
author={Kejing Lu and Zhenpeng Pan and Yoshiharu Ishikawa and Chuan Xiao and Jianbin Qin},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=Zg6yWOIecu}
}