Language trees and zipping: a family tree from gzip

Transcript: this stretch, timestamped

Part 1 ended by pinning down entropy: the average surprise of a source, and the hard floor on bits per symbol that no encoder can go below (P6). Part 2 opens by refusing to define anything. Instead Grant puts a result on the table — a phylogenetic tree of European languages, built by a program that knows no linguistics — and lets it hang there as a debt. Everything from P8 through P10 is the machinery needed to pay it off, and P11 comes back at 12:59 to close the loop explicitly. This page is the setup: what the 2002 paper actually did, what the numbers were, and why a general-purpose file compressor has any business knowing that Danish is closer to Swedish than to Basque.

Outline, with timestamps

• 00:00 — The puzzle: cluster documents by language, and recover the lineage between the clusters, using only a function that reads text.
• 00:32 — The constraint and the trick: no pre-baked linguistics, no language models in 2002 — just gzip. Append a snippet of B to A, compress, compare against compressing A alone.
• 01:03 — What the difference means: how well a snippet of B compresses under a coder optimised for A. Small when the patterns match, large when they do not. Normalise it and you have a distance.
• 01:34 — The same trick does authorship attribution, and the reason Grant likes the paper: engineering from compression solving what looks like a machine-learning problem.
• 01:55 — The concept underneath is named: cross-entropy — also the core of how modern language models are trained.
• 02:05 — The plan for the video: first half, cross-entropy from first principles; second half, pre-training and distillation, where the same formula appears to come from somewhere else entirely.
• 02:38 — The promise: reframe LLM training as compression rather than next-token prediction. Then back to basics — bits.

00:00 · The task: a family tree with no linguistics in it

The paper is "Language Trees and Zipping", by Dario Benedetto, Emanuele Caglioti and Vittorio Loreto, all at La Sapienza in Rome — Physical Review Letters 88(4), 048702, January 2002. The corpus is the best-behaved multilingual dataset in existence: the Universal Declaration of Human Rights, the most-translated document there is, in more than fifty versions, all transcoded to Unicode so the character encoding cannot leak information about the language.

The output is a tree, not a classification. Every pair of documents gets a distance, the distances form a matrix, and the matrix goes into a standard phylogenetics program — the Fitch–Margoliash method from Felsenstein's PHYLIP package, with the Neighbor algorithm reported as giving similar results. What comes out separates Romance from Celtic from Germanic from Slavic from Baltic, puts Danish next to Norwegian and Portuguese next to Galician, and leaves Basque and Maltese on their own branches — which is exactly right, since neither is Indo-European.

Two caveats the video has no time for. The tree is unrooted — it asserts relative proximity, not descent from a reconstructed ancestor — and the drawn branch lengths are not the matrix distances. And it is not purely an Indo-European tree: Finnish, Estonian and Hungarian cluster as Ugro-Finnic, Turkish and Uzbek as Altaic. Recovering non-Indo-European families too is the stronger result, not a blemish.

00:32 · The recipe: three file sizes and a subtraction

Take a long document A, a long document B, and a short snippet b cut from B. Form the concatenation A+b, zip it, and measure. Define

Δ_Ab = L(A+b) − L(A)      bits charged to b by a coder warmed up on A
Δ_Bb = L(B+b) − L(B)      bits charged to b by a coder warmed up on b's own source

where L(X) is the compressed size of file X. The first quantity is the cost of b under A's statistics; the second is the cost of b under its own, which is the best this compressor can do. The paper's estimate of the relative entropy per character between the two sources is their difference, normalised by the snippet length:

S_AB = (Δ_Ab − Δ_Bb) / |b|                          (paper, eq. 1)

That is not yet a distance — it is asymmetric and it carries the units of whatever coding the files use. For the tree, the authors symmetrise and make the normalisation self-referential, dividing each half by the corresponding self-compression cost, with a a short snippet cut from A:

S_AB = (Δ_Ab − Δ_Bb)/Δ_Bb  +  (Δ_Ba − Δ_Aa)/Δ_Aa    (paper, eq. 2)

They then force the resulting matrix to satisfy the triangle inequality before handing it to the tree builder. Sizes matter and the paper states them: A of order 32–64 KB, snippet b of 1–15 KB, with results robust across that range. Grant flags at 13:45 that the real metric is a bit more elaborate than the bare difference he draws; equation 2 is what he is glossing over.

01:03 · Why a general-purpose zipper knows anything about language

