Provable Benefits of Sinusoidal Activation for Modular Addition

Tianlong Huang, Zhiyuan LiSubmission to ICLR 2026 · Rejected

TL;DR

Standard neural networks equipped with nonperiodic activations like ReLU struggle with modular arithmetic and fail to extrapolate across sequence lengths. This paper proves that switching to sinusoidal activations creates a dramatic expressivity and generalization gap: a two-layer sine MLP needs only width-2 to compute modular sums for arbitrary sequence lengths, achieves an information-theoretically near-optimal sample complexity of $\widetilde{\mathcal{O}}(p)$, and extrapolates to sequence lengths hundreds of tokens beyond training.

What Problem Does This Paper Address?

Standard deep learning architectures rely on nonperiodic activations (such as ReLU or GELU). While effective for standard vision and language tasks, they struggle when tasks possess intrinsic periodicity—such as parity and modular arithmetic. Mechanistic interpretability research shows that networks solving modular addition often struggle through "grokking" before learning internal Fourier-style circuits (representing tokens as angles and addition as rotation).

The authors tackle a fundamental theoretical and practical question: What happens when you inject an explicit periodic inductive bias directly into the activation function? Using modular addition ($\sum_{i=1}^m s_i \bmod p$) as a benchmark, they theoretically characterize the separation between sine and ReLU networks in underparameterized, overparameterized, and length-extrapolation regimes.

Methods

The paper evaluates two-layer MLPs with shared, position-independent embeddings mapping bag-of-token vectors $x \in \{0, \dots, m\}^p$ to score vectors $s_\theta(x) = V\sigma(Wx) \in \mathbb{R}^p$, where $\sigma \in \{\sin, \text{ReLU}\}$.

  • Expressivity Analysis: Explicit constructive proofs for sine networks (leveraging trigonometric identities to construct Fourier bases) contrasted with linear region counting and positive 1-homogeneity arguments that constrain ReLU networks.
  • Underparameterized Uniform Convergence: A multiclass Natarajan-dimension bound proved via reduction to pairwise binary comparisons and algebraic sign-pattern counting, showing sample complexity scales as $\widetilde{\mathcal{O}}(dp)$ for a wide class of activations (polynomial, rational-exponential, and trigonometric).
  • Information-Theoretic Lower Bounds: A PAC lower bound of $\Omega(p)$ established for any label-permutation-equivariant algorithm (including Adam, AdamW, and SGD with momentum).
  • Overparameterized Margin Bounds: Width-independent generalization bounds derived via $\ell_\infty$ vector-contraction inequalities for Rademacher complexity, using Dudley entropy integrals for sine networks and layer-wise peeling for ReLU networks.
  • Optimization: Evaluated with AdamW (underparameterized), Muon (overparameterized, matching spectral-norm bounds), and vanilla SGD across MLPs and single-layer decoder-only Transformers.

Datasets

The authors use synthetic algorithmic datasets for modular addition:

  • In-Distribution Tasks: Multi-token addition modulo prime $p$ (e.g., $m=2, 3, 4$ with $p \in \{53, 97, 307\}$). Sequences $s_{1:m}$ are drawn i.i.d. uniformly from $\{0, \dots, p-1\}$.
  • Out-of-Domain (OOD) Length Extrapolation Benchmark: Training sequences sampled with lengths $m \in \{2, 3, 4, 5, 7, 13, 19\}$ for $p=53$ and $p=97$, then evaluated on unseen, held-out test sets spanning lengths up to $m = 811$.

Key Insights and Ideas

  • Width-2 Sufficiency vs. Linear Scaling: A biased sine network can compute $\sum_{i=1}^m s_i \bmod p$ exactly for all sequence lengths $m \ge 2$ simultaneously with just two hidden neurons. In contrast, any ReLU network requires width $d \ge \frac{m-p}{p+2} = \Omega(m/p - 1)$ to interpolate a single length $m$.
  • The Homogeneity Trap of ReLU: Because $\text{ReLU}(\alpha z) = \alpha \text{ReLU}(z)$ for $\alpha > 0$, scaling an input preserves the network's argmax prediction. Consequently, an unbiased ReLU network cannot simultaneously fit any two lengths $m_1 \not\equiv m_2 \pmod p$.
  • Near-Optimal Sample Complexity: Empirical Risk Minimization (ERM) over constant-width sine networks attains a sample complexity of $\widetilde{\mathcal{O}}(p)$, matching the information-theoretic lower bound $\Omega(p)$ up to polylogarithmic factors.
  • Width-Independent Normalized Margins: In overparameterized regimes, sine networks naturally produce $\Omega(1)$ normalized margins, ensuring $\widetilde{\mathcal{O}}(p/\sqrt{n})$ test error bounds independent of hidden width. Known ReLU interpolations, by contrast, yield margins that decay exponentially in $m$.

Key Results

  • Sample Efficiency (Underparameterized): Sine MLPs consistently achieve 100% test accuracy with substantially smaller widths and training budgets (e.g., $p=97, m=3$ reaching $\approx 1.0$ accuracy at width 16 with $12\text{k}$ samples, whereas ReLU requires larger widths and training sets to avoid near-chance performance).
  • Length Extrapolation: When trained on short sequences ($m \le 19$), sine MLPs achieve near-perfect ($\ge 99\%$) accuracy on sequences up to length $m=811$. ReLU networks fail even in-distribution and collapse to random guessing ($1/p \approx 0.01$) on longer sequences. Adding a first-layer bias makes sine length generalization robust across broader weight-decay regimes.
  • Extension to Transformers: A 1-layer, 1-head Transformer trained on modular addition with a sine feed-forward activation achieves $\approx 99\%$ test accuracy at only $8\text{k}$–$12\text{k}$ training examples, while ReLU and GELU baselines languish near chance ($< 5\%$) at the same budget.

Limitations and Future Work

  • Algorithmic Scope: Theoretical proofs focus on a minimal setting—two-layer MLPs with bag-of-words / shared embeddings on modular addition. Extending formal proofs to deep architectures, multi-head attention, and general non-abelian group operations remains open.
  • Exponential Margin Bound for ReLU: The authors note that the exponential penalty in sequence length $m$ for ReLU margin bounds is an artifact of the specific polynomial-spline ("Pizza"-style) proof construction; empirical ReLU margins are larger than the theoretical worst-case construction suggests.
  • Optimization Dynamics: While sine networks exhibit superior expressivity and generalization at convergence, sinusoidal loss landscapes are known to introduce optimization challenges (e.g., high sensitivity to learning rate or initialization without adaptive optimizers).

Summary updated

Abstract

This paper studies the role of activation functions in learning modular addition with two-layer neural networks. We first establish a sharp expressivity gap: sine MLPs admit width-$2$ exact realizations for any fixed length $m$ and, with bias, width-$2$ exact realizations uniformly over all lengths. In contrast, the width of ReLU networks must scale linearly with $m$ to interpolate, and they cannot simultaneously fit two lengths with different residues modulo $p$. We then provide a novel Natarajan-dimension generalization bound for sine networks, yielding nearly optimal sample complexity $\widetilde{\mathcal{O}}(p)$ for ERM over constant-width sine networks. We also derive width‑independent, margin-based generalization for sine networks in the overparametrized regime and validate it. Empirically, sine networks generalize consistently better than ReLU networks across regimes and exhibit strong length extrapolation.
BibTeX
@misc{huang2025provable,
  author = {Tianlong Huang and Zhiyuan Li},
  title = {{Provable Benefits of Sinusoidal Activation for Modular Addition}},
  year = {2025},
  eprint = {2511.23443},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2511.23443},
}
Figure