KL divergence: the gap

Transcript: this stretch, timestamped

Everything before this page has been about H(p,q) — the average number of bits you spend when your code is tuned for q and the world hands you p. P14 pushed that all the way to distillation, where both slots hold a model's full distribution. But H(p,q) has an awkward property for anyone who wants to read it as an error: at the optimum it does not go to zero, it goes to H(p), the irreducible entropy of the data. That floor is an accounting nuisance. Subtract it and you get a quantity that is zero at the optimum — the KL divergence. Grant introduces it in the last two minutes as a footnote, then hands you three things to ponder. This page takes the footnote seriously: the algebra, the proof that it can't go negative, the reason it isn't a metric, and the practical consequence — forward versus reverse KL — that people get wrong most often.

Outline, with timestamps

• 31:35 — Setup: recall the one key property — H(p,q) is minimal exactly when q = p.
• 31:45 — Naming the gap: that minimum equals H(p), and the difference is the Kullback–Leibler divergence.
• 31:45 — Compression reading: KL is the bits per symbol wasted by a badly matched code — the robot ledger, redone.
• 32:17 — Distance-ish, but not a distance: zero when equal, grows as they differ, asymmetric.
• 32:47 — Ponder 1 and 2: the compact one-sum form, and how the bar diagram encodes it.
• 33:19 — Ponder 3: in distillation, what changes if you swap cross-entropy for KL?

The definition is a subtraction — and the compact form is the same subtraction 31:45

Fix the truth p and let the model q vary. Cross-entropy as a function of q has a single minimum, and the minimum sits at q = p with value H(p) — the green curve Grant traced out earlier in the video by sliding p around and following the bottom of each cross-entropy curve 11:56. So there are two numbers in play at every q: what you actually pay, and the best anyone could pay. The divergence is the difference.

D(p‖q)  =  H(p,q)  −  H(p)
        =  Σ p(x)·log₂(1/q(x))  −  Σ p(x)·log₂(1/p(x))
        =  Σ p(x)·[ log₂(1/q(x)) − log₂(1/p(x)) ]
        =  Σ p(x)·log₂( p(x) / q(x) )

That last line is Grant's first thing-to-ponder, and the derivation is the whole of it: both sums are weighted by the same weights p(x), so you can pull them under one summation sign and let the logs combine. Nothing subtle happens. What the compact form buys you is that it is a single sum; what it costs you is that it hides the fact that this is a difference of two interpretable quantities, one of which — H(p) — is a property of the world and not of your model.

Grant's second thing-to-ponder is the picture. Throughout the video, cross-entropy is drawn as a bar chart whose bars have width p(x) and height log₂(1/q(x)), so the total area is H(p,q); entropy is the same chart with heights log₂(1/p(x)). KL is the difference of the two areas, which means: keep the widths p(x), and set each bar's height to log₂(p(x)/q(x)). My addition, worth stating because the diagram doesn't: that height is negative for every symbol where q(x) > p(x) — the model over-predicts, so its code word for that symbol is shorter than optimal and you actually save bits there. KL is a signed area, with bars below the axis, and the theorem below is that the bars above always outweigh the bars below.

Why the bars above always win — Gibbs' inequality

This section is my addition; Grant asserts non-negativity implicitly by saying cross-entropy has a minimum at q = p, but the standard one-line proof is worth having, because it also tells you exactly when equality holds.

Look at −D(p‖q) = Σ p(x)·log₂(q(x)/p(x)). The log function is strictly concave, and the p(x) are non-negative weights summing to 1, so Jensen's inequality lets you move the log outside the average:

−D(p‖q)  =  Σ p(x)·log₂( q(x)/p(x) )
         ≤  log₂( Σ p(x) · q(x)/p(x) )        [Jensen, log is concave]
         =  log₂( Σ_{x : p(x)>0} q(x) )
         ≤  log₂(1)  =  0

⇒  D(p‖q) ≥ 0, with equality iff q = p.

The first inequality is tight only when q(x)/p(x) takes the same value everywhere p has mass (strict concavity); the second is tight only when q puts none of its mass outside p's support. Together those force the common ratio to be 1, i.e. q = p. This result is Gibbs' inequality — equivalently, it is the statement that no code can beat the entropy, which is the same fact the compression half of this video established from the coding side. The two directions of the series meet here.

