HYSYNTH: Context-Free LLM Approximation for Guiding Program Synthesis

Summary

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.

Strengths

- It proposes a promising hybrid approach that combines the efficiency of formal program synthesis and the power of LLMs. - Compared to training new models for every new DSL/domain, the proposed approach only needs to extract a small PCFG from a few LLM samples, which is lightweight and robust. - The approach is general; in particular it can be applied to various domains (reasoning about grid puzzles, tensor manipulations, and string manipulations) and with different LLMs. It can outperform baselines substantially according to the experiments. - The problem is well-motivated, and the limitations and related work are discussed in an insightful and thorough manner.

Weaknesses

- The datasets are small and domain specific, and requires implementing a synthesizer. It is unclear whether such an approach can scale to more complex programs, for example to program with loops, or even general-purpose programs. - It mentions in the limitation section that sampling from LLM is costly, and it uses different models like GPT3.5, GPT-4, and DeepSeek, but did not provide a comparison of the costs.

Questions

- Using PCFG as the approximation model seems too simple at first glance, but it works well in the evaluated benchmark. It is also surprising to see that only 10 samples can often achieve comparable performance as the full 100-sample approach (Appendix C). This leads me to wonder whether the model only captures very superficial patterns from the LLM samples, and whether an even simpler surrogate model could be used. For example, It is mentioned in line 151-157 that GPT-4o predicts the relevant components with high accuracy, and never uses irrelevant components in the example. If we directly remove such irrelevant components from the CFG and directly use the search algorithm, how would such a baseline perform? - I am not entirely convinced by the superior performance of HYSYNTH over using LLMs purely without search. For example, for the ARC task, the HYSYNTH approach uses a divide-and-conquer strategy; it would be interesting to see how the LLM baseline performs when it also applies such a strategy. Also, in the paper ExeDec, Section 5.2, the experiments show that presenting DSL programs as Python functions can enable the LLM to better leverage its general knowledge from pretraining and improve the result. I wonder if such a prompting technique would improve the performance of pure LLMs. [1] Shi, Kensen, et al. "ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis." The Twelfth International Conference on Learning Representations. (ICLR 2024)

Rating

7

Confidence

5

Soundness

4

Presentation

4

Contribution

3

Limitations

The limitations are well addressed.

Summary

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.

Strengths

The HYSYNTH method can be implemented directly on existing LLMs without additional model fine-tuning, allowing its performance to improve as the models advance. HYSYNTH performs well with fewer samples, consistently surpassing current methods, making it robust and efficient. Experiments demonstrate that HYSYNTH consistently outperforms both baseline synthesizers and ablations across various configurations.

Weaknesses

The use of LLMs in HYSYNTH appears simplistic and seems not to fully leverage the capabilities of LLMs. HYSYNTH's performance depends on the LLM's capabilities, including additional inference time and prediction accuracy.

Questions

The experiments show that HYSYNTH solves more problems within the same time limit. Does the time reported include the time taken for sampling from the LLM and training the surrogate model? What percentage of the total time does LLM inference take? For GPT-4o's 0% performance on the percentage of syntactically valid completions in the STRING domain, can a more detailed analysis be provided? Could this be improved with a simple CoT strategy or other methods?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors have addressed the limitations of their work.

Summary

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.

Strengths

The paper is the first (concurrent with Li et al [29]) to use pretrained LLMs to guide search-based program synthesis. The approach introduced by HySynth -- to sample programs from a pretrained LLM to learn the weights for a PCFG, and then to guide bottom-up enumerative search according to these weights -- is a natural and simple idea, and the paper demonstrates that it works well across a variety of domains. The simplicity of the approach is a strength, making it possible to apply to a range of domains -- wherever a CFG can describe the DSL used in the domain. The simplicity and generality of the approach make the contribution significant: it is quite likely that additional methods that learn to perform a fast search guided by an LLM will follow in future research, as program synthesis with LLMs is an important and growing area. The experimental results are robust, showcasing the HySynth method across a good diversity of domains and yielding clear improvements in each. (See also Weakness 1 however.) The paper is clearly written, including a robust and clear background section, a clear statement of the method and experimental results, and well contextualized in the context of the literature.

Weaknesses

