Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Artur Back de Luca, George GiapitzakisKimon FountoulakisUniversity of Waterloo { abackdel , ggiapitz , kimon.fountoulakis }@uwaterloo.ca · 2025
Read Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks by Artur Back de Luca, George GiapitzakisKimon FountoulakisUniversity of Waterloo { abackdel , ggiapitz , kimon.fountoulakis }@uwaterloo.ca (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16763.txt.
Introduction
Artur Back de Luca, George Giapitzakis, and Kimon Fountoulakis ask whether neural networks can learn exact algorithms in a 2025 paper. Networks excel at smooth approximation but often fail to generalize perfectly on discrete tasks such as arithmetic. The authors study two layer networks in a wide network limit, using a kernel framework that describes their training.
They show a large enough ensemble of such networks can be trained to execute four tasks exactly, with high probability: permuting bits, binary addition, binary multiplication, and a simple branch instruction. That last instruction is Turing complete, so the result extends in principle to any computable function. Only logarithmically many training examples are needed, thanks to data structuring and correlation control.
Catalog record
| CREATOR | Artur Back de Luca, George GiapitzakisKimon FountoulakisUniversity of Waterloo { abackdel , ggiapitz , kimon.fountoulakis }@uwaterloo.ca |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 116 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-16763
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks Artur Back de Luca, George GiapitzakisKimon FountoulakisUniversity of Waterloo { abackdel , ggiapitz , kimon.fountoulakis }@uwaterloo.ca Abstract 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. * * footnotetext: Equal contribution. 1 Introduction There has been growing interest in the computational capabilities and efficiency of neural networks both from a theoretical and empirical perspective Giannou et al. 2023 ; Kaiser and Sutskever 2016 ; McLeish et al. 2024 ; Pérez et al. 2021 ; Saxton et al. 2019 ; Siegelmann and Sontag 1995 . Most works have either demonstrated the expressive power of different architectures through simulation results or learnability from a probably approximately correct (PAC) viewpoint. While important, the mere existence of parameter configurations that realize a specific computation or a generalization bound does not offer insight into the ability to learn to execute an algorithm through gradient-based training. In fact, simulating algorithmic instructions with neural networks often involves approximating discontinuous functions that gradient descent is difficult to converge to with standard training datasets ( Back De Luca and Fountoulakis 2024 ) . By modeling training with the Neural Tangent Kernel (NTK), we prove that two-layer fully connected networks in the infinite-width limit can learn to execute binary permutations , binary addition , binary multiplication , and SBN instructions with a logarithmic number of examples. Rather than training on traditional input-output pairs, we exploit the locality of these algorithms by casting each step as a set of templates. We show that training with these local templates is sufficient for full algorithmic execution. To our knowledge, this is the first NTK-based proof of exact learnability for these tasks. A high-level overview of our approach is shown in Figure 1 . Contributions. Our approach is built on two key innovations that overcome the interference and ambiguity in training data that can usually create problems for neural learning for discrete tasks: 1. Algorithmic template representation: We demonstrate how to design training data that represent local computations (i.e., operating only on a subset of bits) that can be composed to execute complete algorithms. Each algorithmic instruction is represented by “templates” and entire algorithms (e.g., binary permutations, binary addition, binary multiplication, and SBN instruction execution) can be executed by iteratively matching these templates. The total number of templates is logarithmic in the number of all possible inputs. 2. Provable exact learnability: We prove that, by training on an orthonormalized version of our templates, we can control unwanted correlations in the NTK regime and show that an ensemble of two-layer fully connected networks in the infinite-width limit can learn to execute algorithmic instructions exactly with high probability. Figure 1 : Simplified illustration of the framework used in our analysis. The left panel shows an example algorithm (binary addition) where each function, highlighted in blue and red, is translated into binary training instructions shown in the central panel with matching colors. Each instruction specifies a condition over part of the current algorithm state and maps it to a corresponding output. Instructions are grouped into blocks, indicated by boxed column labels in \mathcal{X} and \mathcal{Y} , each representing a subset of the input state. For binary addition, some blocks represent segments of the summands, while others reflect the carry state. For the applications discussed in Section 6 , this block structure allows the number of instructions in \mathcal{X} and \mathcal{Y} to scale linearly with bit length \ell . The right-most panel shows how instructions are used within an iterative framework to update the state vector \hat{\bm{x}}_{i} , which serves as input to the neural network at the i -th step. The state is first encoded, as described in Section 5 , before being passed to the model. In the NTK regime, we show that the network performs template matching against training samples to execute the appropriate instructions. As \hat{\bm{x}}_{i} evolves, it activates new templates, progressing through the algorithm. Predictions are rounded at each step to mitigate noise, and repeating this process reproduces the algorithm’s full execution. 2 Literature review The NTK framework ( Jacot et al. 2018 ) provides insight into continuous-time gradient descent (gradient flow) in fully connected feed-forward neural networks. It has been extended to discrete gradient descent ( Lee et al. 2019 ) and generalized to other architectures like recurrent neural networks (RNNs) and Transformers Yang 2020 ; Yang and Littwin 2021 . Although NTK theory has been widely developed, few works offer task-specific guarantees. Notable examples include Boix-Adserà et al. 2024 , which proves that Transformers can generalize to unseen symbols for a class of pattern-matching language tasks. Our work addresses a different setting: we show that shallow feed-forward neural networks in the infinite-width limit trained by gradient descent can learn to exactly execute algorithmic instructions using a logarithmic number of examples. Complementing NTK-based results, other studies have demonstrated the expressive power of neural architectures by simulating algorithmic tasks. Following this approach, Siegelmann and Sontag 1995 proves that RNNs are Turing-complete, and Hertrich and Skutella 2023 demonstrates that RNNs can solve the shortest path problem and approximate solutions to the knapsack problem. Similarly, simulation results on Transformers also establish Turing completeness ( Pérez et al. 2021 ; Wei et al. 2022a ) and present constructive solutions that generalize across input lengths for arithmetic tasks Cho et al. 2025 , linear algebra ( Giannou et al. 2023 ; Yang et al. 2024 ) , graph-related problems ( Back De Luca and Fountoulakis 2024 ) , and parallel computation ( Back de Luca et al. 2025 ) . However, these results rely on hand-crafted parameter settings without training, and therefore do not address the core issue of exact learnability examined in this work. Learning to execute algorithms has been the focus of numerous empirical studies. These works explore architectural modifications and prompting techniques, particularly aimed at improving generalization in arithmetic tasks Deng et al. 2024 ; Deng et al. 2025 ; Jelassi et al. 2023 ; McLeish et al. 2024 ; Mistry et al. 2022 ; Neelakantan et al. 2016 ; Nogueira et al. 2021 ; Power et al. 2022 ; Reed and de Freitas 2016 ; Saxton et al. 2019 ; Wang et