# Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 61 references that are in the map.
- First posted on arXiv 27 May 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer](https://mlsanity.com/paper/1701.06538/) (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)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [KAN: Kolmogorov-Arnold Networks](https://mlsanity.com/paper/2404.19756/) (2024)
- [Opening the Black Box of Deep Neural Networks via Information](https://mlsanity.com/paper/1703.00810/) (2017)
- [Variational Dropout Sparsifies Deep Neural Networks](https://mlsanity.com/paper/1701.05369/) (2017)
- [Simulation Intelligence: Towards a New Generation of Scientific Methods](https://mlsanity.com/paper/2112.03235/) (2021)
- [Estimating or Propagating Gradients Through Stochastic Neurons](https://mlsanity.com/paper/1305.2982/) (2013)
- [Towards the Limit of Network Quantization](https://mlsanity.com/paper/1612.01543/) (2016)
- [Scalable Model Compression by Entropy Penalized Reparameterization](https://mlsanity.com/paper/1906.06624/) (2019)
- [DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks](https://mlsanity.com/paper/1907.11900/) (2019)
- [Information Bottleneck Analysis of Deep Neural Networks via Lossy Compression](https://mlsanity.com/paper/2305.08013/) (2023)
- [Compact and Computationally Efficient Representation of Deep Neural Networks](https://mlsanity.com/paper/1805.10692/) (2018)
- [Entropy-Constrained Training of Deep Neural Networks](https://mlsanity.com/paper/1812.07520/) (2018)

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

- [Algorithmic Simplification of Neural Networks with Mosaic-of-Motifs](https://mlsanity.com/paper/2602.14896/) (2026)
- [Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis](https://mlsanity.com/paper/2605.15551/) (2026)
- [Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking](https://mlsanity.com/paper/2609.13197/) (2026)

## Abstract (arXiv)

Understanding and controlling the informational complexity of neural networks is a central challenge in machine learning, with implications for generalization, optimization, and model capacity. While most approaches rely on entropy-based loss functions and statistical metrics, these measures often fail to capture deeper, causally relevant algorithmic regularities embedded in network structure. We propose a shift toward algorithmic information theory, using Binarized Neural Networks (BNNs) as a first proxy. Grounded in algorithmic probability (AP) and the universal distribution it defines, our approach characterizes learning dynamics through a formal, causally grounded lens. We apply the Block Decomposition Method (BDM) -- a scalable approximation of algorithmic complexity based on AP -- and demonstrate that it more closely tracks structural changes during training than entropy, consistently exhibiting stronger correlations with training loss across varying model sizes and randomized training runs. These results support the view of training as a process of algorithmic compression, where learning corresponds to the progressive internalization of structured regularities. In doing so, our work offers a principled estimate of learning progression and suggests a framework for complexity-aware learning and regularization, grounded in first principles from information theory, complexity, and computability.