We are glad that you found the ideas in the paper to be “interesting” and “conceptually pleasing” and that you found the overall paper to be “refreshing” and “well-written.” Thank you for your vote for acceptance.

Please allow us to address the points that you raised below:

The tasks are a quite contrived, and it feels like the problem definition is tailored exactly to this kind of solution. All the tasks are synthetic and based on lambda calculus.

It is true that some program synthesis tasks have the synthetic quality that you are describing (as Reviewer NLqL points out, this is “a common limitation of program synthesis models/systems”). However, we don’t feel it is accurate to say that these tasks have somehow been tailored to our solution—we’ve selected a canonical set of benchmarks that have been studied extensively in prior program synthesis work [1, 2]. This affords the ability compare performance against prior results (see Appendix B.3) to a degree that we would not have been able to had we constructed an original benchmark. Evaluating on a novel benchmark would also have been more likely to raise concerns about “tailoring” of the kind described here.

What practical problems can the proposed approach be helpful for? Who is expected to use the proposed approach?

First, we want to start by addressing a possible misperception that systems based on DSLs of the kind we study here lack real-world application. Ideas from this line of inductive program synthesis research have resulted in many high-profile applications over the years, including:

• Tabular autocompletion [5], which has powered Microsoft’s billion dollar Excel product line since 2013 and continues to do so a decade later [6]. The REGEX domain in our work is a restricted version of the DSL used for systems like FlashFill.
• Scientific data analysis, which has been applied to analyze diverse phenomena ranging from large scale video datasets of social behavior in laboratory mice [7, 8] to protein binding and activity prediction for RNA splicing [9]. Our CLEVR domain, which requires reasoning about spatial relationships between objects in scenes, presents many of the same challenges needed for analyzing this kind of graph-structured data.
• Long-horizon robotics tasks of the kind that are performed by industrial/warehouse robots [10]. Our LOGO domain, which requires synthesizing programs to instruct a “turtle” how to move on a 2D surface by specifying angles and velocities, can be viewed as a version of the kind of planning problems involved in robotics domains.

These recent advances also a key part of the motivation for the neurosymbolic & hybrid AI systems track at ICLR this year. Situated in this context, the ideas and methods we introduce in LILO should have broad appeal, not just for this audience, but for the ML community in general. In particular, we believe that LILO’s general design pattern around synthesis, refactoring, and documentation has relevance to practical software engineering tools like Copilot that are used by millions of programmers every day.

Practically speaking, our code implementation (withheld for anonymity) has already garnered attention from the GitHub community and students at multiple universities are presently using LILO as the basis for research projects. Concretely, we put significant effort into making the LILO codebase beginner-friendly through documentation and by providing (for the first time in this line of work) a Dockerized development environment. Lastly, we strongly resonate with your assessment that LILO is “simpler than DreamCoder, which is good.”

We are glad that you found this work to demonstrate a “successful combination of LLM and symbolic tools” and appreciate the strong rating for acceptance.

Thank you for the valuable feedback! Based on your questions, we’ve updated several areas of Section 3 to clarify details about the search module. We hope these changes—and the clarifications below—will address any issues you encountered in the “Presentation” category.

Response to questions

In the dual-system program search module, what is the relationship between the enumerative search and LLM-guided search?

Good question! It’s a straightforward serial implementation: first, we run LLM-guided search as a fast “System 1” first pass (Alg. 1, lines 5-6) and then run enumerative search as a slow “System 2” process to try to solve tasks that were not solved by the LLM. We agree that this is not as clear as it could be; we will update Sec. 3 of our submission to emphasize that LLM-guided search and enumerative search are separate procedures.

Various approaches have been proposed for combining neural and symbolic search methods (e.g., [1] for a review), but most of this work is from the pre-LLM era. Smarter ways of integrating LLMs and enumeration for program search is something we’re currently exploring — of particular interest are methods for grammar-constrained generation with LLMs (e.g., [2]) — but this is probably beyond the scope of the current paper.

Lastly, it’s worth noting that DreamCoder’s enumerative search, which we use in LILO, trains a neural network to predict PCFG weights, so “enumeration” is itself an instance of neurally-guided symbolic search. We provide more detail on this below, in response to your questions.

What does PCFG stand for?

A probabilistic context free grammar (PCFG) is a generalization of a context-free grammar that assigns a real-valued weight to each production rule. We define this term towards the start of the Preliminaries section on p. 3: “the prior is defined under a probabilistic context free grammar (PCFG; Johnson 1998)...”

More formally, a PCFG can be defined as a quintuple $G = (M, T, R, S, P)$ where $M$ is a set of non-terminal symbols, $T$ is a set of terminal symbols, $R$ is a set of production rules, $S$ is the start symbol, and $P$ is a function that assigns a probability to each rule in $R$. This probabilistic element allows for the generation of a diverse range of structures. Moreover, as we describe below, training a task-conditioned neural network to infer $P$ is a natural way to guide search in the PCFG.

