What Cross-Entropy Connects: Compression, Language Models and KL Divergence

Grant Sanderson begins with a 2002 experiment: compressing text from different languages together can reveal similarities and help recover a language family tree. The method uses general compression rather than built-in linguistic knowledge.

Append a snippet of document B to document A, compress the result, and compare its size with compressed A alone. The added size roughly indicates how well a compressor adapted to A handles B; similar patterns tend to compress more efficiently.

The motivating idea is cross-entropy: how well does a coding scheme fitted to one distribution work on data from another? The same mathematics later appears in language-model training.

In a toy robot example, instructions up, down, left and right occur with probabilities 1/2, 1/4, 1/8 and 1/8. A suitable prefix code uses one, two, three and three bits respectively.

For an ideal code, a symbol with probability q carries −log₂q bits of information. Real probabilities need not yield whole numbers of bits per symbol, but longer messages can approach the corresponding average.

Now change the actual distribution: up and down occur 1/8 each, left 1/4 and right 1/2. If the old code is retained, weighting its lengths by the new frequencies gives an average of 2.625 bits per instruction.

Call the actual distribution P and the distribution used to design the code Q. Cross-entropy is H(P,Q) = −Σ pᵢ log₂qᵢ: the average ideal code length under P when lengths are based on Q. Conventions for naming the order vary, so the formula matters.

Consider two outcomes. A code based on Q = (1/2, 1/2) uses one bit per symbol even if reality is P = (0.9, 0.1). Switching the roles changes the result: a code optimized for the skewed distribution costs about 1.74 bits when the true outcomes are evenly split.

Cross-entropy is asymmetric: changing which distribution supplies frequencies and which supplies code lengths changes the value. It should not be treated as an ordinary symmetric distance.

Fix P and vary Q. The minimum occurs when Q matches P, and that minimum is the entropy H(P). In compression language, matching the code to the actual source gives the best possible average ideal length.

The language-tree experiment uses a related empirical idea rather than computing exact cross-entropy. A text is only a sample from its language, and gzip finds repeated sequences rather than achieving theoretical optimal compression.

For a language model, the input is a sequence of tokens and the output is a probability distribution for the next token. Training changes model parameters to reduce a loss measured over a large collection of text.

At each position, take the probability the model assigns to the token that actually occurs. Its negative logarithm is the token’s surprise from the model’s perspective; averaging these values gives the standard next-token log loss.

A model is penalized heavily when it assigns a very small probability to an observed token. Machine-learning implementations commonly use natural logarithms; changing the base scales the loss by a constant.

At this level of abstraction, pre-training minimizes average next-token surprise. Sanderson notes that batching, optimizers and making training run at enormous scale are substantial additional engineering work.

A single observed token can be represented as a one-hot distribution, so its log loss is a cross-entropy. Sanderson finds the deeper explanation more satisfying: consider all examples sharing the same context and their empirical distribution of next tokens.

For a prompt such as “my name is,” some names occur more often than others. Averaging the negative log probability over those occurrences produces cross-entropy between the data’s empirical distribution P and the model’s predictions Q.

Minimizing that average over Q favors matching the frequencies in the data. Sanderson sketches a Lagrange-multiplier argument for the logarithm when the per-example loss depends only on the probability assigned to the observed outcome and must recover arbitrary target distributions.

The constraint is that all predicted probabilities sum to one. The stationarity condition leads to a derivative proportional to 1/q, yielding a logarithm under the assumptions of this local scoring form. Other scoring rules can use the whole predicted distribution, so this is not a claim that every useful loss must be log loss.

Distillation makes the two distributions explicit. A smaller student model is trained to approximate a larger teacher model: for a given context, compare the student’s full distribution with the teacher’s full distribution.

The teacher’s probabilities give a softer and richer signal than a single observed token. Sanderson compares it to learning chess from a strong player who explains several possible moves, rather than seeing only the move that happened in one game.

The compression and training perspectives seem different, but both use the same quantity. The model’s average surprise can be interpreted as the ideal code length for text under its predictions.

Sanderson previews a later lesson on turning a predictor into a compressor. A suitable coding algorithm can make the length of an encoded text approximately equal to its information content according to the predictor.

KL divergence is the gap between cross-entropy and entropy: DKL(P‖Q) = H(P,Q) − H(P). In compression terms, it measures the extra ideal bits per symbol spent by using a code based on Q for a source distributed as P.

KL divergence is zero when the distributions agree, but it is generally asymmetric. It is therefore useful as a measure of mismatch, not a symmetric metric.

As an exercise, Sanderson asks what would change if distillation used KL divergence instead of cross-entropy. With a fixed teacher P, H(P) is constant with respect to the student Q, so the two objectives have the same student gradient and optimum.