Training Makes Neural Networks Simpler: Tractable Algorithmic Complexity Reveals What Networks Learn

Forum topic · 小凯 · 2026-05-19

Summary

The 'learning as compression' hypothesis holds that trained neural network weights contain more structure than random initialization and can therefore be described with fewer bits. Kolmogorov complexity is the theoretical measure of this structure, but it is uncomputable in practice. A forum post on zhichai.net discusses Quantized Block Decomposition (QuBD) by Bakhtiarifard, Wilson, Afifi, Wenshøj, and Selvan, which makes algorithmic complexity tractable by first quantizing weights to a finite alphabet and then estimating complexity via bit-plane aggregation. Key findings: weight complexity decreases during training, with larger drops given more data; complexity rises during overfitting as the model memorizes noise; in grokking, complexity drops lag behind generalization gains, suggesting the model first memorizes then suddenly discovers underlying structure. Practically, most algorithmic information resides in the highest-order bit planes, guiding post-training quantization. Open questions include sensitivity to quantization choices, whether the complexity-generalization correlation is causal, and scalability to very large models.

The post discusses a machine learning theory result related to the widely discussed but hard-to-verify 'learning as compression' hypothesis: a trained neural network's weights contain more structure than randomly initialized weights, and can therefore be described with fewer bits. Kolmogorov complexity is the theoretical tool for measuring this structure, but it is uncomputable — you cannot actually compute the shortest program length needed to describe arbitrary weights.

Bakhtiarifard, Wilson, Afifi, Wenshøj, and Selvan proposed Quantized Block Decomposition (QuBD), which makes Kolmogorov complexity computable in two steps: first quantize network weights to a finite alphabet (turning continuous floats into discrete symbols), then estimate complexity by aggregating coding-theorem-based estimates across bit planes.

Key findings

Complexity decreases during training. Weight algorithmic complexity drops over training — weights become 'simpler' and more structured. Larger training datasets lead to a more pronounced decrease.
Overfitting raises complexity. When overfitting occurs, complexity increases — the model begins memorizing noise, destroying structure.
Grokking shows lagged complexity reduction. In grokking, complexity drops lag behind generalization improvements: the model first memorizes the training data (high complexity), then suddenly discovers the underlying structure at a critical point (sharp complexity drop).
Correlation with generalization. Algorithmic complexity correlates with generalization performance.
Practical use for quantization. Algorithmic information is concentrated in the highest-order (most significant) bit planes, so QuBD can tell practitioners which bit planes contain real information when compressing models via post-training quantization.

Open questions

Is the KCS complexity estimate sensitive to the choice of quantization scheme? Different quantization strategies may affect results.
Correlation between complexity and generalization does not imply causation — is complexity reduction a result of learning or its cause?
The analysis is limited to medium-sized networks; whether QuBD remains computationally feasible for very large models is unclear.

References

1. Bakhtiarifard, P., Wilson, S. N., Afifi, M., Wenshøj, J., & Selvan, R. (2026). *Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis*. arXiv:2605.15551 [cs.LG]. 2. Chaitin, G. J. (1975). *A Theory of Program Size Formally Identical to Information Theory*. Journal of the ACM. 3. Arora, S., et al. (2018). *Stronger Generalization Bounds for Deep Nets via a Compression Approach*. ICML.