Could the author describe the input-output, architecture, and training of this multi-layer perceptron? Is this model pre-trained? DSL-specific?

Happy to provide more clarification! Here, we are talking about a piece of DreamCoder’s enumerative search algorithm that trains a “recognition network” (i.e., an RNN encoder + a MLP) to guide enumerative search by inferring $P$: the probabilities on production rules in the PCFG, as defined above.

All of this machinery is part of prior work (i.e., DreamCoder) and uses off-the-shelf Pytorch components, so we don’t allocate much space in the main paper body to describe these details. Nevertheless, these are natural questions for a reader interested in implementation, so we provide an overview of the architecture below. We refer to Appendix I in the DreamCoder supplement for further details details and will add a pointer to this appendix in the paper.

• Inputs and outputs: The recognition network takes as input a set of input/output examples for a specific task and produces an $|\mathcal{L}| \times |\mathcal{L}|$ tensor with values in $[0, 1]$ specifying transition probabilities for every production in the PCFG.
• Architecture/training: The input/output examples are encoded using an RNN (specifically, a bidirectional GRU) for text-based domains and a CNN for image-based domains. The actual MLP module is very small (only two layers, with a hidden size of 64) so the whole architecture can be learned efficiently in-the-loop. During each learning iteration, the recognition network is trained for a maximum of 10K gradient steps.
• Pre-training: As implemented, the model doesn’t use any pre-trained components. Following prior work with these datasets, we assume ground truth access to the CLEVR scene graphs, which allows us to use a text-based encoder for that domain. If we wanted to train on the original images, one could easily swap in a pre-trained CNN, or even a SOTA segmentation model, for the encoder.
• DSL-specificity: Overall, the recognition network architecture is fairly general—the main domain-specific pieces are the choice of encoder and the dimensionality of the output, which depends on $|\mathcal{L}|$.

The proposed 'LILO' is strongly based on LLM and it mentions using different models like Codex, gpt-3.5-turbo, gpt-4, but did not provide direct comparison of the their performance.

While we would have liked to be in a position to systematically benchmark various LLMs for LLM-guided synthesis, as we discuss in Footnote 1, cost considerations required us to restrict our analysis to Codex.

As a concrete example, based on our numbers in Appendix C.1, Table 6:

• An equivalent benchmark of gpt-3.5-turbo would have cost **$1,272.36** at the current price of$0.002 / token.
• An equivalent benchmark of gpt-4 would have cost **$38,170.80** at the current price of$0.06 / token.

In contrast, we accessed Codex through OpenAI’s free beta program for researchers, which saved thousands of USD over the project lifetime and afforded higher rate limits than paid GPT models.

As discussed in implementation details, we were able to make use of gpt-3.5-turbo and gpt-4 for AutoDoc, which requires orders of magnitude fewer queries. This is why these models are mentioned in the paper, but we make no claims about having systematically benchmarked these other models for synthesis. We also do not think that exhaustive and costly benchmarking of an ever-changing set of foundation models should be a standard for publication at a conference such as ICLR.

In Figure 10 caption D, the authors mentions LLM output are sampled without clearly specify the filtering/selection standard. I advise the author can give a more detailed explanation.

