Prediction is compression

Any model that assigns probabilities to data can be turned into a lossless compressor, and any lossless compressor implies a probability model. This equivalence is exact, not a metaphor. It explains why a language model's training loss is literally a file size, and why "compresses well" and "predicts well" are the same claim.

From probabilities to code lengths and back

A prefix code assigns each symbol a binary codeword such that no codeword is the beginning of another, so a concatenated stream decodes without separators. The Kraft inequality says that codeword lengths $\ell(x)$ are achievable by some prefix code if and only if

Read the inequality in both directions:^[1]

• Code to model. Any prefix code defines a (sub-)probability distribution $q(x) = 2^{-\ell(x)}$. Short codewords are implicit claims that a symbol is likely.
• Model to code. Any distribution $q$ yields lengths $\ell(x) = \lceil -\log_2 q(x)\rceil$ that satisfy Kraft. The expected length is within one bit of the cross-entropy $H(p,q)$.

So designing a compressor and choosing a probability model are the same problem. The expected cost of coding data from $p$ with model $q$ is $H(p) + D_{\mathrm{KL}}(p\|q)$ bits, as derived in Cross-entropy and KL divergence. A better predictor is a shorter code, bit for bit.

Arithmetic coding removes the rounding

Symbol-by-symbol codes lose up to a bit per symbol to the ceiling in $\lceil -\log_2 q\rceil$. That loss is ruinous when a good predictor assigns 0.99 to the next symbol, which deserves only 0.015 bits. Arithmetic coding avoids it by encoding a whole sequence as a single number in $[0,1)$. It encodes $x_1,\dots,x_n$ in at most about two bits more than the ideal $-\log_2 q(x_1,\dots,x_n)$, and it works with adaptive models whose probabilities change at every step.^[2][1]

Worked example

Use a fixed model over three symbols: $q(\text{A})=0.6$, $q(\text{B})=0.3$, $q(\text{C})=0.1$. Encode the message AAB.

1. Start with $[0, 1)$. Split it in proportion to $q$: A gets $[0, 0.6)$, B gets $[0.6, 0.9)$ and C gets $[0.9, 1)$. The first symbol is A, so keep $[0, 0.6)$.
2. Split $[0, 0.6)$ the same way: A gets $[0, 0.36)$. Keep it.
3. Split $[0, 0.36)$: A gets $[0, 0.216)$, B gets $[0.216, 0.324)$ and C gets $[0.324, 0.36)$. Keep B's interval, $[0.216, 0.324)$.

The final interval has width $0.6\times0.6\times0.3 = 0.108$, so the ideal code length is $-\log_2 0.108 \approx 3.21$ bits. To transmit it, send a short binary fraction whose whole dyadic interval fits inside. The four bits 0100 represent $[0.25, 0.3125)$, which lies inside $[0.216, 0.324)$, so the message costs 4 bits. A fixed-length code for a three-symbol alphabet needs 2 bits per symbol, or 6 bits in total. The decoder, holding the same model, repeats the same interval splits and recovers AAB.

Nothing in the procedure requires the probabilities to be fixed. At step $t$ the interval can be split using any conditional $q(x_t\mid x_{<t})$, provided the decoder can compute the same one. That is exactly what an autoregressive language model supplies.

The training loss is a file size

By the chain rule of probability, the code length of a whole sequence under an autoregressive model is a sum of per-token terms:

The right-hand side is the language-model loss (in bits) summed over the sequence. A model with a validation loss of 0.8 bits per byte, plugged into an arithmetic coder, compresses that validation text to about 10% of its raw size (0.8 of 8 bits). The only extra cost is the coder's small constant overhead. Lowering the loss and shrinking the compressed file are the same goal.

Delétang and colleagues took this equivalence literally. They connected pretrained language models to an arithmetic coder and measured compression on 1 GB datasets. Chinchilla 70B, trained primarily on text, compressed ImageNet image patches to 43.4% of raw size and LibriSpeech audio to 16.4%. Those figures beat the domain-specific compressors PNG (58.5%) and FLAC (30.3%).^[3] Their inputs were chunked into 2,048-byte sequences, and the comparison was also reported against the classical compressors run on unchunked data.

The model has to be paid for too

The raw figures above leave out the size of the model, which the decoder also needs. Delétang et al. report an adjusted compression rate that adds the parameter bytes, in a two-part code. On this measure, the large pretrained models do badly on 1 GB datasets. At two bytes per parameter, Chinchilla 70B's weights alone take about 140 GB, far more than the data. In experiments with smaller Transformers trained on Wikipedia text, they also found that, for a fixed dataset, increasing model size helps only up to a point. Beyond it, the parameter cost outweighs the gain in prediction, so dataset size limits the useful model size.^[3]

This is the minimum description length (MDL) principle, which Rissanen formalised in 1978: choose the model that minimises the bits needed to describe the model plus the bits needed to describe the data given the model.^[4] MDL turns Occam's razor into accounting. A model that memorises its data has a long first part, while a model too simple to capture regularities has a long second part.

There is a less obvious way to pay for the model. In incremental (online) coding, the sender and receiver train identical models from the same starting point. Each new block of data is coded with the model trained on all previous blocks, so the parameters never have to be transmitted. Blier and Ollivier showed that deep networks compress their training data well under this scheme even after accounting for model cost. Variational bounds designed for the same purpose gave surprisingly poor results.^[5] On this view, a training run that learns quickly is itself a short description of its data.

What the equivalence does and does not say

The equivalence is exact for log-loss: every bit of cross-entropy improvement is a bit of compression. Several popular extensions go further than the mathematics supports:

• Compression is not the deployment objective. A better compressor of the pretraining distribution is not automatically better at a downstream task, at following instructions, or at being truthful. Those depend on what parts of the distribution matter and on post-training.
• Compute is free in the accounting. A 70-billion-parameter model is a very slow compressor. The code-length equivalence ignores runtime, which is why practical compressors use small models.
• The floor is unknown. No one knows the true entropy of natural text, so a compression rate on its own does not say how much structure remains to be learned.

The equivalence is still the clearest single account of what pretraining optimises. Making next-token prediction more accurate is the same as finding a shorter description of the data, and short descriptions are possible only when the data have exploitable structure. The same accounting reappears in Generalization, where the question is which of many perfect fits to trust.

Key takeaways

• The Kraft inequality makes prefix codes and probability distributions interchangeable. Code length $\approx -\log_2 q(x)$.
• Arithmetic coding turns any sequential predictor into a compressor within about two bits of $-\log_2 q(x_{1:n})$, and it works with adaptive, context-dependent probabilities.
• A language model's summed training loss in bits is the compressed size of the data under that model.
• Pretrained LLMs compress even non-text data well when parameter cost is ignored. Counting parameters (MDL) reverses the picture for small datasets.
• Incremental coding pays for the model through the cost of learning, which links fast learning, short descriptions and generalization.

Sources