Research map / Learning theory and algorithms / Combinatorial and search optimization
CrossBeam: Learning to Search in Bottom-Up Program Synthesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CrossBeam's model-guided bottom-up search instead of BUSTLE | String program synthesis · String manipulation, 50K candidates, 127 total tasks | tasks solved: 59 -> 95.4 | Helped |
| Use CrossBeam's model-guided bottom-up search instead of BUSTLE | String program synthesis · String manipulation, 1M candidates, 127 total tasks | tasks solved: 94 -> 104.6 | Helped |
| Use CrossBeam instead of prior ILP methods | Inductive logic programming · Randomly generated tasks up to size 19 | success rate: 0% -> over 50% | Helped |
| Use CrossBeam instead of Metagol or Popper | Inductive logic programming · Handcrafted tasks | success rate: 60% -> 93% | Helped |
| Train from randomly sampled argument lists rather than model-produced search contexts (ablation) | CrossBeam · String manipulation benchmarks | tasks solved | Hurt |
| Use deterministic beam search rather than UniqueRandomizer during evaluation (ablation) | CrossBeam · String manipulation benchmarks | tasks solved | Hurt |
| Sample argument lists with replacement rather than using UniqueRandomizer during evaluation (ablation) | CrossBeam · String manipulation benchmarks | tasks solved | Hurt |
| Use beam search or sampling for evaluation instead of UniqueRandomizer (ablation) | CrossBeam · Early search, few candidate programs | search efficiency | Helped |
| Use UniqueRandomizer instead of beam search or sampling for evaluation (ablation) | CrossBeam · Extended search over thousands of candidates | tasks solved | Helped |
| Use CrossBeam rather than BUSTLE | String program synthesis · Wallclock comparison, 127 total tasks | tasks solved: 91.8 vs 112 | Hurt |
Closest papers by meaning
- Eco Search: A No-delay Best-First Search Algorithm for Program Synthesis (AAAI 2025 · similarity 0.88)
- Bayesian Program Learning by Decompiling Amortized Knowledge (ICML 2024 · similarity 0.87)
- HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis (NeurIPS 2024 · similarity 0.87)
- Program Synthesis with Best-First Bottom-Up Search (Abstract Reprint) (AAAI 2024 · similarity 0.86)
- Planning in Natural Language Improves LLM Search for Code Generation (ICLR 2025 · similarity 0.86)
- Provable Test-Time Scaling for Beam Search in LLM Reasoning (NeurIPS 2026 · 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.