Kolmogorov Complexity and MDL

Shannon entropy is a property of a distribution. It has nothing to say about a single object. The string of the first million digits of \(\pi\) and a million random digits have identical entropy under a uniform model over digit strings, and are obviously not equally complex: one has a twelve-line generating program, the other has none shorter than itself.

Kolmogorov, Solomonoff, and Chaitin independently formalised the difference in the mid-1960s. The Kolmogorov complexity \(K(x)\) of a string is the length of the shortest program, in some fixed universal language, that prints \(x\) and halts.

What the definition buys and what it costs

The invariance theorem rescues the definition from arbitrariness. For any two universal languages \(U\) and \(V\) there is a constant \(c\), depending on the pair but not on \(x\), such that \(|K_U(x) - K_V(x)| \le c\). The choice of programming language shifts complexity by an additive constant, so asymptotic statements are language-independent.

The cost is severe: \(K\) is uncomputable. If it were computable you could search for the shortest string whose complexity exceeds a given bound, and describe that string by the search itself, which is Berry's paradox made formal. No approximation from below is computable either; you can only ever exhibit upper bounds, by finding some program that works.

The relationship to entropy is the bridge back to usable theory: for a computable source \(p\), the expected Kolmogorov complexity satisfies

So on average, the shortest-program length equals the entropy, up to the cost of describing the source itself. Randomness in the Shannon sense and incompressibility in the Kolmogorov sense coincide in expectation while differing on individuals.

MDL: the computable shadow

Minimum description length, introduced by Rissanen in 1978, restricts the class of "programs" to a model family you can actually search, and turns the ideal into a model selection rule. Choose the model \(M\) minimising

the bits to describe the model plus the bits to describe the data given the model. A model too simple pays in the second term; a model too complex pays in the first. Overfitting becomes a coding inefficiency rather than a statistical mystery, and the trade-off needs no held-out set to state.

Two-part MDL as written is crude, and modern MDL uses normalised maximum likelihood or Bayesian mixture codes instead, which avoid the arbitrariness of how you encode the model. But the two-part form is the one that explains the intuition, and it maps directly onto familiar objects: \(L(D \mid M)\) is the negative log-likelihood, and \(L(M)\) behaves like a regulariser whose strength is not a free hyperparameter but a consequence of the coding scheme.

Why this matters for language models

A trained language model with an arithmetic coder is a lossless compressor of exactly the MDL form, and the compressed size of a corpus is the model's negative log-likelihood on it plus a constant. Delétang et al. push the identity to its conclusion, showing that Chinchilla 70B, trained on text, compresses ImageNet patches to 43.4 percent of raw size, beating PNG at 58.5 percent, and LibriSpeech audio to 16.4 percent against FLAC's 30.3 percent (Delétang et al., 2024, Language Modeling Is Compression, arXiv:2309.10668, ICLR 2024).

The MDL accounting adds the sharp caveat: those figures ignore \(L(M)\). Counting the 70 billion parameters needed to describe the compressor, Chinchilla is a catastrophic compressor of a single ImageNet patch and an excellent one only amortised over a corpus large enough to dwarf the model. Whether a scaling result is impressive depends entirely on whether you charge for the model, and this is the cleanest lens available for that argument.

When it breaks

Kolmogorov complexity is uncomputable, so every claim about it in an applied paper is a claim about some computable surrogate: gzip length, a model's negative log-likelihood, a circuit's parameter count. Those surrogates disagree with each other and with \(K\), and the disagreement is not a small constant in practice even though the theory promises a constant asymptotically.

MDL, meanwhile, is only as good as the code you chose for models. Two people can apply MDL to the same problem, choose different model codes, and reach opposite conclusions, both correctly. That is not a flaw so much as a demand for honesty: the prior is now explicit and written as a code length instead of hidden in a regularisation constant. Compare language modelling as compression and statistical learning theory, which bound generalisation from a different direction.