CrossBeam: Learning to Search in Bottom-Up Program Synthesis

Kensen Shi, Hanjun Dai, Kevin Ellis, Charles Sutton

Introduction

Program synthesis—the automated generation of code from specifications such as input-output examples—is a core challenge in artificial intelligence. The primary obstacle is the "combinatorial explosion": the space of possible programs grows exponentially with program length. While previous neural approaches have attempted to guide search by predicting useful functions, they often remain "passive" advisors to traditional combinatorial algorithms. CrossBeam introduces a paradigm shift by training a neural model as an "active" searcher that learns to navigate the search space step-by-step.

The CrossBeam Model

CrossBeam is built upon bottom-up enumerative search, where basic constants and variables are iteratively combined using operations from a Domain-Specific Language (DSL). The core innovation is a neural architecture that manages the search process by considering the entire "search context"—the set of all subprograms discovered thus far and their execution results.

The detailed neural architecture of the CrossBeam model, featuring value embeddings and a pointer network for argument selection.

The model utilizes a pointer network to select arguments for DSL operations from the pool of existing subprograms. It is trained "on-policy," learning from its own search trajectories to recover from errors and identify promising partial solutions. A "UniqueRandomizer" component further ensures diversity during evaluation, preventing the search from becoming trapped in redundant areas of the state space.

Experimental Evaluation

The authors evaluated CrossBeam across two domains: string manipulation and inductive logic programming (ILP). In string manipulation, benchmarks included 38 new tasks and 89 SyGuS tasks from the BUSTLE dataset. In ILP, the model was tested on randomly generated logic tasks and mathematical relations.

Performance comparison of CrossBeam against baselines on BUSTLE's string manipulation tasks. CrossBeam significantly outperforms prior methods in the number of programs synthesized within a fixed budget.

Key Results

  • Efficiency: In string manipulation, CrossBeam solved 62% more tasks than the previous state-of-the-art (BUSTLE) within a budget of 50,000 candidate programs. It demonstrated a 16x to 25x improvement in search efficiency.
  • Robustness: On complex logic tasks where traditional systems like Metagol and Popper failed (0% success rate), CrossBeam maintained a nearly 100% success rate.
  • Execution-Guided Learning: By executing every subprogram, CrossBeam leverages intermediate results to inform subsequent search steps, mirroring the iterative process used by human programmers.

Discussion and Future Work

While CrossBeam is highly efficient in terms of the number of programs explored, the computational overhead of the neural network currently results in slower wallclock time per program compared to optimized non-neural engines. Future work will focus on improving engineering through better batching and scaling the approach to more general-purpose programming languages and larger DSLs. Additionally, learning dynamic search budget allocation remains an open area for exploration.

Summary updated

BibTeX
@inproceedings{shi2022crossbeam,
  author = {Kensen Shi and Hanjun Dai and Kevin Ellis and Charles Sutton},
  title = {{CrossBeam: Learning to Search in Bottom-Up Program Synthesis}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=qhC8mr2LEKq},
}
Figure