math

Information Theory and Compression

How much information is there? How much do we waste when our model is wrong?

Published 2026-05-06 · Updated 2026-10-11

On this page

Find a section

An event that we expect needs little explanation. An unlikely event needs more. A probability model turns this intuition into code lengths. Entropy averages the lengths of a code matched to the source. Cross-entropy averages the lengths of a code matched to another model.

This distinction connects several topics in the atlas. It explains a language model’s log loss. It also explains why an ordinary compressor can sometimes recognize a language or writing style. The connection is precise for ideal probability codes. It becomes an empirical approximation for a real zip program.

From probability to a code

Suppose a decoder already knows a probability distribution Q. A high-probability symbol should receive a short code. A low-probability symbol can receive a longer code because it occurs less often.

\ell_Q(i)=-\log_2 Q(i)

Ideal information length in bits. A single binary codeword must have an integer length; block and arithmetic coding approach fractional average lengths.

A probability of 1/2 corresponds to one bit. A probability of 1/8 corresponds to three bits. For independent events, probabilities multiply while information lengths add. This is why a logarithm is the right conversion.

A concrete prefix code is 0, 10, 110, 111. For probabilities [1/2, 1/4, 1/8, 1/8], its mean length is 1.75 bits. No codeword begins another, so the decoder can identify symbol boundaries without separators.

Why these lengths are optimal: Kraft’s inequality

A binary prefix code has lengths ℓᵢ with $K=\sum_i 2^{-\ell_i}\le1$ . No complete codeword is the prefix of another. Define $q_i=2^{-\ell_i}/K$ on a finite alphabet with positive source probabilities.

\mathbb{E}_{i\sim P}[\ell_i]=H_2(P)+D_{\mathrm{KL},2}(P\|Q)-\log_2 K\ge H_2(P)

KL is nonnegative and K ≤ 1. Equality requires a complete code matched to P, when the required lengths are realizable.

Choose Shannon code lengths $\ell_i=\lceil-\log_2 p_i\rceil$ for positive probabilities on a finite alphabet. These lengths satisfy Kraft’s inequality because rounding up cannot increase its sum. Their expected length obeys $H_2(P)\le\mathbb{E}[\ell_i]<H_2(P)+1$ . This is an achievable bound, not a guarantee for every prefix code.

For blocks of n independent symbols, the same construction adds less than one bit per block. The overhead per symbol is therefore less than 1/n. The decoder must also know the block boundaries or total symbol count. Arithmetic coding uses successive probability intervals instead of separate integer codewords.

A biased binary source shows why blocks matter. For probabilities [0.9, 0.1], the ideal average is about 0.469 bits. A binary prefix code for individual symbols still needs one bit for each outcome. Entropy is an achievable limiting average, not a fractional codeword that you can emit for one toss.

Symbol-code construction and bounds ↗

What entropy measures

Let P describe the source that produces our data. Its Shannon entropy is the expected surprise under its own probabilities.

H_2(P)=-\sum_i p_i\log_2 p_i=\mathbb{E}_{i\sim P}[-\log_2 p_i]

Use 0 log 0 = 0. Entropy depends on a distribution and on which outcomes it distinguishes.

A fair coin has entropy one bit per toss. A coin with probabilities [0.9, 0.1] has entropy about 0.469 bits per toss. A deterministic source has entropy zero. A uniform distribution over K outcomes has entropy log₂ K, the maximum for that alphabet.

Entropy is not the number of bits needed to store the model P itself. It is the average information in an outcome drawn from P, assuming the coding model is already shared. Model parameters, headers and the decoder can create additional storage costs.

Low entropy does not mean low importance. A predictable medical result can still matter greatly. The formula measures uncertainty, not usefulness or semantic meaning.

Cross-entropy and KL

Now keep the source P, but encode its outcomes using Q. The expected length is the cross-entropy H(P,Q). KL divergence is the excess over the source’s own entropy.

\begin{aligned}H_2(P,Q)&=-\sum_i p_i\log_2 q_i\\D_{\mathrm{KL},2}(P\|Q)&=\sum_i p_i\log_2\frac{p_i}{q_i}\\H_2(P,Q)&=H_2(P)+D_{\mathrm{KL},2}(P\|Q)\end{aligned}

Add and subtract

-\sum_i p_i\log_2 p_i

. The expectation is always over P.

This decomposition separates the uncertainty we cannot remove with a better code from the cost of using the wrong code. For a fixed P, minimizing cross-entropy minimizes forward KL. It does not reduce H(P).

