The length of the shortest program that reproduces a given string, a measure of how much information one specific object carries, approximated in practice by how well it compresses.
The Kolmogorov complexity of a string is the length of the shortest program that outputs that string and stops. Written \(K(x)\), it measures the information contained in \(x\) rather than how long \(x\) happens to be. A million characters of "ab" repeated has a tiny \(K(x)\), because a three-line loop reproduces the whole thing. A million characters of coin-flip noise has \(K(x)\) close to a million, because no description of it is shorter than the string itself.
Two properties govern how the idea is used. It is uncomputable: no program returns the shortest description for every input, so every figure quoted in practice is an upper bound produced by one specific compressor. And it is defined only up to an additive constant that depends on the programming language you pick, so comparisons between strings under one fixed compressor carry meaning while absolute values do not.
Shannon entropy describes a source: the average number of bits needed per symbol drawn from a probability distribution. Kolmogorov complexity describes one object: the bits needed to write this particular string down. The two meet at the point where the entropy of a source equals the expected complexity of the strings it emits.
Our corpus study of The Verge measured both sides of that split across 152,192 articles: order-0 entropy over symbol frequencies, and gzip bits per byte over the raw bytes. The gzip figure is the computable stand-in. Because a compressed file plus its decompressor is a program that outputs the original, gzip output length bounds the complexity from above:
$$\lvert \text{gzip}(x) \rvert \ \ge \ K(x) - c$$where \(c\) is a constant that does not depend on \(x\). Every practical "information density" number, ours included, is a bound of this kind rather than \(K(x)\) itself.
A model that assigns a probability to each next token defines a compressor. Feed those probabilities to an arithmetic coder and the code length for a text is its negative log-likelihood under the model, so a better predictor is a shorter code by exactly the same margin. This is why language model quality is reported in bits per byte, the same unit as compression, and why a model's token probabilities and its compression rate on a corpus are two views of one number.
The quantity that bears on AI visibility is the conditional form, \(K(x \mid y)\): the shortest description of \(x\) for someone who already has \(y\). Set \(y\) to what a model absorbed from its training data, and \(K(x \mid y)\) counts the bits your page adds to what that model can already produce unaided.
A page that restates the settled consensus has low conditional complexity. The model generates that text from its prior, so grounding on your copy of it leaves the answer unchanged. A page carrying a measurement, a date, a price, a named entity, or a result the model has not seen has high conditional complexity, and it is the only kind of page that can move what the answer says. This is the information-theoretic reading of the pressure described by primary bias and selection rate, and the reason semantic compression works: it raises the information a single extracted grounding chunk carries without lengthening the page.
