> Feynman said: "What I cannot create, I do not understand." Today's story is the reverse—about why a technique we all use every day works, yet no one could actually prove it until now.
---
Introduction: A Question No One Could Answer
Everyone who has trained a neural network has used weight decay. You add one line to your optimizer, weight_decay=0.01, 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 all make intuitive sense, but a fundamental question was never rigorously answered:
What exactly does weight decay regularize? How does the "simple" function class it favors relate to 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: write the shortest possible program that makes a universal computer output a given string.
For example, outputting "ABABABABABABABABABAB" (a repeated pattern) needs only about print "AB" * 10—a dozen or so characters. But for a truly random string like "K7xP2mQ9vL3nR5wJ1", the shortest program is essentially print "K7xP2mQ9vL3nR5wJ1"—the program must contain the string itself.
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 this, Ray Solomonoff defined the Universal Prior in 1964: assign each possible output probability \($2^{-K(s)}$\). More regular strings get higher probability; more random ones, 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 will eventually beat any competitor on any prediction task.
There is only one problem: the Solomonoff prior is uncomputable. Computing \($K(s)$\) requires searching over all programs, which is equivalent to solving the halting problem. For over seventy years it remained a theoretical ideal—known to be optimal, but unusable in practice.
1.2 Weight Decay
Weight decay, on the other hand, is a technique almost naive in its simplicity.
You add a term to the loss: \($\text{Loss} + \frac{\lambda}{2} \|\theta\|_2^2$\), where \($\theta$\) are all network weights. Mathematically this is equivalent to assuming a Gaussian prior \($\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 is:
---
Chapter 2: Building the Bridge
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, one parameter per bit of program.
Concretely: take a universal recurrent network (e.g., a Transformer), implement a Turing machine simulator with fixed parameters, then inject each bit of \($p$\) as an extra routing weight. Total parameters = fixed simulator parameters + \(|p|\) routing weights.
So the shortest program of \($|p| = K(s)$\) bits yields a network with at most \($K(s)$\) nonzero parameters: \($\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 with \($W$\) nonzero parameters: each parameter needs three numbers—its layer, the two neurons it connects, and its value. At fixed precision, each value has finitely many possibilities. \($W$\) parameters involve at most \($2W$\) 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 of length \($O(W \log W)$\) that outputs the same string. Hence \($K(s) \leq O(\mathcal{N}(s) \log \mathcal{N}(s))$\).
That's it. Two directions combine into a sandwich.
---
Chapter 3: Why the Log Factor Is Inherent
A beginner might wonder: "Is the \($\log \mathcal{N}$\) factor just slack in the proof? Can it be removed?"
The answer is no. And the paper proves it with an elegant construction.
3.1 The Permutation Example
Consider a permutation \(\pi\) of \(N\) elements. There are \(N!\) possible permutations.
A typical permutation has Kolmogorov complexity about \($\log_2 N! \approx N \log_2 N$\) bits—you must specify the new position of each of \($N$\) elements, \($\log_2 N$\) bits per address.
Meanwhile, a network with only \($\Theta(N)$\) ternary parameters can output the permutation matrix: each parameter encodes the position of one "1", with the position implicit in the topology—a parameter connecting source neuron \($i$\) to target neuron \($j$\) carries \($\log_2 N$\) bits of information in \($i$\) and \($j$\) themselves!
So: \($\mathcal{N}(s_\pi) = \Theta(N)$\) while \($K(s_\pi) = \Theta(N \log N)$\). The log factor is not a flaw—it's a feature. Network topology is itself an information channel.
3.2 How Much Information Can One Parameter Carry?
A fixed-precision parameter value carries \($O(1)$\) bits. But a parameter's *address*—which two neurons it connects—can carry \($\log_2 W$\) bits, since there are \($W^2$\) possible connections.
That's why the log is inherent: networks have not only parameter values but also parameter topology, and topology is a hidden information carrier.
---
Chapter 4: Fixed Precision—An Essential Premise
The paper emphasizes: fixed precision is the crucial precondition.
Why? With infinite-precision real weights, neural networks are super-Turing—they can compute what Turing machines cannot. Then \($K(s) = \infty$\) (some outputs aren't computable at all) while \($\|\theta\|$\) is finite. The equivalence breaks.
Even rational weights fail: a rational \($p/q$\) has bounded magnitude (\($|p/q| \leq B$\)) but its numerator and denominator can carry arbitrarily many bits. The link between Kolmogorov complexity and weight norm breaks again.
Only at fixed precision—where each weight comes from a finite set—does the weight norm genuinely equal description length.
The good news: this is exactly how modern deep learning actually runs. fp16, bf16, int8, int4—every model you use already runs at fixed precision. This theorem is not an ivory-tower assumption but a direct characterization of 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 output probability \($Q(s)$\) satisfies:
While the Solomonoff prior gives \($-\log M(s) = K(s) + O(1)$\).
The prior induced by weight decay differs from the optimal universal prior by only a log factor in the exponent. No halting problem, no search over all programs—just run SGD with weight decay, and you are already approaching the optimal prior.
5.2 Why Do Quantized Models Generalize Better?
The paper makes a testable prediction: weight decay should be more effective for deeply quantized networks (int4, int8).
At very low precision, \($\|\theta\|_2^2$\) is almost exactly the number of nonzero parameters—each value has few possibilities, so the norm no longer "dilutes" the description-length signal. Quantization + weight decay is the setting closest to the pure Solomonoff prior.
5.3 "Simple Data Benefits More"
The paper predicts: low-Kolmogorov-complexity tasks (algorithmic reasoning, regular languages, structured prediction) benefit more from weight decay than complex tasks (natural images, free text).
This also explains why weight decay matters especially on small datasets—small data's "effective information" is sparser, closer to a low-complexity function, and thus more easily captured by a good prior.
---
Chapter 6: Feynman's Take
If Feynman read this paper, he might say:
"You see, this is the kind of discovery I love. It answers a question everyone thought they knew the answer to, but no one truly understood. It builds a bridge with two simple reductions—programs encoded into networks, networks encoded into programs. On one end of the bridge is a 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 'wobbly' (that log factor)—because network parameters have not only values but connections, and connections themselves secretly transmit information. You can't call this purely theoretical (it explains why weight decay works), nor purely engineering (it connects to Kolmogorov complexity and the Solomonoff prior).
Work that crosses the theory-practice boundary like this is rare."
---
Conclusion
For thirty years, weight decay has been a technique that "works but nobody knew why." We used it because experience told us to.
This paper gives the first rigorous answer: weight decay works because, at fixed precision, it approximately implements Solomonoff's universal prior—the theoretically optimal yet classically uncomputable inductive bias.
Sometimes the deepest truths hide inside the most ordinary operations.
---
*Paper info*
- 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