Research map / Learning theory and algorithms / Combinatorial and search optimization
Uncovering a Universal Abstract Algorithm for Modular Addition in Neural Networks
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.
Proposes that MLPs and transformers trained on modular addition all implement a common abstract algorithm, the approximate Chinese Remainder Theorem, built on approximate cosets, and predicts O(log n) frequencies suffice for deep networks.
Problem
Prior interpretability work reported disjoint mechanisms (Clock, Pizza, coset circuits, GCR) for modular addition and group multiplication, casting doubt on the universality hypothesis; the paper asks whether these solutions share a common abstract algorithm across architectures and depths.
Approach
Generalizes cosets to approximate cosets (sets of elements close in the Cayley graph generated by a step size), shows neurons with sinusoidal preactivations activate on approximate cosets, and unifies prior mechanisms under an abstract approximate Chinese Remainder Theorem (aCRT) requiring O(log n) random frequencies.
Key results
- Networks trained on modular addition learn O(log n) distinct frequencies, with logarithmic fits to frequency counts across moduli reporting very high R^2.
- Layer-1 neurons in MLPs and transformers are well approximated by single sinusoids (simple neurons), with fits maintaining near-perfect accuracy when replaced.
- Theory gives that margin between correct and incorrect logits grows with number of learned frequencies, and a corollary predicts O(log n) frequencies yield logit margin Omega(log n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace MLP neurons with simple-neuron fits (ablation) | MLPs · Modular addition | test accuracy: 100% | No clear effect |
| Fit deeper transformer neurons using only first-order sinusoids instead of allowing order-two terms (ablation) | Transformers · Modular addition | test accuracy | Hurt |
| Add trainable input embeddings (ablation) | One-hidden-layer MLPs · Modular addition | number of learned frequency types: from learning \lfloor\frac{n}{2}\rfloor types to much fewer types | Mixed |
| Add depth (ablation) | One-hot encoded MLPs · Modular addition | number of learned frequency types: from learning \lfloor\frac{n}{2}\rfloor types to much fewer types | Mixed |
| Increase network width (ablation) | One-layer architectures · Modular addition | presence of secondary frequencies in neuron fits | Helped |
| Use precise coset-aligned frequencies rather than approximate coset frequencies | All architectures · Modular addition, n=66 | frequency preference | Helped |
Surprising findings
- Networks often learn only a single frequency that divides the modulus alongside non-coset frequencies, and no meaningful distinction was found between coset-aligned and non-coset neurons.
- Adding depth or trainable embeddings shifts MLPs from learning floor(n/2) frequencies to only a handful of frequencies.
Limitations
- Only cyclic groups are analyzed in depth; groups between cyclic and permutation extremes are not explored.
- Theory does not bound how many neurons are needed per learned frequency.
- Why networks shift to O(log n) frequencies (training dynamics vs. learned solution) is left open.
Experimental setup
Datasets: modular addition dataset (all n^2 pairs)
Benchmarks: modular addition (mod n across primes, composites, powers of 2)
Metrics: R^2 of sinusoidal fits to neuron preactivations number of learned frequencies R^2 of logarithmic fit (frequencies vs modulus) test accuracy
Baselines: Clock Pizza GCR coset circuits
Builds on: Fourier Multiplication Algorithm (Clock) Pizza circuit Group Composition via Representations (GCR) Chinese Remainder Theorem
Closest papers by meaning
- Neural networks are more modular than single neurons suggest (NeurIPS 2026 · similarity 0.85)
- Feature emergence via margin maximization: case studies in algebraic tasks (ICLR 2024 · similarity 0.85)
- Breaking Neural Network Scaling Laws with Modularity (ICLR 2025 · similarity 0.85)
- Emergence in non-neural models: grokking modular arithmetic via average gradient outer product (ICML 2025 · similarity 0.85)
- Position: A Theory of Deep Learning Must Include Compositional Sparsity (ICML 2025 · similarity 0.84)
- Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks (NeurIPS 2025 · similarity 0.84)
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.