A complete four-outcome example
Outcome	P	Q	Length under P	Length under Q
A	1/8	1/2	3 bits	1 bit
B	1/8	1/4	3 bits	2 bits
C	1/4	1/8	2 bits	3 bits
D	1/2	1/8	1 bit	3 bits

The expected matched length is 1.75 bits. The mismatched length is 2.625 bits. The extra cost is 0.875 bits per outcome. Some individual symbols become cheaper under Q. The weighted average is still worse.

A better code, not a less random source

P stays fixed. Move Q toward P. The blue cost cannot change; the burgundy mismatch cost can.

Model correction 0%

H(P)KL(P‖Q)

Entropy 1.750 bitsExtra 0.875 bitsTotal 2.625 bits

P = [0.125, 0.125, 0.250, 0.500]
Q = [0.500, 0.250, 0.125, 0.125]

Exact four-outcome example. Bar scale: 3 bits. These are ideal average lengths, not measured file sizes.

Changing the log base multiplies all three quantities by the same constant. Many machine-learning libraries use natural logarithms. Convert their losses from nats to bits with $L_{\mathrm{bits}}=\frac{L_{\mathrm{nats}}}{\ln2}$ .

Direction, support and units

KL is an expected log-likelihood ratio. It is not a metric: it is asymmetric and does not generally satisfy the triangle inequality. KL(P‖Q) weights every penalty by P. Swapping the distributions changes which events are important. It also changes which missing probabilities cause an infinite penalty.

Zero probabilities are mathematical conditions, not numerical accidents
Case	Contribution to KL(P‖Q)	Reason
pᵢ = 0	0	The source never draws this event
pᵢ > 0 and qᵢ = 0	+∞	Q has no code for a possible event
pᵢ = qᵢ > 0	0	No mismatch for this event

Under a restricted model family, forward KL often favors coverage of source modes. Reverse KL can favor a concentrated approximation. These are useful tendencies, not universal guarantees. If Q can represent P exactly, both have the same zero-divergence solution.

A fixed teacher distribution P makes H(P) constant with respect to student parameters. Forward KL and teacher-to-student cross-entropy therefore have the same student gradient. This equivalence requires the same distributions and temperature. It fails if the target itself depends on the optimized parameters.

These choices appear in different applications. Classification matches label distributions. Variational inference often minimizes an approximate-posterior-to-target KL. RL can constrain a policy against a reference. The sampling distribution and KL direction determine which events receive weight; the phrase “KL penalty” alone does not specify the operation.

Do not silently add ε to every probability when you want an exact divergence. That changes the distributions and removes meaningful support failures. For positive probabilities, compute the log-likelihood ratio as $\log p_i-\log q_i$ instead of forming the ratio first. A positive probability ratio can overflow even when both logarithms are finite. This numerical failure differs from a true support failure. If stored probabilities have already rounded to zero, taking their logarithms cannot recover the missing mass; keep model log probabilities directly when possible. If smoothing is necessary, state the smoothing rule.

Jensen–Shannon and mutual information

KL can be infinite and asymmetric. Jensen–Shannon divergence first compares each distribution with their common mixture $M=\frac{P+Q}{2}$ .

\begin{aligned}\operatorname{JSD}_2(P,Q)&=\tfrac12D_{\mathrm{KL},2}(P\|M)+\tfrac12D_{\mathrm{KL},2}(Q\|M)\\&=H_2(M)-\tfrac12H_2(P)-\tfrac12H_2(Q)\end{aligned}

For equally weighted distributions, 0 ≤ JSD₂ ≤ 1 bit. In nats, the upper bound is ln 2.

The mixture contains every event supported by either source. The two KL terms are therefore finite. Disjoint distributions reach one bit. Identical distributions give zero. JSD itself need not satisfy the triangle inequality, but its square root is a metric.

There is a useful experiment behind this formula. Draw a fair binary label Z, then draw X from P or Q according to Z. JSD(P,Q) equals the mutual information I(X;Z). It measures how much the observation reveals about its source.

If P and Q have disjoint support, one observation identifies the source label: it supplies one bit. If P equals Q, the observation cannot identify the label: it supplies zero bits. The mixture formula connects these two endpoints without requiring either source to encode the other’s unsupported events.

I(X;Y)=H(X)-H(X\mid Y)=D_{\mathrm{KL}}(P_{XY}\|P_XP_Y)

Mutual information measures dependence. It is not simply the entropy of either variable.

For P = [0.5, 0.5] and Q = [0.4, 0.6], JSD is about 0.00506 nats, or 0.00730 bits. Stating the unit prevents an apparent disagreement between implementations.

