# Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 15 May 2026.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [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)
- [Energy and Policy Considerations for Deep Learning in NLP](https://mlsanity.com/paper/1906.02243/) (2019)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [A White Paper on Neural Network Quantization](https://mlsanity.com/paper/2106.08295/) (2021)
- [Sharp Minima Can Generalize For Deep Nets](https://mlsanity.com/paper/1703.04933/) (2017)
- [Information-theoretic analysis of generalization capability of learning algorithms](https://mlsanity.com/paper/1705.07809/) (2017)
- [TinyViT: Fast Pretraining Distillation for Small Vision Transformers](https://mlsanity.com/paper/2207.10666/) (2022)
- [Emergence of Invariance and Disentanglement in Deep Representations](https://mlsanity.com/paper/1706.01350/) (2017)
- [Compressing Deep Convolutional Networks using Vector Quantization](https://mlsanity.com/paper/1412.6115/) (2014)
- [Deep learning generalizes because the parameter-function map is biased towards simple functions](https://mlsanity.com/paper/1805.08522/) (2018)
- [Carbontracker: Tracking and Predicting the Carbon Footprint of Training Deep Learning Models](https://mlsanity.com/paper/2007.03051/) (2020)
- [Compute Trends Across Three Eras of Machine Learning](https://mlsanity.com/paper/2202.05924/) (2022)
- [Soft Weight-Sharing for Neural Network Compression](https://mlsanity.com/paper/1702.04008/) (2017)
- [The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning](https://mlsanity.com/paper/2304.05366/) (2023)
- [Deep Learning is Not So Mysterious or Different](https://mlsanity.com/paper/2503.02113/) (2025)
- [Compute-Efficient Deep Learning: Algorithmic Trends and Opportunities](https://mlsanity.com/paper/2210.06640/) (2022)
- [SETOL: A Semi-Empirical Theory of (Deep) Learning](https://mlsanity.com/paper/2507.17912/) (2025)
- [Improvement of Spiking Neural Network with Bit Planes and Color Models](https://mlsanity.com/paper/2410.08229/) (2024)
- [Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis](https://mlsanity.com/paper/2505.20646/) (2025)
- [Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs](https://mlsanity.com/paper/2602.14896/) (2026)

## Abstract (arXiv)

Training large-scale deep neural networks (DNNs) is resource-intensive, making model compression a practical necessity. The widely accepted ''learning as compression'' hypothesis posits that training induces structure in network weights, which enables compression. Measuring this structure through Kolmogorov-Chaitin-Solomonoff (KCS) complexity is appealing, but existing estimators based on the Coding Theorem Method (CTM) and the Block Decomposition Method (BDM) are limited to small binary objects and do not scale to modern DNNs. We introduce the Quantized Block Decomposition method (QuBD), which extends algorithmic complexity estimation to any k-ary object. QuBD first quantizes the network weights to a finite alphabet, then estimates the KCS complexity by aggregating per bit-plane CTM estimates. We show theoretically that QuBD yields a strictly tighter estimation gap with respect to true KCS complexity than binarization-based methods. Using QuBD, we study how the algorithmic complexity of neural network weights evolves during training, showing that it decreases as models learn, scales with data budget, increases during overfitting, follows the delayed generalization observed during grokking, and correlates with generalization performance. We further show that algorithmic information resides predominantly in the most significant bit-planes, which can serve as a practical diagnostic for determining appropriate post-training quantization levels. This work offers novel insights into learning mechanisms in DNNs by providing the first scalable, tractable estimates of KCS complexity for large, non-binary objects such as DNN weights.