arXiv:2605.10878v2 Announce Type: replace-cross Abstract: Why do neural networks generalize better when their parameter norm is small? We prove that, in looped neural networks with constant-precision weights, the smallest weight norm of a network computing a function is asymptotically equivalent to the Kolmogorov complexity of that function, divided by its logarithm. The proof has two reductions: looped neural networks can encode information at a rate of logarithmically many bits per non-zero parameter encoded via the sparsity pattern, while any fixed-precision network can be described by enumerating its non-zero parameters with logarithmic addressing cost. Both bounds have the same leading constant factors, giving an asymptotic equivalence. More broadly, by establishing a theoretical link between norm minimization and algorithmic simplicity, we provide an avenue towards understanding generalization in modern deep learning.