The midpoint is [0.45, 0.55]. The two natural-log KL terms are approximately 0.00503 and 0.00509. Average them to obtain JSD. For discrete inputs, validate nonnegativity and unit total mass first. Compute zero-mass terms by their limits; no epsilon clipping is required to handle structural zeros. Evaluating a dense K-bin divergence takes O(K) arithmetic, with no need to store every intermediate term.

Jensen–Shannon distance can compare normalized topic histograms or support distribution-shift monitoring. Such comparisons depend on the chosen bins and sampling noise; they do not directly evaluate the semantic quality of arbitrary generated samples.

Context changes the compression limit

The preceding formulas compare distributions over one outcome. A text compressor must encode a sequence, where earlier outcomes can help predict later ones. Natural language is not an independent sequence of characters. A letter that looks uncertain in isolation can become predictable after its context. A unigram entropy and a contextual entropy describe different prediction problems.

H(X_1,\ldots,X_n)=\sum_{t=1}^n H(X_t\mid X_1,\ldots,X_{t-1})

The chain rule does not assume independence. Conditioning cannot increase entropy on average, though a particular observed context can be unusually uncertain.

For a stationary finite-alphabet process, the entropy rate can be written as the limiting conditional uncertainty. It also equals the asymptotic joint entropy per symbol.

\begin{aligned}h&=\lim_{n\to\infty}\frac{H(X_1,\ldots,X_n)}{n}\\&=\lim_{n\to\infty}H(X_n\mid X_1,\ldots,X_{n-1})\end{aligned}

Stationarity gives the standard conditional-entropy limit. Coding guarantees require their source and coding assumptions; arbitrary text does not supply them automatically.

Shannon’s language experiments used human predictions to estimate contextual redundancy. Short n-gram counts capture local patterns. Longer contexts become too sparse for naive counting. A predictive system supplies generalization across those contexts.

“The entropy of English” is therefore not one alphabet-wide constant we can read from character frequencies. It depends on the source, unit, conditioning and estimation method. A language model’s measured loss is a model-dependent estimate of coding cost, not a direct measurement of a unique true entropy.

Prediction as compression

An autoregressive model supplies Q(xₜ|x<ₜ). The sequence probability is the product of these conditional probabilities. Its negative log probability is the sum of conditional surprises.

-\log_2 Q(x_{1:n})=-\sum_{t=1}^n\log_2 Q(x_t\mid x_{<t})

An arithmetic coder can use these conditionals when encoder and decoder reproduce the same probabilities.

The average token coding cost is the displayed sequence cost divided by n. Its unit depends on the tokenizer: bits per token is not directly comparable across different token vocabularies. Fix the encoding and report bits per byte or character when that is the intended comparison.

This makes next-token log loss a compression objective. Better predictions assign shorter ideal codes to actual continuations. The equality is about probability coding, not a guarantee that a practical implementation creates a smaller standalone file.

Weights, tokenizer, numerical conventions and decoder must be shared or transmitted. Sending a large model to compress a short document can increase total size. Compare total description lengths when the model cost is not amortized.

A well-compressed stream has less obvious redundancy for the same coding scheme. This does not prove that its finite output is uniformly random or cryptographically secure. Statistical unpredictability, secure encryption and semantic understanding are distinct claims.

Shannon entropy concerns an ensemble. Kolmogorov complexity concerns the shortest program describing an individual object on a chosen universal machine. It is uncomputable in general. A compressor supplies one computable description, not the exact shortest program.

For optimization details, continue to Losses and Objectives →. That reader separates code length from logit gradients and loss reduction.

Language Trees and Zipping

A language model exposes conditional probabilities directly. A dictionary compressor instead reuses byte patterns from earlier input. Both can exploit predictability, but only the probability model gives the exact coding identities above.

The 2002 paper by Benedetto, Caglioti and Loreto tests whether this indirect model can reveal relationships between texts. A compressor adapted to one text can describe a related text cheaply.

Let A be a long reference and b a short sample from a source B. Define the incremental compressed length $\Delta_{Ab}=C(A+b)-C(A)$ . This is the extra cost of appending b after A, not the cost of compressing b independently.

That cost contains both the sample’s own unpredictability and the mismatch with A. Subtract the cost of appending the same sample after a separate reference B from its own source. This mirrors cross-entropy minus entropy; dividing by the sample length gives a rate.

S_{A\to B}\approx\frac{\Delta_{Ab}-\Delta_{Bb}}{|b|}

The self-reference B provides a baseline. Ideally this resembles an excess coding rate for B under A: a B‖A direction, despite the A→B naming.

Keep units consistent. If C reports bytes and |b| counts input bytes, S reports extra compressed bytes per input byte. Multiply by eight for bits per input byte. The mathematical KL analogy does not automatically change the compressor’s output unit.

