How LLMs work · Prediction, compression and intelligence · Lesson 3

Compression is prediction

You’ll build the machine that turns any predictor into a compressor and see why the file size comes out equal to the predictor’s total surprise.

The whole-bit problem

Last lesson, sun / cloud / rain at $\tfrac12, \tfrac14, \tfrac14$ got a perfect code: 0, 10, 11. That worked because every probability was a power of $\tfrac12$, so every surprise was a whole number of bits.

Real predictions aren’t like that. A language model might give the next token probability $0.9$. Its surprise is $-\log_2 0.9 \approx 0.15$ bits, but a code that hands each symbol its own string of bits can’t spend less than 1 whole bit on anything. When the model is confident, which is most of the time, that wastes almost all of its skill.

A model gives the actual next symbol probability 0.99 a thousand times in a row. A one-codeword-per-symbol code spends at least 1,000 bits. About how many bits does the surprise say the message is worth?

Each symbol is worth $-\log_2 0.99 \approx 0.0145$ bits. Times 1,000 that’s about 14.5 bits. A whole-bit code wastes about 98.5% of the space here. That’s the gap arithmetic coding closes.

The trick: a message is a slice of [0, 1)

Arithmetic coding doesn’t give each symbol its own bits. It encodes the whole message as one number between 0 and 1.

Start with the interval from 0 to 1.
Ask the model for its probabilities for the next symbol. Cut the current interval into slices whose widths are proportional to those probabilities.
Keep the slice for the symbol that actually happened. That slice becomes the new interval.
Repeat for every symbol. At the end, send any short binary number that lies inside the final interval.

Each step multiplies the width by the probability of what happened. A likely symbol barely shrinks the interval. A surprising one shrinks it a lot.

Watch it shrink

Tap the weather day by day. Each row is the interval so far, stretched to full width, with the model’s slices inside it. Then switch models and see what happens to the bill for the same message.

Try the example week with each model. Know-nothing pays $\log_2 3 \approx 1.58$ bits every day, whatever happens. Climate pays less on sunny days and more on rainy ones. Same-as-yesterday wins because real weather comes in runs. Same message, different predictor, different file size.

A model gives the actual symbols probabilities $0.5$, then $0.6$, then $0.2$. How wide is the final interval?

Each step multiplies the width by the probability of what happened: $1 \times 0.5 = 0.5$, then $0.5 \times 0.6 = 0.3$, then $0.3 \times 0.2 = 0.06$.

Why width means bits

A binary fraction with $k$ digits after the point, like $0.0111_2$, pins down a slot of width $2^{-k}$. To land a slot inside an interval of width $w$, you need about $k = -\log_2 w$ digits (plus one or two to be safe).

Now the final width is the product of the probabilities:

$$w = p_1 \times p_2 \times \cdots \times p_n$$

and the log of a product is the sum of the logs, so

$$-\log_2 w = (-\log_2 p_1) + (-\log_2 p_2) + \cdots + (-\log_2 p_n).$$

That’s the total surprise. A symbol with probability 0.99 adds just 0.0145 bits. The fractions of a bit pile up across symbols and nothing is wasted.

A model gives the actual symbols probabilities $\tfrac12$, $\tfrac14$ and $\tfrac18$. About how many bits does arithmetic coding need (ignoring the 1–2 bit overhead)?

Surprises: $-\log_2\tfrac12 = 1$, $-\log_2\tfrac14 = 2$, $-\log_2\tfrac18 = 3$. Total $1 + 2 + 3 = 6$ bits.

Or by width: $\tfrac12 \times \tfrac14 \times \tfrac18 = \tfrac1{64} = 2^{-6}$, and $-\log_2 2^{-6} = 6$.

By hand, start to finish

Two symbols: A with probability $\tfrac34$ (the bottom of each interval), B with $\tfrac14$ (the top). Message: A A B.

Symbol	Interval	Width
start	$[0,\ 1)$	$1$
A	$[0,\ 0.75)$	$0.75$
A	$[0,\ 0.5625)$	$0.5625$
B	$[0.421875,\ 0.5625)$	$0.140625$

