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

Abstract

Many approaches to program synthesis perform a search within an enormous space of programs to find one that satisfies a given specification. Prior works have used neural models to guide combinatorial search algorithms, but such approaches still explore a huge portion of the search space and quickly become intractable as the size of the desired program increases. To tame the search space blowup, we propose training a neural model to learn a hands-on search policy for bottom-up synthesis, instead of relying on a combinatorial search algorithm. Our approach, called CrossBeam, uses the neural model to choose how to combine previously-explored programs into new programs, taking into account the search history and partial program executions. Motivated by work in structured prediction on learning to search, CrossBeam is trained on-policy using data extracted from its own bottom-up searches on training tasks. We evaluate CrossBeam in two very different domains, string manipulation and logic programming. We observe that CrossBeam learns to search efficiently, exploring much smaller portions of the program space compared to the state-of-the-art.
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