EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916538976567296 |
|---|---|
| author | Matricon, Théo Fijalkow, Nathanaël Lagarde, Guillaume |
| author_facet | Matricon, Théo Fijalkow, Nathanaël Lagarde, Guillaume |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17330 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis Matricon, Théo Fijalkow, Nathanaël Lagarde, Guillaume Machine Learning Artificial Intelligence Programming Languages 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. |
| title | EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis |
| topic | Machine Learning Artificial Intelligence Programming Languages |
| url | https://arxiv.org/abs/2412.17330 |