I am thinking of a number from 1 to 8, and you may ask yes-or-no questions. Halving the range each time ("is it 4 or less?"), you need exactly 3 questions, and $3 = \log_2 8$. Now suppose you know I pick 1 half the time. Asking "is it 1?" first wins immediately half the time, and on average you need fewer questions. The more predictable the source, the fewer questions it takes.

That observation, made precise by Claude Shannon in 1948, is information theory. It is exactly the right language for machine learning. The cross-entropy loss that trains every classifier and every language model is an average number of questions. The KL divergence that keeps an RLHF policy close to its starting point is the extra questions you pay for using the wrong distribution. Perplexity, the headline number of language modeling, is the effective number of choices the model is torn between. This section builds all of them from one idea, surprise.

Surprise and entropy

How surprised should you be when an event of probability $p$ happens? Three properties pin down the answer. A certain event ($p = 1$) should carry no surprise. Rarer events should be more surprising. And the surprises of two independent events should add, so that seeing two unrelated things together is exactly as surprising as seeing each in turn. The only functions with these properties are multiples of $-\log p$, so we define the surprise (or information content) of an outcome $x$ as

With $\log_2$ the unit is the bit, and with the natural log it is the nat ($1 \text{ nat} = 1/\ln 2 \approx 1.443$ bits). Machine learning code uses nats, since np.log is natural, while papers about compression and tokenizers often report bits.

The entropy of a distribution is its average surprise,

with the convention $0 \log 0 = 0$ (impossible outcomes contribute nothing). In plain words, entropy measures how unpredictable a source is, the average number of yes-or-no questions (in bits) needed to pin down one draw.

A few values to anchor intuition. A fair coin has $H = 1$ bit. A coin that lands heads 90% of the time has $H = -0.9\log_2 0.9 - 0.1\log_2 0.1 = 0.469$ bits, less than half as unpredictable. A fair six-sided die has $\log_2 6 = 2.585$ bits. And in general a uniform distribution over $K$ outcomes has $H = \log K$, which is the largest entropy any distribution on $K$ outcomes can have (we prove it below). For continuous variables with a given mean and variance, the maximum-entropy distribution is the Gaussian, one reason it is the default assumption in §0.4.

Entropy is the best possible average code length

Shannon's source coding theorem makes the "questions" picture exact. Any lossless code for draws from $p$ needs at least $H(p)$ bits per draw on average, and there are codes that come within 1 bit of it (within a vanishing fraction per symbol, if you encode long blocks). The ideal code gives outcome $x$ a codeword of length $-\log_2 p(x)$, short codes for common outcomes.

Take four outcomes with probabilities $\tfrac12, \tfrac14, \tfrac18, \tfrac18$. Their surprises are 1, 2, 3, and 3 bits, and the prefix code 0, 10, 110, 111 uses exactly those lengths. The average length is $\tfrac12 \cdot 1 + \tfrac14 \cdot 2 + \tfrac18 \cdot 3 + \tfrac18 \cdot 3 = 1.75$ bits, which equals the entropy. A naive fixed-length code would use 2 bits for everything.

This link between probability and compression is not a curiosity. A language model is a compressor. Pair it with an arithmetic coder and it can encode text in about as many bits as its loss, which is why bits per byte (below) is a meaningful way to compare models.

Cross-entropy, the loss behind every classifier

Now suppose the data come from $p$, but you build your code (or your predictions) from a different distribution $q$. Each outcome $x$ costs you $-\log q(x)$, and the average cost is the cross-entropy

In plain words, cross-entropy is the average surprise of a model $q$ at data that actually come from $p$. In the example above, using the fixed-length 2-bit code amounts to $q$ uniform, and $H(p, q) = 2$ bits, a quarter of a bit more than the 1.75 of the ideal code.

In classification the "data distribution" for one example is the one-hot target $\mathbf{e}_y$, so the cross-entropy collapses to $-\log q(y)$, the negative log-probability of the true class. That is the softmax cross-entropy loss of §0.2. A language model's loss is the same thing averaged over tokens,

where $w_t$ is the token at position $t$ and $w_{<t}$ are the tokens before it. This is a sample estimate of the cross-entropy between the true distribution of text and the model. When papers report a loss of 2.0 for a language model, they mean the model is, on average, $2.0$ nats ($2.9$ bits) surprised by each token.

