How do we measure the intrinsic information content of an object? In theoretical computer science, the gold standard is Kolmogorov complexity ($K(x)$), defined as the length of the shortest computer program that can generate a specific string $x$ and then halt. If a string contains highly repetitive patterns—such as a million repetitions of "10"—its program can be incredibly compact. If the string is entirely random noise, the shortest program is simply to print the string verbatim.
However, Kolmogorov complexity suffers from a fatal flaw: it is fundamentally incomputable. Because of Alan Turing’s halting problem, you can never write a general algorithm to find the absolute shortest program for any arbitrary string.
To bridge the gap between elegant theory and practical engineering, researchers across machine learning, biology, and neuroscience use a powerful workaround: lossless compression algorithms. Standard compression utilities (like gzip, LZW, PNG, or JPEG) act as computable upper bounds for Kolmogorov complexity. If a standard compressor can shrink a data file down to $B$ bits, we know for certain that $K(x) \le B$. The resulting compressed file size serves as a highly effective, parameter-free proxy for an object's algorithmic complexity.
Why the Proxy Works: Redundancy and the Coding Theorem
The core intuition behind using compression as a complexity proxy relies on how compression algorithms operate. They scan data for structural regularities, statistical biases, and repeating patterns, replacing them with shorter identifiers.
This mechanism directly mirrors the Coding Theorem in algorithmic information theory. As discussed by A. Pavan et al., the theorem establishes a deep mathematical link between the probability of a string appearing within a computable distribution and its algorithmic complexity: highly structured, predictable strings require fewer bits to represent.
By treating compression sizes as a proxy for description length, researchers can operationalize the Minimum Description Length (MDL) principle. As demonstrated by Ivan Brugere et al. and Arian Maleki et al., MDL allows practitioners to evaluate models and data representations by balancing accuracy against complexity, framing both statistical modeling and signal recovery as optimization problems aimed at minimizing total description length.
Fixing Generative Models: Out-of-Distribution Detection
A striking application of this proxy occurs in deep generative models (such as Variational Autoencoders or Normalizing Flows). Counterintuitively, these models often assign a higher likelihood to out-of-distribution (OOD) data than to their own training data. For instance, a model trained exclusively on complex images of human faces might flag a simple, solid-green square as highly probable.
This failure happens because generative models are inherently biased toward low-entropy, structurally simple inputs. Joan Serrà et al. resolved this issue using compression-based proxies. By compressing input images with standard lossless codecs (like PNG or FLIF), they estimated the raw "background complexity" of each input.
$$\text{OOD Score}(x) = -\log p(x) - |C(x)|$$
Subtracting the compressed size $|C(x)|$ from the model's negative log-likelihood effectively levels the playing field. It subtracts the simplicity bias, isolating whether the model truly understands the structural distribution or is merely reacting to a lack of detail.
In a similar vein, Lucas Theis leverages description lengths under specific coding schemes to identify unrealistic generative samples. By tracking which generated images compress significantly more than typical samples from the target distribution, the framework flags anomalies that lack the expected informational density of real-world data.
Quantifying Complexity Across Domains
Because compression algorithms require no training or hyperparameter tuning, they serve as versatile, cross-disciplinary metrics for structural sophistication.
Vision and Network Architecture
In computer vision, compression metrics help optimize deep networks before training even begins. Suraj Mishra et al. use JPEG compression ratios to quantify the learnable information within biomedical datasets, mapping this complexity directly to a network's pruning potential. For image generation, Amit Vaisman et al. use traditional JPEG sizes to predict the exact reconstruction difficulty and bitrate requirements for diffusion models without running expensive iterative computations.
Furthermore, Shivam Duggal et al. designed an adaptive image tokenizer that treats the number of active tokens as a direct proxy for Kolmogorov complexity, naturally halting token allocation once additional tokens yield diminishing returns in structural reconstruction.
Large Language Models
Compression proxies offer a window into the internal mechanics of Large Language Models (LLMs):
- Memorization: Sunny Duan utilizes compression ratios to evaluate how the inherent algorithmic simplicity of a text sequence influences how deeply and stably an LLM memorizes it during training.
- Jailbreaking: Aldan Creo et al. analyzed millions of adversarial prompts, using lossless compression to reveal that human jailbreak attempts are bounded by a "complexity ceiling" and rely on highly repetitive, formulaic structural patterns.
- In-Context Learning: By measuring the compressibility of sequences generated by LLMs during in-context learning, Eric J Bigelow et al. exposed the sharp phase transitions where models suddenly abandon random behavior in favor of highly compressible, rule-based patterns.
Biology and Human Cognition
The utility of compression extends far beyond silicon. In biology, Qi Liu et al. developed RNACompress, demonstrating that the grammar-based compressibility of RNA secondary structures serves as a direct proxy for their informational complexity and biological activity. On an evolutionary scale, Iain G. Johnston et al. used Lempel-Ziv algorithms to show that natural selection possesses an algorithmic bias, naturally favoring symmetric, low-complexity phenotypes because they require shorter genetic "programs" to produce.
In cognitive science, researchers use these proxies to bypass subjective human ratings. Naveen Kumar et al. showed that audio signal compressibility correlates strongly with perceived emotional arousal in music. Yağmur Güçlütürk et al. combined fMRI data with file compression sizes to map how the human visual and auditory cortices represent naturalistic stimulus richness. The authors also applied this metric to aesthetic preferences, demonstrating that individual differences in art appreciation are rooted in distinct personal preferences for low- versus high-algorithmic complexity.
Even altered states of consciousness can be mapped this way: Fernando Rosas et al. applied Lempel-Ziv-Welch (LZW) complexity to brain dynamics, discovering that psychedelics like LSD physically shift neural activity toward a more disordered, algorithmically complex state.
Reconciling Learning Theory with Occam's Razor
For decades, machine learning has wrestled with a theoretical paradox. The No Free Lunch (NFL) theorem states that no single learning algorithm can outperform any other when averaged over all possible data distributions. Yet, in practice, a handful of architectures generalize spectacularly well across entirely different domains.
Micah Goldblum et al. and Tor Lattimore et al. resolve this contradiction by looking through the lens of Kolmogorov complexity. The universe of all possible data distributions includes pure, unpatterned noise. However, the real world is governed by physical laws, meaning natural data possesses a low Kolmogorov complexity.
By using lossless compression as a computable proxy, the authors demonstrate that real-world datasets are highly compressible compared to random noise. Because modern neural networks possess an innate simplicity bias—an inductive preference for functions with shorter description lengths—they are perfectly matched to the low-complexity structure of the real world.
This principle applies to simpler models as well. Goutam Paul 0001 demonstrated that traditional "node-counting" metrics for decision trees fail to capture true model complexity. By replacing syntactic counts with a compression-based proxy for the tree's data-partitioning behavior, the author reconciled decision tree generalization with Occam's Razor: models that compress their decision boundaries more effectively generalize better, proving that simplicity is not about the size of the code, but the efficiency of the representation.
Key Foundational Work
RNACompress: Grammar-based compression and informational complexity measurement of RNA secondary structure (2008) — contributed 2 concept elements to this direction.
Occam's Razor and a Non-Syntactic Measure of Decision Tree Complexity (2004) — contributed 1 concept elements to this direction.