# Composing Global Solutions to Reasoning Tasks via Algebraic Objects in Neural Nets

arXiv: https://arxiv.org/abs/2410.01779 · HTML: https://mlsanity.com/paper/2410.01779/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 40 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 30 of 32)

- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [GLU Variants Improve Transformer](https://mlsanity.com/paper/2002.05202/) (2020)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [DeepSeek-V2: A Strong, Economical, and Efficient Mixture-of-Experts Language Model](https://mlsanity.com/paper/2405.04434/) (2024)
- [Large Language Models Cannot Self-Correct Reasoning Yet](https://mlsanity.com/paper/2310.01798/) (2023)
- [Progress measures for grokking via mechanistic interpretability](https://mlsanity.com/paper/2301.05217/) (2023)
- [Lifelong Learning with Dynamically Expandable Networks](https://mlsanity.com/paper/1708.01547/) (2017)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [The Reversal Curse: LLMs trained on "A is B" fail to learn "B is A"](https://mlsanity.com/paper/2309.12288/) (2023)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [Slimmable Neural Networks](https://mlsanity.com/paper/1812.08928/) (2018)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Primer: Searching for Efficient Transformers for Language Modeling](https://mlsanity.com/paper/2109.08668/) (2021)
- [The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks](https://mlsanity.com/paper/2306.17844/) (2023)
- [Explaining grokking through circuit efficiency](https://mlsanity.com/paper/2309.02390/) (2023)
- [Physics of Language Models: Part 2.1, Grade-School Math and the Hidden Reasoning Process](https://mlsanity.com/paper/2407.20311/) (2024)
- [On the Power of Over-parametrization in Neural Networks with Quadratic Activation](https://mlsanity.com/paper/1803.01206/) (2018)
- [Grokking modular arithmetic](https://mlsanity.com/paper/2301.02679/) (2023)
- [Learning and Leveraging World Models in Visual Representation Learning](https://mlsanity.com/paper/2403.00504/) (2024)
- [Alice in Wonderland: Simple Tasks Showing Complete Reasoning Breakdown in State-Of-the-Art Large Language Models](https://mlsanity.com/paper/2406.02061/) (2024)
- [ReLU2 Wins: Discovering Efficient Activation Functions for Sparse LLMs](https://mlsanity.com/paper/2402.03804/) (2024)
- [Splitting Steepest Descent for Growing Neural Architectures](https://mlsanity.com/paper/1910.02366/) (2019)
- [Pre-trained Large Language Models Use Fourier Features to Compute Addition](https://mlsanity.com/paper/2406.03445/) (2024)
- [Emergence of Maps in the Memories of Blind Navigation Agents](https://mlsanity.com/paper/2301.13261/) (2023)
- [Feature emergence via margin maximization: case studies in algebraic tasks](https://mlsanity.com/paper/2311.07568/) (2023)
- [Emergent Representations of Program Semantics in Language Models Trained on Programs](https://mlsanity.com/paper/2305.11169/) (2023)
- [When Can Transformers Count to n?](https://mlsanity.com/paper/2407.15160/) (2024)
- [Unified View of Grokking, Double Descent and Emergent Abilities: A Perspective from Circuits Competition](https://mlsanity.com/paper/2402.15175/) (2024)

## Built on by (most cited first, 6 of 6)

- [Provable Scaling Laws of Feature Emergence from Learning Dynamics of Grokking](https://mlsanity.com/paper/2509.21519/) (2025)
- [Unlocking Out-of-Distribution Generalization in Transformers via Recursive Latent Space Reasoning](https://mlsanity.com/paper/2510.14095/) (2025)
- [Distributional Biases in Post-Training: A Markovian Analysis of Reasoning Trajectories](https://mlsanity.com/paper/2511.07368/) (2025)
- [Neural Networks Provably Learn Spectral Representations for Group Composition](https://mlsanity.com/paper/2606.02993/) (2026)
- [Why Neural Network Can Discover Symbolic Structures with Gradient-based Training: An Algebraic and Geometric Foundation for Neurosymbolic Reasoning](https://mlsanity.com/paper/2506.21797/) (2025)
- [Assign and Add: A Mechanistic Study of Compositional Arithmetic](https://mlsanity.com/paper/2605.31497/) (2026)

## Abstract (arXiv)

We prove rich algebraic structures of the solution space for 2-layer neural networks with quadratic activation and L2 loss, trained on reasoning tasks in Abelian group (e.g., modular addition). Such a rich structure enables analytical construction of global optimal solutions from partial solutions that only satisfy part of the loss, despite its high nonlinearity. We coin the framework as CoGS (emphunderlineComposing underlineGlobal underlineSolutions). Specifically, we show that the weight space over different numbers of hidden nodes of the 2-layer network is equipped with a semi-ring algebraic structure, and the loss function to be optimized consists of sum potentials, which are ring homomorphisms, allowing partial solutions to be composed into global ones by ring addition and multiplication. Our experiments show that around 95% of the solutions obtained by gradient descent match exactly our theoretical constructions. Although the global solutions constructed only required a small number of hidden nodes, our analysis on gradient dynamics shows that overparameterization asymptotically decouples training dynamics and is beneficial. We further show that training dynamics favors simpler solutions under weight decay, and thus high-order global solutions such as perfect memorization are unfavorable. The code is open sourced at https://github.com/facebookresearch/luckmatters/tree/yuandong3/ssl/real-dataset.