The robot ledger: 0.875 bits wasted per instruction 32:17

"In the language of compression, you would think of it as describing how many bits per symbol are you wasting by using a poorly optimized code."— Grant Sanderson, 31:45

The video's running example makes this concrete, and it is worth doing the arithmetic yourself. The original mission had the robot going up half the time, down a quarter, left and right an eighth each 3:38 — call that q, and note that the optimal code for it is exactly 1, 2, 3, 3 bits, because those probabilities are all powers of ½. Then the mission is rotated: right becomes half, left a quarter, up and down an eighth each — call that p. The encoder is hard-coded, so you keep paying q's code lengths at p's frequencies 5:41.

The new distribution is a permutation of the old one, so it has the same entropy: H(p) = ½·1 + ¼·2 + ⅛·3 + ⅛·3 = 1.75 bits. And 2.625 − 1.75 = 0.875 — which matches the last column exactly, as the algebra above says it must. So the stale code costs you seven-eighths of a bit on every instruction sent, a 50% overhead on a 1.75-bit budget. Notice the last column's signs: you gain on left and right, whose code words are now too long for how often they occur, and you lose on up and down. The gains are real; they are just smaller than the losses.

A trap in this particular example, and my addition: here D(q‖p) also equals 0.875, because p is a relabelling of q under the swap up↔right, down↔left, so the two divergences are forced to agree. Do not learn asymmetry from the robot. Learn it from the next section.

Divergence, not distance 32:17

KL behaves like a distance in the two ways you first check — it is zero when the distributions match and grows as they separate — and then fails the other two axioms outright. Grant flags the first failure: D(p‖q) ≠ D(q‖p). His own two-outcome example earlier in the video supplies the numbers. Take the even distribution (½, ½) and the skewed one (0.9, 0.1):

Both cross-entropies are Grant's 9:22–9:52 numbers — 1 bit one way, "around 1.74 bits" the other. Subtract the right entropy from each and you see the divergences differ too: 0.531 against 0.737. Same pair of distributions, two different answers depending on which one you call the truth.

The second failure is less advertised and worth verifying, so I checked it: KL also violates the triangle inequality. Take three distributions on two outcomes, a = (0.9, 0.1), b = (0.5, 0.5), c = (0.1, 0.9). Then D(a‖c) = 2.536 bits, while D(a‖b) + D(b‖c) = 0.531 + 0.737 = 1.268 bits. Going "via b" is less than half as expensive as going direct, so D(a‖c) ≤ D(a‖b) + D(b‖c) is false by a factor of two. A quantity that is neither symmetric nor triangle-obeying is not a metric, and the word divergence is the field's way of saying so out loud. (It is not lawless, though: KL is jointly convex in its two arguments, and Pinsker's inequality bounds total variation distance below it, ‖p − q‖_TV ≤ √(D(p‖q)·ln2 / 2) with D in bits. So small KL does imply the distributions are genuinely close — the converse direction is what fails.)

Forward vs reverse: covering versus collapsing

My addition, and the practically important half of the asymmetry. Which slot you put the truth in changes what your fitted q looks like, and the mechanism is visible directly in the formula Σ p(x)·log₂(p(x)/q(x)).

Forward KL, D(p‖q) — truth first, model second. The sum is weighted by p, so only symbols the truth actually produces contribute. But wherever p(x) > 0 and q(x) → 0, the term p(x)·log₂(p(x)/q(x)) → +∞. The model is punished without bound for assigning near-zero probability to something that happens. Conversely, where p(x) = 0 the term is 0 no matter what q does (using the standard convention 0·log 0 = 0), so the model pays nothing for hallucinating mass in empty regions. Net effect: q spreads out to cover every mode of p. This is called mass-covering, or mean-seeking — a Gaussian fit to a two-humped truth by forward KL straddles both humps and puts its peak in the valley between them.

Reverse KL, D(q‖p) — model first, truth second. Now the weights are q(x), so a region the model ignores costs nothing at all: if q(x) = 0, that term vanishes regardless of how much mass p has there. What is punished infinitely is the reverse — putting q's mass where p has essentially none. Net effect: q retreats onto whichever single region of p it can fit inside, and abandons the rest. This is mode-seeking, or zero-forcing.