Thank you for the attention to detail. This filtering/selection pipeline is already described in Section 3 ("For each completion, we run parsing, type inference, and execution checks to identify valid programs that solve the target task.”). To provide more detail, our post-processing pipeline for LLM completions contains the following steps:

Given a completion: str

1. Check whether completion parses to a valid program in the DSL. If not, discard.
2. Check whether we can perform type inference on completion. If not, discard. At this point, completion represents a valid, well-typed program in the DSL.
3. Check whether program satisfies the target task specification (i.e., execute it against all I/O examples). If it does, add program to the set of task solutions.

If there are any specific aspects that you would like more detail on, please let us know. Our code on GitHub (currently anonymized for review) will also provide a clear reference for how this pipeline is implemented.

We are glad that you found this work to be “novel,” “well-described” and “well-motivated;” and that you felt our experiments and analysis were “comprehensive.” We are also delighted that you agree LILO provides a “generalizable blueprint for integrating language models with formal program synthesis,” as this is exactly what we set out to accomplish with this work.

Thank you for your review and comments! Please allow us to address some of the points that you raised below:

In Table 1, the proposed 'LILO' framework has substantially higher standard deviation than the baseline across three domains. It indicates LILO's performance varies more widely across different runs, suggesting less stability in this field.

Part of the novelty of our method is in the integration with a LLM, which inherently introduces variability across runs. In response to your comments and those of the other reviewers, we have updated Table 1 to more transparently present this variability by underlining all results that fall within $1\sigma$ of the best (bolded) result.

While some of the online synthesis conditions approach LILO’s performance, we note that none of the results from offline synthesis (Table 1, bottom half) fall within $1\sigma$ of the best (bolded) result. Thus, we are confident that our results indicate that LILO meaningfully outperforms the other models considered in offline synthesis.

We also would like to highlight that $\sigma$ is computed with respect to relatively small $N=3$ runs due to the computational cost of each full run of online program synthesis, so it is not a very tight approximation of the variability in performance. Prior work (e.g., DreamCoder, LAPS) does not report this variability as part of the main results, but we felt it important to include some kind of variability estimate in our Table 1.

The dual-system search module combines LLM-guided and enumerative search, yet the tradeoff and relative contributions are not deeply analyzed.

Thank you for the suggestion. We have added two new baselines to the “offline synthesis” section for the LLM Solver and LLM Solver (+ Search). While these are primarily intended to address a specific concern from Reviewer oPbs, these baselines also help to further pinpoint the relative contributions of LLM-guided search, enumerative search, and compression within LILO.

Beyond these new baselines, our existing results set already gives significant attention to the question of the relative contributions of the two search methods. As a recap, we include the following baselines/ablations as part of our original experiments:

• LILO (No Search)
• LLM Solver (+ Search)

This pair of conditions (removing enumerative search from LILO / adding enumerative search to the LLM-only baseline) is directly targeted at analyzing the tradeoffs and relative contributions of the two search methods. We discuss these findings on p. 7 (”To isolate the effects of search…”). In addition to the quantitative results, we also mention several qualitative examples of tasks that are solved with enumerative search but not LLM-guided search (e.g., how to draw a “snowflake” or “staircase” in the LOGO domain; see Fig. 5).

We are heartened that you found value in so many facets of this work: that the problem space is “important” and “difficult”; that the methods are “sound”, “compelling”, and “clearly-described”; that the experiment design is “reasonable”; and that the overall paper is “well-written”.

Thank you for your insightful comments and detailed suggestions. In response to your review, we have:

• Run two new baselines (See Baseline B, below)
• Started working on a new AutoDoc evaluation
• Addressed many of your minor comments, with plans to address all of them in the final submission

New Baselines

We appreciate your attention to detail around the experiment design and hope to fully address your concerns below. Concretely, the following two experimental conditions were proposed.

Baseline A: Base DSL + Stitch

Proposal: This baseline is similar to a DreamCoder + Stitch integration, where Stitch replaces DreamCoder’s compression module. The motivation for this condition is to address the possibility of a confound due to the choice of compression module, which could account for the performance delta between LILO and DreamCoder in the experiments.

Response: Your concerns about this confound highlight an oversight in our methods presentation: Stitch is already used as the compression module for all models reported in the paper. This includes our DreamCoder condition, which corresponds exactly to the proposed “Baseline A.” Specifically, we swapped out DreamCoder’s compression module to use Stitch while preserving the rest of the architecture. There were two motivations for this change:

(1) To improve the efficiency of the “sleep” phase: for even modestly-sized datasets (i.e., hundreds of programs), Stitch makes the difference between compression running in tens of seconds vs. tens of hours (see the performance benchmarks in [1]; we find similarly striking efficiency improvements on our domains).

(2) To facilitate direct comparability between LILO and DreamCoder and remove the possibility of the confound described here.

Thank you for highlighting for this oversight—this is precisely the kind of background assumption that would be difficult for the authors to catch in our own work. We promise to clarify this point in our updated submission!

Baseline B: LLM Solver + Search + Stitch

Proposal: This baseline is an extension of the existing LLM Solver (+ Search) condition, where Stitch is run on the final iteration. The motivation for this condition is to produce a library that can be evaluated in offline synthesis so as to isolate the effect of intermediate compression on performance. The reviewer states that if LILO were to outperform this ablation in offline synthesis, it would be a “strong mark in favor of the method.”

Response: We immediately saw the value of this proposal and ran this baseline over the weekend. For completeness/consistency with the online synthesis conditions, we also ran the analogous version of this baseline for the LLM Solver (no Search) condition, which we expect to be weaker than LLM Solver (+ Search).

After running the experiment, we can now confidently report that LILO outperforms both of these baselines by a good margin ($>1\sigma$) on all domains. As intended, the only implementational difference between LILO and the new LLM Solver (+ Search) baseline with post-hoc Stitch compression is the intermediate compression + documentation steps. Therefore, we agree that this result makes a strong argument in favor of performing library learning in-the-loop.

We have updated our submission with these new results (Table 1 and Figure 4)—please see the updated PDF! Thank you for this insightful suggestion—we certainly feel these new baselines strengthen the empirical claims of the paper and hope you feel similarly.

Additional experiments

Evaluating the quality of AutoDoc documentation against human experts.

We appreciated your suggestion to compare AutoDoc outputs against expert-generated documentation. Internally, we had discussed something similar as a follow-up to this paper and were inspired by your suggestion to start working on a limited version of this experiment. So far, we have manually corrected AutoDoc errors (e.g., the kind of issues highlighted in Fig. 5) and and are working on a head-to-head evaluation of downstream LLM-guided synthesis performance. We are not sure whether we will have something ready in time for the review response deadline, but will keep you posted.