Abstract
Grokking is the intriguing phenomenon where a model learns to generalize long after it has fit the training data. We show both analytically and numerically that grokking can surprisingly occur in linear networks performing linear tasks in a simple teacher-student setup with Gaussian inputs. In this setting, the full training dynamics is derived in terms of the training and generalization data covariance matrix. We present exact predictions on how the grokking time depends on input and output dimensionality, train sample size, regularization, and network initialization. We demonstrate that the sharp increase in generalization accuracy may not imply a transition from "memorization" to "understanding", but can simply be an artifact of the accuracy measure. We provide empirical verification for our calculations, along with preliminary results indicating that some predictions also hold for deeper networks, with non-linear activations.
Introduction
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 theories about models transitioning from "memorization" to "understanding."
This paper challenges that narrative by demonstrating that grokking—this mysterious sudden jump in generalization—isn't exclusive to complex transformers. Even simple linear models can "grok," revealing that the phenomenon is often a mathematical artifact of how we measure accuracy rather than a fundamental shift in the model's internal representation.
Methods
The authors employ a Teacher-Student setup where a linear "Teacher" model generates labels from Gaussian noise. A "Student" linear model then attempts to learn this transformation using Mean Squared Error (MSE) loss and Gradient Descent.
To derive the training dynamics analytically, the study uses:
- Gradient Flow: Analyzing dynamics in continuous time.
- Random Matrix Theory (RMT): Using the Marchenko-Pastur distribution to describe the eigenvalues of the training data's covariance matrix.
- Thresholded Accuracy: Defining "accuracy" as the percentage of predictions falling within a small error margin ($\epsilon$).
The "Accuracy" Illusion and the Covariance Gap
The paper's central insight is that grokking can be an illusion created by thresholding. While the model's loss (MSE) might decrease smoothly and exponentially, the accuracy metric—which uses a binary threshold—remains flat until the loss finally dips below that threshold. At that point, accuracy appears to "jump" suddenly.
This lag between training and generalization is driven by the Covariance Gap. Training loss is calculated based on the empirical covariance of the training set, while generalization depends on the population covariance. Since gradients are driven by training data, the model minimizes training error faster than generalization error, creating a predictable delay.
Key Results and Exact Predictions
The authors derived a closed-form equation for "grokking time" ($\Delta t_{grok}$) that predicts the generalization jump based on initialization, noise, and dimensionality.
- The Critical Ratio ($\lambda$): Grokking time is primarily determined by $\lambda = d_{in}/N_{tr}$. As the number of parameters approaches the number of data points ($\lambda \approx 1$), the grokking time diverges significantly.
- Dimensionality Effects: The model shows that grokking time also depends on the output dimensionality $d_{out}$.
- Weight Decay: Adding $L_2$ regularization can suppress grokking in overparameterized networks by shifting the "flat directions" in the loss landscape that cause the generalization lag.
- Generality: Preliminary results suggest these analytical predictions hold for 2-layer networks with non-linear activations (like
tanh), indicating the "artifactual" explanation may extend to deeper architectures.
Conclusion and Future Work
This work suggests that grokking might be a simpler phenomenon than previously thought, often arising from the interplay between smooth loss optimization and discrete accuracy measurement. However, limitations remain: the current math assumes Gaussian inputs and MSE loss. Future work will explore more complex data structures and classification-specific loss functions like cross-entropy to see if these "artifactual" explanations still hold in more realistic deep learning regimes.
Summary updated