Research map / Learning theory and algorithms / Combinatorial and search optimization
Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Eco Search, a best-first bottom-up program synthesis algorithm with constant delay between outputs for pre-generation cost functions, built on Bee Search and Heap Search ideas.
Problem
Best-first enumerative program synthesis slows down over time because the delay between outputting successive programs grows (logarithmically in state-of-the-art methods), limiting scalability of cost-guided combinatorial search.
Approach
Combines Bee Search's cost tuple representation with per-non-terminal data structures and a frugal expansion, then uses bucket queues exploiting the bounded spread of queue costs so each output takes constant compute time with integer costs.
Key results
- Eco Search solves the same number of tasks as Bee Search in slightly more than half the time on string manipulation and 78% of the time on integer lists, solving at least 20 new tasks.
- Eco Search outperforms all others, solving 13 more tasks than Bee Search on integer lists and 20 more than its non-bucketed variant.
- Heap Search is far outperformed; Eco Search reaches the same score in 14% of Heap Search's time on string manipulation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Eco Search instead of Heap Search | Best-first program synthesis search · FlashFill SyGuS tasks | time to solve the same number of tasks: 14% of the time | Helped |
| use Eco Search instead of Bee Search | Best-first program synthesis search · FlashFill SyGuS tasks | time to solve the same number of tasks: slightly more than half the time | Helped |
| use Eco Search instead of Bee Search | Best-first program synthesis search · DeepCoder integer list tasks | time to solve the same number of tasks: 78% of the time | Helped |
| add bucketing (ablation) | Eco Search · DeepCoder integer list tasks | tasks solved: 13 more tasks | Helped |
| add bucketing (ablation) | Eco Search · DeepCoder integer list tasks | tasks solved: 20 more tasks | Helped |
| remove bucketing (ablation) | Eco Search · Grammar scaling: derivation rules | enumeration speed | Hurt |
| vary the bucket size (ablation) | Eco Search · Grammar scaling: derivation rules | enumeration performance | No clear effect |
| increase the number of derivation rules | Eco Search · Grammar scaling: derivation rules | time to enumerate one million programs | No clear effect |
| increase the number of non-terminals | Eco Search · Grammar scaling: non-terminals | time to enumerate one million programs: 2x more time | Hurt |
| increase the number of non-terminals | Bee Search · Grammar scaling: non-terminals | time to enumerate one million programs: 3x more time | Hurt |
| increase the distance to the starting non-terminal | Eco Search · Grammar scaling: distance to start non-terminal | time to enumerate one million programs: 6x more time | Hurt |
Surprising findings
- Bee Search fails to enumerate 10K programs within timeout even for grammar R_4, and scales poorly with number of non-terminals (slower than Heap Search beyond 15 non-terminals).
Limitations
- Constant-delay guarantee requires integer costs; experiments discretize probabilities in log space.
- Performance drops as grammar complexity grows; does not scale to very large DSLs.
- Experiments are in pure Python re-implementations on a single CPU machine with limited domains (two).
Experimental setup
Datasets: FlashFill SyGuS string manipulation tasks (205) DeepCoder integer list tasks (366) synthetic dataset used to train cost-function network
Benchmarks: FlashFill SyGuS 205 string tasks DeepCoder 366 integer list tasks parametric grammars D_k, N_k, R_k
Metrics: number of tasks solved vs cumulative time throughput (programs per time) time to enumerate 1M programs
Baselines: Heap Search Bee Search Eco Search without bucketing
Builds on: Bee Search Heap Search Euphony A* search
Closest papers by meaning
- Program Synthesis with Best-First Bottom-Up Search (Abstract Reprint) (AAAI 2024 · similarity 0.91)
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.87)
- From I/O to Code with Discovery Agent (NeurIPS 2026 · similarity 0.86)
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.86)
- Thought of Search: Planning with Language Models Through The Lens of Efficiency (NeurIPS 2024 · similarity 0.86)
- Self-Improving Language Models for Evolutionary Program Synthesis: A Case Study on ARC-AGI (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.