Research map / Learning theory and algorithms / Combinatorial and search optimization
Program Synthesis with Best-First Bottom-Up Search (Abstract Reprint)
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 Bee Search, a best-first bottom-up program synthesis algorithm that searches in an abstract cost-tuple space so programs are generated (not just evaluated) in best-first cost order, plus a new unbounded neural-cost function.
Problem
Cost-guided bottom-up search for programming-by-example synthesis loses information by rounding program costs and does not generate programs in best-first order, wasting evaluations on programs more expensive than the solution.
Approach
Bee Search performs best-first search over cost-tuple states indexing a sorted list of program costs, so only programs with the next cheapest cost are generated, without rounding costs; it also introduces the unbounded cost function w_u that uses -log2 of the Bustle neural model's probability.
Key results
- Bee Search is never worse than Probe and Bustle and solves more problems in larger program spaces.
- Bee Search outperforms Heap Search and Brute by a large margin in all settings evaluated.
- Bee Search with the new cost function w_u outperforms all systems tested in the string manipulation domain.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Bee Search instead of Probe or Bustle with the same cost function | cost-guided bottom-up synthesis · string manipulation and bit-vector tasks with more complex DSLs | problems solved | Helped |
| use Bee Search instead of Probe or Bustle with the same cost function | cost-guided bottom-up synthesis · string manipulation and bit-vector tasks with simpler DSLs | problems solved | No clear effect |
| use the unbounded neural cost function instead of previous cost functions | Bee Search · string manipulation tasks | problems solved | Helped |
| use Bee Search instead of Heap Search or Brute | best-first bottom-up synthesis · all evaluated settings | synthesis performance | Helped |
Surprising findings
- Probe may evaluate roughly one billion programs on an example where Bee Search evaluates about one million, due to rounding of costs.
Limitations
- Cost-tuple states may be generated that are never expanded, adding overhead
- Post-generation cost functions require heapify operations that can be costly in the worst case
Experimental setup
Datasets: string manipulation tasks bit-vector manipulation tasks
Benchmarks: string manipulation tasks bit-vector manipulation tasks
Metrics: number of problems solved number of programs evaluated
Baselines: Probe Bustle Heap Search Brute
Builds on: Probe Bustle Heap Search Brute Uninformed bottom-up search
Closest papers by meaning
- Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis (AAAI 2025 · similarity 0.91)
- Simple Baselines are Competitive with Code Evolution (NeurIPS 2026 · similarity 0.85)
- From I/O to Code with Discovery Agent (NeurIPS 2026 · similarity 0.84)
- Program Synthesis via Test-Time Transduction (NeurIPS 2025 · similarity 0.84)
- Online Prompt Selection for Program Synthesis (AAAI 2025 · similarity 0.84)
- Reinforcement Learning and Data-Generation for Syntax-Guided Synthesis (AAAI 2024 · similarity 0.84)
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.