# Improved Tree Search for Automatic Program Synthesis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 13 references that are in the map.
- First posted on arXiv 13 Mar 2023.

## Builds on (most cited first, 6 of 6)

- [DeepCoder: Learning to Write Programs](https://mlsanity.com/paper/1611.01989/) (2016)
- [Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis](https://mlsanity.com/paper/1805.04276/) (2018)
- [Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples](https://mlsanity.com/paper/1804.01186/) (2018)
- [Automatic Program Synthesis of Long Programs with a Learned Garbage Collector](https://mlsanity.com/paper/1809.04682/) (2018)
- [Neural Program Meta-Induction](https://mlsanity.com/paper/1710.04157/) (2017)
- [Solving the Rubik's Cube Without Human Knowledge](https://mlsanity.com/paper/1805.07470/) (2018)

## Abstract (arXiv)

In the task of automatic program synthesis, one obtains pairs of matching inputs and outputs and generates a computer program, in a particular domain-specific language (DSL), which given each sample input returns the matching output. A key element is being able to perform an efficient search in the space of valid programs. Here, we suggest a variant of MCTS that leads to state of the art results on two vastly different DSLs. The exploration method we propose includes multiple contributions: a modified visit count, a preprocessing procedure for the training dataset, and encoding the part of the program that was already executed.