# Hierarchical Neural Program Synthesis

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 53 references that are in the map.
- First posted on arXiv 9 Mar 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Programmatically Interpretable Reinforcement Learning](https://mlsanity.com/paper/1804.02477/) (2018)
- [DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning](https://mlsanity.com/paper/2006.08381/) (2020)
- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [RobustFill: Neural Program Learning under Noisy I/O](https://mlsanity.com/paper/1703.07469/) (2017)
- [Neural GPUs Learn Algorithms](https://mlsanity.com/paper/1511.08228/) (2015)
- [Neural Programmer-Interpreters](https://mlsanity.com/paper/1511.06279/) (2015)
- [NL2Bash: A Corpus and Semantic Parser for Natural Language Interface to the Linux Operating System](https://mlsanity.com/paper/1802.08979/) (2018)
- [Write, Execute, Assess: Program Synthesis with a REPL](https://mlsanity.com/paper/1906.04604/) (2019)
- [Neuro-Symbolic Program Synthesis](https://mlsanity.com/paper/1611.01855/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Neural Task Programming: Learning to Generalize Across Hierarchical Tasks](https://mlsanity.com/paper/1710.01813/) (2017)
- [Learning to Synthesize Programs as Interpretable and Generalizable Policies](https://mlsanity.com/paper/2108.13643/) (2021)
- [Making Neural Programming Architectures Generalize via Recursion](https://mlsanity.com/paper/1704.06611/) (2017)
- [Neural Programmer: Inducing Latent Programs with Gradient Descent](https://mlsanity.com/paper/1511.04834/) (2015)
- [Programming with a Differentiable Forth Interpreter](https://mlsanity.com/paper/1605.06640/) (2016)
- [Differentiable Programs with Neural Libraries](https://mlsanity.com/paper/1611.02109/) (2016)
- [Few-Shot Bayesian Imitation Learning with Logical Program Policies](https://mlsanity.com/paper/1904.06317/) (2019)
- [BUSTLE: Bottom-Up Program Synthesis Through Learning-Guided Exploration](https://mlsanity.com/paper/2007.14381/) (2020)
- [Neural Program Synthesis with Priority Queue Training](https://mlsanity.com/paper/1801.03526/) (2018)
- [Neural Program Meta-Induction](https://mlsanity.com/paper/1710.04157/) (2017)
- [Beyond imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs](https://mlsanity.com/paper/1812.02788/) (2018)
- [Hierarchical Programmatic Reinforcement Learning via Learning to Compose Programs](https://mlsanity.com/paper/2301.12950/) (2023)
- [Latent Programmer: Discrete Latent Codes for Program Synthesis](https://mlsanity.com/paper/2012.00377/) (2020)
- [Learning Compositional Neural Programs with Recursive Tree Search and Planning](https://mlsanity.com/paper/1905.12941/) (2019)
- [Learning Simple Algorithms from Examples](https://mlsanity.com/paper/1511.07275/) (2015)
- [From explanation to synthesis: Compositional program induction for learning from demonstration](https://mlsanity.com/paper/1902.10657/) (2019)
- [Compositional Generalization and Decomposition in Neural Program Synthesis](https://mlsanity.com/paper/2204.03758/) (2022)

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

- [Outline, Then Details: Syntactically Guided Coarse-To-Fine Code Generation](https://mlsanity.com/paper/2305.00909/) (2023)
- [ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis](https://mlsanity.com/paper/2307.13883/) (2023)
- [HumanEval on Latest GPT Models -- 2024](https://mlsanity.com/paper/2402.14852/) (2024)
- [From Frege to chatGPT: Compositionality in language, cognition, and deep neural networks](https://mlsanity.com/paper/2405.15164/) (2024)
- [Spatial-Agent: Agentic Geo-spatial Reasoning with Scientific Core Concepts](https://mlsanity.com/paper/2601.16965/) (2026)
- [AbstractBeam: Enhancing Bottom-Up Program Synthesis using Library Learning](https://mlsanity.com/paper/2405.17514/) (2024)
- [Program Machine Policy: Addressing Long-Horizon Tasks by Integrating Program Synthesis and State Machines](https://mlsanity.com/paper/2311.15960/) (2023)

## Abstract (arXiv)

Program synthesis aims to automatically construct human-readable programs that satisfy given task specifications, such as input/output pairs or demonstrations. Recent works have demonstrated encouraging results in a variety of domains, such as string transformation, tensor manipulation, and describing behaviors of embodied agents. Most existing program synthesis methods are designed to synthesize programs from scratch, generating a program token by token, line by line. This fundamentally prevents these methods from scaling up to synthesize programs that are longer or more complex. In this work, we present a scalable program synthesis framework that instead synthesizes a program by hierarchically composing programs. Specifically, we first learn a task embedding space and a program decoder that can decode a task embedding into a program. Then, we train a high-level module to comprehend the task specification (e.g., input/output pairs or demonstrations) from long programs and produce a sequence of task embeddings, which are then decoded by the program decoder and composed to yield the synthesized program. We extensively evaluate our proposed framework in a string transformation domain with input/output pairs. The experimental results demonstrate that the proposed framework can synthesize programs that are significantly longer and more complex than the programs considered in prior program synthesis works. Website at https://thoughtp0lice.github.io/hnps_web/