SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search
Abstract
Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance in terms of the time-accuracy trade-off. However, they face performance bottlenecks due to the random memory accesses caused by the searching process on the graph indices and the costs of computing exact distances to guide the searching process. To relieve the bottlenecks, a recent method named NGT-QG makes an attempt by integrating quantization and graph. It (1) replicates and stores the quantization codes of a vertex's neighbors compactly so that they can be accessed sequentially, and (2) uses a SIMD-based implementation named FastScan to efficiently estimate distances based on the quantization codes in batch for guiding the searching process. While NGT-QG achieves promising improvements over the vanilla graph-based methods, it has not fully unleashed the potential of integrating quantization and graph. For instance, it entails a re-ranking step to compute exact distances at the end, which introduces extra random memory accesses; its graph structure is not jointly designed considering the in-batch nature of FastScan, which causes wastes of computation in searching. In this work, following NGT-QG, we present a new method named SymphonyQG, which achieves more symphonious integration of quantization and graph (e.g., it avoids the explicit re-ranking step and refines the graph structure to be more aligned with FastScan). Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off: at 95% recall, SymphonyQG achieves 1.5x-4.5x QPS compared with the most competitive baselines and achieves 3.5x-17x QPS compared with the classical library HNSWlib across all tested datasets. At the same time, its indexing is at least 8x faster than NGT-QG.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
24 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and Search cites Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search
- Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
- DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
- DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search cites Accelerating Large-Scale Inference with Anisotropic Vector Quantization
- DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor Search cites Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- A Topology-Aware Localized Update Strategy for Graph-Based ANN Index cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
- A Topology-Aware Localized Update Strategy for Graph-Based ANN Index cites Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal cites A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search
- Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal cites Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal cites ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
Cited by top-tier papers24
- DARTH: Declarative Recall Through Early Termination for Approximate Nearest Neighbor SearchManos Chatzakis, Yannis Papakonstantinou, Themis PalpanasSIGMOD 2026 · 10 citations
- A Topology-Aware Localized Update Strategy for Graph-Based ANN IndexSong Yu, Shengyuan Lin, Shufeng Gong, Yongqing Xie et al.VLDB 2026 · 10 citations
- Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization TraversalWenqi Jiang, Hang Hu, Torsten Hoefler, Gustavo AlonsoVLDB 2025 · 10 citations
- GPU-Native Approximate Nearest Neighbor Search with IVF-RaBitQ: Fast Index Build and SearchJifan Shi, Jianyang Gao, James Xia, Tamas B. Fehér et al.VLDB 2026 · 7 citations
- Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor SearchZhonggen Li, Xiangyu Ke, Yifan Zhu, Bocheng Yu et al.SIGMOD 2026 · 5 citations
Builds on15
- Retrieval-Augmented Generation for Knowledge-Intensive NLP TasksPatrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni et al.NeurIPS 2020 · 19,162 citations
- ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERTOmar Khattab, Matei ZahariaSIGIR 2020 · 1,246 citations
- Accelerating Large-Scale Inference with Anisotropic Vector QuantizationRuiqi Guo, Philip Sun, Erik Lindgren, Quan Geng et al.ICML 2020 · 539 citations
- A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor SearchMengzhao Wang, Xiaoliang Xu, Qiang Yue, Yuxiang WangVLDB 2021 · 354 citations
- Pre-training Tasks for Embedding-based Large-scale RetrievalWei-Cheng Chang, Felix X. Yu, Yin-Wen Chang, Yiming Yang et al.ICLR 2020 · 325 citations
Related papers
- SONG: Approximate Nearest Neighbor Search on GPUWeijie Zhao, Shulong Tan, Ping LiICDE 2020 · 103 citations
- Accelerating Graph Indexing for ANNS on Modern CPUsMengzhao Wang, Haotian Wu, Xiangyu Ke, Yunjun Gao et al.SIGMOD 2025 · 6 citations
- HM-ANN: Efficient Billion-Point Nearest Neighbor Search on Heterogeneous MemoryJie Ren, Minjia Zhang, Dong LiNeurIPS 2020 · 136 citations
- FGIM: a Fast Graph-based Indexes Merging Framework for Approximate Nearest Neighbor SearchZekai Wu, Jiabao Jin, Peng Cheng, Xiaoyao Zhong et al.SIGMOD 2026
- Accelerating High-Dimensional ANN Search via Skipping Redundant Distance ComputationsZiwen Song, Bin Wang, Xiaochun YangSIGMOD 2026 · 1 citation
