🤖 machine learning

Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

This paper introduces the Quantized Block Decomposition (QuBD) method, a scalable algorithm for estimating the Kolmogorov-Chaitin-Solomonoff complexity of deep neural network weights, which reveals that algorithmic complexity decreases during learning, correlates with generalization, and identifies significant bit-planes for effective model quantization.

Original authors: Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, Raghavendra Selvan

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, Raghavendra Selvan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: Learning is Like Packing a Suitcase

Imagine you have a massive, chaotic suitcase full of random clothes, socks, and shoes thrown in haphazardly. This represents a newly trained Deep Neural Network (DNN) right after it starts learning. It has all the "parameters" (the weights), but they are just random noise. It's messy, takes up a lot of space, and is hard to understand.

As the network "learns" (trains on data), it starts organizing this suitcase. It folds the shirts, rolls the socks, and stacks the shoes neatly. It finds patterns. In the world of computer science, this organization is called structure.

The paper's main hypothesis is "Learning as Compression." The idea is that as a model learns, it doesn't just get smarter; it actually becomes simpler and more organized. If you can organize your suitcase well, you can fit it into a smaller bag. This is why we can compress AI models later to make them run faster and use less energy.

The Problem: Measuring "Messiness" is Hard

Scientists have long wanted to measure exactly how organized a neural network is. They use a concept called Kolmogorov Complexity (or KCS complexity).

The Analogy: Think of KCS complexity as the length of the shortest instruction manual needed to recreate a specific object.
- A random pile of clothes has a long manual: "Put a red sock here, a blue shoe there..." (High complexity).
- A neatly folded stack of identical white shirts has a short manual: "Fold 50 white shirts and stack them" (Low complexity).

The Catch: Calculating this "shortest manual" is mathematically impossible for large, complex objects like modern AI models. Existing tools (called CTM and BDM) are like trying to measure the complexity of a whole city by only looking at a single brick. They work for tiny, simple things (like binary code) but break down when you try to use them on the massive, floating-point numbers inside modern AI.

The Solution: QuBD (The "Bit-Plane" Translator)

The authors introduce a new method called QuBD (Quantized Block Decomposition).

How it works (The Metaphor):
Imagine you have a high-resolution digital photo (the AI weights).

Quantization: First, QuBD simplifies the photo by rounding the colors to a specific palette (like turning a photo into a pixel art style). This makes the data manageable.
Bit-Plane Decomposition: Instead of looking at the whole photo at once, QuBD peels the image apart layer by layer, like an onion.
- Layer 1 (The Most Significant Bit): This is the "skeleton" of the image. It holds the big shapes and main structures.
- Layer 2, 3, etc.: These are the fine details, the shading, and the tiny noise.
The Magic: QuBD measures the "messiness" (complexity) of each layer separately and adds them up.

Why is this better?
Old methods tried to flatten the whole photo into black and white (binary) instantly, losing a lot of detail. QuBD looks at the layers one by one. The paper proves mathematically that this gives a much more accurate measurement of how "organized" the data really is.

What They Discovered: The Journey of Learning

Using this new "layer-peeling" tool, the authors watched how AI models change as they learn. Here is what they found:

1. Learning Reduces Complexity
As a model trains, its "suitcase" gets organized. The complexity score goes down.

Analogy: The model starts with a chaotic pile of random numbers. As it learns, it realizes, "Oh, I don't need to remember every single random number; I just need to remember the pattern." The instruction manual gets shorter.

2. Overfitting Makes it Messy Again
If a model trains too long, it starts to memorize the training data instead of learning the pattern. This is called overfitting.

Analogy: The model stops folding the clothes and starts stuffing every single sock into a specific corner just to remember where it was. The suitcase becomes messy again, and the complexity score goes up.

3. The "Grokking" Phenomenon
Sometimes, a model seems stuck, failing to learn, and then suddenly "gets it" (this is called grokking).

Analogy: The model is struggling, and the complexity stays high. Suddenly, it has an "Aha!" moment, the complexity drops sharply, and it starts solving the problem perfectly. The QuBD tool tracked this drop in complexity exactly when the model started generalizing.

4. The "Important" Layers
The authors found that the "skeleton" layers (the most significant bits) contain almost all the useful information. The "fine detail" layers (the least significant bits) are often just random noise.

Analogy: If you are packing for a trip, the clothes (the main structure) matter. The lint in your pockets (the low bits) doesn't matter.
Practical Use: This tells engineers that they can safely throw away the "low bit" layers to compress the model without losing performance. It acts as a diagnostic tool to decide how much to compress a model.

Summary

This paper invented a new ruler (QuBD) to measure how "organized" an AI is. They proved that:

Learning = Organizing: As AI learns, it becomes simpler and more compressible.
Overfitting = Chaos: If it learns too much, it gets messy again.
The "Big Bits" Matter: The most important information is in the top layers of the data, allowing us to safely remove the rest to save space.

