HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis

This paper presents a hybrid program synthesis approach that strengthens the classic bottom-up search with an LLM-guided prior distribution, given as a probabilistic context-free grammar (PCFG). The focus of this paper is to solve complex PBE tasks where programs in unfamiliar DSL are difficult for LLMs to generate directly, and traditional combinatorial search is infeasible. The key insight is that LLM-predicted programs (although incorrect by themselves) can provide valuable intuition regarding which operator or component to use in the correct program. As such, HYSYNTH samples a set of full programs from LLM to train an approximation PCFG model. To perform the bottom-up synthesis, HYSYNTH uses an off-the-shelf or custom synthesizer for the specific domain. The experimental results show its improvement against both vanilla LLM generators and non-LLM-based synthesizers.

The paper introduces a new approach for solving structured prediction and reasoning tasks by leveraging the programming and planning capabilities of LLMs to enhance bottom-up search in program synthesis.

Specifically, HYSYNTH initially generates preliminary solutions directly from the LLM. Since direct LLM sampling performs poorly in unfamiliar DSLs, HYSYNTH does not use these samples directly but calculates the probabilities for a PCFG grammar from them, incorporating LLM guidance into the bottom-up search (CFG -> PCFG).

Experiments show that HYSYNTH consistently outperforms both the baseline synthesizers and ablations, and is effective even with a smaller number of samples.

This paper introduces HySynth, an approach to program synthesis that combines (1) sampling programs from a large language model (LLM) to train a probabilistic context free grammar (PCFG) with (2) applying bottom-up enumerative search guided by the PCFG to solve programming by example tasks. It applies this approach to three domains: the abstract reasoning corpus (ARC), tensorflow expression synthesis, and string expressions (SyGuS). By learning the weights of the PCFG from the samples drawn from the LLM, HySynth produces state of the art results on all three domains, solving more problems in less wall-clock time. The main contribution is the use of an LLM to choose weights to guide a bottom-up enumerative program synthesis search system.

We thank the reviewers for their time, valuable comments, and encouraging feedback! In the global part of the response, we answer shared questions and provide a list of changes we plan to make in a revised version of the paper.

Q1 (Reviewers FZiE and XXbQ): Does the time reported in Fig 4 include the time taken for sampling from the LLM and training the surrogate model? What percentage of the total time does LLM inference take? The LLM baseline is at a disadvantage because many more samples could be drawn within the timeout of 10 minutes.

In our experiments, the results for both the LLM baseline and HySynth are based on 100 samples from the LLM. The time to draw those samples is excluded from the graphs in Fig 4. Reviewer FZiE is right that many more samples could be drawn within 10 minutes. Indeed, one way to conduct our experiments would be to give all techniques the same amount of total time, which can be used towards either LLM sampling or symbolic synthesis. We thought such setup would not be fair for the following two reasons: 1) LLM sampling incurs not only time cost, but non-trivial monetary cost, while symbolic search is virtually free; 2) the time cost of LLM sampling depends on many incidental factors out of our control (e.g. network latency, server load). We chose instead to completely separate the sampling stage from the synthesis stage and to only report the synthesis times in the figures (which is why the LLM-only line is always horizontal, as the reviewer notes). That said, we did compute the time it took to sample 100 solutions, and it amounts to 285 secs for tensor domain and 268 secs for the string domain. Learning the PCFG takes less than 1 sec for all domains. We will report these times in the next version of the paper.

Q2 (Reviewers FZiE and XXbQ): Why does GPT-4o have 0% correctness and syntactic validity on the String domain? Could this be improved with more advanced prompting techniques? Why do we not provide in-context examples for this domain, like for Tensor?

This is due to the specifics of the SyGuS benchmark, from which our String problems are drawn. In this benchmark, each problem comes with a custom restricted grammar; all grammars are subsets of the full SyGus grammar but purposefully impose additional restrictions on the solution (for example, the synthesizer is usually allowed only a handful of string constants, which excludes trivial solutions that simply reproduce the given output examples). In the experiments reported in the paper, we judge syntactic validity against these custom grammars (which is how the SyGus competition is also judged), and the LLMs turn out to be quite poor at following these syntactic restrictions, even though the grammar is given in the prompt. Providing in-context examples is unlikely to help because these examples would have a different grammar, and only confuse the model. If we were to relax the definition of syntactic validity, ignoring the custom grammars and allowing the full SyGuS grammar, LLM solutions would achieve a syntactic validity of 60.5% and solve 20/70 problems correctly (which is better than Unguided search but worse than Probe and HySynth.). We will include these additional results in the paper along with a detailed analysis.

Change list

1. We will report the time and monetary cost of sampling from the different LLMs in our experiments (as mentioned in Q1 above).
2. We will clarify why LLMs get 0% syntactic validity on the String domain and add the results of our new experiments with a relaxed notion of validity (as explained in Q2 above).
3. We will include the results of an ablation study using a simpler surrogate model, which simply excludes the components not used by the LLM (as suggested by Rev MWWa; preliminary results reported in the attached PDF).

This paper proposes performing bottom-up program synthesis search but using a PCFG derived from LLM-generated samples to guide the search, leading to improved performance in a variety of synthesis domains/datasets.

I recommend to accept this paper. Reviewers agreed that the approach is well-motivated and general, the experiments are convincing and thorough, and the writing is clear. The authors answered reviewers' questions and resolved their concerns in the rebuttal. All reviewers are in agreement about acceptance.

I am confident that this paper meets the bar for acceptance. However, I was on the fence about recommending poster or spotlight. On the positive side, the reviewers had a high average score (6, 7, 7) and I agree that the paper and underlying research were done very well. But after much thought, I am recommending a poster presentation because I feel the core idea is very simple and natural, which is a good thing when trying to replicate the work, but it also means the work is a bit more incremental than I would imagine for a spotlight paper. The authors cite multiple prior works which learn how to guide combinatorial program synthesis search by training a model on data in a particular domain, and this paper's contribution is using an LLM to provide this guidance instead, more generally (across multiple domains) and without training. This feels like an instance of a common pattern of generalist LLMs being used to replace specialist models trained from scratch. Under this lens, I am not so surprised that the approach works. Again, I still think the work was done very well and it is a valuable contribution to the AI-for-code research community to have solid confirmation that this approach does indeed work, but I would expect a spotlight paper to provide a bit more novelty.