# Learning Compositional Neural Programs with Recursive Tree Search and Planning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2019.

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

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Modular Deep Learning](https://mlsanity.com/paper/2302.11529/) (2023)
- [Evolving Reinforcement Learning Algorithms](https://mlsanity.com/paper/2101.03958/) (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 Relational Inference with Fast Modular Meta-learning](https://mlsanity.com/paper/2310.07015/) (2023)
- [Synthesizing explainable counterfactual policies for algorithmic recourse with program synthesis](https://mlsanity.com/paper/2201.07135/) (2022)
- [Hierarchical Neural Program Synthesis](https://mlsanity.com/paper/2303.06018/) (2023)
- [Hierarchies of Reward Machines](https://mlsanity.com/paper/2205.15752/) (2022)
- [Learning compositional programs with arguments and sampling](https://mlsanity.com/paper/2109.00619/) (2021)
- [Beyond Fixed Tasks: Unsupervised Environment Design for Task-Level Pairs](https://mlsanity.com/paper/2511.12706/) (2025)
- [Optimizing Large Language Models to Expedite the Development of Smart Contracts](https://mlsanity.com/paper/2310.05178/) (2023)
- [Consistency of Compositional Generalization across Multiple Levels](https://mlsanity.com/paper/2412.13636/) (2024)
- [Training Transformers as a Universal Computer](https://mlsanity.com/paper/2604.25166/) (2026)
- [Understanding in Artificial Intelligence](https://mlsanity.com/paper/2101.06573/) (2021)
- [Stochastic Code Generation](https://mlsanity.com/paper/2304.08243/) (2023)
- [Artificial Neuropsychology: Are Large Language Models Developing Executive Functions?](https://mlsanity.com/paper/2305.04134/) (2023)

## Abstract (arXiv)

We propose a novel reinforcement learning algorithm, AlphaNPI, that incorporates the strengths of Neural Programmer-Interpreters (NPI) and AlphaZero. NPI contributes structural biases in the form of modularity, hierarchy and recursion, which are helpful to reduce sample complexity, improve generalization and increase interpretability. AlphaZero contributes powerful neural network guided search algorithms, which we augment with recursion. AlphaNPI only assumes a hierarchical program specification with sparse rewards: 1 when the program execution satisfies the specification, and 0 otherwise. Using this specification, AlphaNPI is able to train NPI models effectively with RL for the first time, completely eliminating the need for strong supervision in the form of execution traces. The experiments show that AlphaNPI can sort as well as previous strongly supervised NPI variants. The AlphaNPI agent is also trained on a Tower of Hanoi puzzle with two disks and is shown to generalize to puzzles with an arbitrary number of disk