Eco Search : A Constant-Delay Best-First Search Algorithm for Program Synthesis

Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde · 2024

Read Eco Search : A Constant-Delay Best-First Search Algorithm for Program Synthesis by Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17330.txt.

Introduction

Théo Matricon, Nathanaël Fijalkow, and Guillaume Lagarde present EcoSearch, a program synthesis search that never makes you wait longer between answers, in this 2024 arXiv paper. Synthesis tools hunt huge spaces of programs for one that fits a spec, guided by a cost score that ranks promising programs first. Best-first search follows that ranking exactly, yet older versions stall longer and longer as the search deepens.

EcoSearch is the first such algorithm with a constant gap between successive outputs, whatever the cost function was fixed in advance. That steadiness turns into real speed. On two classic test domains it beat its predecessors. The authors frame the result as removing a hidden tax on guided program search.

Catalog record

CREATORThéo Matricon, Nathanaël Fijalkow, Guillaume Lagarde
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE57 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17330

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Eco Search : A Constant-Delay Best-First Search Algorithm for Program Synthesis Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde Abstract Many approaches to program synthesis perform a combinatorial search within a large space of programs to find one that satisfies a given specification. To tame the search space blowup, previous works introduced probabilistic and neural approaches to guide this combinatorial search by inducing heuristic cost functions. Best-first search algorithms ensure to search in the exact order induced by the cost function, significantly reducing the portion of the program space to be explored. We present a new best-first search algorithm called Eco Search , which is the first constant-delay algorithm for pre-generation cost function: the amount of compute required between outputting two programs is constant, and in particular does not increase over time. This key property yields important speedups: we observe that Eco Search outperforms its predecessors on two classic domains. 1 Introduction Program synthesis is one of the oldest dream of Artificial Intelligence: it automates problem solving by generating a program meeting a given specification Manna and Waldinger 1971 , Gulwani et al. 2017 . A very classical scenario for user-based program synthesis, known as programming by example (PBE), uses input output examples as specification. For PBE, combinatorial search for program synthesis has been an especially popular technique Alur et al. 2017 , Balog et al. 2017 , Alur et al. 2018 , Shi et al. 2019 , Barke et al. 2020 , Zohar and Wolf 2018 , Ellis et al. 2021 , Odena et al. 2021 , Fijalkow et al. 2022 , Shi et al. 2022a , Shi et al. 2022b , Ameen and Lelis 2023 . To scale combinatorial search for program synthesis, many approaches rely on defining a heuristic cost function assigning to every program a numerical value, such that the programs with least scores are the most likely to satisfy the specification. For example, DeepCoder Balog et al. 2017 and TF-Coder Shi et al. 2022a use neural models, while Bustle Odena et al. 2021 leverages probabilistic methods for defining a heuristic cost function. Very recently, LLMs have been used for guiding combinatorial search Li et al. 2024 , Li and Ellis 2024 . Best-first search algorithms explore the space in the exact order induced by the cost function: this significantly reduces the portion of the program space to be explored. Since Euphony Alur et al. 2017 ’s use of A^{*} algorithm, several best-first search algorithms have been constructed Shi et al. 2022a , Ellis et al. 2021 , Fijalkow et al. 2022 , Ameen and Lelis 2023 . The major issue of best-first search algorithms is that they slow down over time . This is because in order to ensure optimality they need to consider a growing frontier of potentially next-to-be-generated programs in their data structures, which quickly become enormous. The notion of delay captures this behaviour: it quantifies the amount of compute required between outputting two programs. The first best-first search algorithm had linear delay Alur et al. 2017 , and the state of the art algorithms achieve logarithmic delay Fijalkow et al. 2022 , Ameen and Lelis 2023 : the compute required between outputting the t th and the (t+1) th program is bounded by O(\log(t)) . The fundamental question explored in this paper is whether there exist best-first search algorithms with constant delay . We answer this question positively by constructing the first constant-delay best-first search algorithm called Eco Search for pre-generation cost function. Importantly, Eco Search performs a bottom-up search , which implies that it can take advantage of classical observational equivalence techniques. Technically, Eco Search relies on the “cost tuple representation” introduced in Ameen and Lelis 2023 . A key novelty of Eco Search is a new frugal expansion built on top of the one introduced in that paper, which ensures that it only considers programs when they need to be evaluated. Combined with novel data structures it enables Eco Search to achieve constant delay. We demonstrate the effectiveness of Eco Search in two classic domains: the DeepCoder Balog et al. 2017 domain of integer list manipulations and in the FlashFill Gulwani 2011 domain of string manipulations. In our experiments, Eco Search solves twice as many tasks in the same amount of time than previous methods. To summarize, our contributions are the following: • We introduce Eco Search , a new best-first bottom-up search algorithm; • Through a theoretical analysis we show that Eco Search has constant delay; • Experimentally, we observe that Eco Search provides significant improvements over existing algorithms. 2 Background 2.1 Cost-guided combinatorial search We consider a set P of elements, which for our applications in program synthesis is the class of all programs. Given a specification \varphi we write p\models\varphi when the program p satisfies the specification \varphi : we say that p is a solution program. Note that this definition is independent of the type of specification: a logical formula, a set of input output examples, or any other type of specifications discriminating between solutions and not solutions. The goal of combinatorial search for program synthesis is given a specification \varphi to find a solution program. Sometimes it is useful to find more than one solution program, or even all of them; in this paper we focus on finding a single one, but the algorithms naturally extend to finding a finite number of solution programs. In cost-guided combinatorial search , we further assume a cost function w:P\to\mathbb{R}_{>0} , mapping each program to a (positive) cost. The cost function w is used as a heuristic: the smaller the cost of a program, the more likely it is to be a solution program. In this context, best-first search algorithms enumerate programs by increasing costs. 2.2 Domain-specific languages and context-free grammars Let us now be more specific about how programs are represented. A domain-specific language (DSL) is a programming language designed to solve a specific set of tasks. Classically, we represent DSLs using context-free grammars (CFGs), and more precisely deterministic tree grammars. We let \Sigma denote the set of primitive symbols, which include variables. Each symbol has a fixed arity (variables and constants have arity 0 ). The set of non-terminal symbols is \Gamma , and S\in\Gamma is the initial non-terminal. Derivation rules have the following syntax: X\rightarrow f(X_{1},\dots,X_{k}), where f\in\Sigma has arity k and X,X_{1},\dots,X_{k}\in\Gamma . The CFG is deterministic if given X and f , there is a unique derivation rule from X with f . A grammar acts as a generator: it generates trees, which we call programs. r_{1} : str \rightarrow “Hello” cost: 1.1 r_{2} : str \rightarrow “World” cost: 2.0 r_{3} : str \rightarrow cast ( int ) cost: 4.4 r_{4} : str \rightarrow concat ( str , str ) cost: 5.3 r_{5} : int \rightarrow var cost: 1.8 r_{6} : int \rightarrow 1 cost: 3.3 r_{7} : int \rightarrow add ( int , int ) cost: 5.3 Figure 1 : A simple DSL. To make things concrete, let us consider a small example. Our DSL manipulates strings and integers, hence it uses two types: string and int . It has three primitives: cast: int -> string concat: string -> string -> string add: int ->

Read the complete text