# Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 46 references that are in the map.
- First posted on arXiv 24 Feb 2025.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Simple and Scalable Predictive Uncertainty Estimation using Deep Ensembles](https://mlsanity.com/paper/1612.01474/) (2016)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Averaging Weights Leads to Wider Optima and Better Generalization](https://mlsanity.com/paper/1803.05407/) (2018)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets](https://mlsanity.com/paper/2201.02177/) (2022)
- [Analysing Mathematical Reasoning Abilities of Neural Models](https://mlsanity.com/paper/1904.01557/) (2019)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [From Explicit CoT to Implicit CoT: Learning to Internalize CoT Step by Step](https://mlsanity.com/paper/2405.14838/) (2024)
- [Implicit Chain of Thought Reasoning via Knowledge Distillation](https://mlsanity.com/paper/2311.01460/) (2023)
- [Neural Tangents: Fast and Easy Infinite Neural Networks in Python](https://mlsanity.com/paper/1912.02803/) (2019)
- [Looped Transformers are Better at Learning Learning Algorithms](https://mlsanity.com/paper/2311.12424/) (2023)
- [Tensor Programs II: Neural Tangent Kernel for Any Architecture](https://mlsanity.com/paper/2006.14548/) (2020)
- [Investigating the Limitations of Transformers with Simple Arithmetic Tasks](https://mlsanity.com/paper/2102.13019/) (2021)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Randomized Positional Encodings Boost Length Generalization of Transformers](https://mlsanity.com/paper/2305.16843/) (2023)
- [Learning to Execute](https://mlsanity.com/paper/1410.4615/) (2014)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [Transformers Can Achieve Length Generalization But Not Robustly](https://mlsanity.com/paper/2402.09371/) (2024)
- [Transformers Can Do Arithmetic with the Right Embeddings](https://mlsanity.com/paper/2405.17399/) (2024)
- [Neural Arithmetic Logic Units](https://mlsanity.com/paper/1808.00508/) (2018)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)
- [Length Generalization in Arithmetic Transformers](https://mlsanity.com/paper/2306.15400/) (2023)
- [Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics](https://mlsanity.com/paper/2105.03703/) (2021)
- [Neural Programmer: Inducing Latent Programs with Gradient Descent](https://mlsanity.com/paper/1511.04834/) (2015)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [Neural Arithmetic Units](https://mlsanity.com/paper/2001.05016/) (2020)
- [When can transformers reason with abstract symbols?](https://mlsanity.com/paper/2310.09753/) (2023)

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

- [The Impossibility of Inverse Permutation Learning in Transformer Models](https://mlsanity.com/paper/2509.24125/) (2025)
- [On the Mirage of Long-Range Dependency, with an Application to Integer Multiplication](https://mlsanity.com/paper/2603.29069/) (2026)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization](https://mlsanity.com/paper/2605.22964/) (2026)

## Abstract (arXiv)

Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operations lie at the heart of algorithmic tasks such as arithmetic, which is often used as a test bed for algorithmic execution in neural networks. In this work, we ask: can neural networks learn to execute binary-encoded algorithmic instructions exactly? We use the Neural Tangent Kernel (NTK) framework to study the training dynamics of two-layer fully connected networks in the infinite-width limit and show how a sufficiently large ensemble of such models can be trained to execute exactly, with high probability, four fundamental tasks: binary permutations, binary addition, binary multiplication, and Subtract and Branch if Negative (SBN) instructions. Since SBN is Turing-complete, our framework extends to computable functions. We show how this can be efficiently achieved using only logarithmically many training data. Our approach relies on two techniques: structuring the training data to isolate bit-level rules, and controlling correlations in the NTK regime to align model predictions with the target algorithmic executions.