TL;DR
Grokking—the mysterious phenomenon where a model suddenly learns to generalize long after overfitting—isn't exclusive to complex transformers. This paper proves that even simple linear models "grok," revealing that the sudden jump in generalization is often a mathematical artifact of how we measure accuracy rather than a fundamental shift in the model's "understanding."
What Problem Does This Paper Address?
In 2022, researchers discovered "grokking": a neural network trained on algorithmic tasks (like modular addition) would hit 100% training accuracy almost immediately but stay at 0% generalization accuracy for thousands of epochs. Then, suddenly, generalization would skyrocket to 100%.
This led to a flurry of theories. Is the model "memorizing" first and then "understanding"? Is it a "slingshot" effect in the loss landscape? The authors of this paper argue that we don't need complex theories to explain this. They tackle the problem by asking: Can the simplest possible model—a linear estimator—display grokking? If it can, we can solve the math exactly and see what’s really happening under the hood.
Methods
The authors use a Teacher-Student setup. A "Teacher" (a linear transformation) generates labels from Gaussian noise, and a "Student" (another linear model) tries to learn that transformation using Mean Squared Error (MSE) loss and Gradient Descent.
To make the model analytically solvable, they employ:
- Gradient Flow: Analyzing the training dynamics in continuous time.
- Random Matrix Theory (RMT): Specifically, they use the Marchenko-Pastur distribution to describe the eigenvalues of the training data's covariance matrix.
- Thresholded Accuracy: They define "accuracy" not as the raw loss, but as the percentage of predictions that fall within a small error margin ($\epsilon$).
Datasets
The paper relies on synthetic datasets:
- Inputs: Independent and identically distributed (iid) Gaussian variables.
- Labels: Generated by a perfect linear "Teacher" model.
- Parameters: They vary the input dimensionality ($d_{in}$), output dimensionality ($d_{out}$), and the number of training samples ($N_{tr}$).
Key Insights and Ideas
- The "Accuracy" Illusion: This is the paper's biggest "aha" moment. Even if the model's loss (error) is decreasing smoothly and exponentially, the accuracy metric (which uses a threshold) can look like a flat line that suddenly jumps. The "grokking" transition is often just the moment the smooth loss curve finally dips below the accuracy threshold.
- The Covariance Gap: Training loss is calculated based on the empirical covariance of the training set, while generalization is based on the population covariance. Because the training gradients are driven by the training data, the model minimizes training error faster than generalization error. Grokking is simply the "lag" between these two processes.
- The Critical Ratio ($\lambda$): The time it takes to grok is primarily determined by $\lambda = d_{in}/N_{tr}$. When the number of parameters is close to the number of data points ($\lambda \approx 1$), the grokking time diverges and becomes massive.
- Weight Decay as a Stabilizer: Adding $L_2$ regularization (weight decay) can actually suppress grokking in overparameterized networks by shifting the "flat directions" in the loss landscape that cause the generalization lag.
Key Results
- Exact Predictions: The authors derived a closed-form equation for "grokking time" ($\Delta t_{grok}$) that accurately predicts when the generalization jump will happen based on initialization, noise, and dimensionality.
- Linear Grokking: They successfully demonstrated grokking curves in a simple linear perceptron that look identical to those seen in complex Transformers.
- Beyond Linear: They showed that their analytical predictions hold up surprisingly well for 2-layer networks with non-linear activations (like
tanh), suggesting that this "artifactual" explanation of grokking might apply to much deeper architectures.
Limitations and Future Work
- Gaussian Assumption: The math relies on the inputs being Gaussian. Real-world data (like language or images) has much more complex internal structures that might introduce different types of grokking.
- Loss Functions: The study focuses on MSE. The authors note that more "realistic" measures like cross-entropy or softmax (used in classification) might behave differently and are a subject for future work.
- Optimization Regimes: The paper stays within the "gradient flow" (small learning rate) limit. It doesn't explore "edge of stability" dynamics where very large learning rates might cause different types of sudden generalization.
Summary updated