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

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 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/.

Modern AI systems often need to find useful information from huge collections of documents, images, products, or past user interactions. For example, a chatbot may need to look up relevant documents before answering a question, or an image search system may need to find similar pictures from millions of candidates. This search step must be fast, accurate, and able to handle new data as it arrives, but existing methods often struggle to satisfy all of these needs at the same time. We propose a new search method that organizes data as a network and uses lightweight signals to decide which comparisons are worth doing carefully. Instead of comparing every candidate in full detail, the method first makes a quick estimate and then spends the expensive computation only on promising cases. The same idea also helps build the search structure faster and keep it useful when new items are inserted. In experiments on modern text, image, and multimodal data, our method finds relevant results faster than widely used alternatives while maintaining high accuracy. It also builds the search structure quickly and uses a moderate amount of memory. These properties make it useful for practical AI applications that need fast and reliable search over large and frequently updated data collections.