Neural networks sometimes memorize data for an extended number of training steps without generalizing. Then they suddenly start to generalize. This is called grokking. This paper shows what's happening: the network's complexity goes up, then down. This is a complexity phase transition.

The key finding: In grokking with proper regularization, networks get simpler as they learn. Complexity rises during memorization, peaks, then falls as the network finds simpler patterns that work. Without regularization, complexity stays high and generalization does not emerge.

How to Measure What Networks Learn

Normal methods count parameters, but parameter count is not the same as complexity. This paper uses a different approach: "How many bits does it take to describe what the network learned?" Their metric aims at intrinsic complexity via compressibility.

Here's the idea: measure how small you can compress the network's weights. Random data doesn't compress much. Data with patterns compresses a lot.

The researchers use Kolmogorov complexity and rate-distortion theory to measure network complexity. Their method gets 30-40 times better compression than simple methods. This gives them a tight upper bound on complexity by using lossy compression after coarse-graining, letting them track complexity dynamics during training.

Three Stages of Learning

Stage 1: Memorization
Complexity rises as the network memorizes examples. It stores each one individually. High complexity.

Stage 2: Peak
Complexity reaches its highest point. The network has memorized everything but hasn't found the underlying rule.

Stage 3: Generalization
Complexity falls. The network finds a simpler pattern that works for all data. It stops storing individual examples and learns the rule.

In these experiments, networks without regularization remain in a high-complexity memorization phase and don't generalize. They never make the transition to simplicity.

The Link Between Compression and Generalization

The paper connects complexity to the Minimum Description Length Principle. This principle says simpler models are better.

A lookup table that memorizes all data drives data entropy to zero, but the model complexity equals the original data entropy. So the total description length doesn't decrease. No compression is achieved. A model that finds patterns can compress the data much more. Under MDL, the model that best compresses the data is expected to generalize best.

Better compression predicts better generalization under MDL. This is a principled link, not an identity. Both involve finding simple patterns in data.

A New Training Method

The researchers created a new training technique called spectral entropy regularization. It penalizes network complexity during training. This pushes networks toward simpler representations and helps them generalize instead of memorizing.

Why This Matters

This work answers a key question: Why do simpler models generalize better?

Good learning isn't about more parameters or more data. It's about finding the simplest explanation that fits. The paper argues that simpler, more compressible solutions generalize better and provides a way to measure and encourage that. The evidence comes from grokking tasks, showing that compressibility tracks with generalization.

Now we can measure the path from complexity to simplicity as it happens.

Note: These results are shown on modular arithmetic grokking tasks using small transformers. Regularization is key to seeing the clean complexity phase transition. The findings may apply more broadly, but the experiments focus on this specific setting.