Research map / Optimization / Implicit bias and generalization
Emergence in non-neural models: grokking modular arithmetic via average gradient outer product
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.
Shows that grokking of modular arithmetic occurs in Recursive Feature Machines (kernel machines with AGOP-based feature learning), not only in neural networks, and links the learned block-circulant features to the Fourier Multiplication Algorithm.
Problem
Grokking of modular arithmetic is often cited as an emergent phenomenon in neural networks trained by gradient descent; it is unclear whether the sharp test-accuracy transition depends on neural architectures or gradient-based optimization, and whether standard progress measures predict it.
Approach
Grokking arises from task-specific feature learning via the AGOP: iterating RFM (kernel ridgeless regression plus AGOP feature update) gives a sharp accuracy transition despite zero training loss and constant early test loss, with feature matrices that become block-circulant; such circulant features let kernel machines implement the Fourier Multiplication Algorithm.
Key results
- RFM with quadratic/Gaussian kernels on modular arithmetic (p=61) transitions from near-zero to 100% test accuracy after ~10 iterations while training loss stays at zero and test loss is flat in early iterations.
- Standard kernel machines trained on random block-circulant transformed inputs generalize, and neural networks trained on random circulant-transformed inputs reach 100% test accuracy within several hundred epochs at 17.5% training fraction where untransformed inputs do not reach 100% within 3000 epoc
- Neural feature matrices and square-root AGOP of one-hidden-layer quadratic networks correlate at 0.92 to 0.955 across add, sub, mul, div.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use iterative AGOP feature learning with a kernel machine | RFM · Modular arithmetic, p = 61 | test accuracy: near-zero -> 100% | Helped |
| Transform neural-network inputs with a random block-circulant matrix | One-hidden-layer fully connected network · Modular addition and multiplication, training fraction 17.5% | epochs to 100% test accuracy: within several hundred epochs; standard inputs do not achieve 100% within 3000 epochs | Helped |
| Use standard one-hot inputs instead of random block-circulant transformed inputs | One-hidden-layer fully connected network · Modular addition and multiplication, training fraction 17.5% | test accuracy: do not achieve 100% test accuracy even within 3000 epochs | Hurt |
| Enforce block-circulant structure in RFM feature matrices at every iteration | RFM · Modular arithmetic, including addition | test loss | Helped |
| Use random circulant features instead of learning features through AGOP | Standard Gaussian kernel machine · Modular addition and multiplication, p = 61 | generalization | Helped |
| Use no regularization instead of weight decay or AGOP regularization (ablation) | One-hidden-layer neural network · Modular addition, p = 61 | test accuracy: does not go to 100% | Hurt |
| Add weight decay (ablation) | One-hidden-layer neural network · Modular addition, p = 61 | test accuracy: 100% | Helped |
| Add trace-of-AGOP regularization (ablation) | One-hidden-layer neural network · Modular addition, p = 61 | test accuracy: 100% | Helped |
| Use no regularization instead of weight decay or AGOP regularization (ablation) | One-hidden-layer neural network · Modular addition, p = 61 | grokking | Hurt |
| Increase RFM iterations while training loss remains zero | RFM · Modular arithmetic, p = 61 | training loss: identically zero | No clear effect |
| Use AGOP alignment and circulant deviation to track training progress | RFM · Modular arithmetic, p = 61 | feature progress before test-loss improvement: first 10 iterations | Helped |
| Train RFM on two modular tasks simultaneously | RFM · x + y mod p and x^2 + y^2 mod p, p = 61 | task-wise grokking timing | Mixed |
Surprising findings
- Test loss and accuracy stay constant for many iterations while circulant deviation and AGOP alignment improve, so the transition is not predicted by training or test loss.
- Grokking in RFM occurs without a lazy-to-rich transition, contrary to two-phase explanations of grokking in neural networks.
Limitations
- Theoretical result covers a specific construction (quadratic kernel with block-circulant feature matrix over all data), not the learned RFM features generally.
- Progress measures like circulant deviation are task-specific and require reordering by discrete logarithm for multiplication/division; AGOP alignment requires access to the final trained model.
Experimental setup
Datasets: synthetic modular arithmetic (addition, subtraction, multiplication, division) mod p=61 modular addition mod 97 x^2+y^2 mod 61
Benchmarks: modular arithmetic tasks (add, sub, mul, div) mod 61
Metrics: test accuracy test loss (MSE) circulant deviation AGOP alignment
Baselines: one-hot standard kernel machine standard neural network training (one-hidden-layer quadratic network)
Builds on: Recursive Feature Machines Neural Feature Ansatz Fourier Multiplication Algorithm grokking
Closest papers by meaning
- Learning to grok: Emergence of in-context learning and skill composition in modular arithmetic tasks (NeurIPS 2024 · similarity 0.88)
- Model Capacity Determines Grokking through Competing Memorisation and Generalisation Speeds (NeurIPS 2026 · similarity 0.87)
- Grokking as a First Order Phase Transition in Two Layer Networks (ICLR 2024 · similarity 0.87)
- Grokking as the transition from lazy to rich training dynamics (ICLR 2024 · similarity 0.87)
- Feature emergence via margin maximization: case studies in algebraic tasks (ICLR 2024 · similarity 0.86)
- Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking (ICLR 2024 · similarity 0.86)
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.