The Memory Problem
Storing vectors at full float32 precision is expensive. One billion vectors at 1,536 dimensions requires approximately 6 terabytes of RAM. Even at 128 dimensions, it's 512 GB. Cloud RAM at this scale costs tens of thousands of dollars per month. Product Quantization (PQ) is the standard technique for compressing vectors by 16x to 64x with acceptable accuracy loss.
The core idea: instead of storing the exact floating-point coordinates of a vector, store a compact code that identifies which pre-computed "pattern" the vector most closely resembles. It's lossy compression — like JPEG for images — but the loss is controlled and predictable.
How PQ Works: Step by Step
Step 1 — Split (Decompose):
Take a vector with D dimensions and split it into M equal sub-vectors, each with D/M dimensions.
Example: A 128-dimensional vector split into M=8 sub-vectors of 16 dimensions each.
Original: [d1, d2, ..., d128]
Split: [d1..d16] [d17..d32] [d33..d48] ... [d113..d128]
sub-vec 0 sub-vec 1 sub-vec 2 sub-vec 7
Step 2 — Train Codebooks (K-Means per sub-space):
For each of the M sub-spaces, run K-Means clustering on the training data to find K* centroids (typically K=256). These centroids form a codebook* — a lookup table of representative patterns for that sub-space.
Each sub-space has its own independent codebook. With M=8 sub-spaces and K*=256 centroids each, you have 8 codebooks × 256 entries × 16 floats = 32,768 floats total. This is negligible memory.
Step 3 — Encode (Quantize):
For each stored vector, find the nearest centroid in each sub-space's codebook. Replace the 16 floats with the 1-byte centroid ID.
Original sub-vec 0: [0.12, -0.34, ..., 0.87] (16 floats = 64 bytes)
Nearest centroid in codebook 0: centroid #42
Encoded: 42 (1 byte)
Step 4 — Result:
Original vector: 128 floats × 4 bytes = 512 bytes
PQ-encoded: 8 codes × 1 byte = 8 bytes
Compression ratio: 64x
Asymmetric Distance Computation (ADC)
At query time, you never decompress the stored vectors. Instead, you use Asymmetric Distance Computation:
- Pre-compute distance tables: For the query vector, split it into M sub-vectors. For each sub-space, compute the distance from the query sub-vector to all K*=256 codebook centroids. Store these in a lookup table.
Table for sub-space 0: [dist(q0, centroid_0), dist(q0, centroid_1), ..., dist(q0, centroid_255)]
- Approximate distance via table lookup: For any stored PQ code
[42, 17, 203, ...], the approximate distance to the query is:
approx_dist = table_0[42] + table_1[17] + table_2[203] + ...
This replaces 128 floating-point multiplications with 8 integer table lookups and 7 additions. On modern CPUs with SIMD instructions, this is extraordinarily fast.
The accuracy trade-off: PQ distance is an approximation. The error is bounded by the quantization error of each sub-space — how far the true sub-vector is from its assigned centroid. Finer codebooks (more centroids, more sub-spaces) reduce error but increase memory and computation. The standard IVF-PQ configuration (M=8, K*=256) typically achieves Recall@10 of 0.85–0.95 depending on dataset characteristics.
A common interview question: "Why is PQ called product quantization?" The answer is that the full codebook is the Cartesian product of the M sub-space codebooks. With M=8 sub-spaces and K*=256 centroids each, the theoretical codebook has 256^8 ≈ 1.8 × 10^19 possible codes — far more than you could ever store explicitly. PQ achieves this expressiveness by factoring the codebook into independent sub-spaces, making it tractable. This is the key insight that makes PQ practical where a single large codebook would be impossible.
Senior depth — scalar quantization as an alternative: PQ is not the only compression option. Scalar Quantization (SQ) compresses each dimension independently from float32 to int8, achieving a 4x compression with almost no recall loss. Many production systems use SQ8 (8-bit scalar quantization) as a first step because it's simpler to implement, has no training requirement, and the recall degradation is minimal. PQ is reserved for cases where 4x compression is insufficient and you need 16x–64x reduction.