Back to the language trees: what zip was measuring

Transcript: this stretch, timestamped

Ten pages of machinery have been laid down for this moment. P1 posed the thesis — compression and prediction are the same problem seen from two sides. P8 through P10 built cross-entropy from the ground up: what a code optimised for q costs when reality is p, why that cost is minimised exactly when q = p, and why the minimum is the entropy of p. Grant now turns that machinery around and points it at the opening hook — the 2002 "Language Trees and Zipping" result — and the strange claim from minute one becomes almost obvious. This page is the hinge: behind it, cross-entropy as a fact about codes; ahead of it, on P12, exactly the same expression showing up as the loss function of a large language model, with a transformer standing where gzip stands here.

Outline, with timestamps

• 12:59 — Callback: with the cross-entropy diagram in hand, go back and look at the zipping trick again.
• 13:15 — The procedure restated: snippet of B onto A, compress, subtract the size of A compressed alone.
• 13:31 — The identification: the zipper is optimised for A's patterns, so the difference asks cross-entropy's question.
• 13:52 — Caveat one: the authors' actual distance metric is more elaborate than the bare difference.
• 14:03 — Caveat two: this compares two documents, not two distributions — it is an empirical estimate.
• 14:15 — Caveat three: gzip is nowhere near the Shannon limit; LZ77 just points back at earlier repeats.
• 14:34 — The verdict: insofar as it approximates cross-entropy, it is still a useful distance, and it did a real NLP job.
• 14:45 — The general pattern: cross-entropy is what you reach for to quantify how one setting's patterns differ from another's — which hands off to language models.

12:59 · The measurement, written out

Strip the trick to its arithmetic. Let A be a long document in one language and B a long document in another. Take a short snippet b out of B, glue it onto the end of A, compress the concatenation, and subtract:

Δ_Ab  =  |zip(A·b)|  −  |zip(A)|        bits

The subtraction is doing the work. Every fixed cost cancels — the gzip header, the checksum, the Huffman tables describing A's own blocks — leaving only the bits spent on b given that the compressor had already read A. Divide by |b| and you have a rate in bits per character, comparable across pairs. That conditioning is the whole idea, and Grant flagged it in the first minute: the difference measures how well a snippet of B compresses when the compressor is mostly optimised for A.

13:31 · Why that difference is a cross-entropy

"How well does a compression scheme optimized for one context perform when faced with another context?"— Grant Sanderson, 13:31

That is not an analogy to cross-entropy; it is the definition. An encoder built around a distribution q spends about log₂(1/q(x)) bits on the symbol x. If symbols actually arrive from p, the expected cost per symbol is the weighted sum

H(p, q)  =  Σ p(x) · log₂( 1 / q(x) )     bits per symbol

