Nearest Neighbour

Residual quantization: compressing what the centroid missed

IVF-PQ — a cluster index whose vectors are stored product-quantized — is the standard configuration for very large collections. Described as “partition, then compress” it sounds like two independent techniques stacked. It isn’t quite, and the interesting part is the join between them: the codes don’t encode the vectors. They encode what the partition already failed to capture.

The naive approach

Compose the two techniques the obvious way. Assign each vector to its nearest centroid. Separately, encode each vector with a product quantizer trained over the whole collection. Store the code in the centroid’s list.

naive(v):
    cell  ← nearest centroid to v
    code  ← PQ_encode(v)                 # trained on the whole collection
    append (id, code) to list[cell]

This works and it is not silly. But look at what the codebooks have to cover. Trained over the whole collection, each slice’s 256 entries must span the full range of values that slice takes anywhere in the space. The codebook is a summary of the entire distribution, and any single vector is being approximated by the nearest of 256 globally-placed representatives per slice.

How it fails, or rather how it wastes: we already know something about the vector that the codebook isn’t using. We know which cell it’s in — which is to say, we know it is near a particular centroid, and the centroid is stored exactly. Encoding the vector from scratch throws that knowledge away and pays to re-express information the cell assignment already carried.

The idea: encode the leftover

Don’t quantize the vector. Quantize the residual — what’s left after subtracting the centroid.

r = v − centroid(cell(v))

Geometrically: the centroid says roughly where the vector is, and the residual is the correction from there. Store the cell ID (which you were storing anyway, implicitly, by putting the vector in that cell’s list) and a compressed correction. At query time, reconstruct as centroid + decoded_residual.

Why this is better is a statement about the spread of what you’re compressing. The vectors in a cell are scattered across the whole occupied space; the residuals in a cell are all small, because a vector is by construction near its own centroid. And residuals from different cells, pooled together, are all small too — they are each a local offset, centred on zero.

Quantization error scales with the spread of the data being quantized. A codebook of 256 entries covering a small region achieves a much finer approximation than 256 entries covering a large one. So encoding residuals with the same number of bits gives lower error than encoding raw vectors — the same storage, a more accurate reconstruction, and therefore better recall at identical memory. There is no trade being made here; it is strictly better use of the same budget.

There is a second effect that compounds it. Residuals are not just smaller, they are more homogeneous. Raw vectors form a lumpy, clustered, multi-modal distribution, and a codebook trained on it must spend entries covering the gaps between modes. Residuals from every cell overlay into a single roughly unimodal blob centred at the origin, which is close to the ideal shape for k-means to cover efficiently with a fixed number of representatives. One codebook, trained on all residuals pooled, serves every cell.

train(sample, nlist):
    centroids ← k-means(sample, nlist)
    residuals ← { v − nearest_centroid(v) : v in sample }
    codebooks ← PQ_train(residuals)          # one set, shared by all cells

encode(v):
    c    ← nearest centroid to v
    code ← PQ_encode(v − c)
    append (id, code) to list[c]

reconstruct(cell, code):
    return centroid[cell] + PQ_decode(code)

What this costs at query time

The two-stage structure now has a subtlety, and it’s the price of the trick.

Without residuals, the distance tables are query-dependent only: compute the query’s distance to every codebook entry once, then every candidate in every probed cell is a sum of table lookups. One table set per query.

With residuals, the reconstruction is centroid + decoded_residual, and the distance from the query to that depends on which centroid. Expand the squared distance:

‖q − (c + r)‖²  =  ‖(q − c) − r‖²

The right-hand side is the distance from the cell-adjusted query q − c to the residual r. So the distance tables must be built per probed cell, using q − c rather than q. If you probe nprobe cells, you build nprobe table sets instead of one.

That is a real cost and it is bounded and predictable: nprobe × m × 256 distance computations of d/m dimensions each, per query. It is paid once per cell, not per candidate, so it amortises well when cells hold many vectors and badly when nprobe is large and cells are small. This is one concrete reason the nlist/nprobe balance in a residual-quantized index differs from an uncompressed one: the fixed per-probe overhead is higher.

An implementation can dodge it by expanding the expression differently, keeping a query-independent term and a term involving the centroid, so that some of the work is precomputable per cell at build time. The trade there is extra stored statistics per cell against per-query arithmetic. Which variant an engine uses is an implementation choice, not a property of the algorithm, and it is worth knowing that the choice exists when a compressed cluster index’s cost doesn’t behave the way the naive model predicts.

The same idea, iterated

Residual encoding generalises in a way worth recognising, because several designs are instances of it.

If quantizing the residual leaves an error, quantize that error too. Stack coarse-to-fine stages, each one encoding what the previous stage got wrong:

r₀ = v
for stage s in 1..S:
    codeₛ  ← nearest entry in codebookₛ to rₛ₋₁
    rₛ     ← rₛ₋₁ − codebookₛ[codeₛ]

The reconstruction is the sum of one entry from each stage’s codebook. This is residual quantization in its own right, and it gives a different way to spend a bit budget than PQ does: PQ divides the vector into slices and encodes each independently, while residual stacking encodes the whole vector repeatedly at increasing precision. The two compose — each residual stage can itself be a product quantizer — and the common IVF-PQ arrangement is exactly the two-stage case with a very coarse first stage whose codebook is the centroid list.

Seen that way, the coarse quantizer and the fine quantizer are the same kind of object at different scales. The centroid list is a codebook with nlist entries used for routing; the PQ codebooks are codebooks with 256 entries per slice used for scoring. That framing is what makes several designs intelligible: using a graph index to search the centroid list is just applying an index to a codebook lookup, and multi-level partitioning is a residual hierarchy with a probe budget at each level.

What it gives up

A hard coupling between the partition and the codes. The codes are offsets from specific centroids, so they are only meaningful relative to the centroid list they were built against. Retrain the centroids and every stored code is invalid — not degraded, invalid, because it is a correction to a point that has moved. In the naive non-residual composition, codes and centroids are independent and either could in principle be replaced alone. Residual encoding trades that independence for accuracy, and it means the staleness of the partition now also implicates the compression.

Reconstruction requires the centroid. Decoding a vector is a lookup plus an addition, which is cheap, but it does mean the centroid list must be resident. It is small, so this is rarely a constraint.

Error is no longer uniform across the collection. A vector far from its centroid has a large residual, and a large residual is quantized with proportionally more error. So the vectors most poorly represented are the ones in sparse regions and the ones near cell boundaries — which are, unhelpfully, the same vectors that boundary effects already make hardest to retrieve. The two error sources are correlated and they compound in the same place.

None of it changes what compression fundamentally is. The stored representation is still lossy, the approximate distances are still approximate, and exact ordering still comes from a rescoring stage over full-precision vectors. Residual encoding makes the candidate list better for the same memory. It does not make the compressed distances trustworthy enough to skip the rescore.

quantizationcluster-index