Reproduce “EcoSearch: A Constant-Delay Best-First Search Algorithm for Program Synthesis” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Théo Matricon, Nathanaël Fijalkow, Guillaume Lagarde
Eco Search is the first best-first search algorithm demonstrated to achieve constant delay for program synthesis using pre-generation cost functions. It empirically outperforms prior state-of-the-art methods, solving approximately 30% more tasks overall and achieving the same task completion rate in about 66% of the time required by previous algorithms on benchmarks like DeepCoder and FlashFill.
Key insights
- For pre-generation cost functions, the cost difference between any program and its immediate successor is bounded by a constant, allowing for efficient cost management.
- At any given time, the costs of all programs awaiting generation in any non-terminal's queue are bounded within a constant range, enabling the use of constant-time 'bucket queues'.
- The 'frugal expansion' component, even without bucketing, offers significant performance improvements over prior algorithms by reducing computational overhead and memory usage.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.