7.4
Placing the tools
The big picture
Step back from algorithms. The most useful single axis for placing a compression method is where it spends its compute. Then one table with everything, and a decision guide.
1Encoder-heavy against decoder-heavy
Video codecs are the classic deliberate asymmetry: a film is encoded once, slowly, and decoded millions of times. Vector indexes have the same shape (3.2 The running example). Additive codebooks are the vector-search version of that bargain.
A qualitative map Horizontal: work to encode one vector. Vertical: work to decode or score one. Dot size: error at a tight budget (bigger is worse). A ring means the method needs the vectors in sequence order. Positions are judgement calls informed by the measurements, not measurements.
- Bottom left, cheap both ways: scalar quantization, binary codes, PCA truncation. Excellent at several bits per dimension; poor at a fraction of a bit.
- Lower middle: PQ and OPQ. The workhorse when ingest rate matters.
- Bottom right, encoder-heavy: RQ with beams, additive quantization, LSQ. The same search cost as PQ, better codes, paid at build time.
- Predictive and entropy-coded variants: a better rate for storage and transport, at the cost of random access and SIMD scans.
- Top, decoder-heavy: neural decoders. The lowest error, but decoding runs a network, so they re-rank shortlists.
2The full scorecard
| Method | Implicit codebook | Encode | Search / decode | Training | Error at a tight budget | Random access | Best for |
|---|---|---|---|---|---|---|---|
| Scalar / binary | per-coordinate grid | trivial | trivial | none | high | yes | ≥ 4 bits/dim; first-stage filter |
| VQ (k-means) | K points | K·d | 1 lookup | k-means | high | yes | the IVF coarse quantizer |
| PQ / OPQ | (rotated) grid | K·d | M lookups | k-means per block | medium | yes | fast ingest, generous budgets |
| RQ, greedy | free sums | M·K·d | M lookups + norm | sequential k-means | low | yes | the default free-codebook choice |
| RQ, beam B | free sums | B × greedy | M lookups + norm | B × greedy | lower | yes | static, memory-bound indexes |
| AQ / LSQ (ICM) | free sums | restarts × M²K | M lookups + norm | re-encode per epoch | lowest linear | yes | GPU builds, tight budgets |
| Predictive RQ | sums, conditioned on the past | 2 × greedy | sequential only | closed-loop | low | keyframes | streams, archives with locality |
| + entropy-coded codes | same | + cheap | decode first | count frequencies | same, fewer bits | blocks | storage, transport |
| Lossless (model + ANS) | exact | model + coder | full decode | fit tables | zero | blocks | the canonical archive, the wire |
| Neural codebooks | input-dependent sums | network per candidate | network per step | SGD, GPU | lowest | yes | re-ranking shortlists |
3A decision guide
- Reach for additive codebooks RQ with a small beam, or LSQ: when the corpus is large and mostly static, memory per vector is the binding constraint, the budget is tight (8 to 32 bytes), and you can afford a long batch job at build time.
- Prefer PQ / OPQ When vectors must be indexed the moment they arrive, encoding runs on CPU at ingest, or the budget is generous enough that the gap is small.
- Prefer scalar or binary When you can spend a bit or more per dimension, want no training, or need a cheap first-pass filter. With a float query and re-ranking, 1 bit per dimension goes a long way (5.4 Bits as a compressed sketch).
- Add prediction and entropy coding When data comes in sequences and is read sequentially: archives, transfer, streaming. Keep them out of the random-access search path.
- For exact copies Choose the precision first. Then a bell curve per coordinate, triangular prediction, the previous vector if there is one, and ANS. Measure before adding anything cleverer (6.7 Where should the bits go?).
- Use hashing For near-duplicates, for streams with heavy churn, and when there is nothing to train on (5.3 Random cuts against learned cuts).