The engine inside gzip is LZ77. As it scans it keeps a sliding window of recently-seen text, and at each position looks for the longest match between what is coming up and something already in the window. A match is emitted as a pair (d, n) — go back d characters, copy n of them — at a cost of roughly log₂ d + log₂ n bits. A sequence that recurs often has a small typical back-distance and is therefore cheap; a rare one has a large d and is expensive.

That is the whole reason this works. The window is a model. A crude, non-parametric one — no grammar, no vocabulary, no notion of a word — but it assigns short codes to frequent substrings and long codes to rare ones, which is what a statistical model of text does. And the approximation is not merely suggestive: for an ergodic source of entropy rate s bits per character, the LZ77 compression ratio converges to s as the input grows. Zip a long enough file and you have measured its entropy rate.

Now run the tape on A+b with A English and b Italian. Through the English, the window fills with English; the moment the Italian starts, the coder is still looking backwards into English for matches, and mostly fails — so those first Italian characters are expensive. Given enough Italian it would relearn, and the price would fall back towards Italian's own entropy rate. That is why b must stay short: a snippet long enough for the compressor to re-adapt measures nothing.

01:34 · What the paper reported, in numbers

The tree is the headline, but the two cleaner benchmarks the paper reports first are what to quote when someone doubts a subtraction of file sizes can carry this much signal.

Twenty characters is the number that should stop you: two dozen characters of Portuguese shift a compressed file size measurably more when appended to a Spanish corpus than to a Danish one. That is very little evidence doing a very confident job.

01:55 · What the extra bytes actually measure

Here is the connection the video spends the next ten minutes earning. The derivation below is this page's addition; Grant states the conclusion and defers the argument. Model source B as emitting symbols from a distribution p, and the compressor warmed up on A as implementing a code built for a distribution q. An optimal code for q spends log₂(1/qᵢ) bits on symbol i (the whole content of P8). Run that code on symbols arriving with frequencies p and the average cost per character is the weighted sum

H(p, q) = Σᵢ pᵢ · log₂(1/qᵢ)          cross-entropy: q's code, p's frequencies
H(p)    = Σᵢ pᵢ · log₂(1/pᵢ)          entropy: the floor, achieved when q = p
D(p‖q)  = H(p, q) − H(p)              the excess — Kullback–Leibler divergence

Line those up against the file sizes. Δ_Ab/|b| is bits per character for b under A's model — an empirical stand-in for H(p, q); Δ_Bb/|b| is the same under b's own model, a stand-in for H(p). So equation 1 is

S_AB = (Δ_Ab − Δ_Bb)/|b|  ≈  H(p, q) − H(p)  =  D(p‖q)

which is exactly why the paper calls its quantity the relative entropy and cites Kullback and Leibler for it. The raw extra bytes are cross-entropy; subtracting the self-compression baseline strips out how intrinsically compressible B happens to be and leaves pure model mismatch.

Two descendants of the same trick (added here)

Rudi Cilibrasi and Paul Vitányi later turned the idea into a general clustering method with a cleaner normalisation, the Normalized Compression Distance: for a compressor C,

NCD(x, y) = ( C(xy) − min{C(x), C(y)} ) / max{C(x), C(y)}

It lands in roughly [0, 1], is symmetric by construction, and is the computable shadow of the uncomputable normalized information distance built from Kolmogorov complexity. Their paper clusters genomes, music and text with the same code path.

The modern echo is the 2023 "gzip beats BERT" result — Jiang et al., pairing NCD-with-gzip against a k-nearest-neighbour classifier for text classification with zero training and zero parameters. Read the criticism alongside it: Ken Schutte showed the headline out-of-distribution table effectively scored top-2 accuracy through the k=2 tie-break, and the advantage largely evaporates when ties are scored conventionally. Compression distance is a strong zero-cost baseline, not a replacement for a trained model.

02:05 · The rest of the video is the explanation

Grant lays out the plan explicitly. First half: what cross-entropy is, how it falls out of the study of codes, and how to picture it — P8 (the optimal-code recap), P9 (the definition and its two asymmetric slots), P10 (worked numbers and the bound H(p,q) ≥ H(p)). At 12:59 he returns to this cold open and states the identification directly — that is P11, where he also lists why this is an estimate rather than the thing itself: a text is not literally a sample from a stationary distribution, and gzip is very far from the Shannon limit.

"What I like about this paper is what a pure example it is of when the theory and the engineering behind compression can be surprisingly useful to tasks which would seem to fall in the domain of machine learning and artificial intelligence."— Grant Sanderson, 01:34

The second half then derives the same formula from a completely different starting point — the loss used to pre-train a language model — which is the payoff the whole series is built towards.

"Whenever you see the same formula pop up in two separate contexts, it's math's way of kind of winking at you and hinting at a connection."— Grant Sanderson, 02:38