KL divergence, the price of the wrong model

How much worse than ideal is a model $q$? Subtract the best possible cost, $H(p)$, from what you actually pay, $H(p, q)$. That difference is the Kullback-Leibler divergence,

In plain words, KL divergence is the extra surprise, per draw, that you suffer by believing $q$ when the truth is $p$.

The most important fact about it is that it is never negative, and it is zero only when $q = p$. This is Gibbs' inequality, and the proof takes one line. Using $\log u \le u - 1$ (the log lies below its tangent line at 1),

with equality exactly when $q(x) = p(x)$ everywhere. Two corollaries follow at once. Cross-entropy is never below entropy, $H(p, q) \ge H(p)$, so a model's loss is bounded below by the entropy of the data. And with $q$ the uniform distribution $\mathcal{U}$ over $K$ outcomes, $D_{\mathrm{KL}}(p \Vert \mathcal{U}) = \log K - H(p) \ge 0$, which proves that the uniform distribution has the most entropy.

Now the punchline for machine learning. When we train a model $q_\theta$ by minimizing cross-entropy on data from $p_{\text{data}}$,

the entropy term does not depend on $\theta$, so minimizing cross-entropy is minimizing $D_{\mathrm{KL}}(p_{\text{data}} \Vert q_\theta)$, the extra surprise the model suffers on real data, which is also maximum likelihood (§0.4). The leftover $H(p_{\text{data}})$ is a floor no model can beat, the inherent unpredictability of the data. The "irreducible loss" term in neural scaling laws (§9.3) is an estimate of it.

Play with two distributions below. Make $q$ put almost no mass where $p$ has some, and watch $D_{\mathrm{KL}}(p\Vert q)$ explode while $D_{\mathrm{KL}}(q\Vert p)$ stays moderate.

import numpy as np

def entropy(p, base=np.e):
    raise NotImplementedError

def cross_entropy(p, q, base=np.e):
    raise NotImplementedError

Forward and reverse KL

KL divergence is not symmetric, and the direction you choose changes what you get. This is one of the most important practical ideas in this section, so let's go slowly.

Suppose the truth $p$ is complicated (here, two separated bumps) and you must approximate it with something simple, a single Gaussian $q$. Which Gaussian is "closest" depends on which KL you minimize.

Forward KL, $D_{\mathrm{KL}}(p \Vert q) = \mathbb{E}_p[\log p - \log q]$, averages over where $p$ has mass. If $q$ is tiny where $p$ has mass, $\log q$ is hugely negative there and the penalty is enormous, infinite if $q = 0$. So the best $q$ covers every region of $p$, even if that means putting mass in the gap between the bumps. It is called mass-covering or mean-seeking. For a Gaussian $q$ the answer is exact. Since $D_{\mathrm{KL}}(p\Vert q) = -\mathbb{E}_p[\log q] + \text{const}$, and $-\mathbb{E}_p[\log\mathcal{N}(x;\mu,\sigma^2)] = \frac{\mathbb{E}_p[(x-\mu)^2]}{2\sigma^2} + \tfrac12\log(2\pi\sigma^2)$, setting derivatives to zero gives $\mu = \mathbb{E}_p[x]$ and $\sigma^2 = \operatorname{Var}_p(x)$. Forward KL matches the moments, and with two bumps the mean sits in the valley between them.

Reverse KL, $D_{\mathrm{KL}}(q \Vert p) = \mathbb{E}_q[\log q - \log p]$, averages over where $q$ has mass. Now the big penalty is for $q$ putting mass where $p$ is tiny, and there is no penalty for ignoring parts of $p$, since regions where $q \approx 0$ contribute nothing to the average. So the best $q$ squeezes into one bump and fits it well. It is called mode-seeking or zero-forcing.

The forward fit is centered at 0 with a standard deviation of about 2.1, matching the mixture's moments and putting a large share of its mass, its peak included, in the valley where $p$ has almost none. The reverse fit locks onto one bump (the grid happens to pick the right-hand bump at $+2$, and the left-hand one ties by symmetry) with exactly that bump's width. Its divergence is $\log 2$, because inside its bump $q = 2p$, so $\log(q/p) = \log 2$ everywhere $q$ has mass.