Here is a discrete case you can check by hand. Let the truth be bimodal over five bins, p = (0.45, 0.04, 0.02, 0.04, 0.45), with H(p) = 1.521 bits, and score three candidate models under each direction:

The two columns pick different winners from the same three candidates. Forward KL takes the flat coverer; reverse KL takes the single-mode collapse. (Both reject the third candidate, which piles mass into the low-probability valley — reverse KL especially, since that is precisely its forbidden move.)

Why the two words get used interchangeably — and Grant's third puzzle 33:19

"I want you to ask yourself, what would happen if instead you used the KL divergence? After all, if the KL divergence is like a distance measure, wouldn't this be a more natural choice?"— Grant Sanderson, 33:19

Spoiler for the puzzle, with the reasoning. In distillation the teacher is frozen: p is a fixed distribution and only the student's parameters θ move. So

D(p‖q_θ)  =  H(p, q_θ)  −  H(p)
                            └──────┘
                       constant in θ

⇒  ∇_θ D(p‖q_θ)  =  ∇_θ H(p, q_θ)

The gradients are identical. Swapping cross-entropy for KL changes the reported loss by a constant offset and changes nothing about the parameter updates, the optimum, or the trained model. The only thing you gain is interpretability of the number on the screen: KL bottoms out at 0, so "loss 0.03" means "0.03 bits per token worse than the teacher", whereas cross-entropy bottoms out at the teacher's own entropy and you cannot tell from the number alone how much room is left. The only thing you lose is one extra computation per step (you have to evaluate H(p)). In ordinary pre-training the same argument holds with p the empirical data distribution — and there it is even more thoroughly a constant, since it does not depend on the model at all.

That constant-offset identity is why ML writing slides between "cross-entropy loss" and "KL loss" without ceremony. They are the same objective. The distinction only bites when p itself is being learned — in a VAE, in an EM step, in any objective where both arguments move — and then you have to be careful about which term you dropped.

Where KL turns up next, and what Part 3 owes us 29:42

Four places you will meet this formula again, each stated only as far as I can state it accurately:

• The variational lower bound (ELBO), in VAEs and variational inference. For a latent-variable model, log p(x) = ELBO(q) + D(q(z|x) ‖ p(z|x)). Because KL is non-negative, the ELBO is a genuine lower bound on the log-evidence, and the slack is exactly the KL from your approximate posterior to the true one. Maximising the ELBO is therefore the same as minimising that KL. Note the argument order: the approximation is in the first slot, so this is reverse KL — which is why variational posteriors are famously too narrow.
• The KL penalty in RLHF. Objectives of the form "maximise reward, minus β times the KL from the current policy to the frozen reference policy" keep a fine-tuned model from drifting off the manifold its pre-training put it on. The policy sits in the first slot; the penalty is estimated from sampled tokens rather than summed exactly, since the sum over all sequences is intractable.
• Mutual information. I(X;Y) = D( p(x,y) ‖ p(x)·p(y) ) — mutual information is a KL divergence, between the joint distribution and the product of the marginals. Everything you now know about KL (non-negativity, zero iff equal) immediately gives you the corresponding facts about mutual information: it is never negative, and it is zero exactly when the variables are independent.
• Model selection. Akaike's information criterion is derived as an estimate of the expected KL divergence from the true data-generating distribution to the fitted model — which is why AIC is an information criterion and not an arbitrary penalty on parameter count.

As for Part 3: this video is explicit that it is not finished. Grant closes by promising "one very visual and very beautiful compression algorithm" that turns a general predictor into a compressor, so that the number of bits spent on a text matches its information content from the model's perspective — and that once you have it, cross-entropy training is literally training the best possible text compressor, which finally lets the series confront the phrase "compression is intelligence" head-on 29:42. He does not name the algorithm. My guess, flagged as a guess: the description fits arithmetic coding — it encodes a whole message as a single number inside a nested subdivision of the unit interval, its output length tracks −Σ log₂ q almost exactly rather than rounding each symbol up to a whole bit, and the interval picture is exactly the kind of thing that animates well. Part 3 was not released at the time of writing, so treat all of that as unconfirmed.

This page is the end of the cross-entropy arc. From here the map turns to the other thing entropy is for: not measuring how wrong a model is, but choosing what to do next. P16 starts the Wordle arc, where expected information gain — an entropy computation you can do on your laptop — picks the guess that on average tells you the most.

