Research map / Optimization / Implicit bias and generalization
Why Do You Grok? A Theoretical Analysis on Grokking Modular Addition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically explains grokking on modular addition: kernel-regime permutation-equivariant learners need Omega(1) fraction of data, while l_inf-regularized two-layer quadratic networks generalize with far fewer samples.
Problem
Why grokking occurs on modular addition: why kernel-regime (early-training) networks fail to generalize across architectures, and how weak regularization later enables generalization.
Approach
Shows via permutation equivariance that any permutation-equivariant kernel method needs a constant fraction of all data to generalize on modular addition, while bounded-l_inf-norm two-layer quadratic networks that interpolate generalize with O(1/p) (regression) or ~p^{5/3} (classification) samples, so grokking reflects a kernel-to-rich regime transition.
Key results
- Permutation-equivariant kernel methods need n = Omega(p^3) (regression) or Omega(p^2) (classification) samples before population l2 loss drops below the all-zero predictor.
- Empirical NTK kernel regression can reach zero training error with h = O~(p) width; l-infinity norm of trained weights does not grow with p.
- Regression rich-regime bound gives population loss O(p^2/n * log^3 n) relative to zero predictor, so generalization with n = O~(p^2) samples; classification bound gives O~(sqrt(p^{5/3}/n)) error.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| keep training in the permutation-equivariant kernel regime | Kernel methods on modular addition, regression · Modular addition regression | population square loss: ≥ p/2 | Hurt |
| use a small-ℓ∞-norm interpolating solution instead of a kernel-regime predictor | Two-layer quadratic network · Modular addition regression | population square loss: n = \tilde{\omega}(p^2) | Helped |
| use an interpolating solution with large normalized ℓ∞ margin instead of a kernel-regime predictor | Two-layer quadratic network · Modular addition classification | 0-1 error: \tilde{\bigO}(p^{5/3}) | Helped |
| reduce the initialization scale | Two-layer quadratic network · Modular addition regression | train-test accuracy gap | Helped |
| reduce the initialization scale | Two-layer quadratic network · Modular addition classification | train-test accuracy gap | Helped |
| reduce the initialization scale | Two-layer quadratic network · Modular addition | training difficulty | Hurt |
| train with tiny ℓ∞ regularization until the network leaves the kernel regime | One-layer Transformer · Modular addition | eNTK change before fitting the training set | No clear effect |
Surprising findings
- Shrinking the initialization scale mitigates grokking but slows time to final generalization.
- The authors note that the gromov2023grokking claim that its analytical solution is what gradient descent finds does not match their experience.
Limitations
- Kernel lower bounds are on l2 loss, not classification error; classification-error lower bound left open.
- Rich-regime results assume bounded l-infinity norm and interpolation, not proven that GD reaches them; empirical support only.
- Transformer results are extended by conjecture/small modifications rather than fully proven.
Experimental setup
Datasets: modular addition synthetic data
Benchmarks: modular addition (synthetic)
Metrics: population l2 loss 0-1 error train/test accuracy empirical NTK change l-infinity norm of weights
Baselines: kernel regression (permutation-equivariant) all-zero predictor
Builds on: grokking (Power et al., 2022) neural tangent kernel Adam implicit bias l-infinity optimistic rates
Closest papers by meaning
- Grokking Beyond the Euclidean Norm of Model Parameters (ICML 2025 · similarity 0.91)
- Grokking at the Edge of Numerical Stability (ICLR 2025 · similarity 0.90)
- Grokking as the transition from lazy to rich training dynamics (ICLR 2024 · similarity 0.90)
- Grokking in Linear Estimators -- A Solvable Model that Groks without Understanding (ICLR 2024 · similarity 0.89)
- Let Me Grok for You: Accelerating Grokking via Embedding Transfer from a Weaker Model (ICLR 2025 · similarity 0.88)
- Deep Networks Always Grok and Here is Why (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.