SAQ: Pushing The Limits Of Vector Quantization Through Code Adjustment And Dimension Segmentation

Abstract

Approximate Nearest Neighbor Search (ANNS) plays a critical role in applications such as search engines, recommender systems, and RAG for LLMs. Vector quantization (VQ), a crucial technique for ANNS, is commonly used to reduce space overhead and accelerate distance computations. However, despite significant research advances, state-of-the-art VQ methods still face challenges in balancing encoding efficiency and quantization accuracy. To address these limitations, we propose a novel VQ method called SAQ. To improve accuracy, SAQ employs a new dimension segmentation technique to strategically partition PCA-projected vectors into segments along their dimensions. By prioritizing leading dimension segments with larger magnitudes, SAQ allocates more bits to high-impact segments, optimizing the use of the available space quota. An efficient dynamic programming algorithm is developed to optimize dimension segmentation and bit allocation, ensuring minimal quantization error. To speed up vector

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyli2025saq

Related papers

• Practical And Asymptotically Optimal Quantization Of High-dimensional Vectors In Euclidean Space For Approximate Nearest Neighbor Search (2024)8.82
• Rabitq: Quantizing High-dimensional Vectors With A Theoretical Error Bound For Approximate Nearest Neighbor Search (2024)12.54
• Quantization Meets Projection: A Happy Marriage For Approximate K-nearest Neighbor Search (2024)0.00
• Dimensionality-reduction Techniques For Approximate Nearest Neighbor Search: A Survey And Evaluation (2024)0.00
• Aisaq: All-in-storage ANNS With Product Quantization For Dram-free Information Retrieval (2024)0.00
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• Routing-guided Learned Product Quantization For Graph-based Approximate Nearest Neighbor Search (2023)4.52
• Quicker ADC : Unlocking The Hidden Potential Of Product Quantization With SIMD (2018)10.50