Research map / Optimization / Implicit bias and generalization
Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets
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.
Proves a semi-ring algebraic structure over 2-layer quadratic-activation network weights and uses ring homomorphisms (sum potentials) to compose global optimal solutions for Abelian group multiplication, validated by matching gradient-descent solutions.
Problem
Understanding and analytically characterizing global optimal solutions of 2-layer quadratic-activation networks with L2 loss trained on modular addition / Abelian group multiplication, and why gradient descent selects low-order (Fourier) rather than memorizing solutions.
Approach
The weight space across different hidden-layer widths forms a commutative semi-ring, and the L2 loss depends only on sum potentials that are ring homomorphisms; hence global solutions can be composed algebraically from partial solutions via ring addition and multiplication.
Key results
- About 95% of gradient-descent order-4/6 solutions are factorable and match the theoretical constructions (d=23,71,127; q=512, weight decay 5e-5).
- Factorization error is about 0.04 relative to solution norm of order 1 for d=23.
- Solutions concentrate at order 4 and 6 per frequency; perfect memorization (order d^2) is not reached by gradient descent under weight decay.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Factorize gradient-descent solutions using CoGS constructions | 2-layer MLP solutions on modular addition · Modular addition, d∈{23,71,127} | fraction matching order-4/order-6 structures: around 95% | Helped |
| Use CoGS to predict empirical solution structure | Gradient-descent solutions · Modular addition, d∈{23,71,127} | structure prediction rate: ∼ 98% | Helped |
| Increase group size | Gradient-descent solution distribution · Modular addition, d∈{23,71,127} | frequency of the ν=i × ξ order-4 solution (%): 47.07 ± 1.88; 72.57 ± 0.70; 82.96 ± 0.39 | Helped |
| Remove the loss term corresponding to R_* (ablation) | CoGS Fourier solution construction · Modular addition | hidden nodes per frequency required for a global solution: 6 to 3 | Helped |
| Increase weight decay | 2-layer MLP trained with gradient descent · Modular addition | solution order | Helped |
| Increase weight decay until the model collapses | 2-layer MLP trained with gradient descent · Modular addition | solution quality | Hurt |
| Increase network width toward infinity | Sum-potential training dynamics · Modified modular-addition loss using the first two terms | decoupling of sum-potential dynamics: q → +∞ | Helped |
Surprising findings
- Gradient descent never produces some constructed solutions (e.g., z_3c * z_syn), indicating strong implicit bias.
- Perfect memorization solutions of order d^2 are not favored; dynamics prefer low-order Fourier solutions.
Limitations
- Analysis restricted to 2-layer quadratic activation networks with L2 loss on Abelian group multiplication.
- Full gradient dynamics not characterized; path connecting perfect memorization to low-order solutions left open.
- Does not directly address grokking.
Experimental setup
Datasets: synthetic modular addition / abelian group multiplication
Metrics: fraction of gradient descent solutions factorizable into con factorization error solution order distribution train/test accuracy
Baselines: gradient descent solutions analytic infinite-width Fourier solutions
Builds on: grokking quadratic activation networks Fourier solutions for modular addition
Closest papers by meaning
- Feature emergence via margin maximization: case studies in algebraic tasks (ICLR 2024 · similarity 0.85)
- Learning Polynomial Problems with $SL(2, \mathbb{R})$-Equivariance (ICLR 2024 · similarity 0.85)
- Compositional Reasoning with Transformers, RNNs, and Chain of Thought (NeurIPS 2025 · similarity 0.84)
- The Gradient of Algebraic Model Counting (AAAI 2025 · similarity 0.84)
- Semialgebraic Neural Networks: From roots to representations (ICLR 2025 · similarity 0.84)
- Position: Algebra Unveils Deep Learning - An Invitation to Neuroalgebraic Geometry (ICML 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.