product quantization

**Product Quantization (PQ)** is a vector compression technique that reduces high-dimensional embeddings to compact codes, enabling efficient storage and fast similarity search in RAG (Retrieval-Augmented Generation) systems. It achieves 10-100× compression with controlled accuracy loss. **How Product Quantization Works** 1. **Split**: Divide each D-dimensional vector into M sub-vectors of dimension D/M. For example, split a 768-dim vector into 96 sub-vectors of 8 dimensions each. 2. **Cluster**: For each sub-vector position, run K-means clustering on training data to learn a codebook of K centroids (typically K=256, requiring 8 bits). 3. **Encode**: Replace each sub-vector with the index of its nearest centroid in the corresponding codebook. 4. **Result**: The original vector (768 floats = 3,072 bytes) becomes M bytes (96 bytes) — a 32× compression. **Distance Computation** To compute similarity between a query vector and PQ-encoded vectors: - Precompute a distance lookup table between query sub-vectors and all codebook centroids. - Approximate distance as a sum of M table lookups — extremely fast compared to full vector dot products. **Advantages** - **Massive Compression**: 10-100× memory reduction enables billion-scale vector search. - **Fast Search**: Distance computation via table lookups is much faster than full-precision arithmetic. - **Scalable**: Enables RAG systems to handle massive knowledge bases on limited hardware. **Trade-offs** - **Lossy Compression**: Approximate distances may miss true nearest neighbors (recall degradation). - **Training Required**: Must run K-means clustering on representative data. - **Accuracy vs. Compression**: More sub-vectors (larger M) = better accuracy but less compression. **Use in Vector Databases** PQ is a core component of FAISS (Facebook AI Similarity Search) and is used in production vector databases: - **FAISS IVF-PQ**: Combines inverted file indexing with product quantization. - **Milvus**: Supports PQ for memory-efficient indexing. - **Pinecone**: Uses PQ-like compression internally. **Typical Configuration** - **Dimensions**: 768 (BERT) or 1536 (OpenAI). - **Sub-vectors**: 96 (for 768-dim) or 192 (for 1536-dim). - **Codebook size**: 256 (8-bit codes). - **Compression**: 32× (768 floats → 96 bytes). - **Recall@10**: 95-98% (with proper tuning). Product quantization is **essential for large-scale RAG** — it makes billion-vector search practical on commodity hardware.