Program Synthesis with Best-First Bottom-Up Search (Abstract Reprint)

Saqib Ameen, Levi H. S. Lelis

Introduction

Program synthesis—the automated generation of code from high-level specifications like input-output examples—is a cornerstone of modern developer productivity tools. A common strategy for this task is Bottom-Up Search (BUS), which iteratively constructs complex expressions from basic building blocks. While cost-guided models have been introduced to prioritize likely solutions, existing BUS algorithms often fail to achieve true "best-first" efficiency. This paper introduces Bee Search, a novel algorithm designed to navigate the abstract space of program costs to minimize memory overhead and maximize search performance.

Traditional cost-guided BUS systems suffer from a significant structural flaw: they generate and store programs before fully accounting for their relative costs. Even when guided by sophisticated neural models, these systems often instantiate a vast number of suboptimal programs that are never part of the final solution. This "generation-first" approach leads to high memory consumption and slows down the search process, particularly as the Domain-Specific Language (DSL) grows in complexity. The authors identify that the primary bottleneck is not the evaluation of programs, but the act of generating them in the first place. By the time a program is in memory, valuable computational resources have already been spent.

Methodology: The Bee Search Algorithm

Bee Search addresses these inefficiencies through three primary innovations designed to ensure that every bit of guidance from a cost model is utilized to prune the search space.

1. Search in Abstract Cost Space

Unlike traditional methods that build programs and then assign costs, Bee Search operates within an abstract space of program costs. By navigating this space first, the algorithm maintains a strict best-first ordering during the generation phase. This shift allows the system to prioritize the most promising program structures before they are even instantiated.

2. Zero-Waste Generation

By operating in the abstract cost space, Bee Search achieves "zero-waste" generation. It avoids creating any program in memory that is more expensive than the eventual solution. This drastically reduces the memory footprint compared to traditional BUS, as the system no longer stores the expensive, useless programs that typically exhaust system resources.

3. Enhanced Cost Function

To further refine the search, the authors developed a new cost function. This function is designed to more effectively extract and utilize nuanced information from existing cost models, such as neural networks that predict program structure. This ensures that the search is guided by the most accurate probability estimates available.

Experimental Evaluation

The researchers evaluated Bee Search against state-of-the-art (SOTA) cost-guided BUS approaches using two primary benchmarks:

  • String Manipulation: Tasks involving text transformation (e.g., extracting a last name from a full name), common in end-user applications like Microsoft Excel.
  • Bit-Vector Tasks: Low-level bitwise operations typical in systems programming and compiler optimization.

The evaluation spanned both simple and complex DSLs to determine how the algorithm scales with language expressivity.

Key Insights and Results

The experimental results highlight several critical findings regarding the efficiency of program generation:

  • The Complexity Advantage: Bee Search significantly outperforms existing SOTA tools on complex DSLs. As the search space expands, the efficiency of the abstract cost space search acts as a "force multiplier," allowing Bee Search to find solutions where other methods fail due to memory constraints.
  • Performance Parity on Simple Tasks: On simpler DSLs with smaller search spaces, Bee Search performs on par with existing methods. This indicates there is no performance "penalty" for using a more sophisticated search strategy on easier problems.
  • Cost Function Efficacy: The new cost function, when paired with Bee Search, showed marked improvements in string manipulation tasks, demonstrating the value of preserving information from the underlying cost models.

Discussion and Limitations

While Bee Search represents a significant advancement, its performance advantage is most pronounced in complex environments. In very simple DSLs, the gap between Bee Search and traditional BUS narrows, suggesting that the overhead of managing the abstract cost space is most justified for difficult synthesis tasks. Furthermore, as a cost-guided search, Bee Search remains dependent on the quality of the underlying cost models; the algorithm is only as effective as the estimates provided to it.

Conclusion

Bee Search redefines the efficiency of Bottom-Up Search by moving the search process into an abstract cost space. By ensuring that only the most promising programs are ever instantiated, it solves the memory-bottleneck issues inherent in previous SOTA tools. This approach paves the way for more robust program synthesis in increasingly complex programming domains beyond simple string and bit-vector manipulation.

Summary updated

Abstract

Cost-guided bottom-up search (BUS) algorithms use a cost function to guide the search to solve program synthesis tasks. In this paper, we show that current state-of-the-art cost-guided BUS algorithms suffer from a common problem: they can lose useful information given by the model and fail to perform the search in a best-first order according to a cost function. We introduce a novel best-first bottom-up search algorithm, which we call Bee Search, that does not suffer information loss and is able to perform cost-guided bottom-up synthesis in a best-first manner. Importantly, Bee Search performs best-first search with respect to the generation of programs, i.e., it does not even create in memory programs that are more expensive than the solution program. It attains best-first ordering with respect to generation by performing a search in an abstract space of program costs. We also introduce a new cost function that better uses the information provided by an existing cost model. Empirical results on string manipulation and bit-vector tasks show that Bee Search can outperform existing cost-guided BUS approaches when employing more complex domain-specific languages (DSLs); Bee Search and previous approaches perform equally well with simpler DSLs. Furthermore, our new cost function with Bee Search outperforms previous cost functions on string manipulation tasks.
BibTeX
@inproceedings{ameen2024program,
  author = {Saqib Ameen and Levi H. S. Lelis},
  title = {{Program Synthesis with Best-First Bottom-Up Search (Abstract Reprint)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i20.30591},
}
Figure