The Complexity Dynamics of Grokking

Abstract

We demonstrate the existence of a complexity phase transition in neural networks by studying the grokking phenomenon, where networks suddenly transition from memorization to generalization long after overfitting their training data. To characterize this phase transition, we introduce a theoretical framework for measuring complexity based on rate-distortion theory and Kolmogorov complexity, which can be understood as principled lossy compression for networks. We find that properly regularized networks exhibit a sharp phase transition: complexity rises during memorization, then falls as the network discovers a simpler underlying pattern that generalizes. In contrast, unregularized networks remain trapped in a high-complexity memorization phase. We establish an explicit connection between our complexity measure and generalization bounds, providing a theoretical foundation for the link between lossy compression and generalization. Our framework achieves compression ratios 30-40x better than naïve approaches, enabling precise tracking of complexity dynamics. Finally, we introduce a regularization method based on spectral entropy that encourages networks toward low-complexity representations by penalizing their intrinsic dimension.

References in corpus (14)

• LoRA: Low-Rank Adaptation of Large Language Models
• Scaling Laws for Neural Language Models
• Mixed Precision Training
• QLoRA: Efficient Finetuning of Quantized LLMs
• Scaling Laws for Autoregressive Generative Modeling
• Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets
• Progress measures for grokking via mechanistic interpretability
• The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits
• Thermodynamic costs of Turing Machines
• Towards Understanding Grokking: An Effective Theory of Representation Learning
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning
• Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton
• Omnigrok: Grokking Beyond Algorithmic Data
• Explaining grokking through circuit efficiency