Training Makes Neural Networks "Simpler": Algorithmic Complexity Measures Learning Quality

"Learning as compression" is a hypothesis widely discussed in machine learning theory but difficult to verify. It states that the weights of a trained neural network contain more structure than randomly initialized weights—and can therefore be described with fewer bits. Kolmogorov complexity is the theoretical tool for measuring "how much structure" exists, but it is uncomputable: you cannot actually compute the length of the shortest program describing an arbitrary set of weights.

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

Armed with this tool, they made a series of observations:

• Training reduces complexity. The algorithmic complexity of weights genuinely decreases during training—weights become increasingly "simple" and structured.
• More data, bigger drop. The decrease is more pronounced with larger amounts of training data.
• Overfitting raises complexity. When overfitting occurs, complexity rises instead—the model begins memorizing noise, destroying structure.
• Grokking shows a lag. In the "grokking" phenomenon, the drop in complexity lags behind the improvement in generalization—the model first memorizes the training data (high complexity), then at some critical point suddenly discovers the underlying structure (complexity plummets).
• Correlation with generalization. There is a correlation between complexity and generalization performance.

One practical finding: algorithmic information is concentrated mainly in the most significant bit planes. This means that when performing post-training quantization compression—when you want to know how many bits suffice—QuBD can tell you which bit planes contain real information.

What remains unclear

• Is the KCS complexity estimate sensitive to the choice of quantization scheme? Different quantization strategies may affect the results.
• The correlation between complexity and generalization does not necessarily imply causation—is decreasing complexity a result of learning, or a cause of it?
• The analysis is currently limited to moderately sized neural networks—does QuBD remain computationally feasible on very large models?

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.