These two behaviors show up across the book.

The last row is worth spelling out. Pretraining minimizes the forward KL $D_{\mathrm{KL}}(p_{\text{data}} \Vert q_\theta)$, because we have samples of text but no formula for its probability. RLHF penalizes the reverse KL $D_{\mathrm{KL}}(\pi_\theta \Vert \pi_{\text{ref}})$ between the policy being trained and the reference model it started from (§16.4), because the samples come from the policy and both log-probabilities are available. That choice is also what gives the best policy its explicit form, the reference tilted by $e^{r/\beta}$, on which DPO is built (§17.1). The mode-seeking nature of reverse KL is one commonly offered explanation for why RLHF-tuned models produce less diverse outputs than their base models.

Estimating KL from samples

In RLHF and GRPO you cannot sum over every possible sequence. You estimate $D_{\mathrm{KL}}(q \Vert p)$ from samples $x \sim q$, using the ratio $r(x) = p(x)/q(x)$. The obvious estimator is $k_1 = -\log r$, which is unbiased (its mean is exactly the KL) but very noisy, and it is negative for many samples even though KL never is. John Schulman's note on the topic (linked below) popularized a better one,

It is unbiased, because $\mathbb{E}_q[r] = \sum_x q(x)\frac{p(x)}{q(x)} = 1$, so the $(r - 1)$ term has mean zero and $\mathbb{E}_q[k_3] = \mathbb{E}_q[-\log r] = D_{\mathrm{KL}}(q\Vert p)$. It is never negative, because $\log r \le r - 1$. And when $p$ and $q$ are close it has much lower variance, because the added $r - 1$ term is negatively correlated with $-\log r$ and cancels much of its noise. A third choice, $k_2 = \tfrac12(\log r)^2$, has low variance but is biased. GRPO's KL penalty (§18.4) is exactly $k_3$ with $q = \pi_\theta$ and $p = \pi_{\text{ref}}$. (It is unbiased only when the samples really come from $\pi_\theta$. GRPO samples from a slightly older copy of the policy, so in practice it is a close approximation.)

import numpy as np

def kl_estimators(logq, logp):
    raise NotImplementedError

Mutual information

How much does knowing one variable tell you about another? Start with conditional entropy, the uncertainty left in $X$ once you know $Y$,

The mutual information is how much knowing $Y$ reduces the uncertainty about $X$,

In plain words, mutual information is how far the joint distribution is from what it would be if the variables were independent. It is symmetric, never negative, and zero exactly when $X$ and $Y$ are independent.

Notice the term inside the sum. $\log\frac{p(x,y)}{p(x)p(y)}$ is the pointwise mutual information (PMI), how much more often $x$ and $y$ occur together than independence predicts, so mutual information is the average PMI over the joint distribution. PMI between words and their contexts is what classical word vectors are built from (§1.4). A small example makes it concrete. Take the rain and wet-grass table of §0.4, with $X$ whether it rained and $Y$ whether the grass is wet, and joint probabilities $p(\text{rain}, \text{wet}) = 0.3$, $p(\text{rain}, \text{dry}) = 0.02$, $p(\text{none}, \text{wet}) = 0.08$, and $p(\text{none}, \text{dry}) = 0.6$. Rain has entropy $H(X) = 0.904$ bits. Looking at the grass removes more than half of it, $I(X; Y) = 0.495$ bits, leaving $H(X \mid Y) = 0.41$ bits.

Mutual information is the quantity contrastive learning secretly maximizes. The InfoNCE loss used to train CLIP and modern embedding models satisfies $I(X; Y) \ge \log N - \mathcal{L}_{\text{InfoNCE}}$ for a batch of $N$ candidates (van den Oord et al., 2018), so driving the loss down pushes up a lower bound on the information shared by the two views. You'll derive this in §7.2.

import numpy as np

def mutual_information(P, base=2):
    raise NotImplementedError

def conditional_entropy(P, base=2):
    raise NotImplementedError

Perplexity, and bits per byte

A language model's loss is an average cross-entropy in nats per token, which is hard to feel. Perplexity turns it into a count,