Keep b short relative to the reference and the compressor's history window. A long snippet teaches the compressor B while it is being measured. Later matches then use earlier parts of b rather than the patterns in A, weakening the intended cross-source comparison.

The theoretical bridge assumes the compressor learns useful source statistics. A real implementation has a finite dictionary, headers and adaptation delays. Its incremental cost is a proxy, not an exact KL estimator. Small samples can even give negative excess estimates.

def incremental_cost(reference, sample, compress):
    return len(compress(reference + sample)) - len(compress(reference))

# Same encoding, compressor options and reference-length policy.
best = min(references, key=lambda a: incremental_cost(a, sample, compress))

The paper tests language recognition, author attribution and a tree of language similarities. It uses short samples of roughly 1–15 KB with references around 32–64 KB. These sizes interact with the compressor’s window; they are not universal settings.

Historical results and their scope
Experiment	Reported observation	What it does not prove
Language identification	100 selected texts, ten European languages; nearest reference matched the language	Universal performance on short, mixed or unseen languages
Author attribution	84/90 correct nearest authors; 89/90 within the first two	Topic-independent identification or resistance to leakage
Language tree	More than 50 translated versions of the same document	Historical ancestry or exact linguistic distances

For the tree, the paper symmetrizes two relative excess costs. It then adjusts the distance matrix and applies the Fitch–Margoliash tree-fitting procedure to translations of the Universal Declaration of Human Rights. The resulting tree is unrooted. Its branches are not literal historical descent or exact pairwise distances. The reported grouping includes Romance, Germanic, Celtic, Slavic, Baltic and Uralic/Ugro-Finnic languages. Shared script, borrowing, morphology, topic and translation order can all affect placement. Family-like clusters alone do not separate those causes.

\begin{aligned}D(A,B)&=\frac{\Delta_{Ab}-\Delta_{Bb}}{\Delta_{Bb}}\\&\quad+\frac{\Delta_{Ba}-\Delta_{Aa}}{\Delta_{Aa}}\end{aligned}

Requires positive baseline costs. Symmetrization alone does not establish a mathematical metric.

Language Trees and Zipping ↗ is interesting because it extracts structure without a trained neural representation. Its broadest claims still need careful controls.

Compression as a representation criterion

A compressor discovers reusable patterns without an explicit embedding vector. This can provide a training-free baseline when objects have meaningful sequential structure. It is weaker when meaning is not reflected in surface patterns: paraphrases may share few bytes, while unrelated documents can share boilerplate.

The same principle motivates minimum description length (MDL). Choose a representation or grouping that shortens the total description, including its own cost. Merely lowering cluster-label entropy would favor a trivial single cluster; it is not sufficient evidence of useful structure.

L_{\mathrm{total}}(z,x)=L(z)+L(x\mid z)

A conceptual description-length objective. z is a representation/model; both terms need a stated coding scheme, not merely a smaller entropy statistic.

A learned structure earns its cost when it makes the observations cheaper to encode. Whether that structure supports a downstream task must still be measured. This is a connection between coding and representation learning, not a proof that compression equals intelligence.

What a compression experiment can establish

Compression similarity emphasizes patterns that the chosen compressor can reuse. Neural embeddings emphasize relationships learned through their own training objective. Neither representation is a universal measure of meaning.

Control the bytes. Fix encoding, normalization and file format. Shared boilerplate can dominate similarity.
Control reference length. A longer reference can help until the compressor’s window forgets earlier content.
Control leakage. Separate authors, topics and translated documents when the task requires those distinctions.
Check order. C(A + B) can differ from C(B + A). Report both directions when useful.
Use several samples. Estimate variability rather than trusting one favorable excerpt.
Measure implementation effects. Check several compressors, reference windows and snippet sizes. Container headers can dominate short inputs, and adaptation rules change the scores.
Compare baselines. Character n-grams, naive Bayes and embeddings answer useful competing hypotheses.

The same experiment can be tried on DNA, source code or time series encoded as symbols. Success establishes predictive regularity under that representation. It does not by itself establish causality, intelligence or semantic comprehension.

Sources and connected notes

Shannon: A Mathematical Theory of Communication ↗ · Shannon: Prediction and Entropy of Printed English ↗ · Kullback and Leibler: On Information and Sufficiency ↗ · Benedetto, Caglioti and Loreto ↗ · Lempel and Ziv: Universal Sequential Compression ↗ · Su Jianlin: Minimum-entropy clustering discussion ↗ · Visual Information Theory ↗ · Reinventing Entropy video ↗ · Cross-entropy visual explanation ↗