Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach
New 'Projection-Augmented Graph' method for vector search achieves up to 5x faster queries than current industry standard HNSW.
A research team led by Kejing Lu and Chuan Xiao has published a new paper introducing Projection-Augmented Graph (PAG), a novel framework designed to revolutionize Approximate Nearest Neighbor Search (ANNS). ANNS is the critical backbone technology for modern AI applications like retrieval-augmented generation (RAG), recommendation systems, and semantic search, where finding the most similar data points (vectors) in massive databases must be done quickly and efficiently. The researchers identified six key demands of modern AI workloads—high query speed, fast indexing, low memory use, scalability to high dimensions, robustness across different retrieval sizes, and support for online data updates—and built PAG to address all of them simultaneously.
PAG's core innovation is the integration of projection techniques directly into a graph-based index structure. This allows the system to perform 'asymmetric comparisons' between exact and approximate distances, guided by statistical tests, which dramatically cuts down on the number of costly, exact distance computations needed during a search. The result is a significant leap in performance. Experimental results on six modern benchmark datasets show that PAG consistently outperforms Hierarchical Navigable Small World (HNSW) graphs, the current industry-standard algorithm used in libraries like FAISS and Weaviate. PAG achieved query-per-second (QPS) rates up to five times faster than HNSW at equivalent recall accuracy, all while offering competitive indexing speed and a manageable memory footprint.
The framework also proves robust as data dimensionality increases—a common challenge for AI models—and naturally supports the insertion of new data without requiring a complete rebuild of the index, a crucial feature for live, updating systems. The team has made the source code publicly available, paving the way for integration into major vector databases and AI infrastructure stacks. This advancement could lead to substantially faster and more efficient RAG pipelines, real-time recommendation engines, and any AI application dependent on lightning-fast similarity search.
- PAG framework achieves up to 5x faster query speeds than the standard HNSW algorithm on six benchmark datasets.
- Unifies projection techniques with a graph index to reduce exact distance computations via asymmetric comparisons.
- Designed to meet six modern AI demands: high speed, fast indexing, low memory, scalability, robustness, and online updates.
Why It Matters
This breakthrough can dramatically speed up RAG systems and AI applications that rely on searching massive vector databases, improving latency and cost.