Execution-guided within-prompt search for programming-by-example

Regarding your comment: "This section does not do a good job explaining the proposed technique clearly. [...]"

• We will add a leading example to the end of each component that clearly demonstrates how everything works together. Figure 1 contains almost all details, except for the implementation details in Section 4.1 and the fact that step 4 is simply a concatenation of step 3 to the initial prompt. We can extend this figure to include the prompt for the next iteration.

Regarding your comment: "There are also several poorly defined terms and inconsistencies in notation (defining what a policy, value, program, function, operation, etc. are). [...]"

• We apologize for some inconsistent use of terms like function and program that hindered in understanding our contribution. We will fix such issues. We hope the common response above helps in conveying the main ideas. We are mostly using the standard definitions of policy and value functions reinforcement learning. Program and operation are defined on line 164.
• We will indeed “close the loop” by adding a full example. The search space is represented exactly like in Figure 1. The prompt for the next iteration is obtained by simply concatenating the new (combined) operations, because all states are represented in one “super-state” of a bloated program.

Regarding your comment: "The evaluation in this paper is lacking. [...] At minimum, chain-of-thought prompting needs to be there, [...]."

• Note that our claim is not to perform better than any domain-specific approach. Our claim is that (1) language models perform better when they can reason about the intermediate results, and (2) language models can perform within prompt search. These claims result in a method that can be applied to any domain. We have significantly extended our evaluation with controlled experiments on other search strategies and adapted the “simple” strategies to generate-and-test with an aligned budget. Please see the general comment for more information.
• Regarding different models, initial exploration shows that the model does not perform well on smaller models, because they do not adhere to the specification, without fine-tuning for the operation completion task. We leave this as future work, and will make this limitation explicit.

Regarding your comment: "I do like the diversity of the datasets being evaluated. However, I would like more details about the benchmarks and why they were chosen: what are the challenges that each benchmark provides? How many examples do you need to give, and is it different for each benchmark? what language is each benchmark targeting? etc. "

• They were chosen to represent different domains, from common string transformation benchmarks (PROSE, PlayGol and SyGuS) to benchmarks where the task is sometimes very hard to understand (Lists and MBPP). MBPP was specifically added to highlight the DSL-free aspect of synthesis with LLMs. Besides MBPP, none of these benchmarks target a specific language. We targeted Python.

Regarding your comment: "The metrics are not defined properly. First, the pass@k metric has a very specific definition already established in the Codex paper[1]. This metric samples the top k responses from an LLM and measures the probability of at least one sample being correct. That means the metric used in the paper is more like pass@8 (since it is considering 8 responses, but I am not sure if that is necessarily the top-8 responses), or equivalently pass@3. I would like to know the results for different values of k for all baselines with and without search and execution. I also don't think all@3 metric has been defined, nor has the notation being used in 4.3 (line 307/308) been defined."

• To compute pass@k, we need to sample N > k completions and then compute the probability that any subset of k completions contains at least one correct one. If N = k, as you suggest, this collapses to 0 (none is correct) or 1 (one is correct). We set N = 8 and k = 1 to compute pass@1, estimated over 8 completions (simple baselines) and 3 repetitions (anything with iterations).
• We have updated the metrics to reflect the budget that each method requires. For example, getting 4 completions at each iteration essentially generates 4 programs in total, so we would compare the pass@1 rate of our method with the pass@4 rate of the “simple” baseline. See the general comment for more information.
• We note that the notation (n k) is standard notation for the binomial coefficient of “n choose k,” but we have removed the all@3 results.

def pass_at_k(n, c, k):
  """
  :param n: total number of samples
  :param c: number of correct samples
  :param k: k in pass@$k$
  """
  if n - c < k: return 1.0
  return 1.0 - np.prod(1.0 - k /
    np.arange(n - c + 1, n + 1))

Thank you for your review.

Regarding your comment: "There is a simple LLM PBE baseline: [...]"

• Note that our claim is not to perform better than any domain-specific approach. Our claim is that (1) language models perform better when they can reason about the intermediate results, and (2) language models can perform within prompt search. These claims result in a method that can be applied to any domain.
• As outlined in the common response, we will extend the “simple” baseline to a generate-and-test strategy with the same budget as our approach. We will also add results on more generic baselines—such as chain-of-thought, self-debugging and tree-of-thought (out-of-prompt search). See the general comment for more information about additional experiments.

Regarding your comment: "The paper only uses one model to perform experiments (GPT-4). [...]"

• Empirical, small-scale experiments show that the approach does not work for smaller (weaker) models, because they are not as capable at following the straight-line instruction. We will highlight this limitation in the paper. Fine-tuning a small model as a better policy on synthetic data [2] remains future work, and we will add it as such.
• [2] [2406.08316] Is Programming by Example solved by LLMs?

Regarding your question: "It is not clear how the LLM determines which states (partial programs) to expand. [...] Are all the partial programs being expanded with k actions in the default policy setting?"

