Where should the bits go?

1The two-part code

Some predictors are not free. A coarse code (an RQ code, quantized PCA coefficients) must be stored before it can be used to predict. The file then has two parts:

\kbits{\text{total bits}} \;=\; \underbrace{\kcode{\text{side information}}}_{\text{describes the guess}} \;+\; \underbrace{\kres{\text{residual}}}_{\text{exact value given the guess}}

This is a two-part code, and choosing how much to spend on the first part is the minimum description length principle in its plainest form.

Fig 6.7.1A quantizer as side information

A quantizer as side information The stored file is the code plus the entropy-coded residual. The decoder recomputes the prediction from the code, so adding the residual restores every bit.

2The exchange rate

From 6.2 Everything is a probability model, a coordinate costs $\log_2(\sigma/\Delta) + 2.05$ bits. Across $d$ coordinates, with $D$ the total squared error of the guess:

\kres{\text{residual bits}} \;\approx\; \frac{d}{2}\log_2 \kres{D} \;+\; \text{const}

In lossy mode the depth of a quantizer is set by a memory budget. In lossless mode it is set by the data: keep adding stages while each one cuts the error by more than 2.8%.

3Dial 1: how many RQ stages?

The progressive property of RQ (4.3 Be greedy) lets us train one deep stack of 24 stages and choose the depth afterwards.

Fig 6.7.2Lossless size against predictor stages

Hover the chart Bits per vector to store the database books exactly, against the number of RQ stages $m$ used as the predictor. Pink band: the code, 8 bits per stage. Dashed lime: the residual alone. Solid lime: the total. The dashed baselines use no quantizer.

The rule predicts the minimum:

Stage	Cuts the error by	Above 2.8%?
9	4.4%	yes: add it
10	3.6%	about break-even
12	3.3%	about break-even, and falling

The measured optimum is $m = 9$ at 2,394 bits, and the curve is nearly flat from 8 to 12: exactly the break-even zone.

4Dial 2: how fine a step for the side information?

Use quantized PCA coefficients as side information instead, with one step size $s$ for all of them. Small directions round to zero and cost almost nothing, so this is water-filling (3.4 From spectrum to bit budget) with a single knob.

Fig 6.7.3Two kinds of side information

Two kinds of side information on one axis x: bits spent on the side information. y: total bits, zoomed. Both curves are shallow bowls with a minimum.

Read the two ends of the orange curve:

Too coarse (left): the side information ignores most of the correlation, and the per-coordinate residual model pays for it.
Too fine (right): the coefficients describe noise that the residual has to describe again on a different grid. The total climbs back to where it started.

5The general rule

Every dial is the same problem. Spend bits on layer A while the marginal saving in layer B exceeds one bit per bit:

\frac{\partial\,\kres{\text{residual bits}}}{\partial\,\kcode{\text{side bits}}} \;=\; -1 \quad\text{at the optimum}

In rate–distortion language this is the equal-slope condition: at the best allocation, every component is working at the same exchange rate. Reverse water-filling is the special case where the components are principal directions.

6When side information pays, and when it does not

This is the part that the formula cannot tell you, and where measuring earns its keep.

The same 64 bits of RQ code, against two residual models

Residual model	Without RQ	With RQ-8 (code included)	RQ’s net effect
A bell curve per coordinate	2,477	2,397	saves 79 bits
Triangular prediction	2,257	2,274	costs 17 bits
Triangular + previous window	2,171	2,220	costs 49 bits

Against a weak residual model, the quantizer code removes 143 bits of residual for a price of 64. Against a strong one it removes only 47, less than it costs.

Side information pays only for structure the residual model cannot already see.

A codebook and a linear predictor were both describing the same thing: the ellipsoidal shape of the cloud. Once the linear model has it for free, the codebook is charging rent.

A codebook would still earn its place if the data had strong non-linear structure: tight, well-separated clusters, where knowing the cluster changes not just the mean but the whole local covariance. These embeddings are close to one big Gaussian (remember the kurtosis of -0.02), so there is little of that to find.

7The hyperparameter sheet

Dial	Trades	How to set it	On this data
Target precision Δ	fidelity ↔ everything	the largest step that leaves recall intact	int8: 4× before any coder
Marginal model	parameters ↔ KL waste	fit, compare cross-entropy on held-out data	Gaussian per coordinate
Temporal coefficient β	—	least squares on training pairs	0.63
Keyframe interval $K$	random access ↔ bits	cost is (keyframe − predicted) / $K$	64: +1.3 bits
RQ stages $m$	code bits ↔ residual bits	add while a stage cuts error > $2^{-16/d}$	0 with a triangular model; 9 without
PCA step $s$	side bits ↔ residual bits	sweep; the bowl is shallow	6
Block size of triangular prediction	decode speed ↔ bits	measure both	full, for the archive