# Grokking as Compression: A Nonlinear Complexity Perspective

**Authors:** Ziming Liu, Ziqian Zhong, Max Tegmark  
**arXiv:** [2310.05918](https://arxiv.org/abs/2310.05918)  
**Date:** 2023-10-09  
**Summary page:** https://www.summarizepaper.com/en/paper/2310.05918v1/

## Key points

- The study investigates the phenomenon of grokking in deep learning models
- Grokking refers to delayed generalization after memorization
- The authors propose that grokking is attributed to compression
- They introduce a metric called linear mapping number (LMN) to measure network complexity
- LMN is preferred over $L_2$ norm for characterizing model complexity due to its interpretability and linear relationships with test losses during compression phase
- LMN reveals an intriguing phenomenon where XOR networks switch between two generalization solutions, which is not observed with $L_2$ norm
- Previous attempts have been made to understand grokking through toy models and measures like linear region number
- This work extends these measures by introducing LMN that can accommodate any activation function
- The authors highlight the connection between compression and deep learning, citing information bottleneck theory and success of language models
- Considering information and compression perspectives are crucial for understanding generalization puzzles in deep learning

## Summary

In this study, the authors investigate the phenomenon of grokking, which refers to the delayed generalization that occurs after memorization in deep learning models. They propose that this phenomenon can be attributed to compression and aim to understand it from a computation/information complexity perspective. To measure network complexity, the authors introduce a metric called linear mapping number (LMN), which is an extension of the linear region number for ReLU networks. LMN provides a way to characterize neural network compression before generalization. The authors argue in favor of using LMN over the popular choice of $L_2$ norm for characterizing model complexity for several reasons. Firstly, LMN can be naturally interpreted as information/computation, whereas $L_2$ norm cannot. Secondly, during the compression phase, LMN exhibits linear relationships with test losses, while $L_2$ norm shows complicated nonlinear correlations with test losses. Lastly, LMN reveals an intriguing phenomenon where XOR networks switch between two generalization solutions, which is not observed with $L_2$ norm. The authors also discuss related works and discussions on grokking and complexity measures in deep learning. Previous attempts have been made to understand grokking through toy models and measures that characterize its dynamics. Complexity measures such as linear region number have been proposed from an information perspective. However, this work extends these measures by introducing LMN that can accommodate general networks with any activation function. Furthermore, the authors highlight the connection between compression and deep learning. The theory of information bottleneck suggests a compression phase followed by a fitting phase in deep learning models. Recent studies have also attributed the success of language models to compression. The authors agree that considering information and compression perspectives are crucial for unlocking generalization puzzles in deep learning and propose that LMN could serve as a useful metric in this regard. In summary, this study explores grokking from a computation/information complexity perspective by introducing the concept of LMN as a measure of network complexity.