• All partial programs are simply represented by one big "bloated" program. For example, in Figure 1, the three operations left after de-duplication and canonicalization are simply concatenated to the previous program to obtain the prompt for next iteration.The model can then choose which variables to use, which corresponds to choosing which nodes to expand. In fact, the model can choose not to use any of the newly added v3, v4, v5 variables, which will correspond to (implicit) backtracking. We will add a full example (that builds on Figure 1) to the end of each section.

Regarding your comment: "Can you clarify the mechanism of backtracking? [...] How is the pruning parameter k set?"

• Backtracking is implicit: we did not use any explicit pruning. A backtrack is simply discarding all previous operations and restarting with the arguments. For example, generating “v9 = a + b” is considered a backtrack, because it is ignoring all values v1 – v8 and “starting from scratch.” We will add a concrete example of backtracking to the paper.

Regarding your question: "How do you ensure that there are no statements with side effects modifying the states, e.g., v3 = (v2=1) then v2 is modified?"

• We do not have such a check in place. We extract the values from the final state, so any side-effects should be captured.

We have considered different methods, but there are some challenges associated with each of them.

• Input tokens are cheaper and affected by caching. WPS allows a lot of caching (the prompt strictly grows) and is sparing on the output, ToT allows the same caching on the program prompt but no caching on the value prompt, and self-debug allows the least caching.
• To compute aligned pass@k rates between methods, the ratio between their token usage has to be a whole number, or we need to compute enough iterations to approximate their LCM (i.e., if approach A uses 2.5 as many tokens as approach B, we'd have to compare pass@2 versus pass@5, which requires many iterations to complete).

Instead of aligning pass@k rate, an alternative is to look at pass@1 rate versus token usage. In the following image, this is plotted for WPS and ToT, which reinforces our finding that WPS is token-efficient and ToT scales better for a bigger budget: https://i.imgur.com/1NsSIXL.png (different data points for same approach and dataset correspond to k = 2, 4 and 8). But: this comparison is not very informative between search and non-search methods, as the latter have lower pass@1 rates for much lower token usage.

We therefore proposed to introduce the aligned pass@k as a metric that can be used across approaches, trading off a slight imbalance in token use for ease-of-use across experiments and being budget friendly (we can scale to the "most expensive" approach).

The output tokens are compared between WPS and ToT in Figure 5, showing that the aligned metric between them seems fair (potentially slightly favoring ToT). In Figure 4, we use the pass@1 rate to indicate that the value function for ToT scales better for k. This figure contains roughly the same information as the above image, but then in function of a concrete hyperparameter.

We find that GPT-4 can generate correct programs for 94.3% of the SyGuS tasks using 8 programs with two rounds of feedback without hypothesis generation, demonstrating strong performance in a direct program generation approach

Thank you for the review. Here we answer the specific questions raised in the review (beyond what we have discussed in the common response above.)

Regarding your comment that semantic annotations can grow exponentially, you are correct that even though the length of the program only grows linearly in terms of the number of iterations, there is a “risk” of intermediate execution results growing very large. This is not very common and has not happened in our experiments. For completeness, we propose to perform an analysis of the prompt size: (1) the number of tokens consumed by code and comments and (2) the probability of generating a correct line as a function of the size of the prompt.

Regarding your comment: "The baselines, [...], may not fully highlight the method's advantages. Incorporating other PBE or LLM-based synthesis techniques with integrated search mechanisms could be helpful." As mentioned in the common response, we will add the following outside-prompt search baselines:

• Tree-of-thought, which corresponds to your suggestion of the model explicitly picking an operation at each iteration (explicit value function).
• Self-debug loop, where we use the conversational paradigm of language models to provide execution results (or exceptions) until a correct program is found. Note that a key feature of within-prompt search is reducing the number of tokens required to perform the search, so we will consider a similar budget for all baselines. See the general comment for more information. Comparing with domain-specific PBE solvers is not in scope as it is orthogonal to the point of the paper.

Regarding your comment: "The paper's within-prompt search mechanism utilizes an implicit backtracking method, but it’s unclear how effectively this avoids redundant or cyclic paths, which could degrade efficiency. "

• Cyclic paths are avoided by pruning semantically equivalent operations: if v6 has the same outputs as v1, then v6 is removed. We don’t explicitly handle redundant paths, but we assume that the model will simply ignore nodes that it thinks are not useful.

Regarding your question: Does this approach work only for imperative programming? It seems it might be more suited for functional or recursive code structures.

• The main requirement is being able to execute partial code, so it requires a “bottom-up” paradigm. An extension can be made to functional programming, where we ask the model to generate and combine functions and provide intermediate outputs on the function level—we leave this as future work. Recursive structures only execute once a base case is reached, which does not allow intermediate results to be shown. Whereas the scope of programming style has some constraints, there are other applications of within-prompt search with execution, for example, program repair, auto-completion or code generation from only natural language and inputs. The “challenge” is replacing the soundness check during the search with another stopping criterion, for example, asking the model to output a [STOP] token. We will add this to future work.

Regarding the question: In Line 244, you mention, “We remove any duplicate lines of code based on their execution results.” Does this apply even if lines are syntactically or semantically different beyond the given examples? Could this lead to false negatives in your experiments?

• We only use the examples given. Technically, it can thus happen that lines that are not identical (on inputs outside of the given examples) are removed, which can negatively affect performance. One way to guard against this is to use execution based on the examples and any additional inputs that are available. In this paper, like previous work, we assume that all examples are given [1].
• [1] [2309.05660] Hypothesis Search: Inductive Reasoning with Language Models

Regarding the question: "Does your approach inherently favor simpler solutions, or can it dynamically adjust priorities based on feedback? Can you do an analysis on the complexity of the synthesized programs? "

• This is an interesting question. Because we check each operation for soundness on the given examples, it is arguably more “breadth first” than generating a straight-line program. We will compare the (canonical) program length of the “Straight” and “WPS” approach to see if we find simpler programs.

We truly appreciate your suggestion for comparing within-prompt search with outside-prompt search. As mentioned in the common response above, and as can be seen in the revised PDF, we add the following outside-prompt search baselines:

• Tree-of-thought, which corresponds to your suggestion of the model explicitly picking an operation at each iteration (explicit value function).
• Counter-example guided loop, where we use the conversational paradigm of language models to provide execution results (or exceptions) until a correct program is found (up to some number of iterations). We additionally sample N programs at each iteration and pick the one with the fewest errors for the next round (roughly turning the search into a beam search of code repair).

The new evaluation shows that our "within-prompt search" is the best choice when we give a similar output-token budget for all baselines. Tree-of-thought can perform better, but only when it is given a higher output-token budget. Please see the general comment and revised PDF for more information.

Regarding your comment: "While I agree that the LLM is certainly a policy (it's sampling the next action), this explanation confused me. [...] Maybe the authors meant it behaves like a certain kind of policy?"

• We agree here. Technically any function that returns an operation is a policy. We mean that it behaves like a “trained” policy that actually prefers operations that are more likely to have a high value. We will make this explicit.

Regarding your comment: "I also agree that the model is implicitly acting as a value function, [...] As a thought on an experiment that might show larger differences, it'd be interesting to see whether something like only giving it 2 unique options and jumping up to 4 or 6 unique options would have a bigger improvement (and not focusing on the unique vs nonunique distinction). "

• Because the model continues sampling until it finds 4 unique operations, this shifts the distribution to having more low-quality operations (as a kind of rejection sampling). We have carried out an experiment for 2, 4 and 8 operations, both in a diverse and non-diverse settings, and show that (1) the implicit value function remains effective, but (2) an explicit value function (ToT) scales better for higher k.

Regarding your comment: "I think that Figures 2a and 2b would likely be better as bar plots instead of a line plots, since the X axis is categorical data not a continuous metric. "

• We have added separate figures for comparison with baselines (new figure) and ablations (current figure 2a and 2b) and change them into bar-plots.

Regarding your comment: "Figure 3 might be better as a heatmap since it's discrete data so arbitrary points aren't needed, and it would help the problem where the density of points is so high that many just look like solid red bars and it's hard to compare them."

• We have updated to a heatmap-style plot.

Regarding your comment: "The approach is limited to working with straightline code – but could perhaps be extended [...]"

• This is indeed an interesting direction that we will leave for future work (and explicitly mention as future work). The challenges to be solved are how to represent the intermediate values for control flow statements. But we note here that straight-line code is very expressive in Python, with functions like itertools.count even supporting infinite loops (we allow functions from the standard library) and the “x if condition else y” construct supporting conditions.

Regarding your comment: "The statements about soundness guarantees in the abstract are confusing – [...] – that doesn't change the soundness in my understanding."

• That is correct. We meant (and have clarified) that building a program line-by-line with execution results is a more efficient way of obtaining a sound program than rejection sampling.

Regarding your comment: "This first line of the contribution list is not itself a contribution of the paper to the field since it's shared by other LLMs synthesis work – it's a feature of the second line (execution-guided within-prompt search) "

• This is a good point; we have updated the contributions accordingly.

Questions

Regarding your question: "Is the "8 iteration" limit used for the "Free" and "Straight" settings too? In particular I want to make sure they're not also restricted to only producing 8 lines, which would limit them compared to the "search" based models that are allowed to use more than one line from a single iteration in their solution."

• No, in free and straight the model can just generate one large program without any limitations on program length (max tokens is set to 2048). We have removed free-form generation from the controlled experiments since it was difficult to account for token budgets there. We will added separate results on free-form code generation and use it to motivate more future work.