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.