Compression-learning identity

Compression-learning identity is the idea that learning and compression are two descriptions of discovering structure in data. A learner finds regularities that explain or predict observations; a compressor uses regularities to describe those observations with fewer bits. In this view, to learn a pattern is to discover a shorter way to describe it.

The name is used here as an umbrella term for related ideas in information theory, statistical learning, and artificial intelligence. The literature includes formal prediction–compression correspondences, the Minimum Description Length principle, and broader claims that powerful compression requires understanding or intelligence. These claims have different scopes; they are not one theorem equating every kind of learning with every kind of compression.

The central intuition

Consider a sequence containing a thousand repetitions of abc. One description lists all three thousand characters. Another gives the pattern and the repetition count. Discovering the repetition supplies both a shorter description and a prediction of what would come next if the pattern continues.

The same idea extends to less obvious regularities: grammatical structure, relationships between objects, recurring causes, and mathematical rules. Learning replaces separate observations with a reusable explanation, while retaining a way to account for the details the explanation does not predict.

The important economy is therefore model plus unexplained detail. Simply deleting inconvenient observations makes a description shorter without explaining them. Lossless compression must preserve enough information to reconstruct the original data.

Prediction and compression

A probabilistic model assigns probabilities to possible observations. Coding methods can turn those probabilities into code lengths: likely observations receive short descriptions, while surprising ones require more bits. The ideal length associated with an outcome x is:

L(x) = −log₂ p(x)

For a sequence, the corresponding ideal description length is the sum of the negative logarithms of the model's conditional predictions. Arithmetic coding can approach this length, with coding overhead. Improving next-token log loss therefore improves the data's achievable compression length under the same model and encoding setup.

This is a precise connection between prediction quality and compression. It does not require the predictor's internal state to resemble a zip file. Delétang and colleagues demonstrate the connection using language models as compressors and also show how compressors can be used to construct conditional generative models.

Minimum Description Length

Jorma Rissanen's Minimum Description Length (MDL) principle makes compression a criterion for learning and model selection. Peter Grünwald's tutorial develops the principle as a method for identifying regularities through short descriptions.

A simple two-part formulation chooses the model M minimizing:

L(M) + L(D | M)

Here L(M) is the length needed to describe the model, and L(D | M) is the length needed to encode the data using it. An elaborate model may fit observations very closely but cost too much to describe. A tiny model may leave too much unexplained. Learning seeks a useful balance between those costs.

This makes the compression claim more substantial than “a model has fewer parameters than its training set.” A complete coding account includes whatever the decoder needs: model information, shared assumptions, and residual data. MDL has more sophisticated formulations than the two-part expression, but the expression captures its basic tradeoff.

Kolmogorov complexity

Kolmogorov complexity formalizes the shortest-description idea. For a fixed universal computer U, the complexity of a finite string x is the length of the shortest program that outputs x and halts:

K_U(x) = min { |p| : U(p) = x }

A long sequence can have low complexity if a short program generates it. An incompressible string instead requires approximately its own length to specify. The complexity depends on the reference computer, but changing between universal computers changes it by at most an additive constant independent of x.

Conditional complexity, K(y | x), measures the shortest program producing y when x is available as background information. It gives a precise language for asking how knowledge of one dataset helps explain another.

K is not computable in general. A working compressor supplies an upper bound, including the decoding machinery, rather than a guaranteed shortest description. Shortest program length also does not imply fastest execution. Kolmogorov complexity concerns individual objects; Shannon entropy concerns uncertainty under a probability distribution.

Ilya Sutskever: An Observation on Generalization

In An Observation on Generalization, presented at the Simons Institute on 14 August 2023, Ilya Sutskever develops a compression-based perspective on unsupervised learning using Kolmogorov complexity.

The motivating problem is an objective mismatch: unsupervised training optimizes prediction, reconstruction, or another objective, while the user cares about success on a different task. Why should improving the first objective help the second? Sutskever proposes compression as a way to reason about that transfer, including cases where the unlabeled data offers no useful help.

Shared structure and joint compression

His central thought experiment considers two datasets, X and Y, compressed together. A sufficiently capable compressor can exploit patterns in X to encode Y more efficiently, and vice versa. The saving relative to separate descriptions measures shared structure. In algorithmic information theory, this is expressed through algorithmic mutual information, schematically:

Shared information ≈ K(X) + K(Y) − K(X, Y)

The expression suppresses coding and complexity-variant overheads. For practical compressors, a corresponding difference in compressed sizes is evidence of structure that the chosen compressor exploits, rather than an exact computation of algorithmic mutual information.

Here X is the unlabeled dataset and Y is the supervised task dataset. The claim concerns whole datasets, rather than conditioning on just one example. Sutskever uses conditional Kolmogorov complexity to describe the ideal task and argues that joint compression can capture the same benefit, with technical qualifications.

Low regret: using all available help

Sutskever asks how much predictive value a learning procedure leaves unused in its unlabeled data. Low regret means doing close to the best possible job of using X to describe Y; it does not mean that X must contain useful information about Y.