In plain words, perplexity is one over the geometric mean of the probabilities the model gave to the tokens that actually occurred, which makes it the number of equally likely choices that would leave you as uncertain as the model is, on average. That is why it is often called the effective branching factor.

Work one by hand. A model assigns probabilities 0.5, 0.1, 0.9, and 0.25 to the four tokens of a short text. Their logs are $-0.693$, $-2.303$, $-0.105$, and $-1.386$, so the mean loss is $4.487/4 = 1.122$ nats per token, and the perplexity is $e^{1.122} = 3.07$. The geometric mean probability is $1/3.07 = 0.326$. Notice what perplexity is not. The average of the inverse probabilities, $(2 + 10 + 1.11 + 4)/4 = 4.28$, is a different and meaningless number, and so is the average of per-token perplexities.

Three anchor values follow from the definition.

1. A uniform model has perplexity $V$. If $q = 1/V$ for every token, $\mathcal{L} = \log V$ and $\operatorname{PPL} = V$. This is also where a freshly initialized model starts, so a GPT-2 model with its vocabulary of 50,257 tokens should begin training near a loss of $\ln 50{,}257 = 10.82$ nats. Checking that number is the first step of the debugging recipe in §0.7.
2. A perfect model has perplexity 1. It puts probability 1 on every token that occurs. No real model gets there, because text has entropy of its own, the floor $H(p_{\text{data}})$ from the KL section above.
3. One zero sends perplexity to infinity. If any $q(w_t \mid w_{<t}) = 0$, then $\log 0 = -\infty$ and $\operatorname{PPL} = \infty$. Short of zero, one confident mistake still costs a lot. A token given probability $10^{-9}$ adds $20.7$ nats to the total, as much as 20 ordinary tokens at a loss near 1. Perplexity punishes overconfidence far more than it rewards confidence, which is the cross-entropy's character showing through.

The same quantity has three common units, and you should convert between them without thinking. The loss $\mathcal{L}$ is in nats per token. Dividing by $\ln 2$ gives bits per token. And perplexity is both $e^{\mathcal{L}}$ and 2 raised to the bits per token. A loss of 2.0 nats per token is $2.0/\ln 2 = 2.89$ bits per token and a perplexity of $e^2 = 2^{2.89} \approx 7.4$, as unsure as choosing among 7 or 8 equally likely tokens at every step.

At real scale, the OpenAI GPT-2 checkpoints, evaluated on the OpenWebText validation set, reach a loss of 3.12 nats per token for the 124M-parameter model and 2.54 for the 1.5B-parameter one (Karpathy's nanoGPT reports these baselines). Those are perplexities of $e^{3.12} \approx 22.6$ and $e^{2.54} \approx 12.7$. Going from 10.82 at initialization to 3.12 shrinks the effective number of choices per token from 50,257 to about 23.

Computing it over a corpus

Perplexity is a statement about a whole evaluation set, and the most common mistakes are in how the per-token numbers are combined.

• Pool the tokens, then exponentiate. The perplexity of a corpus is $\exp(\text{total nats} / \text{total counted tokens})$. Averaging per-document perplexities gives too much weight to short documents, and even with equal-length documents it comes out too large, because $e^x$ is convex, so the average of the exponentials exceeds the exponential of the average whenever the documents' losses differ (Jensen's inequality). Averaging per-batch mean losses is wrong for the same reason whenever batches hold different numbers of counted tokens, the bug that gradient accumulation also has to avoid (§0.9).
• Count only real predictions. Padding positions, and the first token of a sequence (which nothing predicts), must be excluded from both the total loss and the token count. Whether the end-of-sequence token counts is a convention that has to be stated, because it changes the number (§3.1).
• Context changes the number. The same model scores lower perplexity when each token sees more context. Cutting a long text into non-overlapping chunks leaves the first tokens of every chunk with almost no context and inflates perplexity. Evaluating with an overlapping sliding window fixes this at extra cost (§6.6 builds it).

Comparing across tokenizers with bits per byte

Perplexity per token depends on the tokenizer. A tokenizer with longer tokens has fewer, harder predictions per document, so two models with different tokenizers cannot be compared by per-token loss (§2.1). What does not depend on the tokenizer is the total probability the model assigns to the text, so the fix is to normalize the total by something every tokenizer shares, the raw bytes of text. If a document of $N_{\text{bytes}}$ bytes is split into $T$ tokens and the model's total loss is $T \cdot \mathcal{L}$ nats, then