Where people get stuck

"So gzip is measuring Kolmogorov complexity?" No, and the gap is not small. Kolmogorov complexity is the length of the shortest program producing the string; it is uncomputable, and the paper invokes it only as the ideal that compressors gesture at. LZ77 finds repeated substrings within a bounded window — DEFLATE's is 32 KB — and nothing else. It cannot notice that a text is in iambic pentameter or that a sequence is the digits of π. Every claim here is about a specific weak compressor, which is why the method needs a distance and a clustering step rather than an absolute number.

Why the file sizes have to be tuned. Bigger A is not automatically better. Once A exceeds the sliding window, the beginning of it is gone from the coder's memory by the time the snippet arrives, so extra corpus buys nothing and the ratio drifts for unrelated reasons. Meanwhile b must stay short enough that the coder never re-adapts to it. The 32–64 KB / 1–15 KB numbers are not arbitrary — they are the band where the window is full of A and still full of A when b ends.

Which document is in which slot. Δ_Ab measures B seen through A's model, not the reverse, and the two differ. The paper's own gloss is that it is "the difficulty for a generic person of mother tongue A to understand the text written in language B" — a native Spanish speaker reading Portuguese is not in the same position as the reverse when the two corpora differ in size or richness. That asymmetry is inherited straight from cross-entropy: H(p,q) ≠ H(q,p), and it is why equation 2 explicitly adds both directions.

Why subtract anything at all. A tempting simplification is to rank languages by Δ_Ab alone. That fails, because Δ_Ab confounds two effects: how far B's statistics are from A's, and how compressible B is on its own terms. A language whose UDHR translation is simply more repetitive will look "close" to everything. Subtracting Δ_Bb — B's own floor — cancels that term. In the formalism, it is exactly the step from cross-entropy to KL divergence.

Going deeper, verified

• Language Trees and Zipping — Benedetto, Caglioti & Loreto (2002), arXiv preprint · Four pages, no prerequisites past this page; contains the equations, the results table and the tree figure.
• Phys. Rev. Lett. 88, 048702 — the version of record for the paper above · Cite this one; the APS site sits behind a bot check, so the arXiv link is the readable copy.
• Clustering by Compression — Cilibrasi & Vitányi (2005, IEEE Trans. Inform. Theory 51(4) 1523–1545) · The Normalized Compression Distance, its theory, and clustering experiments well beyond text.
• "Low-Resource" Text Classification: A Parameter-Free Classification Method with Compressors — Jiang, Yang, Tsirlin, Tang, Dai & Lin (Findings of ACL 2023) · The modern gzip-plus-kNN classifier; the same distance, twenty-one years later.
• Bad numbers in the "gzip beats BERT" paper? — Ken Schutte (2023) · The tie-breaking critique of the table above; read before repeating the headline.
• RFC 1951: DEFLATE Compressed Data Format Specification — Deutsch (1996) · What gzip actually does, including the 32 KB window that governs how big your files may be.

Exercises

1. Rebuild one row of the distance matrix — Fetch the UDHR in English, Dutch, Italian, Spanish and Finnish as UTF-8. Fix a 4 KB snippet b of Spanish; build 48 KB corpora for the others; compute Δ_Ab = L(A+b) − L(A) with gzip -9 for each A, and report the results in bits per character of b. A good answer states every file size, gives five numbers, and shows Italian below Dutch below Finnish. It also notes whether Δ_Ab for Spanish-on-Spanish is close to gzip's standalone ratio on Spanish.
2. Find the window cliff — Hold b fixed and sweep |A| from 4 KB to 512 KB, plotting Δ_Ab/|b|. Predict the shape first: falling while the window is still filling with useful A, then flat, because DEFLATE cannot see past 32 KB. Re-run with xz, whose dictionary is far larger, and show the flattening point moves. A good answer names the window size for each tool and explains why "more corpus" stops helping.
3. Separate cross-entropy from KL by hand, then measure it — With p = (0.9, 0.1) and q = (0.5, 0.5), verify H(p) = 0.469 bits, H(p,q) = 1 bit, D(p‖q) = 0.531 bits. Swap the roles and get H(p) = 1, H(p,q) = 1.737, D = 0.737 — note that the second of these is the ≈1.74 bits Grant computes at 09:52. Then generate 200 KB of i.i.d. bytes from q, append 4 KB drawn from p, and compare the measured Δ/|b| against 1.737 bits per symbol. A good answer explains the gap: gzip is not an optimal code for a memoryless binary source, and says which direction the error goes.