The ideal conditional compressor has a simulation guarantee: it can match a computable alternative's description by including the program implementing that alternative. Schematically, for a suitable lossless coding procedure A:

K(Y | X) ≤ L_A(Y | X) + description length of A + coding overhead

This is a comparison of information costs, including the competing procedure's description. It is not a guarantee of equal runtime. If X contains relevant structure, the ideal description can exploit it; if X is irrelevant, the procedure need not obtain a benefit from it. The framework defines successful use of side information without promising that every unlabeled corpus improves every task.

Neural networks as practical program search

Sutskever compares a neural network to a computing circuit and stochastic gradient descent (SGD) to a restricted search over programs. Larger networks can express richer computations, motivating their interpretation as practical attempts to approach the ideal compressor. Maximum-likelihood training connects to coding through negative log likelihood, with model-description cost also included.

In the Q&A he explicitly limits the analogy. SGD's search depends on optimization dynamics and data order, while the ideal shortest-description formulation abstracts away from that search. The theory also ignores compute cost: a short explanation can be prohibitively expensive to find or execute. It therefore supplies an informational ideal, rather than a proof that making a network larger always improves learning.

Evidence from pixels, and what remains unexplained

Sutskever presents image GPT (iGPT) as an empirical proof of concept beyond language. A transformer trained to predict successive pixels learns image representations useful for classification, despite receiving no class labels during pretraining. The accompanying paper evaluates linear probes and fine-tuning; its CIFAR-10 results distinguish 96.3% linear-probe accuracy from 99.0% accuracy after full fine-tuning.

He stresses that useful linear representations are a bonus the compression argument does not explain. A linear probe tests whether a simple linear classifier can extract task information from learned features. His argument more directly motivates adapting a model to a related task than expecting those features to be linearly separable.

His suggestion that next-pixel prediction forces more long-range understanding than filling in masked pixels is offered as a speculation. The observed usefulness of iGPT supports predictive pretraining; it does not establish that every good compressor exposes task knowledge through a linear classifier.

Researchers associated with the idea

Marcus Hutter argues that strong compression is closely related to intelligence. His Human Knowledge Compression Prize motivates progress in AI through better lossless compression of an encyclopedia: increasingly effective compression of varied knowledge is expected to require increasingly capable models of that knowledge. This is a research program connecting compression and understanding, rather than a proof that any small archive possesses general intelligence.

Jürgen Schmidhuber emphasizes compression progress: the improvement in an observer's ability to describe the same experience. In his account of curiosity and intrinsic motivation, an agent is rewarded for discovering previously unknown regularities that make its observations more predictable or compressible.

The distinction matters. A familiar repetition can already be easy to compress, while teaching the observer little. Pure noise may be surprising without offering a learnable pattern. Compression progress concerns the discovery between those extremes: data becomes easier to explain because the learner has improved.

Does good compression strictly require learning?

The strongest defensible answer depends on what learning means.

If learning means discovering or acquiring exploitable regularities, improving compression on unfamiliar structured data is a natural measure of learning. An adaptive compressor can acquire symbol frequencies, repeated phrases, or contextual dependencies as it processes a stream. A trained predictor can acquire much richer regularities before encoding begins.

But a fixed compressor can successfully compress a suitable input without updating its model. A run-length encoder already knows how to represent long repetitions; its rule may have been supplied by its designer. In that case, the regularity is being exploited without a new learning process during that compression operation.

The stronger slogan is therefore best understood as a claim about obtaining broadly effective compression of unknown structure. A system must somehow acquire or embody the structure it exploits. This may happen through training, adaptation, search, or prior design. Whether all those routes should be called learning is partly a question of definition.

Scope and limits

Compression performance depends on the data, the encoding convention, and what knowledge is shared with the decoder. A short encoded message produced using an enormous pretrained model is not automatically a short total description; the model's cost must either be counted or explicitly treated as shared background knowledge.

Sutskever also distinguishes compressing a fixed finite dataset from predicting an indefinitely large stream of new data. A one-time model-description cost can be amortized over that stream, so a larger model may be worthwhile despite costing more to encode. In the Q&A, he notes that recording prediction costs before updates during single-pass training offers another coding perspective on the learning process.

Learning should also be assessed on what it explains beyond a memorized sample. A pattern inferred from one sequence may fail on the next. Predictive compression on new observations can test whether a discovered representation remains useful.

The identity is most direct for probabilistic prediction evaluated by log loss and for learning framed through description length. Extending it to all intelligence introduces further questions about goals, action, reasoning, and interaction. Neither the coding correspondence nor MDL establishes that informational compression physically concentrates matter.

Relation to literal singularity theory

Literal singularity theory takes intelligence as compression and proposes a further physical trajectory: better models lead to better use of matter, culminating in competing black-hole civilizations. The compression-learning identity supplies the informational motivation for that hypothesis. The proposed transition from a shorter description to gravitational organization remains an additional physical conjecture.

See also

• Literal singularity theory