In plain words, convert the document's total surprise to bits and divide by its length in bytes. For example, a loss of 2.0 nats per token with an average of 4 bytes per token is $2.0 / (4 \ln 2) = 0.72$ bits per byte. Bits per byte is also directly a compression rate. A model at 0.72 bits per byte, driving an arithmetic coder, would compress text to 9% of its original size (0.72 out of 8 bits). For GPT-2 small, using the common rule of thumb of about 4 bytes of English per token, 3.12 nats per token is $4.50$ bits per token and about $1.1$ bits per byte. Bytes are not characters. Most non-English scripts take 2 to 4 bytes per character in UTF-8, so bits per character and bits per byte differ there, and papers should say which they report. You'll use these conversions in §6.6.

import numpy as np

def perplexity(token_logprobs):
    raise NotImplementedError

def bits_per_byte(token_logprobs, n_bytes):
    raise NotImplementedError

import numpy as np

def corpus_perplexity(logprobs, mask):
    raise NotImplementedError

def doc_perplexities(logprobs, mask):
    raise NotImplementedError

Label smoothing

Cross-entropy with one-hot targets has a strange optimum. Once a training example is classified correctly, the loss $-\log p_y$ keeps decreasing as $p_y \to 1$, which requires the logit gap between the true class and the others to grow without bound. On data the model can fit perfectly, the logits drift toward infinity, and the model becomes overconfident.

Label smoothing (Szegedy et al., 2016) replaces the one-hot target with a softened one. With smoothing $\epsilon$ and $K$ classes,

In plain words, mix a little of the uniform distribution into every target, which adds a penalty for putting very low probability on any class.

Three consequences follow from what we already know. The gradient is still "predicted minus target", $\mathbf{p} - \mathbf{y}^{\text{LS}}$ (the derivation in §0.2 holds for any target distribution). The loss is minimized when $\mathbf{p} = \mathbf{y}^{\text{LS}}$, by Gibbs' inequality, so the optimal logit gap between the true class and any other is finite, $\log\frac{1 - \epsilon + \epsilon/K}{\epsilon/K}$, which is about 9.1 for $K = 1000$ and $\epsilon = 0.1$. And the minimum loss is no longer 0 but the entropy $H(\mathbf{y}^{\text{LS}})$, so do not be alarmed when a smoothed model's training loss plateaus above zero.

Without smoothing the gap keeps growing, roughly logarithmically in the number of steps, forever. With smoothing it settles quickly at the predicted value, $\log 91 \approx 4.51$ for these 10 classes. Label smoothing became standard in image classification and machine translation, and the original Transformer used $\epsilon = 0.1$. It has a known cost. Müller, Kornblith & Hinton (2019) showed that it tends to erase the information in a network's logits about which wrong classes are similar to the right one, which makes smoothed networks worse teachers for knowledge distillation. Most large language model pretraining does not use it.

import numpy as np

def smoothed_cross_entropy(logits, y, eps):
    raise NotImplementedError

In PyTorch

Read more

• Shannon (1948). A Mathematical Theory of Communication. The founding paper, still remarkably readable.
• MacKay (2003). Information Theory, Inference, and Learning Algorithms. Free, and the best book connecting information theory to learning.
• Christopher Olah (2015). Visual Information Theory. Entropy, cross-entropy, and KL as pictures of code lengths.
• John Schulman (2020). Approximating KL Divergence. The $k_1$, $k_2$, $k_3$ estimators and their bias and variance.
• Karpathy. nanoGPT. Its README lists the OpenWebText losses of the GPT-2 checkpoints quoted in this section.
• Szegedy et al. (2016). Rethinking the Inception Architecture for Computer Vision. Introduces label smoothing (Section 7).
• Müller, Kornblith & Hinton (2019). When Does Label Smoothing Help? Calibration benefits, and why smoothed teachers distill poorly.
• van den Oord, Li & Vinyals (2018). Representation Learning with Contrastive Predictive Coding. InfoNCE and its mutual-information bound.

Watch next

▶

▶

▶