# Neural Weight Norm = Kolmogorov Complexity

arXiv: https://arxiv.org/abs/2605.10878 · HTML: https://mlsanity.com/paper/2605.10878/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 38 references that are in the map.
- First posted on arXiv 11 May 2026.

## Builds on (most cited first, 19 of 19)

- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Stronger generalization bounds for deep nets via a compression approach](https://mlsanity.com/paper/1802.05296/) (2018)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)
- [On the Computational Power of Transformers and its Implications in Sequence Modeling](https://mlsanity.com/paper/2006.09286/) (2020)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [Why Do We Need Weight Decay in Modern Deep Learning?](https://mlsanity.com/paper/2310.04415/) (2023)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [How Powerful are Decoder-Only Transformer Neural Models?](https://mlsanity.com/paper/2305.17026/) (2023)
- [Constant Bit-size Transformers Are Turing Complete](https://mlsanity.com/paper/2506.12027/) (2025)
- [Bridging Kolmogorov Complexity and Deep Learning: Asymptotically Optimal Description Length Objectives for Transformers](https://mlsanity.com/paper/2509.22445/) (2025)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)
- [Efficient Turing Machine Simulation with Transformers](https://mlsanity.com/paper/2512.00003/) (2025)

## Built on by (most cited first, 2 of 2)

- [Intelligence from Learnable Novelty](https://mlsanity.com/paper/2607.18433/) (2026)
- [Gauging, Measuring, and Controlling Critic Complexity in Actor-Critic Reinforcement Learning](https://mlsanity.com/paper/2607.00452/) (2026)

## Abstract (arXiv)

Why does weight decay work? We prove that, in any fixed-precision regime, the smallest weight norm of a looped neural network outputting a binary string equals the Kolmogorov complexity of that string, up to a logarithmic factor. This implies that weight decay induces a prior matching Solomonoff's universal prior, the optimal prior over computable functions, up to a polynomial factor. The result is norm-agnostic: in fixed precision, every weight norm collapses to the non-zero parameter count up to constants, so the same sandwich bound holds for any norm used as a regulariser. The proof has two short reductions: any program for a universal Turing machine can be encoded into neural weights at unit cost per program bit, and any fixed-precision network can be described by enumerating its non-zero parameters with logarithmic addressing overhead. Both bounds are tight up to constants, with the logarithmic factor realised by permutation encodings: a network whose parameters encode a permutation produces a string whose Kolmogorov complexity is the non-zero parameter count times its logarithm. The fixed-precision assumption is essential: with infinite precision, neural networks can encode non-computable functions and the weight norm loses its relevance.