skip to content

What does product quantization compress in a vector index, and at what cost?

level: middleimportance: must knowfreq 62%

answer

  1. trade bytes for approximate distances
  2. split the vector, not the corpus
  3. one small codebook per slice
  4. one byte per subvector code
  5. lookup tables replace float maths

basics

~20 s

Product quantization splits each vector into subvectors and replaces every subvector with the id of the nearest centroid in a small per-subspace codebook. Storage drops to a few bytes per vector, but every distance computed from codes is an estimate.

solid answer

~50 s

PQ is the compression axis of this index family. A 768-dimension vector is cut into m contiguous subvectors — with m=64 that is 12 dimensions each — and a separate codebook of 256 centroids is trained for each of the 64 subspaces. Encoding replaces each subvector with the 8-bit id of its nearest centroid, so the whole vector becomes 64 bytes instead of 3072: a 48x reduction that decides whether a billion-vector corpus fits in RAM at all. Distances are then computed *without* decompressing. For a given query you precompute, per subspace, the distance from the query's subvector to all 256 centroids — a small lookup table — and score a candidate by summing 64 table lookups. That is asymmetric distance computation: the query stays full precision, the database side is codes. The cost is quantization error. Codes are lossy, so the ranking they produce is approximate, and close competitors can swap order — which is why serious systems rescore.

code

python · 5 lines
python
dims, m, bits = 768, 64, 8
sub_dim = dims // m              # 12 dimensions per subvector
code_bytes = m * bits // 8       # 64 bytes of codes per vector
raw_bytes = dims * 4             # 3072 bytes as float32
print(sub_dim, code_bytes, raw_bytes, raw_bytes / code_bytes)

go deeper

for a junior

Know that product quantization stores a short code instead of the full float vector, that it saves a large multiple of memory, and that the distances it produces are approximate.

for a middle

Be ready to walk the mechanics: split into m subvectors, one codebook of 256 centroids per subspace, one byte per subvector, and distances computed by summing precomputed lookup-table entries.

for a senior

Show that you reason about the error budget — how m and bit depth set reconstruction error, why top-of-list ordering suffers most, and why compressed scores are treated as a shortlist rather than a final ranking.

for a principal

Own the choice across the whole compression family and its consequences: what footprint target forces PQ over int8, whether the embedding model quantizes gracefully, and what recall you are willing to buy back with rescoring.