This gives us a new way to understand how deep learning works, not just by looking at accuracy scores, but by looking at the fundamental structure of the data itself.

Technical Summary: Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis

Problem Statement

Training large-scale deep neural networks (DNNs) is increasingly resource-intensive, necessitating model compression techniques such as pruning, knowledge distillation, and quantization. The "learning as compression" hypothesis posits that training induces structural organization in network weights, thereby enabling compression. While Kolmogorov-Chaitin-Solomonoff (KCS) complexity is the theoretical metric for measuring such structure, it is non-computable. Existing estimators based on the Coding Theorem Method (CTM) and the Block Decomposition Method (BDM) are limited to small binary objects and fail to scale to modern DNNs, which involve large, non-binary (floating-point) weight tensors. Furthermore, existing methods often rely on binarization, which can be lossy and obscure meaningful structural information.

Methodology: Quantized Block Decomposition (QuBD)

To address scalability and precision limitations, the authors introduce the Quantized Block Decomposition (QuBD) method. This approach extends algorithmic complexity estimation to any $k$ -ary object through the following pipeline:

Quantization: Network weights $W \in \mathbb{R}^d$ are mapped to a finite alphabet $\Sigma_q$ using an affine uniform quantizer, resulting in integer codes $W^{(q)}$ .
Bit-Plane Decomposition: Each quantized weight is decomposed into its binary expansion across $q$ bit-planes. The $l$ -th bit-plane $\beta_l$ collects the $l$ -th bit of all $d$ symbols.
Aggregation: The KCS complexity is estimated by aggregating per-bit-plane CTM estimates. The total complexity is calculated as $C_{QuBD}(W) = \sum_{l=0}^{q-1} C(\beta_l)$ , where $C(\beta_l)$ is derived from pre-computed CTM tables for small binary blocks.

Theoretical Advantages:
The paper provides theoretical proofs demonstrating that QuBD yields a strictly tighter estimation gap relative to true KCS complexity compared to binarization-based methods.

Residual Decomposition (Theorem 3.1): The paper formalizes that estimating an object from its quantized prefix $y_q$ misses residual information $R_q$ contained in the discarded lower bits.
Bit-Plane Residual Loss (Theorem 3.2): It is proven that adding bit-planes reduces the residual loss. Specifically, retaining multiple bit-planes yields a strictly smaller residual than one-bit binarization, provided the bit-planes are not identical.
Saturation Analysis: The authors analyze the "saturation" of finite CTM tables. They show that while serialization (flattening all bits) saturates CTM tables quickly due to the sheer volume of blocks, bit-plane decomposition scales the support effectively by evaluating local structures independently across planes, maintaining informative estimates at larger scales.

Key Results

Using QuBD, the authors provide the first scalable empirical characterization of learning dynamics in DNNs beyond simple feedforward networks:

Complexity Reduction During Training: As models learn, the algorithmic complexity of their weights decreases. This is observed across Multi-Layer Perceptrons (MLPs) and Vision Transformers (ViTs), where complexity reduction correlates with improved test accuracy.
Overfitting and Complexity: During overfitting, algorithmic complexity increases. This suggests that memorization introduces structure that is algorithmically complex (less compressible), contrasting with the simplification observed during generalization.
Grokking Phenomenon: In "grokking" experiments (where models generalize well after a long period of overfitting), QuBD complexity remains high during the high-validation-loss phase and only decreases significantly once the validation loss drops to zero, tracking the delayed generalization.
Bit-Plane Information Distribution: Algorithmic information is not uniformly distributed. The most significant bit-planes (MSB) exhibit the largest complexity reduction (indicating high structure), while lower bit-planes often show complexity ratios close to 100% (random).
Diagnostic for Compression: The concentration of algorithmic information in the MSBs correlates with Post-Training Quantization (PTQ) performance. Models can be quantized to 4–6 bits with minimal accuracy loss, as the lower bit-planes contain negligible algorithmic information. QuBD complexity serves as a practical diagnostic to determine optimal quantization levels and identify layers suitable for pruning.

Significance and Claims

The paper claims to offer the first scalable, tractable estimates of KCS complexity for large, non-binary objects such as DNN weights. Its significance lies in:

Operationalizing "Learning as Compression": It provides empirical evidence that training induces structure in weights, measurable via algorithmic complexity, supporting the hypothesis that learning is a process of compression.
Theoretical Superiority: It establishes theoretically that bit-plane decomposition offers a tighter bound on KCS complexity than binarization, addressing a fundamental limitation in previous algorithmic information theory applications to DNNs.
Practical Utility: It demonstrates that algorithmic complexity analysis can serve as a diagnostic tool for model compression, identifying redundant capacity (e.g., lower bit-planes or specific layers) without requiring performance loss.

The authors conclude that algorithmic information theory provides a powerful paradigm for explaining deep learning mechanisms, offering a concrete method to characterize learning dynamics that aligns with generalization performance and phenomena like grokking.