vector quantization

**Vector Quantization (VQ)** is a compression technique that maps continuous high-dimensional vectors to a discrete set of representative vectors (called a **codebook**), reducing storage and enabling efficient similarity search in RAG systems. **How Vector Quantization Works** 1. **Training**: Run clustering (K-means) on a training set of vectors to learn K representative vectors (centroids) — the codebook. 2. **Encoding**: Replace each vector with the index of its nearest codebook entry. 3. **Storage**: Store only the codebook indices (log₂(K) bits per vector) instead of full vectors. 4. **Decoding**: Reconstruct approximate vectors by looking up codebook entries. **Example** - **Original**: 768-dimensional float32 vector = 3,072 bytes. - **Codebook**: 256 entries (8-bit indices). - **Compressed**: 1 byte per vector (index into codebook). - **Compression**: 3,072× (though codebook must be stored separately). **Types of Vector Quantization** - **Scalar Quantization (SQ)**: Quantize each dimension independently (simple, less compression). - **Product Quantization (PQ)**: Split vector into sub-vectors, quantize each sub-vector separately (better compression-accuracy trade-off). - **Residual Quantization (RQ)**: Iteratively quantize the residual error (highest accuracy). **Advantages** - **Compression**: Dramatically reduces memory footprint for large vector collections. - **Fast Search**: Distance computation can use lookup tables or specialized hardware. - **Scalability**: Enables billion-scale vector search on limited hardware. **Disadvantages** - **Lossy**: Quantization introduces approximation error — may miss true nearest neighbors. - **Training Overhead**: Requires clustering on representative data. - **Codebook Storage**: Must store and load the codebook (typically small overhead). **Use in RAG** Vector quantization enables efficient semantic search over massive document collections: - **Coarse Search**: Use quantized vectors for fast candidate retrieval. - **Reranking**: Fetch full-precision vectors for top candidates and rerank. **Frameworks** - **FAISS**: Implements multiple VQ variants (IVF, PQ, SQ, RQ). - **ScaNN** (Google): Optimized vector quantization for similarity search. - **Qdrant**: Vector database with built-in quantization support. Vector quantization is a **fundamental technique** for scaling RAG systems to billions of documents while maintaining sub-second query latency.