For the direct sampling baseline, there is either a clarity or methodological issue. It is unclear how many samples are drawn from the LLM in the direct sampling approach, and if the number of samples is more than 1, it is not clear what is done to produce diversity (i.e. setting the temperature during sampling, or sampling without replacement e.g. with unique randomizer [1]). From the horizontal lines in Figure 4a, 4b, and 4c, it seems overwhelmingly likely that only a single sample is drawn from GPT4o for the direct sampling baseline, which places this baseline at a disadvantage since >>1 samples can be drawn within 10 minutes. The disadvantage is compounded because direct sampling is trivially parallelizable, so the number of samples that could be drawn in this time is large. And as one further point in favor of drawing multiple samples for the direct sampling baseline, the HySynth approach itself uses as many as N = 100 samples from the LLM (line 273). I recognize this may be a costly baseline to run (I have not computed the cost), and suggest a reduced time limit if the cost is prohibitive for the 10m time limit. [1] Incremental Sampling Without Replacement for Sequence Models https://arxiv.org/pdf/2002.09067 The other weaknesses I observed are touched upon in the limitations section of the paper. The main limitation of the significance of the work is (as stated in the paper) that is requires a DSL, and particularly one that has a CFG, and so a custom synthesizer for each DSL, for the method to be applied. This requires meaningful work to apply HySynth to a new domain. Another concern (also addressed in the limitations section) is the possibility of data leakage in the evaluations. I share the authors' view that this is not a major issue _provided_ they address the first weakness I state above for the direct sampling baseline.

Questions

Is the time to draw N samples from the LLM and construct the PCFG included in the plots in Figure 4a, 4b, 4c? If not, I would encourage doing so. Why do you include few-shot examples when prompting for the tensor domain, but not for the string domain (or have I misread this?)? It seems more important for the string domain given that 0% of the LLM-generated programs in the string domain are valid completions. nit: Figure 2 suggests the I/O examples are provided as an input to the synthesizer, rather than just the PCFG. I don't believe this is correct or intended. Is it correct to state that the PCFG is reasonably approximating the LLM's condition distribution over output programs for a given prompt (line 65)? Though it is trained to approximate this, I expect it is quite a poor approximation. And then the approach does not sample from the PCFG, but rather enumerates from it, making it unclear to me that a good unbiased approximation of the LLM's conditional distribution is what is desired (certainly if the PCFG could perfectly mimic this distribution that would be great!, but perhaps there is better; beyond wanting to somewhat approximate the LLM's condition distribution, increased functional diversity over the 10m search period is also important.)

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations section (4.3) captures the main limitations of the system well and articulates them clearly. The Broader Research Impacts appendix (K) touches on the research, albeit not societal, impact of the work. This seems sufficient to me.

Response to Rebuttal

Thank you for your rebuttal, and in particular Global Responses 1 and 2. Regarding Global Response Q1 (Q1, Q3 in "Rebuttal by Authors"): > The time to draw those samples is excluded from the graphs in Fig 4. Thank you for clarifying this. This is a very important detail to have omitted, and it does meaningfully change the results of the paper / what is conveyed in Figure 4. The baselines ARGA, Probe, TF-Coder, and Unguided are being given a 268-285 second disadvantage in Figure 4 compared with HySynth and No-Search. Eyeballing it, it looks like HySynth still outperforms the baselines even when this adjustment is accounted for, but not as immediately or decisively as Figure 4 currently conveys. My recommendation for making this clear would be to include the sampling time in the Figure 4 plots, giving all methods the same total time (not just the same search time) for a fair comparison. Making clear the total time spent by each method (not just the time spent searching) is necessary for a fair comparison of the methods if you wish to claim that HySynth outperforms the other methods (a key claim of the paper, line 86). > 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. Thanks for measuring this. This suggests that running the No-Search / "GPT-4o" baseline for 10 minutes would involve drawing no more than 225 samples, and so the cost might be quite affordable. A back-of-the-envelope calculation suggests the total cost would be between $3 - $4 USD per domain (so up to $12 USD total). If you do this, the Fig. 4 plot for the "GPT-4o" baseline would then show progress over time like the other methods, rather than being a fixed horizontal line. > 1) LLM sampling incurs not only time cost, but non-trivial monetary cost, while symbolic search is virtually free Yes, it's true that sampling is more expensive than search per unit time, but I don't think this justifies ignoring the sampling time. (e.g. the caption for Fig 4 currently reads as "Number of benchmarks solved by HYSYNTH as a function of time", not even specifying search time; similarly the language used in 4.2 is "We compare the time to solution for the main HYSYNTH configuration, baseline synthesizers, and the two ablations; the results for the three domains are shown in Fig. 4", again giving the impression that this measures total time.) Regarding Global Response Q2 (Q4 in "Rebuttal by Authors"): > Providing in-context examples is unlikely to help because these examples would have a different grammar, and only confuse the model. This is possible, but I would not be surprised if in-context examples did help, even if they came from different grammars. (The way I expect you would prompt the model, the grammars would be included in the in-context examples.) -------- Q2: Thank you for clarifying. Q5: Thank you for clarifying; that was my mistake. Q6: Thank you for your comment and agreeing to update the text.