# Grokking as Compression: A Nonlinear Complexity Perspective

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 23 references that are in the map.
- First posted on arXiv 9 Oct 2023.

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

- [Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/1702.03118/) (2017)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Towards Understanding Grokking: An Effective Theory of Representation Learning](https://mlsanity.com/paper/2205.10343/) (2022)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit](https://mlsanity.com/paper/2207.08799/) (2022)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Omnigrok: Grokking Beyond Algorithmic Data](https://mlsanity.com/paper/2210.01117/) (2022)
- [Explaining grokking through circuit efficiency](https://mlsanity.com/paper/2309.02390/) (2023)
- [The Slingshot Mechanism: An Empirical Study of Adaptive Optimizers and the Grokking Phenomenon](https://mlsanity.com/paper/2206.04817/) (2022)
- [Grokking modular arithmetic](https://mlsanity.com/paper/2301.02679/) (2023)
- [A Tale of Two Circuits: Grokking as Competition of Sparse and Dense Subnetworks](https://mlsanity.com/paper/2303.11873/) (2023)
- [Unifying Grokking and Double Descent](https://mlsanity.com/paper/2303.06173/) (2023)
- [Predicting Grokking Long Before it Happens: A look into the loss landscape of models which grok](https://mlsanity.com/paper/2306.13253/) (2023)
- [Symbolic Pregression: Discovering Physical Laws from Distorted Video](https://mlsanity.com/paper/2005.11212/) (2020)

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

- [Mechanistic Interpretability for AI Safety -- A Review](https://mlsanity.com/paper/2404.14082/) (2024)
- [Rethinking LLM Memorization through the Lens of Adversarial Compression](https://mlsanity.com/paper/2404.15146/) (2024)
- [Information-Theoretic Progress Measures reveal Grokking is an Emergent Phase Transition](https://mlsanity.com/paper/2408.08944/) (2024)
- [Towards Empirical Interpretation of Internal Circuits and Properties in Grokked Transformers on Modular Polynomials](https://mlsanity.com/paper/2402.16726/) (2024)
- [Grokking Beyond Neural Networks: An Empirical Exploration with Model Complexity](https://mlsanity.com/paper/2310.17247/) (2023)
- [When Do Neural Networks Learn World Models?](https://mlsanity.com/paper/2502.09297/) (2025)
- [Bridging Lottery Ticket and Grokking: Understanding Grokking from Inner Structure of Networks](https://mlsanity.com/paper/2310.19470/) (2023)
- [Explaining Grokking and Information Bottleneck through Neural Collapse Emergence](https://mlsanity.com/paper/2509.20829/) (2025)
- [Grokking vs. Learning: Same Features, Different Encodings](https://mlsanity.com/paper/2502.01739/) (2025)
- [Grokking Finite-Dimensional Algebra](https://mlsanity.com/paper/2602.19533/) (2026)
- [A Two-Phase Perspective on Deep Learning Dynamics](https://mlsanity.com/paper/2504.12700/) (2025)
- [Truth as a Compression Artifact in Language Model Training](https://mlsanity.com/paper/2603.11749/) (2026)
- [Phase Transitions in Driven Informational Systems: A Two-Field Perspective on Learning Theory and Non-Equilibrium Chemistry](https://mlsanity.com/paper/2605.16325/) (2026)
- [A Spectral Theory of Grokking: Weight Decay induces Feature Learning](https://mlsanity.com/paper/2609.26679/) (2026)

## Abstract (arXiv)

We attribute grokking, the phenomenon where generalization is much delayed after memorization, to compression. To do so, we define linear mapping number (LMN) to measure network complexity, which is a generalized version of linear region number for ReLU networks. LMN can nicely characterize neural network compression before generalization. Although the L2 norm has been a popular choice for characterizing model complexity, we argue in favor of LMN for a number of reasons: (1) LMN can be naturally interpreted as information/computation, while L2 cannot. (2) In the compression phase, LMN has linear relations with test losses, while L2 is correlated with test losses in a complicated nonlinear way. (3) LMN also reveals an intriguing phenomenon of the XOR network switching between two generalization solutions, while L2 does not. Besides explaining grokking, we argue that LMN is a promising candidate as the neural network version of the Kolmogorov complexity since it explicitly considers local or conditioned linear computations aligned with the nature of modern artificial neural networks.