Underneath every result so far lies one currency: description length. Learning is compression, simplicity is a probability, and Occam's razor is not a preference but a theorem.
“A model that predicts well compresses well.” That sounds like a metaphor, or at best an analogy. It is neither. It is an identity, and you can compute both sides of it. Once you take it literally, a surprising amount of what the earlier chapters treated separately — overfitting, generalization, why simple explanations deserve preference — turns out to be one subject measured in one unit.
The organizing principle has one sentence: total code length equals model bits plus residual bits, and the smallest total wins. Everything in this chapter is that sentence in a different costume — selecting among models, weighing two hypotheses, pricing the precision of a weight, reading a cross-entropy as a file size, or assigning belief to competing programs. We take them in turn.
To communicate a dataset to someone who has neither, you may send a model and then the residuals — the corrections the model fails to predict. A complex model costs more to send but leaves smaller residuals; a simple one costs little but leaves much unexplained. The minimum description length principle says: choose the model minimizing the total.
The zero-error model loses
Each parameter costs 12 bits to encode. Three candidates fit the same data:
MDL selects B at 430 bits. Note what happened to Model C: it achieves zero training error and is the worst of the three, losing by 290 bits. Overfitting, usually described in words, is here a number — the price of the parameters exceeds the residual bits they save.
The same accounting compares two hypotheses directly. If \( H_1 \) needs 30 bits to specify and assigns the observed data probability \( 2^{-10} \), its total is \( 30 + 10 = 40 \) bits. If \( H_2 \) needs only 12 bits but assigns probability \( 2^{-35} \), its total is \( 47 \). The simpler hypothesis loses by 7 bits — odds of \( 2^7 = 128 \) to 1 against it. Simplicity is charged in the same currency as fit, and the sum decides.
Hypothesis A is a 15-bit program with likelihood \( 2^{-4} \). Hypothesis B is a 5-bit program with likelihood \( 2^{-k} \). What is the largest integer \( k \) for which B is still preferred?
A totals \( 15 + 4 = 19 \). B totals \( 5 + k \), which must be under 19, so \( k \le 13 \).
The connection between prediction and compression is not a metaphor. When a model assigns probability \( q \) to the token that actually occurs, an optimal code spends \( -\log_2 q \) bits encoding it. The average of that quantity over a corpus is the cross-entropy, so a model's cross-entropy in bits per token is literally the per-token size of the compressed corpus.
A corpus, in gigabytes
A corpus of \( 23 \) billion tokens is modeled at a cross-entropy of \( 1.6 \) bits per token. The compressed size is \( 23\times 10^9 \times 1.6 = 36.8\times 10^9 \) bits, and dividing by \( 8\times 10^9 \) bits per gigabyte gives 4.6 GB. Improving the model to 1.4 bits per token would shrink the same corpus to 4.0 GB. Every gain in predictive quality is, exactly and measurably, a gain in compression.
One conversion has to be made explicit, because it is where the identity meets a real corpus and where nearly everyone slips. A model's loss is quoted per token, and a file's size is measured in characters or bytes. The two differ by the tokenizer's compression ratio \( \gamma \), the average number of characters a token stands for — Section 2.4, and about 4 for English. Bits per character is bits per token divided by \( \gamma \), and if you compare two models whose tokenizers differ without making that division, you are comparing rulers rather than models.
Two models, two tokenizers, one file
Model P reaches 1.8 bits per token at \( \gamma = 4.2 \) characters per token. Model Q reaches 1.4 bits per token at \( \gamma = 3.0 \). Which compresses a 1 GB text file smaller?
Per character, P spends \( 1.8/4.2 = 0.429 \) bits and Q spends \( 1.4/3.0 = 0.467 \) bits. On \( 10^9 \) characters that is \( 4.29\times10^8 \) bits \( = 53.6 \) MB for P against \( 4.67\times10^8 \) bits \( = 58.4 \) MB for Q.
P wins, though its per-token loss is the worse of the two by a wide margin. The comparison people actually make — 1.4 against 1.8 — gets the answer backwards, because a token is not a fixed amount of text. This is trap class T4 wearing a compression costume: the number moved, but so did the ruler.
(a) A model scores 1.6 bits per token at \( \gamma = 3.8 \). Give its bits per character, and the compressed size of a 40 GB corpus. (b) A tokenizer is improved so \( \gamma \) rises from 3.8 to 4.4 while bits per token rises from 1.6 to 1.8. Did the model get better or worse at compressing text?
(a) \( 1.6/3.8 = 0.421 \) bits per character; \( 4\times10^{10} \times 0.421 / 8 = 2.11\times10^9 \) bytes, about \( 2.1 \) GB. (b) Better: \( 1.8/4.4 = 0.409 \) bits per character against \( 0.421 \). The per-token figure got worse and the thing that matters got better, because each token now carries more text.
A subtler costume: how many bits does a single weight cost? If we transmit weights not as exact numbers but as a distribution — a posterior \( \mathcal{N}(\mu, \sigma_q^2) \) against a shared prior \( \mathcal{N}(0, \sigma_p^2) \) — the cost is the Kullback–Leibler divergence between them,
\[ D_{\mathrm{KL}} = \ln\frac{\sigma_p}{\sigma_q} + \frac{\sigma_q^2 + \mu^2}{2\sigma_p^2} - \frac{1}{2} \quad\text{nats}. \]Three readings of this formula matter more than the formula itself. When the posterior equals the prior (\( \sigma_q = \sigma_p = 1, \mu = 0 \)), the cost is exactly zero: a weight you have learned nothing about is free. As \( \sigma_q \to 0 \) the first term diverges: infinite precision costs infinite bits. And a weight the network is content to leave noisy — large \( \sigma_q \) — is a cheap weight.
Three weights, three prices
Take a shared prior of \( \sigma_p = 1 \) and price three weights the network might want.
One it has learned nothing about (\( \mu = 0 \), \( \sigma_q = 1 \)): \( \ln 1 + \frac{1 + 0}{2} - \frac12 = 0 \) nats. Free, exactly.
One it is mildly confident about (\( \mu = 0.5 \), \( \sigma_q = 0.5 \)): \( \ln 2 + \frac{0.25 + 0.25}{2} - \frac12 = 0.693 + 0.25 - 0.5 = 0.443 \) nats.
One it insists on (\( \mu = 0.5 \), \( \sigma_q = 0.01 \)): \( \ln 100 + \frac{0.0001 + 0.25}{2} - \frac12 = 4.605 + 0.125 - 0.5 = 4.23 \) nats — nearly ten times the mild one, for a weight in the same place with the same mean.
The whole bill is in the first term, \( \ln(\sigma_p/\sigma_q) \), and it diverges as \( \sigma_q \to 0 \). Precision, not magnitude, is what a description-length penalty charges for, which is why such a penalty produces a model that is confident about a few things and vague about most.
Students routinely get this backwards, assuming a noisy weight must be costly. The reverse is true, and the reversal is the mechanism: because precision costs bits, a network under a description-length penalty buys precision only where precision buys accuracy, and lets every other weight stay blurry. That is how such a penalty produces simple models — not by removing weights, but by declining to pay for their exactness.
Compute the coding cost for \( \sigma_p = 1 \), \( \sigma_q = 0.1 \), \( \mu = 0.5 \), in nats and in bits. (Use \( \ln 10 = 2.303 \), and 1 nat = 1.4427 bits.)
\( \ln(1/0.1) + \frac{0.01 + 0.25}{2} - 0.5 = 2.303 + 0.13 - 0.5 = 1.933 \) nats \( = 1.933 \times 1.4427 = 2.79 \) bits.
Now the deepest costume. Chapter 1 introduced the Kraft inequality: a set of prefix-free descriptions with lengths \( \ell_i \) satisfies \( \sum_i 2^{-\ell_i} \le 1 \). Read in reverse, this licenses treating \( 2^{-\ell} \) as a probability assigned to a description of length \( \ell \). That single move converts a preference for simplicity into a consequence of probability theory.
Here is the step that surprises people. We are about to conclude that shorter explanations are more probable — not as a working assumption, not as a scientific convention, but as an arithmetic consequence. If that sounds like it must be smuggling something in, look carefully at what actually gets assumed. It is only that descriptions are written in a code no description of which is a prefix of another. Everything else follows.
Every extra bit halves the vote
Suppose several programs are each perfectly consistent with the data observed so far, so their likelihoods are all 1. Under the prior \( P(p) = 2^{-\ell(p)} \), their posterior weights are proportional to \( 2^{-\ell} \). Comparing two programs of lengths \( \ell_1 < \ell_2 \), their posterior ratio is \( 2^{\ell_2 - \ell_1} \): each additional bit of description length halves a program's share of belief. No preference for simplicity was assumed; it fell out of the length prior.
To predict, mix the programs by their weights. Take three consistent programs of lengths 8, 12, and 20 bits, predicting the next bit as 1, 0, and 1 respectively. Scale all weights by \( 2^{20} \) to work in integers: they become \( 2^{12} = 4096 \), \( 2^{8} = 256 \), and \( 1 \), totaling 4353. The programs predicting 1 hold \( 4096 + 1 = 4097 \), so
\[ P(\text{next bit} = 1) = \frac{4097}{4353} = 0.941. \]The 20-bit program holds \( 1/4353 = 0.023\% \) of the belief — twelve extra bits have reduced it by a factor of 4096. Equal fit does not mean equal belief.
In the setting above, suppose the shortest program were 16 bits instead of 8 (others unchanged). Recompute \( P(\text{next bit} = 1) \).
Weights scaled by \( 2^{20} \): \( 2^{4} = 16 \), \( 2^{8} = 256 \), \( 1 \); total 273. Programs predicting 1 hold \( 16 + 1 = 17 \), so \( P = 17/273 = 0.062 \) — now below one half, because the 12-bit program predicting 0 has become the shortest.
A short but sharp idea. Consider the set \( M \) of all 10,000-bit strings containing exactly 5,000 ones. Its size is \( \binom{10000}{5000} \), and by the approximation of Chapter 1, \( \log_2\binom{2n}{n} \approx 2n - \tfrac12\log_2(\pi n) \), which here gives about 9,993 bits: specifying a member takes nearly the full 10,000 bits, so a typical member is essentially incompressible.
Now take the alternating string \( 0101\ldots01 \). It belongs to \( M \) — it has exactly 5,000 ones. Yet its description length is tiny: “print 01 five thousand times” is a few dozen bits. Its randomness deficiency — the gap between the bits a typical member needs and the bits this member actually needs — is nearly maximal, about 9,993 bits. The string satisfies every constraint the model imposes and is nonetheless an outrageous thing for that model to produce. Membership in a model is not typicality under it, and conflating the two is how one fails to notice a black swan.
A member that no model would produce
Take \( M \), the set of 10,000-bit strings with exactly 5,000 ones, and compare two of its members.
A typical member: by Chapter 1's approximation, \( \log_2\binom{10000}{5000} \approx 2n - \tfrac12\log_2(\pi n) \) with \( n = 5000 \), giving \( 10{,}000 - \tfrac12\log_2(15{,}708) = 10{,}000 - 6.97 \approx 9{,}993 \) bits. Specifying it takes essentially the full 10,000 bits; it is incompressible.
The alternating string \( 0101\ldots01 \): also in \( M \), and describable in a few dozen bits. Its randomness deficiency — what a typical member costs minus what this one costs — is about \( 9{,}993 \) bits, very nearly the maximum possible.
Both satisfy every constraint the model imposes. One is what the model is about; the other is an outrage the model cannot rule out. Membership is not typicality, and a model that only checks membership has no way to notice the difference.
Grokking. A network trained on a rule-like task sometimes memorizes first and only much later — abruptly — discovers the rule that generalizes. In code-length terms this is unmysterious. The arithmetic is in the box below. Both solutions sit at zero training error, so the training loss is silent about the transition — but the description length is not, and neither is the test accuracy. Delayed generalization is a search finding the short code late.
Grokking, in bits
A network memorizes 1,000 training examples at 10 bits each: \( 10{,}000 \) bits of model. Later it finds the rule that generates them, which costs \( 500 \) bits. Both encodings leave zero residual — both fit the training data exactly — so the training loss cannot tell them apart, and does not.
\[ \frac{10{,}000}{500} = 20\times \ \text{compression, at unchanged training error.} \]The description length fell by a factor of twenty while the quantity being optimized did not move at all. That is why the transition looks sudden and unmotivated on a loss curve and is neither: the search was always running, over a space in which short codes are rare and therefore found late.
Double descent. Classical wisdom says test error traces a U as model size grows. Modern practice sees it fall, rise to a peak, and fall again past the point where the model can interpolate the training data. The peak is quantifiable. For least squares with \( p \) parameters and \( n \) samples (\( p < n-1 \)) at noise variance \( \sigma^2 \), the expected excess test risk is \( \sigma^2 p/(n-p-1) \) — take this as given. As \( p \to n-1 \) the denominator vanishes and the risk diverges: at the interpolation threshold there is effectively one interpolating solution, and it is maximally sensitive to noise. Past the threshold many interpolating solutions exist, an optimizer biased toward small norm can select a simple one, and the risk falls again.
The approach to the threshold
With \( n = 100 \) samples and \( \sigma^2 = 1 \), compare the excess risk at \( p = 50 \) and \( p = 90 \). At \( p = 50 \): \( 50/(100-50-1) = 50/49 = 1.02 \). At \( p = 90 \): \( 90/(100-90-1) = 90/9 = 10 \). The ratio is 9.8. Adding parameters near the threshold is not mildly harmful; it is catastrophic — and yet pushing further past it recovers.
The chapter's last costume applies description length to agents rather than models. If we score an agent's performance \( V_i \in [0,1] \) across many environments, how should the environments be weighted? Weighting each by \( 2^{-K_i} \), where \( K_i \) is the environment's description complexity, gives
\[ \Upsilon = \sum_i 2^{-K_i} V_i. \]Three properties follow immediately. By Kraft, \( \Upsilon \le 1 \) for any agent. An agent competent only in very complex environments scores near zero, because \( 2^{-K} \) decimates them: Occam is built into the definition of intelligence itself. And adding one bit to every environment's complexity halves \( \Upsilon \) exactly.
Scoring an agent, and a caution about rewards
An agent scores \( V = 0.5, 0.9, 0.3 \) in environments of complexity \( K = 1, 2, 3 \) bits. Then \( \Upsilon = \tfrac12(0.5) + \tfrac14(0.9) + \tfrac18(0.3) = 0.25 + 0.225 + 0.0375 = \) 0.51.
A related calculation, using Chapter 1's geometric series, prices a temptation. An agent discounting the future at \( \gamma = 0.95 \) values a perpetual per-step reward \( r \) at \( \gamma r/(1-\gamma) = 19r \). This beats a one-time reward of 1 whenever \( r > 1/19 = \) 0.053. A trickle worth barely five percent of the one-off prize is already preferable — which is why an agent able to seize its own reward channel finds doing so overwhelmingly attractive, and why the reward source must be kept outside the agent's control.
Everything above was the same sentence in different clothes: total code length decides. It selects models and exposes overfitting as arithmetic; it makes cross-entropy a literal file size; it prices a weight's precision and thereby explains how simplicity is bought; it converts Occam's razor from a preference into a theorem via the length prior; it distinguishes membership from typicality; and it dissolves grokking and double descent into statements about which code is short and how many solutions exist. Part II ends here. Part III turns to the modern era, and it opens with a shift in what is scarce: not the compute to train a model, but the bytes and bandwidth to serve one.
A · Drills
B · Problems
C · Challenge
Reproduce Derivation 10.1 (the length prior, its halving rule, and a mixture prediction) on blank paper. Work Worked Example 10.1 from a blank table and B-1 closed book. Then, as the Part II capstone, sweep the whole Derivation Bank so far — every result from Chapters 3 through 10 — reproducing each from nothing. Part III assumes all of it.