Imagine you are given the sequence 2, 4, 6, 8 and asked to predict the next number. The intuitive answer is 10, following the rule $f(x) = 2x$. Mathematically, however, an infinite number of higher-order polynomials can perfectly fit these four points while yielding completely different outputs for the next step.
This scenario illustrates the fundamental problem of induction: any finite set of observations can be explained by an infinite number of hypotheses. To learn anything at all, a system must possess an inductive bias—a predefined preference for certain explanations over others. In A Critique of the Valiant Model, Wray Buntine et al. argue that formalizing this bias via statistical priors is a mathematical necessity. Without a structured preference, a learning agent treats all consistent explanations as equally likely, rendering generalization impossible. The most robust and universally applicable framework for this preference is the simplicity prior, which provides a rigorous mathematical foundation for Occam's Razor.
Quantifying Simplicity via Representation Length
To operationalize Occam's Razor, we must first answer a difficult question: how do we objectively measure the "simplicity" of a hypothesis? The core insight of this research direction is to equate simplicity with compressibility or representation length—the number of symbols or bits required to specify a hypothesis within a formal language.
In a Bayesian framework, we can penalize complexity by designing a prior probability distribution that decreases as the description length of the hypothesis increases. For example, in Learning and using relational theories, Charles Kemp et al. assign prior probabilities to structural theories using an exponential decay based on their symbolic description length:
$$P(H) \propto 2^{-\text{len}(H)}$$
Why does this specific exponential penalty make sense? The intuition becomes clear when we look at computation. In Principles of Solomonoff Induction and AIXI, Peter Sunehag et al. derive this preference from a foundational "indifference principle" over binary program strings. If an agent is completely unbiased toward individual bits in a program, shorter programs naturally receive a higher cumulative probability weight than longer ones simply because there are fewer of them.
This forms the basis of Solomonoff induction. As Marcus Hutter demonstrates in On Universal Prediction and Bayesian Confirmation, penalizing theories based on their algorithmic complexity provides a universal mechanism to prevent "retrofitting"—the practice of engineering highly complex, bespoke hypotheses to explain existing data. A theory specifically engineered to fit known evidence results in a long, convoluted program description, naturally receiving a low prior probability.
Balancing Fit and Complexity to Prevent Overfitting
When a learning algorithm lacks a simplicity prior, it tends to overfit by memorizing the training data. Under pure maximum-likelihood estimation, a model will gladly invent highly intricate, brittle rules to capture every quirk and noise artifact in the dataset.
By incorporating a description-length penalty, the learning objective shifts from maximizing data fit to balancing fit against structural complexity.
┌─────────────────────────────────────────────────┐
│ Learning Objective │
└────────────────────────┬────────────────────────┘
▼
┌───────────────────┴───────────────────┐
│ Minimize: Loss(Data) + Length(Model) │
└───────────────────────────────────────┘
This balance is highly effective across diverse structured learning tasks:
- Grammar Induction: In Bayesian Grammar Induction for Language Modeling, Stanley F. Chen showed that applying a description-length prior to probabilistic context-free grammars prevents the model from simply memorizing the training sentences. Instead, it forces the induction of compact, generalized rule sets that perform better on unseen data.
- Action Modeling: When learning probabilistic action models from state transitions, David Martínez 0004 et al. demonstrate in Learning Probabilistic Action Models from Interpretation Transitions that preferring general operators with fewer preconditions prevents overfitting. Specific exceptions are only added to the model when empirical evidence strongly justifies the increased complexity cost.
The Simplicity Bias in Human Cognition
Humans are remarkably adept at learning from sparse data, often grasping an abstract rule from just a few examples. Cognitive science research suggests this ability is driven by an innate simplicity prior embedded within a mental "Language of Thought."
When humans learn spatiotemporal patterns, we do not merely track raw coordinates. Instead, we perform a form of probabilistic program synthesis. In Human spatiotemporal pattern learning as probabilistic program synthesis, Tracey Mills et al. show that human predictions of movement are best modeled by assigning higher prior probabilities to shorter symbolic programs. This bias steers us toward discovering geometric regularities and repetitions.
This mathematical preference for parsimony explains several key aspects of human learning:
- Early Abstraction: In A model of rapid phonotactic generalization, Tal Linzen et al. demonstrate that a parsimony bias—a preference for the smallest set of rules—replicates how human learners rapidly adopt broad templates before mastering specific details.
- Relational Learning: When discovering abstract logical categories from limited data, a simplicity prior allows systems to narrow down massive hypothesis spaces efficiently, mirroring human inductive leaps (Abstraction and Relational learning by Charles Kemp et al.).
- Function Extrapolation: Even when learning continuous functions, human inductive biases can be modeled by assigning non-uniform priors over structural hypotheses, such as favoring simple linear kernels over highly non-linear alternatives (Modeling human function learning with Gaussian processes by Thomas L. Griffiths et al.).
Emergent Simplicity in Neural Networks
While simplicity priors have historically been engineered explicitly into Bayesian models, recent work reveals that massive, overparameterized neural networks can exhibit an implicit simplicity bias.
In In-Context Learning Dynamics with Random Binary Sequences, Eric J Bigelow et al. investigated how Large Language Models (LLMs) learn in-context when presented with binary patterns. They discovered that LLMs possess an internal simplicity bias, consistently favoring shorter and more compressible algorithmic explanations for the data in their context windows.
Rather than adjusting gradually, the models undergo sharp phase transitions, suddenly switching from random guessing to deterministic pattern-following as they lock onto the lowest-complexity representation available. This suggests that the capacity for robust generalization, even in deep learning, may fundamentally depend on the emergence of a simplicity prior.
Key Foundational Work
A Critique of the Valiant Model (1989) — contributed 2 concept elements to this direction.
Bayesian Grammar Induction for Language Modeling (1995) — contributed 2 concept elements to this direction.