Eco Search: A No-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 no-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 classical domains.
BibTeX
@article{Matricon_Fijalkow_Lagarde_2025, title={Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34139}, DOI={10.1609/aaai.v39i18.34139}, abstractNote={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 no-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 classical domains.}, number={18}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Matricon, Théo and Fijalkow, Nathanaël and Lagarde, Guillaume}, year={2025}, month={Apr.}, pages={19432-19439} }