EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis
This work addresses the efficiency of program synthesis for developers and researchers, offering incremental improvements in search algorithms.
The paper tackles the problem of combinatorial search blowup in program synthesis by introducing EcoSearch, a constant-delay best-first search algorithm that ensures compute time between outputting programs does not increase over time, resulting in speedups over predecessors in two classic domains.
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 EcoSearch, 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 EcoSearch outperforms its predecessors on two classic domains.