# Making Neural Programming Architectures Generalize via Recursion

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

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2017.

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

- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Measuring Coding Challenge Competence With APPS](https://mlsanity.com/paper/2105.09938/) (2021)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [WizardMath: Empowering Mathematical Reasoning for Large Language Models via Reinforced Evol-Instruct](https://mlsanity.com/paper/2308.09583/) (2023)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [Scalable agent alignment via reward modeling: a research direction](https://mlsanity.com/paper/1811.07871/) (2018)
- [Teaching Arithmetic to Small Transformers](https://mlsanity.com/paper/2307.03381/) (2023)
- [Beyond A*: Better Planning with Transformers via Search Dynamics Bootstrapping](https://mlsanity.com/paper/2402.14083/) (2024)
- [Neural Production Systems: Learning Rule-Governed Visual Dynamics](https://mlsanity.com/paper/2103.01937/) (2021)
- [Large Language Models can Learn Rules](https://mlsanity.com/paper/2310.07064/) (2023)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Learning Transformer Programs](https://mlsanity.com/paper/2306.01128/) (2023)
- [Learning Iterative Reasoning through Energy Diffusion](https://mlsanity.com/paper/2406.11179/) (2024)
- [Towards Data-and Knowledge-Driven Artificial Intelligence: A Survey on Neuro-Symbolic Computing](https://mlsanity.com/paper/2210.15889/) (2022)
- [Learning Iterative Reasoning through Energy Minimization](https://mlsanity.com/paper/2206.15448/) (2022)
- [Pointer Value Retrieval: A new benchmark for understanding the limits of neural network generalization](https://mlsanity.com/paper/2107.12580/) (2021)
- [How to Reuse and Compose Knowledge for a Lifetime of Tasks: A Survey on Continual Learning and Functional Composition](https://mlsanity.com/paper/2207.07730/) (2022)
- [Recursion of Thought: A Divide-and-Conquer Approach to Multi-Context Reasoning with Language Models](https://mlsanity.com/paper/2306.06891/) (2023)
- [Neural-guided, Bidirectional Program Search for Abstraction and Reasoning](https://mlsanity.com/paper/2110.11536/) (2021)
- [Pushing the Limits of Rule Reasoning in Transformers through Natural Language Satisfiability](https://mlsanity.com/paper/2112.09054/) (2021)
- [Recursive Algorithmic Reasoning](https://mlsanity.com/paper/2307.00337/) (2023)
- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [Hierarchical Neural Program Synthesis](https://mlsanity.com/paper/2303.06018/) (2023)
- [Neural Sequence-to-grid Module for Learning Symbolic Rules](https://mlsanity.com/paper/2101.04921/) (2021)
- [Evolutionary Training and Abstraction Yields Algorithmic Generalization of Neural Computers](https://mlsanity.com/paper/2105.07957/) (2021)
- [Gradient-Based Program Synthesis with Neurally Interpreted Languages](https://mlsanity.com/paper/2604.18907/) (2026)
- [Synthesizing Programs with Continuous Optimization](https://mlsanity.com/paper/2211.00828/) (2022)
- [State-Space Constraints Can Improve the Generalisation of the Differentiable Neural Computer to Input Sequences With Unseen Length](https://mlsanity.com/paper/2110.09138/) (2021)
- [Neuro-Symbolic Sudoku Solver](https://mlsanity.com/paper/2307.00653/) (2023)
- [Training Transformers as a Universal Computer](https://mlsanity.com/paper/2604.25166/) (2026)

## Abstract (arXiv)

Empirically, neural networks that attempt to learn programs from data have exhibited poor generalizability. Moreover, it has traditionally been difficult to reason about the behavior of these models beyond a certain level of input complexity. In order to address these issues, we propose augmenting neural architectures with a key abstraction: recursion. As an application, we implement recursion in the Neural Programmer-Interpreter framework on four tasks: grade-school addition, bubble sort, topological sort, and quicksort. We demonstrate superior generalizability and interpretability with small amounts of training data. Recursion divides the problem into smaller pieces and drastically reduces the domain of each neural network component, making it tractable to prove guarantees about the overall system's behavior. Our experience suggests that in order for neural architectures to robustly learn program semantics, it is necessary to incorporate a concept like recursion.