When a neural network is trained on a logical task, it doesn't just learn any function that fits the data. Among the infinite number of mathematical rules that could explain the training set, gradient descent consistently picks a specific kind: the one with the lowest possible "complexity."
Recent research has identified that this complexity is often measured by the polynomial degree of the function. This phenomenon, known as min-degree bias, acts as an implicit Occam’s Razor, determining whether a model learns a robust general rule or a fragile shortcut.
The Mathematical Occam’s Razor
In the context of Boolean functions (logic gates, parity, and retrieval tasks), any operation can be represented as a multivariate polynomial. For example, a simple AND gate has a lower degree than a complex parity check across many bits.
Emmanuel Abbe, Samy Bengio, and their colleagues have shown in Generalization on the Unseen, Logic Reasoning and Degree Curriculum that gradient descent is fundamentally "lazy." It prioritizes low-degree Fourier components—essentially the simplest correlations between a few input bits—before it ever attempts to learn high-degree, global logic.
This bias explains a common failure mode in AI reasoning. If a training set can be "solved" by a low-degree polynomial that doesn't represent the true underlying logic, the model will adopt that shortcut. When the model is later tested on "unseen" data where that shortcut no longer holds, it fails, even if its training accuracy was perfect.
Why Gradient Descent Prefers Low Degrees
The preference for simplicity isn't just a lucky accident; it is baked into the optimization process. In Learning to Reason with Neural Networks: Generalization, Unseen Data and Boolean Measures, Emmanuel Abbe and Elisabetta Cornacchia demonstrate that gradient descent exhibits a "spectral bias."
Think of the network's learning process as building a function piece by piece. The "easiest" pieces for the gradient to find are those that have high Boolean influence—features that, when flipped, significantly change the output. These influential features typically correspond to low-degree terms. Consequently, the model captures simple local correlations (low-order interactions) long before it captures the intricate, multi-step dependencies (high-order interactions) required for true algorithmic reasoning.
From Shortcuts to World Models
While min-degree bias can lead to shortcuts, it is also the reason neural networks can learn "world models" at all. If networks didn't have a bias toward simplicity, they might just memorize every data point as a unique, high-degree noise term.
In When do neural networks learn world models?, Tianren Zhang and Feng Chen argue that this bias toward "low realization degree" is what allows a network to recover the true latent variables of a system. When a network is forced to solve multiple tasks simultaneously, the simplest mathematical explanation that fits all tasks is often the actual underlying structure of the data—the "world model."
The Challenge of Length Generalization
The most significant hurdle for min-degree bias is length generalization: the ability to solve a 100-digit addition problem after only seeing 10-digit examples.
As explored by Yang Chen and Zhouchen Lin in Low-Dimension-to-High-Dimension Generalization and Its Implications for Length Generalization, the "simplest" interpolator for a small problem is rarely the recursive rule needed for a large one. Because the model's built-in bias favors the lowest-degree solution for the training size, it often ignores the recursive logic that would allow it to scale.
To overcome this, researchers are finding that we cannot rely on gradient descent alone; we must design architectures (like specific position embeddings) that align the model's natural "simplicity bias" with the actual structure of the logical task.