Compression Is Prediction Is Intelligence — LLMs Through Information Theory

Training a model to guess the next token is training it to shrink a file. Route the prediction through arithmetic coding and "probability model" and "code" turn out to be the same object — which makes cross-entropy loss literally the size of the compressed output. Built up from zero, ending at why the Hutter Prize treats compression ratio as an intelligence test.

Language Modeling Is Compression

If you can finish the sentence, you don't need to hear it

Hand someone the phrase "a foregone conclu___" and any English speaker fills in "sion." Which means those letters never needed to be sent. The receiver can regenerate them.

Now try to write "a foregone conclusion is a kumquat." That last word can't be dropped. Nobody would have guessed it.

That's the whole of compression, right there. Anything predictable doesn't need to be transmitted. Only the unpredictable part does. Real language, though, isn't a binary of "certain" versus "no idea." It sits in between: the next character is "s" with 90% probability, something else with 10%. If we could convert that fractional confidence into a fractional number of bits — without rounding — then the compression ratio would be determined by nothing but the quality of the prediction.

The conversion is called arithmetic coding, and the best predictor we currently have is a large language model. This article walks a single straight line to one conclusion: the cross-entropy loss you train an LLM with is the size of the compressed file, in different units.

Code length is the log of a probability

First, a bridge between "how sure the prediction is" and "how many bits."

Sending the result of a coin flip costs one bit; each outcome has probability $1/2$. Sending the face of a 1024-sided die costs ten bits ($2^{10} = 1024$); each face has probability $1/1024$. Line those up and the pattern is visible. The number of bits you need is the log of one over the probability.

Here $p(x)$ is the probability of the event and $\ell(x)$ is the number of bits it takes to convey it. Read it in words and it says: common things get written short, rare things get written long. The minus sign is bookkeeping — $\log_2 0.5 = -1$, so flipping the sign turns a negative log into a positive bit count.

What matters is that this runs in both directions. Given probabilities, code lengths follow. Given an assignment of code lengths, you can recover a probability distribution from it — Kraft's inequality guarantees as much. So a probability model and a code are two names for the same thing. If you have built a good predictor, you have already built a good compressor. All that's missing is the machinery to convert mechanically between the two.

Seeing the correspondence also dissolves a recurring argument about compression. When someone says "our compressor doesn't use a model," what they have is a probability model in the shape of a code table. There is no such thing as a compressor without one.

Seen this way, the entropy $H(p) = -\sum_x p(x)\log_2 p(x)$ is "the average number of bits when you use the best possible predictor." Shannon showed this is a floor — no cleverness in code design gets you below it. (See Information Theory for AI for the derivation.)

Arithmetic coding: carving up an interval

One problem. $-\log_2 p(x)$ is almost always fractional. An event with probability 0.9 costs about 0.152 bits — and you cannot write 0.152 bits into a file.

A "one symbol, one bit string" scheme like Huffman coding charges you a minimum of one whole bit no matter how confident you are. One bit where 0.152 would do: more than 6× wasted.

Arithmetic coding escapes this by refusing to chop the output up per symbol. All it does is carve an interval.

1. Start with $[0, 1)$
2. Give each symbol a slice whose width is proportional to its probability
3. Narrow to the slice of the symbol that actually arrived, and repeat inside it
4. At the end, write out one number that lies inside the surviving interval, in binary

Concretely: three symbols A (probability 0.5), B (0.3), C (0.2), and we want to send BA. Split $[0,1)$ into A: $[0,\ 0.5)$, B: $[0.5,\ 0.8)$, C: $[0.8,\ 1)$. The first symbol is B, so narrow to $[0.5,\ 0.8)$, width 0.3. Split that by the same ratios and take A's slice: $[0.5,\ 0.65)$, width 0.15.

That final width of 0.15 is $0.3 \times 0.5$ — exactly the probability of the sequence BA. And the bits needed to pin down a number inside that interval come to roughly $-\log_2 0.15 \approx 2.74$. Practical implementations are known to add at most about two bits of overhead across the entire message.

So those 2.74 bits are B's share and A's share, each a fractional number of bits, summed without ever being rounded up. That is the decisive difference from Huffman coding, which throws away the remainder once per symbol. (For the head-to-head comparison, and for ANS, see Entropy Coding from Scratch.)

And one more property, which is the one that matters from here on. The probabilities used in step 2 are allowed to change at every step. You can rebuild the distribution based on everything seen so far, and decoding still works — as long as the encoder and the decoder run the same procedure and arrive at the same numbers.

Implementations have exploited this for decades. CABAC, the entropy coder in H.264 and H.265, updates its per-context probabilities as it encodes; because both sides run the same update rule, no probability table ever has to be transmitted. The coding framework itself hasn't changed in decades — what changed is what you plug into it.

And there is now an open socket where that "distribution rebuilder" goes.