Improved Tree Search for Automatic Program Synthesis

Aran Carmon, Lior Wolf
3/13/2023
cs.LGcs.PLcs.SE

No confident code implementation found for this paper. 1 possible match can be shown below.

Abstract

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. 1 weaker match is hidden by default — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Optimizing Instruction Synthesis: Effective Exploration of Evolutionary Space with Tree Search

80% match2024

LLM Tree Search

77% match2024

SRA-MCTS: Self-driven Reasoning Augmentation with Monte Carlo Tree Search for Code Generation

76% match1 repo362024

Program Synthesis with Best-First Bottom-Up Search

76% match2023

RoT: Enhancing Large Language Models with Reflection on Search Trees

76% match1 repo142024

In Search of Trees: Decision-Tree Policy Synthesis for Black-Box Systems via Search

76% match2024

Cite this paper

@article{carmon2023improved,
  title  = {Improved Tree Search for Automatic Program Synthesis},
  author = {Aran Carmon and Lior Wolf},
  year   = {2023},
  eprint = {2303.07166},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2303.07166v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2303.07166.svg)](https://codeofpaper.com/paper/2303.07166)

Discussion