LambdaBeam: Neural Program Search with Higher-Order Functions and Lambdas

Summary

The paper extends the CrossBeam method with synthesizing intermediate lambda functions to solve the programming by example task. The authors introduce the Merge operator to construct new lambda functions by choosing an operator from the DSL, and its arguments from existing terms (variables or lambda functions). The inputs to the Merge operator are predicted by the neural model, so the lambda functions are built step-by-step bottom-up, similarly to the whole synthesized program. Lambda functions can not be executed on the input/ouput examples so they are executed on hardcoded canonical argument tuples instead and are encoded using property signatures computed on the results, the expected output of the program, and the arguments of the lambda function.

Strengths

As the authors claim and also as far as I know this is the first neural search method to synthesize general-purpose (not hardcoded) lambda functions, which has been an open problem for years. DreamCoder (cited in the Related Work) can also synthesize lambda functions but it does so by finding common program fragments in synthesized programs in a Bayesian framework.

Weaknesses

The paper - understandably - refers to the CrossBeam paper many times. It contains a summary of CrossBeam in lines 100-121, but reading that paper still helped a lot to undertand this paper. Also, I think that Figure 2 from the CrossBeam paper should be included as Section 3.3 talks about parts of that Figure. It would be good to include CrossBeam without lambda functions as a baseline for the evaluations; currently it is hard to know how much of the improvement is due to the lambda functions. Part 3.1 could be clearer: - the example is at the end of the section, maybe an example-first approach could be better - Merge ensures that there are no free variables and also unifies the arguments. When reading through the section it seems from line 128 to 147 that the only criterion we need is that we have no free variables and that alone ensures the unification of the arguments. - I'm not sure these are correct: - line 157 says that Merge runs the function $f$, - line 160 says that $a_k(i_k)$ evaluates to a concrete value, I think it should be an expression line 217 says that $S$ contains variable tokens, but I think it also contains lambda expressions. I'm not sure how to intepret line 223: "an embedding of the weight of this value". I couldn't find which LLM the authors used as a baseline, it should be cited. I couldn't find the range of the inputs and outputs, it would be good to include them.

Questions

There were 16 canonical argument tuples for each combination of tuple length and argument types. To me it seems somewhat low. Wouldn't more be helpful, or does the slowdown of the search counteract the improvement? Why do most of the methods perform worse on the handwritten tasks compared to the synthetic tasks? Is it because the generation of the synthetic tasks is similar to their algorithm? Figure 4 (Synthetic tasks) shows significant improvement in the LLM results as the task weight grows from 9-10 to 11-12. Is that an anomaly or is there an explanation? It would be interesting to see what happens after task weight 11-12.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

Limitations are addressed at the end of the Results, maybe they could have their own section.

Summary

The paper presents LAMBDABEAM, a nn-based search method for program synthesis which is built upon CROSSBEAM and can handle lambda functions and higher-order functions. Specifically, to build lambda terms, LAMBDABEAM enforces that every term constructed during search has no free variables by introducing a novel operator called MERGE. Furthermore, to learn lambda expressions, LAMBDABEAM constructs a new generalization of property signatures to represent lambda expressions. The paper shows that LAMBDABEAM outperforms existing techniques in the integer list manipulation domain (a modified DeepCoder).

Strengths

1. This addresses a meaningful problem, that is how to search for lambdas and higher-order functions which would enable the synthesis of arbitrary looping computations and extend the boundary of neural program synthesis. 2. The experiment result is promising. 3. The writing is clear. 4. In the current era dominated by LLMs in the field of program synthesis and code generation, this paper makes a good attempt towards small and meaningful works. I believe that this type of work and LLMs-related works will inspire and complement each other.

Weaknesses

1. Placing a figure that illustrates the LAMBDABEAM Model architecture would be better. Although the design largely follows CROSSBEAM, a LAMBDABEAM figure is necessary for showing the differences and for readers unfamiliar with CROSSBEAM. 2. Experimental settings are somewhat confusing. For example, what causes the differing number of I/O examples for list output and integer output in the hand-written? What is the name of the pre-trained LLM since the performance gap among different LLMs on program synthesis is significant. Can the authors further explain these settings? 3. Can the authors fine-tune the LLM on the proposed DSL which might be a better comparison?

Questions

1. Will CROSSBEAM be improved with restarts? 2. Considering the elapsed time with quantitive computing resources used would be better if possible. 3. How might this kind of nn-based search method be combined with LLMs? 4. A experimental comparison with Dreamcoder is needed.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors have discussed the limitations in the results part.

Summary

In this work the authors introduce LambdaBeam a method crafted to explicitly handle lambda functions and higher-order functions for neurally guided program synthesis. Towards this goal the authors first introduce a method to represent lambda functions which enables variable order independent canonical representation, and eases creation of lambda functions by merging other lambda functions. Then, the authors adapt CrossBeam a pre-exiting method for program synthesis to synthesize lambda functions, while also employing property signatures to represent lambda functions. When deployed on integer list manipulation tasks, Lambda beam surpasses other competitive baselines, in terms of both speed and success rate.

Strengths

### Originality Previous works do not explicitly model lambda functions, or learn how to compose them. This is an original contribution of the paper. ### Quality & Clarity The paper at a paragraph level is well written. ### Significance The approach towards representation of lambda functions is a interesting, useful and novel contribution that may be useful for many future program synthesis approaches. Furthermore, the approach is able to beat strong baselines such as lambda^2 an off-the-shelf program synthesis tool, and a 60B parameter large language model.

