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

Eduardo Y. Sakabe [email protected], Felipe S. Abrahão [email protected], Alexandre Simões [email protected], Esther Colombini [email protected], Paula Costa [email protected], Ricardo Gudwin [email protected], Hector Zenil [email protected] · 2025

Read Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis by Eduardo Y. Sakabe [email protected], Felipe S. Abrahão [email protected], Alexandre Simões [email protected], Esther Colombini [email protected], Paula Costa [email protected], Ricardo Gudwin [email protected], Hector Zenil [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20646.txt.

Introduction

Eduardo Sakabe and co-authors argue that learning in neural networks is a march toward algorithmic simplicity, in their 2025 arXiv paper. Standard entropy measures miss the deep structural regularities networks absorb. Using binarized networks as a test bed, the team measures complexity with an algorithmic method based on decomposing outputs into simple blocks.

Across model sizes and repeated randomized training runs, this algorithmic complexity tracked training loss more closely than entropy did, falling as networks internalized structure. The authors read this as empirical support for the learning-as-compression hypothesis: training progressively compresses the world's regularities into the network. They propose complexity-aware training and regularization built on the measure.

Catalog record

CREATOREduardo Y. Sakabe [email protected], Felipe S. Abrahão [email protected], Alexandre Simões [email protected], Esther Colombini [email protected], Paula Costa [email protected], Ricardo Gudwin [email protected], Hector Zenil [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE36 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-20646

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis Eduardo Y. Sakabe [email protected], Felipe S. Abrahão [email protected], Alexandre Simões [email protected], Esther Colombini [email protected], Paula Costa [email protected], Ricardo Gudwin [email protected], Hector Zenil [email protected] Abstract 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. 1 School of Electrical and Computer Engineering, University of Campinas (UNICAMP), Brazil 2 Centre for Logic, Epistemology and the History of Science, University of Campinas (UNICAMP), Brazil 3 Oxford Immune Algorithmics, Oxford University Innovation & London Institute for Healthcare Engineering, U.K. 4 Algorithmic Dynamics Lab, Karolinska Institute & King’s College London, U.K. 5 DEXL, National Laboratory for Scientific Computing (LNCC), Brazil 6 Department of Control and Automation Engineering, São Paulo State University (UNESP), Brazil 7 Institute of Computing, University of Campinas (UNICAMP), Brazil 8 Research Departments of Biomedical Computing and Digital Twins, School of Biomedical Engineering and Imaging Sciences 9 King’s Institute for Artificial Intelligence, King’s College London, U.K. 1 Introduction Understanding the distributional structure of neural network weights from an information-theoretic perspective has driven a range of advances in training efficiency, model compression, and architecture optimization. For example, [ 31 ] proposed an entropy-based criterion to dynamically adjust the number of hidden neurons, relating increases in weight entropy to growing representational demands. Similarly, [ 32 ] used the stabilization of weight entropy as a stopping criterion during training. Other approaches incorporate entropy directly into the loss function to regularize complexity and encourage more compact representations [ 23 , 13 , 22 , 37 ] . Complementarily, post-training compression techniques leverage entropy coding and quantization to reduce model size with minimal impact on accuracy [ 9 , 5 , 24 , 39 , 38 ] . From the universal (algorithmic) coding theorem (see Section 2 ) within the context of algorithmic information theory (AIT) [ 7 , 4 , 3 , 19 ] , these approaches are often grounded in algorithmic probability [ 45 , 6 , 42 , 10 ] and universal (Solomonoff) induction [ 19 , 15 ] , such as the minimum description length (MDL) principle [ 19 , 26 ] , which posits that the best model is the one that minimizes the total length of two descriptions: the model itself (its parameters or structure) and the data given the model (how well it fits the data). Shannon entropy is widely used in this context because it quantifies the expected bit-length required to encode outcomes from a probabilistic source [ 28 ] , directly aligning with MDL. In the case of neural networks, weight entropy serves as a proxy for model complexity, estimating the information needed to represent the network’s parameters. Yet, entropy—while widely adopted—captures only statistical variability, overlooking algorithmic and causal structure critical to understanding how neural networks internalize and compress information. AIT offers an encompassing perspective focused on formal-theoretic measures of complexity (particularly, algorithmic ( program-size ) complexity and algorithmic probability ) rather than statistical ones, emphasizing the need to capture not just the statistical properties of the data, but also the generative structure (or process) underlying data. Universal induction has been regarded as a theoretical solution to Artificial General Intelligence (AGI), positing that the most intelligent systems are those capable of compressing and generalizing via the shortest explanatory programs [ 10 , 21 ] . We build on this foundation using the Block Decomposition Method (BDM) [ 45 , 42 , 46 , 44 ] , a computable and resource effective approximation to the (semicomputable) algorithmic complexity values, to estimate its value in application to the (global) complexity of neural network weights. BDM offers a practical and computable approximation that captures both statistical (at global scales) and algorithmic regularities (at local scales), providing a complexity measure that is more granular and more robust to changes in computation models, programming languages, and feature selection characterization of (irreducible/incompressible) information content than entropy is [ 42 , 18 , 40 ] . Such an approach aligns more closely with the theoretical underpinnings of intelligence as algorithmic compression and model synthesis [ 16 , 45 , 10 ] . Because the most powerful implementation of BDM operates on binary representations (even when it can also deal with non-binary objects) and can deal with 2D objects such as weight matrices, we binarize network weights and constrain our experiments to Binarized Neural Networks (BNNs) [ 14 ] , which enable its direct application. In our main experiment, we trained binarized Multilayer Perceptrons (MLPs) [ 14 ] with varying hidden layer sizes on MNIST [ 17 ] , evaluating the correlation between model complexity—measured via BDM and entropy—and training loss across 200 training runs per architecture. Our findings reveal that the Pearson and Spearman correlations between BDM and training loss were consistently higher than those between entropy and loss, suggesting that BDM may serve as a more effective indicator of model complexity and its relationship with training dynamics (see also further discussion in Section 5 ). This empirical result supports the broader theoretical claim that training in neural networks can be understood as a process of algorithmic compression [ 33 ] —where structure is extracted and encoded in the weights—mirroring the regression/prediction principles proposed e.g. by Solomonoff [ 10 ] . These insights highlight the limitations of entropy-based approaches and point to the need for complexity-aware learning principles rooted in algorithmic probability [ 41 , 40 ] , such as those introduced in [ 12 ] , which applied BDM to guide learning on non-differentiable spaces. While related work has primarily examined entropy in terms of layer outputs and mutual information, such as those investigating the bottleneck principle [ 35 , 30 , 2 ] , our approach focuses instead on the complexity of the model itself—specifically the distribution and structure of its weights—rather than the dynamics of input-output mappings in activation values across layers. This distinction matters: weight-based complexity reflects the internal representational capacity and structural organization of the model (which is the case we study in this work); whereas layer output-based measures pertain to how data is processed during inference. Our results suggest, and we argue, that understanding and quantifying such an intrinsic complexity of a

Read the complete text