The B step keeps the top quarter of $[0, 0.5625)$. Its bottom is $0.75 \times 0.5625 = 0.421875$.

Ideal cost: $-\log_2 0.140625$. Since $0.140625 = \tfrac{9}{64}$, that’s $\log_2 64 - \log_2 9 = 6 - 3.17 = 2.83$ bits. Check it by surprises: $0.415 + 0.415 + 2 = 2.83$. ✓

Now find a short binary number whose whole slot fits inside. $0.0111_2 = \tfrac14 + \tfrac18 + \tfrac1{16} = 0.4375$, and its slot runs from $0.4375$ to $0.4375 + \tfrac1{16} = 0.5$. That sits inside $[0.421875, 0.5625)$. So the message is sent as the 4 bits 0111: 2.83 ideal plus about 1 of overhead.

Show how the receiver decodes 0111

The receiver has the same model, and knows the message is 3 symbols long. It reads $x = 0.4375$.

Is $x$ below $0.75$? Yes, so the first symbol is A. Stretch $[0, 0.75)$ back to $[0, 1)$: $x \to 0.4375 \div 0.75 = 0.5833$.
Is $0.5833$ below $0.75$? Yes, so A. Stretch: $0.5833 \div 0.75 = 0.7778$.
Is $0.7778$ below $0.75$? No, so B.

Out comes A A B. It’s the guess-count trick from Lesson 1 again: an identical predictor on the other end replays the same probabilities, so only the surprises have to travel.

The sender compresses with a great model, and the receiver decodes with a slightly different one. What happens?

Decoding asks “which slice is $x$ in?”, and the slices come from the model’s probabilities. Different probabilities give different slice boundaries, and after the first mismatch every later symbol is garbage. Sender and receiver must share the exact same predictor.

And the other way round

Any compressor also contains a predictor. If a code spends $\ell$ bits on some symbol, it’s acting as if that symbol has probability $2^{-\ell}$. Give something 3 bits and you’ve implicitly called it a 1-in-8 event. So “the best compressor” and “the best predictor” are the same object described two ways.

This isn’t just theory. In 2023 a DeepMind team (Delétang et al., “Language Modeling Is Compression”) plugged large language models into an arithmetic coder. Chinchilla 70B, trained mostly on text, compressed ImageNet image patches to 43.4% of their raw size and LibriSpeech audio to 16.4%, beating PNG (58.5%) and FLAC (30.3%), which were designed for those jobs. The catch: that doesn’t count the model itself, which is vastly bigger than the data. Lesson 6 comes back to why that matters.

A compressor always spends 3 bits on the word “the”. What probability is it implicitly giving “the”?

$\ell$ bits means probability $2^{-\ell}$: $2^{-3} = \tfrac18 = 0.125$.

Check

Two models compress the same 1 MB of English. Model X averages 2.1 bits per character, model Y 1.4. Which made the better predictions, and how do you know?

With arithmetic coding, bits per character is the model’s average surprise, $-\log_2 p$ of what actually came next. Lower surprise means higher probability on the truth, which is exactly what better prediction means.

An arithmetic coder’s interval has width $0.5$. The model gives the next actual symbol probability $0.5$. What’s the new width?

Multiply the width by the probability of what happened: $0.5 \times 0.5 = 0.25$. That’s 2 bits of total surprise so far: $-\log_2 0.25 = 2$.

Why does arithmetic coding beat a code that gives each symbol its own bit string, like 0 / 10 / 11?

Separate codewords cost at least 1 bit each. Arithmetic coding multiplies widths across the whole message, so a symbol with probability 0.99 costs 0.0145 bits. It’s lossless: nothing is thrown away.

In your own words: why is a better next-symbol predictor automatically a better compressor?

Arithmetic coding shrinks an interval by the probability of each actual symbol, and the bits needed are $-\log_2$ of the final width, which is the sum of $-\log_2 p$ over the message: the model’s total surprise. A model that puts more probability on what actually happens has less total surprise, so the file is smaller. (And any code implies probabilities $2^{-\ell}$, so the link runs both ways.)