## Two independent axes Approximate search has two ways to get cheaper: look at fewer vectors (partitioning, e.g. IVF cells) or make each vector smaller and cheaper to compare (compression). Product quantization is the second axis, and it is the one that determines whether a corpus fits in memory. ## Why not just quantize the whole vector You could cluster whole vectors and store one centroid id each — but to represent a 768-dimension space with useful fidelity you would need an astronomically large codebook, and training it is impossible. PQ's trick is in the word *product*: instead of one codebook over the full space, it takes the Cartesian product of many small codebooks over disjoint subspaces. Split the vector into m contiguous chunks. Train an independent codebook of 2^b centroids per chunk (b=8, so 256 centroids, is the near-universal choice because a code then fits exactly one byte). The effective vocabulary is 256^m distinct reconstructions — vast — while training and storage stay tiny, because each codebook only has to model 768/m dimensions. ## The memory arithmetic This is the number interviewers want: - Raw: 768 dims x 4 bytes = **3072 bytes** per vector. - PQ with m=64, b=8: **64 bytes** per vector, plus a few identifier bytes. - Codebooks themselves: 64 subspaces x 256 centroids x 12 floats = about 786k floats, i.e. ~3 MB total, amortized over the whole corpus. At a billion vectors that is roughly 3.7 TB versus about 77 GB. The first needs a cluster; the second fits one large machine. ## Computing distances over codes Naively you would reconstruct each candidate and compare — that throws away the speed win. Instead, **asymmetric distance computation (ADC)** keeps the query in full precision. For subspace j, precompute the distance from the query's j-th subvector to each of that subspace's 256 centroids: one 64x256 table per query. Scoring a candidate is then 64 table lookups and 64 additions, no floating-point vector maths and no cache-hostile 3 KB read. Distances are approximate on the database side only, which is more accurate than also quantizing the query (symmetric computation). ## The cost: quantization error A code is a lossy reconstruction; the residual between the true subvector and its centroid is discarded forever. The effect on search is that computed distances carry noise of roughly the reconstruction error, so genuinely close candidates get shuffled. Empirically, top-1 accuracy suffers most and the ordering within the true top-50 becomes unreliable, while the coarse question "is this vector in the right neighbourhood" stays fairly robust. That asymmetry is exactly why compressed indexes are usually used to produce a *shortlist* which is then re-ranked against full-precision vectors. The error you accept is set by m and b. Larger m means shorter subvectors, less information crushed per code, better accuracy, more bytes. Halving m halves memory and roughly doubles the reconstruction error. ## The rest of the compression family PQ is the most aggressive but not the only option: - **Scalar quantization (SQ)** maps each dimension independently onto an int8 (or 4-bit) range using per-dimension or global min/max. Simple, ~4x smaller, very low error, easy to reason about, no codebook training beyond computing ranges — often the first thing to try. - **Binary quantization (BQ)** keeps one bit per dimension, typically the sign after centring. 32x smaller, and distance becomes XOR plus popcount — extremely fast on modern CPUs. Error is large, so it is a shortlist mechanism rather than a final ranking. - **PQ** sits between them on compression ratio and above them in per-byte fidelity, at the price of a training pass. How well any of these behave depends on the embedding model: models whose vectors are already well spread and normalized quantize far more gracefully than ones with heavy-tailed dimensions, and some model families are explicitly trained to survive binarization. ## Combining with partitioning PQ composes with IVF: the coarse quantizer picks which lists to scan, and the lists hold PQ codes rather than vectors. A refinement, common in practice, is to PQ-encode the *residual* — the vector minus its cell centroid — rather than the raw vector, because residuals within a cell have much smaller magnitude and variance, so the same code budget captures them more accurately. ## When not to compress Compression is a memory trade, so it only earns its complexity when memory is the binding constraint. If the corpus fits comfortably uncompressed, quantizing costs recall and adds a training step in exchange for RAM you were not short of. Measure the footprint before reaching for it.

  • Why is asymmetric distance computation preferred over quantizing the query too?
    Because the query is a single vector and quantizing it adds error for no storage benefit. Keeping the query in full precision and precomputing its distance to every centroid in every subspace costs one small table per query, then each candidate is scored by summing lookups. Symmetric computation — comparing code to code — is marginally faster to set up but measurably less accurate.
  • When would you choose scalar or binary quantization over PQ?
    Scalar quantization when you need modest savings with minimal risk: about 4x smaller, low error, nothing to train beyond per-dimension ranges. Binary quantization when you want a very fast first-pass filter — 32x smaller and Hamming distance over bits — accepting that its ranking is only good enough to build a shortlist. PQ when memory is the binding constraint and you can afford a training pass.
  • How does PQ interact with an IVF partition?
    They compose cleanly: IVF decides which lists to scan, and each list stores PQ codes instead of vectors. A common refinement encodes the residual (vector minus its cell centroid) rather than the raw vector, because residuals inside one cell have smaller spread, so the same number of code bytes reconstructs them more accurately.

It is paint-by-numbers for vectors: instead of storing the exact colour of every patch, you store the nearest swatch number from a small palette chosen for that patch's region. The picture survives; the exact shades do not.

saying these in an interview costs you the question

  • Thinks PQ compresses the corpus by dropping vectors
  • Says quantized distances are exact once decoded
  • Confuses splitting dimensions with reducing dimensionality
  • Assumes 8-bit codes mean 8 dimensions per subvector
  • Claims compression also speeds up search by shrinking the candidate set

context

resolving links…