Weaknesses

### Weaknesses 1. I think the paper does not clearly justify *why* prior works cannot model lambda functions or higher-order functions. Particularly, it states Programming by examples (PBE) demands a more systematic search strategy but its unclear why that is the case. The paper also doubles down on the belief that other methods *cannot* synthesize programs with arbitrary looping computation, but its unclear why that is the case. For example, large scale models (GPT 3.5) can indeed produce programs with higher-order functions and lambda functions. Its unclear why the paper strongly posits that other methods cannot do this. 2. The paper is not easy to understand and seems to depend on the reader being familiar with CrossBeam> On that note, LambdaBeam strongly depends on CrossBeam which is a small drawback as well (though the other contribution - representation of lambda functions is a general and useful contribution).

Questions

Why did the authors use DeepCoder benchmark? Is integer manipulation benchmark the right choice when solutions many involve a lot of hierarchical reasoning. I am especially concerned since the input contains only 3-5 examples, which might not be sufficient to triangulate the true function. Furthermore, the False Positive rate might be higher simply because of the benchmark used.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The paper does not discuss limitation or potential negative societal impact. Adding information regarding both these aspects in the appendix might further improve the paper.

Summary

This paper presents a method for training a neural module to guide a search-based program synthesis procedure that supports lambda functions. This is accomplished by leveraging the existing technique of property signatures, which essentially represent program constructs using a hand-designed vector of features. The authors design features for representing lambda functions, including evaluating the lambda function on a hardcoded set of inputs. This allows lambda functions to be incorporated in a prior bottom up program search technique called CrossBeam, and they introduce a new Merge operator to build lambda terms from the bottom up. The results on a modified version of the DeepCoder benchmark show their approach outperforms several strong baselines, including symbolic search and an LLM fine-tuned on Python.

Strengths

Representing and synthesizing (lambda) functions is a significant step forward for neural program synthesis. Although the individual techniques are mostly prior art, I consider the combination of techniques to be novel. The writing is generally clear, though I found the implementation details to be quite sparse in places (see Weaknesses)

Weaknesses

The biggest weakness is that the approach is tested on only one synthetic dataset and also relies on hand designed features. Furthermore, the lambda functions only contain 2 variables. It remains to be seen if this approach could scale to more realistic datasets with more data types and more complex functions. Additionally, there are almost no examples in the paper. At the very least, the appendix should include some examples of the synthesis dataset as well as programs synthesized by LambdaBeam. Finally, many of the implementation details are not listed out fully, which impedes reproducibility (e.g., the architecture of the models) and in severe cases, the reader's ability to contextualize the results (e.g., a list of the property signatures used and the evaluation tasks).

Questions

How many programs are there of weight at most 12 (i.e., that were sampled from for the training set)? What size is the property signature? (or how many properties are there) Can you elaborate on why you add an embedding of the weight of a value for embedding lambda expressions? Is Merge complete for lambda functions? This should be addressed in the paper.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors should also address the extent to which the property signatures are tailored to the DSL, and the implications for broader applicability / scalability.

Post-Rebuttal update

I thank the authors for the detailed rebuttal. This rebuttal, along with other reviewer's notes has been useful to improve my understanding of this work. > Weakness 1 "Neural synthesis search" generally covers a much wider space than "deep learning for PBE", and is likely to be misleading for readers. I believe the paper would be improved by making the claims more specific. Example Excerpt from lines 29-31: "The fundamental question explored in this paper is whether a neural program synthesis search policy can learn to reason about lambdas and higher-order functions, which would enable the synthesis of arbitrary looping computations that were not previously possible with neural synthesis search" -> not possible with neural synthesis search techniques which relies on intermediate expression evaluation. Also, any auto-regressive token-wise prediction approach which does not rely on intermediate expression evaluations can model lambda functions (**not just LLMs**). i.e. transformer models which perform program synthesis via a simple next-token-prediction task (as done in PLAD [1]), **without relying on natural language**, can indeed predict lambda functions (if its trained on examples containing lambda functions). > Weakness 2 I appreciate the authors response! > DeepCoder Benchmark I appreciate the authors response! Its indeed true that the handwritten benchmark has a smaller false-positive rate (which reflects well on the proposed method). I can understand the reasons for using this benchmark. Hopefully, in the future works more suitable benchmarks are employed. > Limitations I thank the authors for correcting my statement. The paper does mention the limitations of the proposed approach. I would still suggest the authors add potential negative societal impact in the appendix. The authors have addressed my queries. Therefore, I am raising my rating to 7 Accept (on the expectation that authors will edit the draft to be more specific about the paper's contribution w.r.t. prior work such as in Lines 29-31). ### Reference [1] PLAD: Learning to Infer Shape Programs with Pseudo-Labels and Approximate Distributions, R. Kenny Jones et al., CVPR 2022.

Thank you for your response

Thank you for your insightful response. In Part 3.1 I was not confused by the use of the word "unify", but the structure of the beginning of the section: lines 124-127 talk about equivalent expressions with different variable names (renaming), then from line 128 the paper is about free variables. The two parts are not connected. Renaming (or unifying) is talked about again only from line 148. So my problem was that free variables appear suddenly out of nowhere and seemingly there is a connection but it's not explained. After reading the whole section it cleared up, but I feel it could be improved. I don't think the word "unify" should be changed. I believe that the differences between the handwritten and synthetic tasks should be mentioned in the paper and their distributions should be included in the Appendix.