BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration

By Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton. 2020

61 citations recorded by the source corpus.

Program synthesis is challenging largely because of the difficulty of search in a large space of programs. Human programmers routinely tackle the task of writing complex programs by writing sub-programs and then analysing their intermediate results to compose them in appropriate ways. Motivated by this intuition, we present a new synthesis approach that leverages learning to guide a bottom-up search over programs. In particular, we train a model to prioritize compositions of intermediate values during search conditioned on a given set of input-output examples. This is a powerful combination because of several emergent properties: First, in bottom-up search, intermediate programs can be executed, providing semantic information to the neural network. Second, given the concrete values from those executions, we can exploit rich features based on recent work on property signatures. Finally, bottom-up search allows the system substantial flexibility in what order to generate the solution, allowing the synthesizer to build up a program from multiple smaller sub-programs. Overall, our empirical evaluation finds that the combination of learning and bottom-up search is remarkably effective, even with simple supervised learning approaches. We demonstrate the effectiveness of our technique on a new data set for synthesis of string transformation programs.

Subfields: Hardware and Architecture, Information Systems, Software, Prompting & Reasoning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Hardware and Architecture

In Information Systems

In Software

In Prompting & Reasoning

Citations in the corpus

Reasoning Like Program Executors (2022, background): “Other lines of research leverage program execution in inference as a reliable sanity guarantee for generated programs by pruning non-executable candidates (Wang et al., 2018b; Chen et al., 2019b, 2021; Odena et al., 2020; Ellis et al., 2019; Chen et al., 2019b; Sun et al., 2018; Zohar and Wolf, 2018”
Program Synthesis with Large Language Models (2021, methodology): “…in techniques (both symbolic and ‘neuro-symbolic’) for synthesizing programs [Balog et al., 2017, Devlin et al., 2017, Ellis et al., 2018, 2020, Odena et al., 2020], but these techniques have largely been applied to restricted domain-specific languages (DSLs) [Gulwani, 2011] or to languages…”
Large Language Models Are Zero-Shot Fuzzers: Fuzzing Deep-Learning Libraries via Large Language Models (2022, background): “Traditional program synthesis techniques [50, 53, 63] typically restrict themselves to a small set of functionalities in the language and cannot deal with a large number of library APIs, each with their own specific input and output parameters and types.”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, methodology): “Our executionguided reasoning framework is related to the line of research on execution-guided program synthesis (Odena et al., 2020; Chen et al., 2019a; Wang et al., 2018; Nye et al., 2020a).”
Parsel: A Unified Natural Language Framework for Algorithmic Reasoning (2022, methodology): “Finally, we hope that it would be possible to use Parsel as a framework for bootstrapping increasingly complex program generation (e.g. Anthony et al. (2017); Zelikman et al. (2022); Odena et al. (2020)).”
SmBoP: Semi-autoregressive Bottom-up Semantic Parsing (2020, background): “Bottom-up decoding in semantic parsing has received little attention (Cheng et al., 2019; Odena et al., 2020).”
Value-Agnostic Conversational Semantic Parsing (2021, methodology): “Finally, bottom-up models with similarities to ours include SMBOP (Rubin and Berant, 2020) and BUSTLE (Odena et al., 2020).”
SpreadsheetCoder: Formula Prediction from Semi-structured Context (2021, unknown): “A recent work proposes neural-guided bottom-up search for program synthesis from input-output examples, and they extend the domain-speciﬁc language of FlashFill to support more spreadsheet programs (Odena et al., 2020).”