The Math of Compression: Where Intelligence Begins

Compression and prediction are mathematically equivalent

Information theory reveals that compressing data and predicting the next symbol are two sides of the same coin. This insight reframes large language model training: instead of thinking about next-token prediction via cross-entropy loss, you can view it as learning to build the most efficient text compressor. Understanding this equivalence clarifies why compression is relevant to intelligence.

The claim: compression is intelligence

While 'compression is intelligence' is hard to judge rigorously (intelligence is ill-defined), the safer claim is that the mathematical theory of compression is bizarrely relevant to artificial intelligence. This trilogy explores whether and how compression relates to building intelligent systems.

Three approaches to encoding instructions

A robot on a distant moon receives movement commands (up, down, left, right) with unequal frequencies: 50% up, 25% down, 12.5% left, 12.5% right. Three students propose solutions: (1) naive: 2 bits per instruction; (2) clever: variable-length codes (0 for up, 10 for down, 110 for left, 111 for right); (3) theoretical: what would perfect compression look like?

Average bits per instruction: naive vs. clever encoding

Prefix-free codes prevent ambiguity

For variable-length codes to work, no code word can be a prefix of another (e.g., 10 cannot be a prefix of 100). This prefix-free property ensures the robot can unambiguously decode by reading bits until it forms a complete code word. The clever student's codes (0, 10, 110, 111) satisfy this constraint.

Visualizing code space with a binary tree

A binary tree diagram shows all possible bit strings, with each layer representing strings of a given length. Choosing a code word 'consumes' all strings that start with it (its descendants). The clever student's allocation—0 (half the space), 10 (quarter), 110 (eighth), 111 (eighth)—perfectly mirrors the instruction probabilities, suggesting optimality.

Code space allocation matches instruction probabilities

Perfect compression produces random noise

A theoretical insight: if a compression algorithm is perfect, its output should look like random noise (each bit equally likely to be 0 or 1, independent). This is because if the output were predictable, you could compress it further. The clever student's encoding satisfies this: each bit is a fair coin flip.

Information formula: negative log of probability

If a message compresses to n bits and looks like random noise, all 2^n possible n-bit strings are equally likely, so each underlying message has probability 1/2^n. Taking the negative log base 2 yields: information = -log₂(p). This formula emerges naturally from asking about optimal compression, not as an arbitrary definition.

-log₂(p)

Information of an event with probability p

Fundamental formula of information theory

Intuition: unlikely events carry more information

A highly probable event (p near 1) has low information content; an unlikely event (p near 0) has high information. This matches intuition: learning that a rare event occurred is more surprising and informative than confirming an expected outcome.

Entropy: average information per symbol

For a probability distribution over symbols, entropy is the weighted average of each symbol's information: H = Σ p(i) × (-log₂ p(i)). This represents the minimum average bits per symbol needed to encode messages from that distribution—the fundamental compression limit. Higher entropy means more uncertainty; lower entropy means more predictability.

Language probabilities are context-dependent and non-integer

Unlike the robot example (clean probabilities that are powers of 2), natural language has probabilities that depend heavily on preceding context and are rarely clean powers of 2. This means information values are fractional bits, requiring a more sophisticated interpretation of what fractional bits mean in practice.

Information of a full message sums across symbols

By the chain rule of probability, the probability of a phrase is the product of successive letter probabilities (each conditioned on context). Taking the negative log converts multiplication to addition: information of the full message equals the sum of information for each letter. This elegant property justifies working with fractional bits at the symbol level.

Shannon's empirical approach to language entropy

Shannon could not calculate language entropy directly. Instead, he used experiments: first asking his wife Betty to guess the next letter in a text (measuring predictability), later interviewing multiple people and recording how many guesses were needed to get each letter right. This probed the underlying model of language in human brains, treating them as black boxes with sophisticated language understanding.

Shannon's experimental progression on language entropy

Entropy rate for language: the general case

When symbol probabilities vary (as in language), entropy is generalized to entropy rate: the average information per symbol averaged over all possible messages. This is almost never a clean calculation; it requires probing intelligent models of language rather than just analyzing text statistics. Shannon's estimate of 1 bit per character for English with sufficient context is remarkably low.

~1 bit

Estimated entropy of English per character (with 100+ letter context)

Shannon's empirical estimate suggests extreme compressibility

Cross-entropy loss in language model training

Large language models are trained using cross-entropy loss on next-token prediction. This term has roots in information theory. Reframing the training objective as learning to compress text (rather than just predict tokens) provides conceptual clarity: the model is learning to minimize the average bits needed to encode text, which is precisely what entropy measures.

From interrogating black boxes to designing them

Shannon studied language by interrogating human brains as black boxes—sophisticated, indescribable models of language. Modern machine learning has inverted this: we now design the black boxes ourselves. The mathematical foundations from information theory (information, entropy, cross-entropy) remain central to understanding and training these systems.

Shannon's noiseless coding theorem

No encoding can be more efficient than the entropy limit (average bits per symbol). Moreover, it is always possible to get arbitrarily close to this limit. This theorem, from Shannon's 1948 paper, is the foundation of information theory and establishes entropy as the fundamental measure of compressibility.

Three key expressions to rediscover

Beyond information itself, three core expressions emerge from studying compression: (1) entropy—average information per symbol for a fixed distribution; (2) entropy rate—average information per symbol for varying distributions like language; (3) cross-entropy—used in machine learning to measure how well a model's predicted distribution matches the true distribution.