# Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search

arXiv: https://arxiv.org/abs/1509.05195 · HTML: https://mlsanity.com/paper/1509.05195/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Sep 2015.

## Built on by (most cited first, 11 of 11)

- [The Faiss library](https://mlsanity.com/paper/2401.08281/) (2024)
- [Large Concept Models: Language Modeling in a Sentence Representation Space](https://mlsanity.com/paper/2412.08821/) (2024)
- [Qinco2: Vector Compression and Search with Improved Implicit Neural Codebooks](https://mlsanity.com/paper/2501.03078/) (2025)
- [Discrete Tokenization for Multimodal LLMs: A Comprehensive Survey](https://mlsanity.com/paper/2507.22920/) (2025)
- [Nearest neighbor search with compact codes: A decoder perspective](https://mlsanity.com/paper/2112.09568/) (2021)
- [TensorSLM: Energy-efficient Embedding Compression of Sub-billion Parameter Language Models on Low-end Devices](https://mlsanity.com/paper/2506.13514/) (2025)
- [FaTRQ: Tiered Residual Quantization for LLM Vector Search in Far-Memory-Aware ANNS Systems](https://mlsanity.com/paper/2601.09985/) (2026)
- [Generative Pseudo-Labeling for Pre-Ranking with LLMs](https://mlsanity.com/paper/2602.20995/) (2026)
- [ShopX: A Foundation Model for Intent-to-Item Fulfillment in Agentic Shopping](https://mlsanity.com/paper/2606.31693/) (2026)
- [HERMES: A Multi-Granularity Labeling Substrate for Pre-training Data Mixtures](https://mlsanity.com/paper/2607.02266/) (2026)
- [GS-Codec: A Gaussian-Splatting Bottleneck for Neural Audio Coding](https://mlsanity.com/paper/2610.04651/) (2026)

## Abstract (arXiv)

Quantization methods have been introduced to perform large scale approximate nearest search tasks. Residual Vector Quantization (RVQ) is one of the effective quantization methods. RVQ uses a multi-stage codebook learning scheme to lower the quantization error stage by stage. However, there are two major limitations for RVQ when applied to on high-dimensional approximate nearest neighbor search: 1. The performance gain diminishes quickly with added stages. 2. Encoding a vector with RVQ is actually NP-hard. In this paper, we propose an improved residual vector quantization (IRVQ) method, our IRVQ learns codebook with a hybrid method of subspace clustering and warm-started k-means on each stage to prevent performance gain from dropping, and uses a multi-path encoding scheme to encode a vector with lower distortion. Experimental results on the benchmark datasets show that our method gives substantially improves RVQ and delivers better performance compared to the state-of-the-art.