Now feed the two roles of the experiment into that formula. Reading A leaves the compressor with some implicit model q_A of Italian. The snippet b is Danish, so its symbols arrive from something like p_B. Therefore Δ_Ab ≈ |b| · H(p_B, q_A). Append Danish to a Danish corpus instead and the model is priced correctly, so Δ_Bb ≈ |b| · H(p_B) — the entropy floor, the green curve from 12:28. The floor is not a coincidence: H(p, q) ≥ H(p) for every q, with equality only when q = p. (My addition: that is Gibbs' inequality, one line of Jensen applied to the concave logarithm.) So the two numbers can never cross, and their difference is never negative:

( Δ_Ab − Δ_Bb ) / |b|   ≈   H(p_B, q_A) − H(p_B)   =   D( p_B ‖ q_A )

That last object is the Kullback–Leibler divergence: the bits per character you waste by modelling Danish with Italian. It is also, character for character, equation (1) of the 2002 paper. (My addition: the video reaches KL only in its final chapter — the trick from minute one was already computing one.) A toy you can check by hand, reusing the four-symbol distributions from earlier in the video as two "languages" over one alphabet:

A hundred-odd bytes, from a file-size subtraction, standing in for "how far is Danish from Italian". That is the whole 2002 paper in one row.

13:31 · Every compressor is a model; every model is a compressor

The step above quietly assumed that gzip has a probability model. It does, and the equivalence runs in both directions — this is the sentence the series exists to earn, so it is worth nailing down.

Model → compressor. Given any distribution q over strings, arithmetic coding encodes s in about log₂(1/q(s)) bits, with under two bits of overhead for the entire message. A model you can query for probabilities is already a compressor; the coder is plumbing.

Compressor → model. Run it backwards. Any uniquely decodable binary code with lengths ℓ(x) obeys Kraft's inequality, Σ 2^(−ℓ(x)) ≤ 1. So q(x) = 2^(−ℓ(x)) is a sub-probability distribution — normalise it and you have a genuine model that the code is optimal for. Apply this to whole files and gzip defines q_gzip(s) = 2^(−|zip(s)|): a probability distribution over documents in which a file is "likely" exactly to the degree that it is small. Every lossless compressor on your machine is a language model. Most of them are terrible ones.

Under that reading, Δ_Ab stops being a file-size artefact and becomes a log-likelihood: Δ_Ab ≈ −log₂ q_gzip(b | A), the model's total surprise at the Danish snippet after having been shown Italian. Which is the number a language model reports as its loss.

13:52 · From a difference to a matrix to a tree

Grant says he is glossing over the authors' real metric, so here it is. A raw Δ is asymmetric and not scale-free: it depends on how the files happen to be encoded and on how compressible the target language is on its own. The paper therefore builds each entry of its distance matrix out of two normalised divergences, one in each direction:

S_AB  =  (Δ_Ab − Δ_Bb) / Δ_Bb   +   (Δ_Ba − Δ_Aa) / Δ_Aa

Each term is a divergence divided by the entropy estimate of the language being modelled, which makes the ratio dimensionless and largely independent of how the files are encoded. Summing both directions symmetrises it, since KL is not a metric; the authors then nudge the matrix into satisfying the triangle inequality and feed it to a standard phylogenetics routine (Fitch–Margoliash, from the PHYLIP package) — the tool biologists point at gene sequences. Their corpus was over fifty translations of the Universal Declaration of Human Rights, which is neat experimental design: content is held fixed across every file, so only the language varies. The unrooted tree separates Romance, Germanic, Celtic, Slavic, Baltic, Ugro-Finnic and Altaic, and leaves Basque and Maltese on their own branches — roughly what a linguist would draw.

14:03 · Where the approximation is loose

"…it can't be a very good estimate because gzip is not perfect compression achieving the Shannon limit. Very far from it."— Grant Sanderson, 14:15

Take that seriously. This is a good heuristic, not a measurement, and it helps to know exactly which joints are loose:

• gzip is not an optimal coder. DEFLATE replaces repeated substrings with (distance, length) pointers, then Huffman-codes the result. Its length converges to the source's entropy rate only in the limit of infinite text, and slowly. Every Δ is an over-estimate, and the over-estimates only partly cancel in the subtraction.
• The window is finite. DEFLATE's back-references reach at most 32 KB, so the compressor's "knowledge of Italian" when the Danish starts is whatever fits in that window. The original experiments used files of about 32–64 KB for exactly this reason.
• The model adapts while you measure it. Once enough of b has gone by, the zipper starts finding its matches inside b itself — it "learns Danish" mid-snippet — and the marginal cost per character drifts down toward Danish's own entropy. So Δ_Ab/|b| shrinks as |b| grows, biasing the estimated divergence toward zero. Hence the requirement that b be small enough; the paper's snippets ran 1–15 KB.
• Two documents are not two distributions. There is no p_B in the experiment — only a finite sample treated as if drawn from a stationary ergodic source. Real text is neither, and topic, genre and orthography leak into the estimate alongside language.
• Byte counts are quantised, and normalisation matters. Sizes come in whole bytes, block structure adds jitter, and raw numbers scale with the character encoding — which is why the paper works in a uniform Unicode encoding and divides by Δ_Bb instead of using the bare difference.

None of this sinks the result. Grant's point at 14:34 is that insofar as the file-size difference tracks cross-entropy, it inherits enough of its structure to do real work — recovering language families, and attributing authorship too. A biased estimator with the right monotonicity is often all a clustering algorithm needs.

14:45 · The same quantity, one page later

The closing beat generalises the pattern: reach for cross-entropy whenever you want to quantify how far one setting's patterns are from another's. In 2002 that meant Danish against Italian; on the next page it means a model's grasp of language against the statistics of a training corpus. Nothing about the formula changes — only what plays the part of q. Swap gzip's 32 KB window for a transformer's billions of parameters, and −log₂ q(next token | context), averaged over a corpus, is pre-training loss. Same quantity, better model.

Where people get stuck

"Which document is the model and which is the data?" The corpus you compress first is the model; the snippet you append is the data. A supplies q, b supplies p, and the number you get is H(p_B, q_A) — read the slots of H(p, q) as (reality, model). Swap the documents and you get a different number, because cross-entropy is not symmetric. That asymmetry is why the paper's distance sums both orderings rather than measuring one of them.

"Why subtract Δ_Bb at all — isn't the raw cost of encoding Danish under Italian already the answer?" No, because that cost has two components you want to separate: how intrinsically unpredictable Danish is, and how badly Italian's statistics misprice it. Only the second is about the relationship between the languages. A language with a rich morphology looks "far from everything" if you never subtract its own entropy floor. Subtracting turns a cross-entropy into a divergence, which is the quantity that is zero when the two languages coincide.

"If gzip is so bad, why does the tree come out right?" Because tree-building consumes rankings, not absolute values. Fitch–Margoliash needs Danish–Swedish to score lower than Danish–Portuguese; it does not need either number to be the true divergence in bits. A systematically biased estimator that preserves order is fine. This also predicts the failure mode: pairs whose true divergences are close get shuffled by gzip's noise, which is why the fine structure inside a family is the shakiest part of such a tree.

"Isn't this just Kolmogorov complexity?" Related, but keep them apart. The Shannon-flavoured story here is about the entropy rate of a stochastic source, estimated by a real compressor. The Kolmogorov-flavoured story — shortest program that outputs the string — is uncomputable, and yields a different, later formalisation (normalised compression distance) that also uses gzip as a stand-in. The 2002 paper gestures at both; the video's derivation is the Shannon one.

Going deeper, verified

• Language Trees and Zipping — Benedetto, Caglioti & Loreto (2002), Physical Review Letters 88, 048702 · The paper behind the opening hook; equations (1) and (2) are the ones reconstructed above, and the language tree is Figure 1. Published version: doi:10.1103/PhysRevLett.88.048702.
• Clustering by Compression — Cilibrasi & Vitányi (2005) · The rigorous successor: normalised compression distance, built on Kolmogorov complexity, with proofs that it is a metric and applications well beyond text.
• DEFLATE Compressed Data Format Specification version 1.3 — Deutsch (1996), RFC 1951 · What gzip actually does: LZ77 matching with a 32 KB window plus Huffman coding. Read it if you want to know precisely which approximations you are buying.
• "Low-Resource" Text Classification: A Parameter-Free Classification Method with Compressors — Jiang et al. (2023) · The modern echo — gzip plus a nearest-neighbour rule as a text classifier. Its headline numbers drew scrutiny over evaluation details, which makes it a useful case study in exactly how far the heuristic stretches.

Exercises

1. Reproduce the hook. Grab the Universal Declaration of Human Rights in six languages, build Δ_Ab for every ordered pair using gzip -9, assemble the symmetric normalised matrix from the formula above, and run any hierarchical clustering you like on it. A good answer shows the matrix, notes which pairs are closest, and reports at least one pair the method gets visibly wrong.
2. Check the arithmetic. Using the table above, confirm H(p) = 1.75 and H(p, q) = 2.625 bits per symbol by hand, then verify that D(p‖q) = 0.875. Then swap p and q and compute the divergence again — a good answer states the new number and explains, in one sentence, why it differs.
3. Find the bias. Fix an English corpus A of 64 KB and a French snippet, and plot Δ_Ab / |b| as the snippet grows from 200 bytes to 30 KB. A good answer shows the curve bending downward, identifies roughly where the compressor starts matching inside the snippet rather than inside A, and says what that implies about choosing |b|.