# Neural Execution Engines: Learning to Execute Subroutines

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2020.

## Built on by (most cited first, 30 of 36)

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Toward Transparent AI: A Survey on Interpreting the Inner Structures of Deep Neural Networks](https://mlsanity.com/paper/2207.13243/) (2022)
- [Teaching Algorithmic Reasoning via In-context Learning](https://mlsanity.com/paper/2211.09066/) (2022)
- [The CLRS Algorithmic Reasoning Benchmark](https://mlsanity.com/paper/2205.15659/) (2022)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Softmax is not Enough (for Sharp Size Generalisation)](https://mlsanity.com/paper/2410.01104/) (2024)
- [Latent Execution for Neural Program Synthesis](https://mlsanity.com/paper/2107.00101/) (2021)
- [Code Execution with Pre-trained Language Models](https://mlsanity.com/paper/2305.05383/) (2023)
- [Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks](https://mlsanity.com/paper/2211.00692/) (2022)
- [Simulation of Graph Algorithms with Looped Transformers](https://mlsanity.com/paper/2402.01107/) (2024)
- [How to transfer algorithmic reasoning knowledge to learn new algorithms?](https://mlsanity.com/paper/2110.14056/) (2021)
- [Neural Approximation of Graph Topological Features](https://mlsanity.com/paper/2201.12032/) (2022)
- [Reducing Collision Checking for Sampling-Based Motion Planning Using Graph Neural Networks](https://mlsanity.com/paper/2210.08864/) (2022)
- [Neural Algorithmic Reasoning Without Intermediate Supervision](https://mlsanity.com/paper/2306.13411/) (2023)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [Persistent Message Passing](https://mlsanity.com/paper/2103.01043/) (2021)
- [Learnable Commutative Monoids for Graph Neural Networks](https://mlsanity.com/paper/2212.08541/) (2022)
- [Algorithmic Concept-based Explainable Reasoning](https://mlsanity.com/paper/2107.07493/) (2021)
- [On the Markov Property of Neural Algorithmic Reasoning: Analyses and Methods](https://mlsanity.com/paper/2403.04929/) (2024)
- [Discrete Neural Algorithmic Reasoning](https://mlsanity.com/paper/2402.11628/) (2024)
- [Latent Space Representations of Neural Algorithmic Reasoners](https://mlsanity.com/paper/2307.08874/) (2023)
- [Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learning](https://mlsanity.com/paper/2406.04601/) (2024)
- [Parallel Algorithms Align with Neural Execution](https://mlsanity.com/paper/2307.04049/) (2023)
- [Infusing Lattice Symmetry Priors in Attention Mechanisms for Sample-Efficient Abstract Geometric Reasoning](https://mlsanity.com/paper/2306.03175/) (2023)
- [Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encoding](https://mlsanity.com/paper/2501.00712/) (2025)
- [Gradient-Based Program Repair: Fixing Bugs in Continuous Program Spaces](https://mlsanity.com/paper/2505.17703/) (2025)
- [Tackling Size Generalization of Graph Neural Networks on Biological Data from a Spectral Perspective](https://mlsanity.com/paper/2305.15611/) (2023)
- [SURGE: On the Potential of Large Language Models as General-Purpose Surrogate Code Executors](https://mlsanity.com/paper/2502.11167/) (2025)

## Abstract (arXiv)

A significant effort has been made to train neural networks that replicate algorithmic reasoning, but they often fail to learn the abstract concepts underlying these algorithms. This is evidenced by their inability to generalize to data distributions that are outside of their restricted training sets, namely larger inputs and unseen data. We study these generalization issues at the level of numerical subroutines that comprise common algorithms like sorting, shortest paths, and minimum spanning trees. First, we observe that transformer-based sequence-to-sequence models can learn subroutines like sorting a list of numbers, but their performance rapidly degrades as the length of lists grows beyond those found in the training set. We demonstrate that this is due to attention weights that lose fidelity with longer sequences, particularly when the input numbers are numerically similar. To address the issue, we propose a learned conditional masking mechanism, which enables the model to strongly generalize far outside of its training range with near-perfect accuracy on a variety of algorithms. Second, to generalize to unseen data, we show that encoding numbers with a binary representation leads to embeddings with rich structure once trained on downstream tasks like addition or multiplication. This allows the embedding to handle missing data by faithfully interpolating numbers not seen during training.