Store less; keep the order.
Classes 04–06 make compressed documents fast. This class decides what the compressed documents are. Four ways to shrink a token vector — round it, keep its sign, point at a cluster and correct, or cut the space into pieces — and one metric that judges them all: does the ranking survive? Every scheme the repo implements is measured on full SciFact; the one it doesn't (product quantization) gets an honest chapter anyway, because it's the road most of the industry took.
The memory wall
Late interaction keeps a vector per token, and that decision has a bill. At dim 128 in float32 a token costs 512 bytes; a modest corpus has millions of tokens. Drag the corpus size and watch each storage scheme cross the line where an index stops fitting in RAM:
One more reason, and it's class 02's: the float path is memory-bound at scoring time — chapter 06 measured intensity, and bytes moved is time spent. Fewer bytes per token isn't only a smaller disk bill; it's the headroom every kernel in classes 04–05 cashes in. The question is what to throw away.
What must survive: the order
Here's the liberating fact about compressing a search index: nobody ever reads the scores. A query returns documents sorted by score — so quantization error is invisible until it swaps two documents. Add noise to the true scores and watch when the ranking actually breaks:
So every scheme in this class is judged twice: bytes per token (what it costs) and retention — its NDCG@10 as a fraction of the exact-float 0.7629 on full SciFact (what it keeps). Reconstruction error is only ever a means; order is the end.
Round the floats: scalar quantization
The gentlest move: keep every dimension, spend fewer bits on each. Pick a scale so the largest value maps to 127, round everything to the nearest step, store int8 + one float scale per row. Randomize the input and watch what the rounding costs:
Float16 sits in the same family (2×, even politer). The pattern to notice: scalar quantization shrinks the values but keeps the structure — 128 independent numbers, one per dimension. Every scheme after this one gets its bigger wins by attacking the structure itself.
Keep only the sign
Now the other extreme: one bit per dimension. Keep the sign, discard the magnitude — a 128-dim token becomes 16 bytes, 32× less than float32. What's left of a vector when every value is ±1? Its direction:
This is the scheme class 04 builds its kernel around, and its quality-per-bit is the benchmark the fancier schemes below have to justify themselves against. It also sets up this class's one genuinely surprising measurement — chapter 05 ends with a scheme that spends the same 20 bytes and does 11 points worse.
Point at a cluster, then correct
Between int8's 128 bytes and binary's 16 sits the scheme ColBERTv2 and PLAID made standard, and the one next-plaid ships: run k-means over all token vectors, store each token as a centroid id plus a low-bit correction. The centroid does the pointing; the residual does the polishing. Pick the centroid and watch what happens to the numbers that need storing:
Measured on full SciFact, the knob behaves like a knob should — until it doesn't: residual-4: 0.7609 (99.7%) · residual-2: 0.7635 (100.1% — parity with exact; the codec's error is below this benchmark's resolution) · residual-1: 0.7470 (97.9%). The last number has a history worth more than the number. This page originally reported 0.6312 — 11 NDCG points behind binary at the same 20 bytes — and drew a confident lesson from it about one bit of residual being mostly noise. The lesson was wrong. The engine was scoring raw reconstructions, and quantization bends unit vectors — so a token's accidental reconstruction length was deciding MaxSim. One cached scalar per token (renormalization — class 05, chapter 13) recovered +0.116 NDCG at nbits=1, and residual-1 now edges binary at equal bytes. The retraction earns its place in the course: a measured negative is only as strong as the scoring semantics it was measured under.
Cut the space itself: product quantization
The fourth idea is the one this repo doesn't implement — and the one behind FAISS and most billion-scale ANN systems, so it gets a real chapter. PQ splits the 128-dim space into M subspaces and k-means-quantizes each subspace separately: a token becomes M tiny codebook indices. Step through encoding and scoring a dim-8 toy (M = 4 subspaces × 2 dims, 4 entries each):
So why did the ColBERT lineage pick centroid + scalar residual instead? Three honest trade-offs, not a verdict:
| product quantization | centroid + scalar residual (ch 05) | |
|---|---|---|
| codebooks | M learned tables × 256 entries — captures per-subspace structure, better rate–distortion at the same bits | one shared 16-entry table for all 128 dims — cruder, but 16 bytes total |
| scoring state per query | M × 256 floats of ADC tables — lives in L1/L2, a memory lookup per subspace | the table rides in a register; lookup is one instruction (class 05's tbl/pshufb) |
| who's already pointing | PQ often carries the whole vector alone | the IVF centroid — which stage 1 needs anyway for candidate pruning (class 06) — absorbs the direction; residuals come out small and near-interchangeable, which is what lets one table serve every dim |
And here's the convergence that makes the whole design space feel small: FAISS's fastest PQ
variant, 4-bit fast-scan, shrinks its codebooks from 256 entries to 16 precisely so
the ADC tables fit in a SIMD register and the lookup becomes pshufb — the
identical instruction class 05 builds on. Two schemes, two lineages, one register-shaped
conclusion: if you want compressed scoring at CPU speed, your table must fit in 16 bytes.
Two quantizers, one asymmetry
Every scheme above quantized documents. Nobody quantizes the query the same way — and the reason is just counting:
The scoreboard
Full SciFact — 5,183 docs, 1.19M tokens, dim 128, 300 queries, numpy reference
paths (eval.py --profile). Quality first, and the column that motivates the rest
of the school last:
| scheme | bytes/token | NDCG@10 | retention | p50 ms/query · numpy |
|---|---|---|---|---|
| exhaustive float32 | 512 | 0.7629 | 100% | 20.0 |
| residual nbits=4 | 68 | 0.7609 | 99.7% | 111 |
| residual nbits=2 | 36 | 0.7635 | 100.1% | 82 |
| residual nbits=1 | 20 | 0.7470 | 97.9% | 64 |
| binary (sign bits) | 20 | 0.7460 | 97.8% | 17.7 |
Two readings of one table. The quality story is a triumph: 99.7% of exact ranking at 1/7.5th the bytes, 97.9% at 1/25th — and the 2-bit row at outright parity. Order really does survive brutal compression — chapter 02's promise, kept. The latency column is a scandal: the best-quality scheme is 5.5× slower than the brute-force float GEMM it was supposed to beat (111 ms vs 20), because its numpy path decompresses every candidate back to floats and hands them to BLAS — repaying the entire compression win at query time, plus interest. Compression chose what to store; it wrote a check that scoring has to cash. The next two classes are how: binary's masked-sum identity (class 04: 17.7 → 6.0 ms), then the residual family's in-register table (class 05: 111 → 6.9 ms, and the red column dies).
A field guide
The same four ideas, as they ship in real systems — so when you meet one in a paper or a codebase you can place it on this class's map:
| scheme | bytes/token · dim 128 | reach for it when | shipped by |
|---|---|---|---|
| scalar int8 / f16 | 128 / 256 | queries; anywhere 2–4× is enough and fidelity is sacred | everyone — it's the universal query-side move |
| binary (sign bits) | 16–20 | maximum compression per point of NDCG; simplest possible decoder | Lucene/Elasticsearch BBQ, nano-plaid's headline scheme, next-plaid's binary route |
| centroid + scalar residual | 20–68 (nbits 1–4) | a tunable quality knob on top of an IVF index you already need for pruning | ColBERTv2 / PLAID, next-plaid's residual routes |
| product quantization | 8–32 | single-vector ANN at huge scale; best rate–distortion when no centroid is doing the pointing | FAISS IVF-PQ, ScaNN, most vector DBs |
One closing observation before the kernels. Every row of that table was invented by people
optimizing storage — yet the schemes that won each niche are exactly the ones whose
decode step could later be made to disappear into an instruction: sign bits into a masked sum,
16-entry tables into tbl/pshufb. The bits you choose to keep
determine the kernel you're allowed to write. We've chosen our bits; now we owe them speed.
Six questions
Instant feedback, explanations included. Miss one? The chapter number is next to it.