Entropy
How many bits we need to pay per token
Entropy is one of the most important concepts for machine learning and information theory. I like to think of it as the minimum number of bits needed, on average, to encode an element of a sample space. Claude Shannon established its mathematical foundations in his 1948 paper A Mathematical Theory of Communication. For our purposes, we consider a distribution over symbols (in our case, tokens), given the preceding tokens as context. [3, Sections 6 and 9]
Let P be the true distribution of the next token, given its context. An outcome with probability p carries −log₂ p bits of information: a likely outcome is less surprising, while a rare outcome takes more information to specify.
Entropy is that information averaged over what actually occurs. It sets the minimum expected cost per token of a lossless description when the decoder has the same context. An ideal code can approach this limit over long sequences; an individual token need not cost exactly its entropy.
Two equally likely outcomes have entropy 1 bit. An outcome known with certainty has entropy 0. Importantly, recognize that this is an average over many outcomes, not a promise to transmit a fraction of a physical bit on its own. [1]
Example: sending directions to a rover
Adapted from 3Blue1Brown’s Reinventing Entropy: send a rover one of four movement commands. Suppose successive commands are independent, with up occurring half the time, down a quarter, and left and right an eighth each. [4]
| Command | Probability | Code | Bits |
|---|---|---|---|
| ↑ Up | ½ | 0 | 1 |
| ↓ Down | ¼ | 10 | 2 |
| ← Left | ⅛ | 110 | 3 |
| → Right | ⅛ | 111 | 3 |
Four equally sized codes would cost 2 bits per command. This prefix code is unambiguous: no complete code is the start of another. Its lengths match each command’s information cost, so the expected length equals entropy:
We pay 1 bit for a common up command and 3 for a rare left or right command, averaging 1.75 bits per command. That saves 0.25 bits per command on average compared with a fixed 2-bit code. Left and right together have probability ¼.
Cross-entropy
How many bits we actually expect to pay per token
We usually do not know P. A model supplies its estimate Q. For an autoregressive model, this is Q(x_n \mid x_1,\ldots,x_{n-1}): the probability of the next token given all preceding tokens. We describe that token using the model’s ideal cost, -\log_2 Q(x_n \mid x_1,\ldots,x_{n-1}), but average over tokens drawn from the true conditional distribution P. That gives conditional cross-entropy. The formula below leaves the shared context implicit.
Predictive training minimizes this same negative log-probability. It doesn’t actually matter here if the natural logarithm is used, since dividing the loss by the constant ln(2) converts it to bits without changing the location of the minimum. The paper connects this objective directly to expected encoded length. [2, Section 2: Likelihood Maximization]
Same rover, a slightly worse encoding
The rover still moves up with probability ½, down with ¼, and left and right with ⅛ each. But our model gets up and down backwards: Q gives up probability ¼ and down probability ½. Its code therefore spends 2 bits on the most common command and just 1 bit on the less common down command.
| Command | True P | Model Q | Code | Bits |
|---|---|---|---|---|
| ↑ Up | ½ | ¼ | 10 | 2 |
| ↓ Down | ¼ | ½ | 0 | 1 |
| ← Left | ⅛ | ⅛ | 110 | 3 |
| → Right | ⅛ | ⅛ | 111 | 3 |
Average those code lengths using how often each command actually occurs—not how often the model thinks it occurs:
The cross-entropy is 2 bits per command, compared with entropy of 1.75 bits. We pay an extra 0.25 bits per command on average because our model’s predictions are worse. Both codes recover the exact commands; the mismatch costs efficiency.
KL divergence
When Q = P, cross-entropy equals entropy.
The difference between cross-entropy and entropy has a scary name: KL divergence. Really, it just measures the extra expected bits from using Q instead of P.
H(P,Q) = H(P) + D_{\mathrm{KL}}(P\Vert Q)
You might have learned KL divergence as a sum or integral involving a log ratio. Let’s expand cross-entropy minus entropy to see why the formulas are the same:
KL divergence is nonnegative and reaches zero when the distributions match. The best possible model therefore has H(P, P) = H(P): no avoidable extra cost. [1]
A limited model family may not be able to represent P exactly because of its capacity or structural assumptions. Regularization can also favor simpler predictions over an exact match. In practice, the best achievable model may therefore still have positive KL divergence. [5]
Same data, different predictions
The data has P(A) = 75%, P(B) = 25%. Change the model’s probability of A.
Blue is the data’s entropy; red is the extra expected cost of a mismatched model. The scale stays fixed.
What does the red bar measure?
In this example, red is the extra cost of a mismatched model: cross-entropy minus the data’s entropy. The demo’s red segment instead compares UTF-8 encoding with model encoding, as explained below.
For a uniform code U over the same alphabet of V tokens, each token costs log₂ V bits. If our model Q is perfect, the expected difference is:
The order matters: H(Q, U) averages the uniform code’s cost over Q’s outcomes. It is not H(U, Q), which asks how Q encodes uniformly distributed data. This follows from the entropy and mismatch relationship above. [1]
Our demo compares UTF-8 bytes with variable-length GPT-2 tokens, rather than two codes over the same token alphabet. Its red segment is the observed UTF-8 bit count minus the model’s illustrated information cost, when positive. It is not a direct measurement of entropy or KL divergence. If the model costs more, the red segment is zero; the UTF-8 total remains visible.
Arithmetic Coding
Arithmetic coding turns probability into an interval.
Start with [0, 1). Split it into ordered slices, one per possible token, with widths proportional to the model probabilities. Keep the slice for the token that actually occurred. Predict again using the updated context, then subdivide the kept interval.
The encoded value is a binary fraction, written 0.b_1b_2b_3\ldots{}_2: a point in [0, 1). The first digit contributes ½, the second ¼, the third ⅛, and so on. For example, 0.1_2=0.5 and 0.11_2=0.75. More digits let us place the point more precisely.
While encoding, maintain both the selected interval and a candidate point. For each next token, divide the current interval according to the model probabilities and select that token’s subinterval. Check whether the point lies inside it. If it does, keep the fraction unchanged. If it does not, use more binary digits to choose a point inside the narrower interval. The fraction shown during encoding is provisional: increasing precision can also revise earlier digits until the final code is chosen. Repeat with the model context updated by the token being encoded.
For a simple perfect model, suppose A, B, and C have probabilities ½, ¼, and ¼ at every position. Encoding BAC gives these successive bounds:
For BAC, start with 0.1_2=0.5 inside B’s interval. That point also lies inside BA’s interval, so A needs no new digits yet. C selects [0.59375, 0.625), which excludes 0.5. Extend the fraction to 0.10011_2=0.59375, now inside BAC’s interval. We maintain one point that falls within all the selected intervals.
During decoding, keep the final point fixed. Regenerate the token subintervals from the same model and context, recover the token whose interval contains the point, then repeat inside that interval. The token count tells us when to stop.
Best predictor → best compressor
The best model minimizes expected next-token bits.
The encoded bitstring uniquely determines the selected interval at every step, allowing the decoder to recover the tokens.
At each step, the interval shrinks by a factor of Q(x\mid c), where c is the preceding context. Narrowing the interval by that factor therefore adds -\log_2 Q(x\mid c) bits of information: the ideal additional cost of encoding the next token’s interval. Halving the width costs 1 ideal bit; reducing it to a quarter costs 2. Arithmetic coding shares these costs across the bitstream, with a small termination overhead per sequence. [2, Arithmetic Coding]
To minimize the expected cost of the next token, average over the true next-token distribution P. By the definition of expectation, these objectives have the same minimizing model:
When averaging log loss over a fixed sequence of n tokens, the factor 1/n is a positive constant independent of the model, so minimizing the average is equivalent to minimizing the sum.
So minimizing expected next-token bits is exactly minimizing conditional cross-entropy. As shown above, it reaches its minimum when Q=P, a perfect predictive model. Therefore, the perfect predictor minimizes the expected encoding cost of the next token.
Best predictor ← best compressor
Compressed lengths can become predictions.
We can easily reverse our logic to go the other way. For an ideal code, minimizing expected bits per token means minimizing cross-entropy, whose minimum occurs once again when Q=P.
This implies that the perfect compression algorithm can be transformed into the perfect predictor. Let’s do that.
Suppose we have the prefix Hello and want to score possible next tokens. For each candidate c, compare the compressed length of the prefix with the length after appending c. Call the difference \Delta L(c).
The ideal bit-cost rule is \ell=-\log_2 p. Reversing it gives p=2^{-\ell}, so each length increment gives a weight 2^{-\Delta L(c)}. Every extra bit halves the weight. For a perfect ideal code, these weights are already the next-token probabilities and sum to one. As a caveat, real compressors store whole bits and add overhead, so measured weights may not sum to one. Dividing each weight by their total turns them into probabilities.
| Next token | Extra bits | Weight | Normalized prediction |
|---|---|---|---|
| space | 1 | ½ | 50% |
| ! | 2 | ¼ | 25% |
| x | 2 | ¼ | 25% |
If a more probable next token is cheaper to encode, that cheaper encoding lets us recover its higher probability.
Sources
[1] Stanford EE 376A: Entropy and Neg-log Likelihood — entropy, coding bounds, and the penalty for a mismatched distribution.
[2] Delétang et al., Language Modeling Is Compression, ICLR 2024 — prediction/compression equivalence, arithmetic coding, likelihood maximization, compression-derived prediction, and model-size accounting. PDF · Authors’ code.
[3] Claude E. Shannon, A Mathematical Theory of Communication (1948) — the foundations of information theory, entropy in bits (Section 6), and the source-coding limit (Section 9).
[4] 3Blue1Brown (Grant Sanderson), Reinventing Entropy | Compression is Intelligence Part 1 — the four-direction robot example connecting probabilities, code lengths, and entropy.
[5] Goodfellow, Bengio, and Courville, Deep Learning, Chapter 7 — limited model families, regularization, and the bias–variance tradeoff.
GPT-2 is not a perfect model. This page assumes perfection to explain the optimum; the demo uses real, imperfect model probabilities and finite integer intervals.