The Feynman quote goes: "What I cannot create, I do not understand." Today's story is the reverse — about why a technique we use every day works, when no one could truly prove it until now.
---
Introduction: A Question No One Could Answer
Everyone who has trained a neural network has used weight decay. Add one line — weight_decay=0.01 — to your optimizer, and generalization magically improves. Remove it, and the model starts to overfit.
But why?
For thirty years, people offered explanations: "It makes weights small, so the model is simpler," "It's equivalent to L2 regularization," "It penalizes complex functions." These are all reasonable, but all remain at the level of intuition. A fundamental question was never rigorously answered:
What exactly does weight decay regularize? What is the relationship between the "simple" functions it favors and optimal simplicity?
In May 2026, a single-author paper from ETH Zürich gave a breathtaking answer.
---
Chapter 1: Two Islands
The story involves two seemingly unrelated concepts.
1.1 Kolmogorov Complexity
Imagine a game: using the shortest possible program, make a universal computer output a specific string.
For example, outputting "ABABABABABABABABABAB" (a 20-character repeating pattern) needs a program roughly like print "AB" * 10, about a dozen characters. But to output a fully random string "K7xP2mQ9vL3nR5wJ1", the shortest program is basically print "K7xP2mQ9vL3nR5wJ1" — the program itself must contain the string, so its length matches the string's.
The Kolmogorov complexity K(s) of a string is the length of the shortest program that outputs it. It is the purest definition of "information content" — how compressible a string is.
Building on Kolmogorov complexity, computer science pioneer Ray Solomonoff defined in 1964 the Universal Prior: assign each possible output probability \($2^{-K(s)}$\). Strings with low Kolmogorov complexity (more "regular") get higher probability; random ones get lower.
This prior has a beautiful property: in the limit, it dominates every computable predictor. An idealized Bayesian agent with infinite compute equipped with this prior would eventually beat all competitors on any prediction task.
There is only one problem: the Solomonoff prior is incomputable. Computing \($K(s)$\) requires searching over all possible programs, which is equivalent to solving the halting problem. So for over seventy years, the Solomonoff prior has been a "theoretical ideal" — known to be optimal, but unusable in practice.
1.2 Weight Decay
Meanwhile, weight decay is a technique so naive it borders on childish in deep learning.
You add a term to the loss: \($\text{Loss} + \frac{\lambda}{2} \|\theta\|_2^2$\), where \($\theta$\) is all network weights. Mathematically, this is equivalent to assuming a Gaussian prior over weights \($\pi(\theta) \propto e^{-\frac{\lambda}{2}\|\theta\|_2^2}$\) — smaller weights have higher prior probability.
A trained network outputs something. If we ask: under this Gaussian prior, what is the marginal probability \($Q(s)$\) that the network outputs a particular string \($s$\)? The answer is the sum of prior probabilities of all networks that output \($s$\).
The paper's core finding:
---
Chapter 2: Bridging the Gulf
2.1 The Main Theorem
> Main theorem (informal): At fixed precision, the minimum number of nonzero parameters \($\mathcal{N}(s)$\) needed for a recurrent neural network to output string \(s\) equals the Kolmogorov complexity of \($s$\), up to a logarithmic factor: > >
What does this mean? The implicit prior of weight decay (at fixed precision) is equivalent to Solomonoff's universal prior, up to a logarithmic factor.
The weight_decay=0.01 you casually type is approximately implementing the theoretically optimal inductive bias!
2.2 Why Is This Result So Elegant?
The proof has two directions, each surprisingly short.
Direction one (program → network): Any Turing machine program \($p$\) can be encoded into the weights of a fixed-precision neural network, with each bit of the program corresponding to one network parameter.
Concretely: take a universal recurrent network (e.g., a Transformer), use some fixed parameters to implement a Turing machine simulator, then inject each bit of \($p$\) as an extra routing weight. Total parameters = fixed simulator parameters + |p| routing parameters.
So the shortest program has \($|p| = K(s)$\) bits, and the corresponding network needs at most \($K(s)$\) nonzero parameters. Hence \($\mathcal{N}(s) \leq K(s)$\).
Direction two (network → program): Any fixed-precision neural network can be fully described by a short program.
A network has \($W$\) nonzero parameters. Each parameter can be described by three numbers: which layer, which two neurons it connects, and its value. At fixed precision, each value has only finitely many possibilities. \($W$\) parameters involve at most \($2W$\) distinct neurons, so each address needs \($\log_2 W$\) bits. Total description length: \($O(W \log W)$\) bits.
Prepend a fixed-size "simulator program" (that parses and executes the network), and you get a program that outputs the same string with length at most \($O(W \log W)$\). Hence \($K(s) \leq O(\mathcal{N}(s) \log \mathcal{N}(s))$\).
That's it. Two directions together form a "sandwich."
---
Chapter 3: Why the Log Factor Is Fundamental
Beginners might wonder: "Is this \($\log \mathcal{N}$\) factor just a non-tight proof? Can it be removed?"
The answer: no. And the paper proves it with an elegant construction.
3.1 The Permutation Example
Consider a permutation \(\pi\): rearranging \(N\) elements. There are \($N!$\) possible permutations.
A typical permutation has Kolmogorov complexity about \($\log_2 N! \approx N \log_2 N$\) bits — you need to specify the new position of each of \($N$\) elements, each position requiring \($\log_2 N$\) bits of address information.
Now, a network with only \($\Theta(N)$\) three-valued parameters can output this permutation matrix: each parameter encodes the position of a "1" in the permutation, and the position itself is implicit in the topology — a parameter connecting source neuron \($i$\) to target neuron \($j$\) carries \($\log_2 N$\) bits of information in the very indices \($i$\) and \($j$\)!
So: \($\mathcal{N}(s_\pi) = \Theta(N)$\), while \($K(s_\pi) = \Theta(N \log N)$\). The log factor is not a defect; it is a feature. The network's topology — which parameter connects to which neuron — is itself an information channel.
3.2 How Much Information Can One Parameter Carry?
A fixed-precision parameter value carries only \($O(1)$\) bits of information. But a parameter's "address" — which two neurons it connects — can carry \($\log_2 W$\) bits, since there are \($W^2$\) possible connections.
This is why the log is fundamental: networks have not only parameter values but also parameter topology, and topology itself is a hidden information carrier.
---
Chapter 4: Fixed Precision — The Non-Negotiable Premise
The paper repeatedly emphasizes: fixed precision is the key premise for this result.
Why?
With infinite-precision real-valued weights, neural networks are hypercomputational — they can compute things Turing machines cannot. Then \($K(s) = \infty$\) (some strings the network can output are simply not computable), while \($\|\theta\|$\) is finite. The equivalence breaks.
Even rational weights fail. A rational number \($p/q$\) can be bounded in magnitude (\($|p/q| \leq B$\)), yet its numerator and denominator can carry arbitrarily many bits of information. The connection between Kolmogorov complexity and weight norm breaks again.
Only at fixed precision — where each weight value is drawn from a finite set — does the weight norm truly correspond to description length.
The good news: this is exactly the precision modern deep learning actually runs at. fp16, bf16, int8, int4 — every model you use already runs at fixed precision. So this theorem is not an ivory-tower assumption; it directly characterizes real training.
---
Chapter 5: What Does This Mean?
5.1 Weight Decay Is "Solomonoff at a Discount"
The paper's corollary: under fixed-precision L2 weight decay, the marginal probability \($Q(s)$\) of a network output satisfies:
While the Solomonoff prior gives \($-\log M(s) = K(s) + O(1)$\).
The prior implied by weight decay differs from the theoretically optimal universal prior by only a log factor in the exponent. You don't need to solve the halting problem or search over all programs — you just need SGD with weight decay, and you are already approximating the optimal prior.
5.2 Why Do Quantized Models Generalize Better?
The paper makes a testable prediction: for deeply quantized networks (int4, int8), weight decay should be even more effective.
At very low precision, \($\|\theta\|_2^2$\) almost exactly equals the number of nonzero parameters — each nonzero parameter has only a few possible values, so the norm no longer "dilutes" the description-length signal. Quantization + weight decay is the setting closest to a pure Solomonoff prior.
5.3 "Simple Data Benefits More"
The paper predicts: tasks with low Kolmogorov complexity (algorithmic reasoning, regular languages, structured prediction) benefit more from weight decay than complex tasks (natural images, free-form text).
This also explains why weight decay matters most on small datasets — small data has less "effective information," closer to a low-Kolmogorov-complexity function, easier to capture with a good prior.
---
Chapter 6: Feynman's Review
If Feynman read this paper, he would probably say:
"See, this is the kind of discovery I love. It answers a question everyone thought they knew the answer to, but no one actually understood. It uses two simple reductions — programs encoded into networks, networks encoded into programs — to build a bridge. On one end of the bridge is the regularization trick you use every day; on the other, one of the most beautiful concepts in theoretical computer science.
Even better, it tells you why the bridge is 'shaky' (that log factor) — because network parameters have not only values but also connections, and the connections themselves secretly carry information. You can't say this discovery has no practical value (it explains why weight decay works), and you can't say it's pure engineering optimization (it connects to Kolmogorov complexity and the Solomonoff prior).
Work that crosses the theory-practice boundary like this is far too rare."
---
Conclusion
For thirty years, weight decay has been a technique that "works but no one knew why." We used it because experience told us it works.
This paper finally gives a rigorous answer: weight decay works because, at fixed precision, it approximately implements Solomonoff's universal prior — the theoretically optimal, classically incomputable inductive bias.
Sometimes the deepest truths hide in the most mundane operations.
---
*Paper information*
- Title: Neural Weight Norm = Kolmogorov Complexity
- Author: Tiberiu Musat (ETH Zürich)
- arXiv ID: 2605.10878
- Published: May 11, 2026
- Categories: cs.LG, cs.IT