Where people get stuck

"Which distribution goes in which slot?" The convention in D(p‖q) is: p is the truth, the reference, the thing that generates the data and supplies the weights; q is the model, the approximation, the thing whose code lengths you are stuck paying. Read ‖ as "of, relative to" and read the whole thing as "the bits per symbol wasted by using q's code on p's data". Sanity check: the weights p(x) outside the log always belong to the first argument. Be warned that the notation for cross-entropy is genuinely inconsistent across sources — the video says as much — so when reading a paper, find the summation and look at which letter is the weight rather than trusting the argument order.

"It's a distance, so surely it's symmetric." This is the single most common error, and it is expensive because the two directions fit visibly different models (see the table above). If you need an actual metric, the standard repairs are the symmetrised Jensen–Shannon divergence, JSD(p,q) = ½D(p‖m) + ½D(q‖m) with m = ½(p+q) — whose square root is a metric, and which is finite even when the supports don't overlap — or a genuinely different family like total variation or Wasserstein distance. Do not just average D(p‖q) and D(q‖p) and hope; that fixes symmetry but not the triangle inequality, and it stays infinite whenever either support escapes the other.

"Why does it blow up to infinity?" Because D(p‖q) = ∞ whenever there is any x with p(x) > 0 and q(x) = 0: the model has declared impossible something that actually happens, and no finite number of bits can encode an event your code has no code word for. In practice this is why models are never allowed to output a hard zero — softmax cannot produce one, and label smoothing, temperature, and additive smoothing all exist partly to keep this term finite. If your KL is inf or nan, look for a zero in the denominator distribution before looking anywhere else.

"The video's captions say Kolbach." The spelling is Kullback–Leibler, after Solomon Kullback and Richard Leibler, who introduced it in "On Information and Sufficiency" (1951). The published captions render the surname by ear; the name in the papers is the one to search for.

Going deeper, verified

• On Information and Sufficiency — Kullback & Leibler, Annals of Mathematical Statistics 22(1):79–86 (1951) · the original paper; free full text on Project Euclid via the DOI.
• Information Theory, Inference, and Learning Algorithms — David MacKay (2003) · free PDF; §2.6 introduces relative entropy and proves Gibbs' inequality by exactly the Jensen argument above.
• Variational Inference: A Review for Statisticians — Blei, Kucukelbir & McAuliffe (2016) · the cleanest derivation of the ELBO-plus-KL decomposition, and an explicit discussion of why reverse KL under-disperses.
• Auto-Encoding Variational Bayes — Kingma & Welling (2013) · where the KL-to-the-prior term in the VAE objective comes from.
• Training language models to follow instructions with human feedback — Ouyang et al. (2022) · the InstructGPT paper; its RL objective is the canonical "reward minus β·KL-to-reference" form.

Exercises

1. Rebuild the robot ledger, then break its symmetry — reproduce H(p) = H(q) = 1.75, H(p,q) = 2.625 and D(p‖q) = 0.875 bits for the two robot distributions, both by subtraction and by the single-sum form, and confirm the two agree. Then verify the claim in this page that D(q‖p) = 0.875 too, and explain why — a good answer identifies the permutation up↔right, down↔left that carries q to p and back. Finally, perturb one probability (say make right 0.55 and left 0.20) and show the two directions now differ.
2. Hunt a triangle-inequality violation of your own — over distributions on two outcomes, search for a, b, c with D(a‖c) > D(a‖b) + D(b‖c). A good answer reports a concrete triple and its three numbers (the page's (0.9,0.1), (0.5,0.5), (0.1,0.9) gives 2.536 against 1.268), and says why the violation is easy to find: D(a‖c) grows without bound as c approaches a boundary of the simplex, while a route through an interior b keeps every term finite.
3. Fit a model in each direction — take the bimodal p = (0.45, 0.04, 0.02, 0.04, 0.45) from this page and a one-parameter family of unimodal candidates (for instance a discretised Gaussian on bins 1–5, sweeping mean and width on a grid). Find the member minimising D(p‖q) and the member minimising D(q‖p). A good answer shows the two minimisers are different — the forward one wide and centred, the reverse one narrow and parked on a mode — and reports both divergences for both winners so the crossover is visible in numbers rather than assertion.