Execution-guided within-prompt search for programming-by-example
Authors: Gust Verbruggen
Ashish Tiwari
Mukul Singh
Vu Le
Sumit Gulwani
Venue: ICLR 2025 Poster (2025)
Keywords: programming-by-example
program synthesis
large language models
Primary area: applications to computer vision, audio, language, and other modalities
TL;DR: We propose to sample, combine and execute different lines of code from large language models to perform an execution-guided search for correct programs within one prompt.

Abstract: Large language models (LLMs) can generate code from examples without being limited to a DSL, but they lack search, as sampled programs are independent.
In this paper, we use an LLM as a policy that generates lines of code and then join these lines of code to let the LLM implicitly estimate the value of each of these lines in its next iteration.
We further guide the policy and value estimation by executing each line and annotating it with its results on the given examples. 
This allows us to search for programs within a single (expanding) prompt until a sound program is found, by letting the policy reason in both the syntactic (code) and semantic (execution) space.
We evaluate within-prompt search on straight-line Python code generation using five benchmarks across different domains (strings, lists, and arbitrary Python programming problems).
We show that the model uses the execution results to guide the search and that within-prompt search performs well at low token budgets.
We also analyze how the model behaves as a policy and value, show that it can parallelize the search, and that it can implicitly backtrack over earlier generations.

Published as a conference paper at ICLR 2025
EXECUTION-GUIDER WITHIN-PROMPT SEARCH FOR
PROGRAMMING-BY-EXAMPLI
Gust Verbruggen
Ashish Tiwari, Mukul Singh, Vu Le & Sumit Gulwani
Microsoft
Microsoft Redmond, USA
Keerbergen, Belgium
everbruggenenicroooff... com
(ashish. tiwari, singhmukul, sumi tg | @mi crwsoft..ccomm
ABSTRACT
Large language models (LLMs) can generate code from examples without being limited to a DSL, but they lack search, as sampled programs are independent. this paper,
LLM policy that generates lines of code and then join these lines of code to let the LLM implicitly estimate the value of each of these lines in its next iteration. We further guide the policy and value estimation by executing each line and annotating it with its results on the given examples. This allows to search for programs within single (expanding) prompt until sound program is found, by letting the policy reason in both the syntactic (code) and semantic (execution) space. We evaluate within- within-prompt search on straight-line Python code generation using five benchmarks across different domains (strings, lists, and arbitrary Python programming problems). We show that the model uses the execution results to guide the search and that within- authin-prompt search performs well low token budgets. We also analyze how the model behaves as a policy and value, show that it can parallelize the search, and that it can implicitly backtrack over earlier generations.
INTRODUCTION
Automatically synthesizing code from any form of intent or specification is considered as a holy grail computer science (Gulwani al. 2017). One particularly challenging specification are of inputs and their expected outputs, as the synthesizer has to not only detect pattern between the input and the output, but also write code for Large language models (LLMs) (Brown al. 2020) OpenAl 2024) are trained to recognize patterns in text to predict the most likely next token. Their training data contains significant amounts of code (Xu et al. 2022) and examples of how to use that code, both through tutorials and unit tests.
Consider, for example, a prompt that consists of two assert statements and a function signature:
assert f(a Program Synthesiss ") = 'PS" assert f(a "Large -Langugee -Moeel' ') 'LLM'
def f(a):
Different versions of the gpt model series by OpenAl (4o, 4-turbo, 35-turbo) complete it with variation return " [.join(i for i in split(('-))) make f satisfy the assertions
When the patterns become model overfitting on a dominant (more common) pattern the assertions. If we change the second notice that gpt-4o does not change its answer, a string with results in empty strings. The model then only considers the syntactic space, rather than reasoning about the semantics of the program. A second reason that iteratively sampling tokens does not allow the model to reconsider earlier code like a human would do. Once the model has written return '.join(i[0] for in a. split()) -even if it would now
complicated, however, the LLM often fails. A first reason is the
input to "Large-LLaggugg--Moon that splitting on
realizing
At temperature 0, which for all demonstrations.

---

Published as a conference paper at ICLR 2025
realize that can be empty- cannot easily recover. The model is thus not able to search for correct program, and search is indispensable in symbolic synthesizers (Gulwani et al. (017).
We tackle the limitation search by sampling multiple lines of code, combining them into single program, and implicitly letting the model choose which these lines to continue from in a next iteration. We call this withinn-rompp search as prompt contains all states explored so far. We tackle the limitation on reasoning about semantics by executing generated code and providing these executions comments to the model. The model then has access both the syntax and semanties of the program, and the within-prompt search is thus execution-guidel
Considering the previous example and appropriately prompting the model to generate options for the next line of code, the model generates three unique statements:
v1 a. split( --)
v1 a. split(p [e][a]]
a[0]
These statements are de-duplicated and executed to yield new prompt for the next iteration:
assert f(a Program Synthesis == 'PS" # el
assert f(a "Large-- -Model 'LLM" e2
def f(a):
# ('el': : ['Program' 'Synthesis" 'J, e2 ['Large', 'Language" ", 'Model ']] v2 a[o] C'el': 'p', 'e2; 'L'3
v1 a. split('-))
The model now completes it with v3 = [word[] for word in v1 if word))
Relating this to existing neural program synthesizers, we observe that the model acts as both policy-by generating candidate lines-and value-by choosing which previous lines consider the result of-by looking at both syntax and semantics of generated code. Core differences are that not limited can be used on string transformations (Gulwani 2011) and lists (Rule al. 2024 without any intervention-and does not require any training.
domain-specitn language or even a specific domain the same method
We evaluate the effect of within promin search and execution-guidance on straight-line program synthesis on five benchmarks spanning three domains (string transformations, list functions, and generic Python programming problems). We provide insights in how the model performs policy and value, evaluate the effect more diversity sampling lines of code, and compare with a baseline of unrestricted synthesis.
In summary, we make the following contributions:
We propose execution- guided allows the model reason about the semantics of lines of code while exploring different candidate programs.
search for programming ceatammiinn-----eampe by-exapple, which
We introduce the adapted pass @ rate to evaluate our approach and different baselines on five datasets across various domains.
We analyze properties of the model as a policy and value, show the value of execution, show that out-of-prompt search (which corresponds to tree-of-thought) scales better with more operations being sampled, show that the model can parallelize the search, and show that it can backtrack to earlier programs.
BACKGROUND
Given n input-output examples E {(x;, y/) 1i)) ) the goal of boggramming-by-exaaee find a program P such that P(x;) = yı for all i. Typically, only small subset of examples E, E is given. We say that P is sound if P(x;) ) = yı for all (x;, M.) E E, and we write P P= Eg-
(PBE) is to
It could still add if 1-- not in else
the end of the line, but witnessed this.
2

---

Published as a conference paper at ICLR 2025
Extend prompt for next iteration.
When you create variable, add comment.
assert f(a '1 3', 32) '13" el
def b):
v1 = a[0] # "el"; "1" a.split() { "el": ["1,, "2", "3*] }
}
Model looks at previous nodes and thus acts as value v.
Model predicts production rules in the language
(Python) grammar and thus as policy
v3 b.split()[-1]
v3 b.split()
v3 = b[4]
v3 b. b.sp)it()[o]
Combine, de-duplicate and canonicalize code.
v3 b.split()
"el": [*2%, "3"]
Extract and annotate variable valbes.
v3[-1]
"ei": "3"
v5 v3[0]
# "ei": "2"
Figure I: Overview of our approach for PBE with large language models. ! The model acts as policy by predicting next lines of code. 2 We combine, de-duplicate and canonicalize that code in order for the model to act as a value predictor. 3 We execute code, extract values and add them as comments, We extend the prompt with the newly generated code.
PBE with search Constraining P domain- specifcc language (DSL) defined by a context- free grammar allows us to easily-and and sometimes even Seiciently-searde for programs. FlashFill, likely the most popular application of PBE, traverses its grammar top-down by breaking down the original problem into smaller sub-problems and recursively solving them (Gulwani 2011)) Recent neural approaches perform bottom-up search by using a policy network to prediet one or more production rules to follow, which either initialize new sub-program (terminal) or combine two subprograms (non-terminal) (Parisotto et al., 2017: Balog et al., 2017] Ellis et al. [2018] 202 Odena et al. 2021| Chen et al. 2018). Optionally, separate value network can be used prioritize or filter candidates in subsequent iterations Ellis et al. (2019).
PBE with execution Since each node in a bottom- up search is a program without free variables, can be executed, and those execution results are powerful signal for predictions in subsequent search steps. One approach is to add the current execution state as additional input to the model (Ellis et al.) 2019). Another approach is to use the execution of candidate program P' define new problem specification (x,() 36) (x,, y.) Eg } for the next iteration (Chen al. 2018
PBE with large language models Instead of searching over grammar, some neural approaches generate programs by having the model directly predict tokens from the alphabet of the DSL (Devlin) al. 2017 Bunel et 2018). 8) Pre-trained language models also auto-regressively generate tokens and typically see lot of code during training (OpenAl 2024). They can be prompted or fine-tuned Ellis 2024) generate programs by example, without being limited DSL.
3
EXECUTION-GUIDED WITHIN- SEARCH
We propose to use large language models as both the (explicit) policy and (implicit) value network to search for code in bottom-up way, and inject the execution results of that code to guide the model towards better predictions. An overview of this approach is shown in Figure The following sections describe (1) how the model acts policy, (2) how to prepare that code for the model to implicitly consider the value of each line, (3) how to guide these results by executing the generated code, and (4) how this constitutes an in-prompt search.
3

---

Published as a conference paper at ICLR 2025
3.1 POLICY: PREDICTING LINES OF CODE
Consider function P(x) [ot,.... on where each operation 03(0 x) is function of the outputs of the previous operations oc; and the input x that returns a single value (denoted as o,). The value of On is the return value. An operation can be drawn from the grammar of any programming language.
Encoding the specification given by Fg and a partial program P, [o1.....00) 03] in a prompt, we can sample new operation 02-1 PLLM(- Eg P3 t) from the LLM with & the sampling temperature (Ackley et al., 1985). If the temperature is set to O, the model acts as a deterministic policy that maps each state gEg Pÿ) to its most likely next operation 0j+1. For higher temperatures, it acts as stochastic policy that maps (Eg. P2) to a distribution of operations.
Instead of learned policy the model is prompted to find arg max [QT PJ-1)] where the value Q" (oj, P3-1) of considering an operation 0j in program PJ-1 the expectation that it can be completed into a valid program, or Q(oj. Pj-1) = Ep,-- [P]- 0j Pr } Egl where P, is sequence of operations sampled from the (prompted) policy.
Example The specification Eg and program P2 are en- coded in the prompt on the right. An LLM will auto- complete this program with new statements
f(a ''', b 3')
0g splittO[[11
o = b. split(
def f(a, b):
v1 a[6]
v2 a.split() } P2
Eg
og = b[4]
0g = b. split(()
v3
that correspond to operations.
3.2
VALUE: COMBINING LINES OF CODE
Suppose we sample & operations Oj+1 fo of of+13 from the language model with O. Instead of heuristically picking one operation 0;+1 E Oj+1 to extend P; before sampling the next operation- -erittiionniiiiinggggggee such heuristic hard even without considering the different types of values that each operation can return-ttaeeeee we set Pj+ [c, o 0 with k' < k and let the model act as that heuristic the next iteration (where denotes operation concatenation). Here, fc is function that de-duplicates and canonicalizes the given operations, resulting in a potential subset k' of the k new operations to added.
Instead of a single program, P3 then represents all programs explored in all iterations S J. where each operation can be considered as its own root node. When writing an operation 0s+1, the model needs to select some nodes o, P3 to continue from. Ideally, it selects operations that are expected to lead to a correct program by implicitly considering (o.) = Egow IQ" (o, P:)] to estimate the expected value of each operation o E P,. We call this withit-prompt search (WPS) as the search happens within one prompt that is iteratively extended.
Example 2 Continuing the example, the implicit value function assigns high score to b, as it used in all operations. Since o does not execute, is removed. Operation o is subprogram of ob and og and the substitution of = og (r].spit(([[- and of oz split (alit([() [)] made by fc. P3 is shown on the right. The value function can decide which state to continue from in the next iteration.
def f(a, b):
a[0]
a.split()
v3 b.split()
v4 v3[-1]
v3[0]
We can also use the model of+1 E Oj+1 and getting i next states pr 1 P, Po that we can explicitly search over based on their value. This corresponds to Tree-of- to thought decompositions, the policy corresponding to the thought generator and the value prompt being the state evaluator.
explicit value function by using separate prompt to rank each
(Yao et al., (2224) with lines of code corresponding
3.3 GUIDANCE: EXECUTING CODE
Understanding the execution semantics of P, is crucial when deciding on a next operation 0:41
especially since the specification E, is in this semantic space. Previous work (Ellis et al.) 2019) has shown that executing code [P]]] = [[((x) x E Eg) on the given examples E, and conditioning the policy and value ([3)), F.y) instead of (Pz, F.g) allows them make better decisions in
4

---

Published as a conference paper at ICLR 2025
this semantic (execution) space. The intuition is to mimic human developer using code printing statements to evaluate their progress so far, and then make decisions based on that progress.
We extend this idea our prompted policy and, LLMs have shown strong code understanding capabilities, additionally allow the model to make decisions based on both the semantic and syntactic representation of Pj- Instead of only the final output [P we obtain the value of each operation o E P, on the given examples and add [O,] = ffo(x) x E E o DEE O,} to the condition of our policy-to the prompt.
Example 3 Before sampling new operations, we execute Ps. and annotate each line (operation) with output on the given input (e1) to allow reasoning about both the syntax (code) and semantics (output) of the current states.
def f(a, b):
a[e] "eit:
a.slit)) "et"s [15 125, "97)
b.spitt)) 4 122%, 199)
vs va(e] # "et": "2"
3.4 SEARCH
Sampling multiple operations Oj and combining them into new state (Fg. PJ+1, [O++1] allows us to perform within-prompt search. Each state (program) in the search is combined into a single superstate, which the model can expand. We stop the search when or + Eg for any or E P3 and remove all operations that are not used by ot- We can keep expanding the state until the context window of the LLM is reached and rely on implicit backtracking where the (implicit) value function simply ignores operations that cannot lead to valid program.
Example 4 Instead of keeping track of different states, the "search" consists of single prompt (superstate) that is iteratively expanded (for I iterations).
2
b): w.spiset)
f(o, b0:
def fia, b):
def afo] v n. s.spisr)) F
bisplic()
m.spies b.splic))
vi[-1)
v2(D]
EXPERIMENTS
We evaluate the effect of execution and search, show insights in how the model behaves as policy and value, and describe other properties of the search.
4.1 IMPLEMENTATION DETAILS
We use Python as the programming language in which synthesize programs.
Prompt The prompt consists of four parts: (1) an instruction, (2) a single static example, (3) set of assertions on a function f, and (4) the function f itself. The instruction instructs to generate code without control flow statements, that any function from the standard library can used, that it can variables as a scratchpad, and create comment each time new variable is initialized. The example contains one line that is not nceded. We initialize each line with " v" to ensure that the model generates straight-line program with variables (v1, v2. the model tokenizes digits separately- v1 is always broken down into and 1. A full example is shown the Appendix
Sampling operations As the model is instructed to generate each statement single line, can sample single operation by using the newline character "\nn" as stopping token. Operations that do not parse execute skipped.
Canonicalization After ensuring that each generated line of code assigns its value to a unique variable, concatenate these lines and perform global canonicalization steps. All comparisons made on the abstract syntax tree (AST) level.
1. For every assignment and ensure that the lines remain topologically sorted.
r, we replace any occurrence of r in another operation with
"See the supplementary material.
5

---

Published as a conference paper at ICLR 2025
2. For every assignment where is generator, which does not have pretty printing implementation due to lazy execution semantics, we wrap in a list call as v list
3. We remove any duplicate lines of code based on their execution results.
Execution and comments We assign assertion assert f(x1) y1 unique identifier e1 comment "# e1". This allows us to easily anchor the execution result of each operation v r(x) on to that identifier in a dictionary by mapping "e1": r(x1) J. Ensuring that each value can be printed done in the canonicalization step to not have a disconnect between the operation and the commented values.
Search The search stops when any of the variable results matches the assertions or when limit on the number of iterations is reached.
4.2 EXPERIMENTAL SETUP
Datasets We use five popular datasets that span different domains. No changes are required to apply our approach to these different datasets.
PROSE (Microsoft) is of 354 benchmarks originally used evaluate FlashFill Gul-
wani (2011) first widely adapted application of PBE. We filter it down to 332 non- trivial problems (no empty values, three more examples).
SyGuS (Alur et al.) 2019) is set of 205 benchmarks from the string transformation track of the SyGuS Alur et al. 2013) competition.
Playgol (ropper 2019)
set of 327 benchmarks from inductive logic programming.
Lists (Rule et al.
2024) is dataset of 251 list understanding problems, where each task
transforms a list of integers.
MBPP (Austin et al. 2021) is a dataset of basic Python problems, where each problem consists of both a description in natural language and set of assertions. These assertions are given as part of the input, mostly to provide any synthesizer with information about the expected signature of the function to be synthesized. We only any that are not simply evaluating f(x) == y with x E x and y constants that can be evaluated with eval without additional imports and that are json serializable (no set, no datetime). Across the train and test set, this leaves us with 382 problems.
the assertions, remove
To save on cost of prompting for experiments, we filter trivial benchmarks by using simple prompt conditioned on the first example (X1: y1) E F. to sample five programs pi at = 0.6 and do not include a benchmark if pi }= E' for all of them. This leaves 238 benchmarks from PROSE, 94 benchmarks for SyGus, 170 benchmarks for Playgol, 211 for Lists, and 268 for MBPP.
Hyperparameters Unless specified otherwise, we sample k = 4 operations at each line at a temperature of 0.6, which is common value that achieves nice balance between exploration and exploitation. The model is gpt-4o. We set the maximal number of iterations to 8.
Baselines and variations
We consider four baselines on the task of straight- line code generation.
Straight directly asks the model to generate the code.
Chain-of-thought (CoT) (Wei et al. 2022) asks the model to first explain its thoughts and then generate code. This does not use any execution feedback or search.
Self-debug (Chen al. 2023 Wang al., 2024) executes the code the examples and iteratively asks the model to refine based on the outcome. When an exception is thrown, only exceptions
shown. When no exception is thrown, all wrong outputs are reported as fx) = y' (expected y). We only show the last iteration to the model, so any prompt in iteration i > is structured [system, user;, assistant;-1. user;-1] with assistant;-1 program after i --1 iterations and user,-1 the feedback on that program. We use 8 iterations.
Tree-of-Thougee (ToT) Yao et al. 2024) uses an explicit value prompt to perform a search. As opposed to within-prompt search, this perform outside-prompt search.

---

Published as a conference paper at ICLR 2025
The value prompt asks the model to reason about each line (including its execution) and rate it with sure, maybe or impossible (like the original ToT). Nodes are scored by value their last line first and depth second, meaning that the search backjumps to the last unexplored node in which the last line has the highest score.
The pass @ rate rate- the probability that at least one out of samples correct- is a common metric in code generation (Chen et al. 2021a). Because each method implicitly generates different number of programs to arrive at one completion, we compute the aligned pass@ 8 rate. For example, straight only generates one program per completion, but rithin-prompp search generates 4 programs with = 4, so we compare their pass@4 and pass@) rates, respectively. This corresponds to using generate-and-test strategy for cheaper methods until the same budget is reached. We set the budget to 8 and align the metrics as follows. Straight: pass @ over 32 completions. CoT: pass @4 (the thought counts one program, despite consuming significantly more tokens) over 16 completions. Self-debug: pass@) I repeated over 4 folds. ToT: pass (the value prompt counts as one program as it includes reasoning) repeated over folds. WPS: pass @2 repeated over 4 folds.
Metries
4.3 RESULTS
Search and execution yields better programs. Figure 2 shows the aligned pass@4 rate of straight-line code generation with search, execution, and both. Execution without search is done k with temperature 0 and is thus deterministic (pass @ 1). Without execution, the implicit value function does not help the model select better completions, and the performance is similar to straight-line code generation. With execution and search, within- prommpt search (pass@) allows the model to perform better than the generate and-tesst strategy (pass @:4) in 4 out of 5 benchmarks. On the Lists benchmark, where the problem statement less clear from looking at examples, generating candidates as a single program is more effective than trying to reason about the intermediate values.
Within-prompt search generates good code on budget. Figure 3 shows the aligned pass @8 of all approaches. Within-prompt search is either the best (3/5) or second-best (2/5) generation strategy. SyGus has a set of similar problems with long strings, where different variations of splitting are generated in the first iteration, which results many small value tokens that confuse WPS. By reasoning about which is the correct split, ToT performs better at these. Conversely, on Lists, it is often less clear what the problem is, and either trying different things (WPS) or getting directed, end-to-end feedback (self-debug) perform better. Thinking about the problem (CoT) or generate- and-test strategy (straight) are also effective.
0.8
Stright
Search
0.7
Execution
0.9
aligned passted
0.6
WPS
aligned p
0.8
Approuch
Straight CoT
0.5
Self-dehug
0.4
0.6
ToT
WPS
0.3
0.5
0,2
SyGuS
FlushFill
Playgol
Lists
MBPP
0.4
Playgel
SyGus
FlashFill
Lists
MBPP
Figure 2: Without execution results, search (pass@1) does not improve over straight-line code generation (pass@4). Execution helps both without search (deterministic pass@) 1) and especially if the model can perform within- prompt search (pass@1)
Figure 3: straight-line code generation. Within-prompt search (WPS) is consistently among the top- performers, achieving best scores 3/5 bench- marks.
Comparing different baselines on
Explicit value prompt scales better with number of operations. Figure pass@ @ 1 changes in function of the number of lines sampled for
shows how the we sampled lines
7

---

Published as a conference paper at ICLR 2025
with increasing temperature until exactly & syntactically unique lines are obtained and default sampling strategy. First, we observe that in most settings, performance improves with k. showing that the model can serve both an explicit (ToT) and implicit (WPS) value function. Second, observe that for the same k; the explicit policy (with higher budget) performs better, especially as k increases. The number of choices scales linearly with the iteration i, and the number of tokens scales as n with the number of examples, both of which make the problem of selecting good nodes more difficult.
Diverse
Non-diverse
0.9
Benchmark
SyGuS
0.8
FlashFill
2000
4
0.7
Playgol
pass
Lists
Tokens
1500
Approach
0.6
MBPP
1000
WPS
Approach
ToT
ToT
500
0.4
WPS
2
4 k
2
8
2
Iterations
Figure 4: pass@1 in function of & for diverse (left) and non- diverse (right) policy. Explicitly computing the value of new lines (ToT) scales better with increasing the number of op- erations.
Figure 5: Number of emitted to-
kens in function of number of it- erations for different k. The plicit value function (ToT) requires roughly twice the amount of to- kens.
Prompted model behaves trained policy Tigure/]shove the correctness in function of the average number of statements sampled in the first or any iteration by the policy. There a clear negative correlation: if the policy is certain and samples with less diversity, the model is more likely to solve a problem in the end. Conversely, if the policy samples many diverse lines, it is less likely solve the problem in the end. This indicates that the model does behave like a policy that was trained to prefer lines with higher values.
ToT
WPS
ToT
WPS
1.0
1.0
Benehmark
Beachmark
Lists
Lists
Carret
0.6
MBPP
Concet
MBPP
Phayool
Playgol
0.4
SyGuS
0.4
SyGuS
0.0
0.0
3
2
Average (sstatements)
Average #(statements)
(a) all iterations
(b) first iteration
Figure 6: Regression lines and 95% confidence interval of pass@) I rate in function of the average number of unique operations sampled in (a) any or (b) the first iteration. The first operation (b) less important, as there is still room to recover.
Within-prompt search works in parallel Figure 7 shows the number iterations required to find a successful program of a given length. Some of the weight is above the identity line, where the final program uses two or more nodes from the same iteration at least once. The stochastic policy thus allows wrthin-prompt search to consider different leaf nodes in parallel. This is confirmed
8

---

Published as a conference paper at ICLR 2025
by Figure 8 which shows distribution of the number of iterations taken to solve success Within-prompt search solves more of its cases in fewer iterations.
WPS
To1
0.4
WPS
11
11
ToT
0.3
Lines of code
7
7
0.2
0.1
3
3
0.0
1 2 3 4 6 Iterations
2 3 4 Iterations
7 8
2
7
Iterations
Figure 7: Length of successful programs versus the iteration in which they were found for WPS (left) and ToT (right). Above the line, the policy returned multiple operations that were used in the final program. Below the line, the policy either failed to generate any new results or the value back- tracked and completely ignored the results from one iteration.
Figure 8: Distributions of num- ber of iterations to solve prob- lems for WPS and ToT. Paral- lelism in within-prompt search al- lows problems to be solved in fewer iterations.
Within-prompt search can backtrack Cases below the line in Figure g have iterations without any effect: either the policy failed to generate (valid) new line or the value function backtracked and completely ignored the results from one iteration. Figure / shows how often ToT explicitly backtracked and how often ToT and WPS implicitly backtracked, where an implicit backtrack is
defined as an iteration that did not yield any operations that were kept in the final program.
0.100
0.100
0.100
FlashFill
Lists
Proportion
0.075
Proportion
0.075
Proportion
0.075
MBPP
Playgol
0.050
0.050
0.050
SyGuS
0.025
0.025
0.025
0.000
0.000
0.000
2
5
2
3
(a) ToT: implicit
(b) ToT: explicit
(c) WPS: implicit
Figure 9: (a) Implicit and (b) explicit backtracking for ToT, and implicit (c) backtracking for WPS in successful solves. In general, backtracking quite rare, happening in around 10% of problems. It happens slightly more for WPS, where having more nodes to choose from causes more dead ends.
Example 5 On the problem of determining whether two lists contain the same number of elements, the model takes three iterations (with many duplicate lines) to figure out that does simply need to compare the lengths of the inputs. In the fourth iteration, it immediately suggests the correct line, backtracking over iterations (2) and (3).
assert #ll"n'. 'g'=1 ['at, 'b"1) assert f(l"m", "flala [fa") '6"1) False
F(a, b):
len(s) tells 2, "62":
(2) v2 lon(b) f "es"s 2, "62"s
v3 v2 { "Mi"s True, "627: True
len(set(a))
(an((o)()))
5 RELATED WORK
Programming-by-ae -xxmmple with search Two popular search-based strategies for programming by-example approaches are bottom-up synthesis and top-down synthesis (Gulwani al. 2017

---

Published as a conference paper at ICLR 2025
In forward synthesis, the search space is traversed by combining subprograms into more complex programs through enumeration (Alur et al. 2017) or enumeration with priority defined by a neural network (Odena et al., [202]] Ellis al. 2021 or through incomplete search powered by neural network heuristics (Ellis et al. 2019, Shi et al. 2022 2023).
with language models Without search, auto-regressive neural net- works can also be trained to output the program token by token (Devlin et al. 2017: Bunel et al.) 2018). This is particularly interesting with large, pre-trained language models, which can be fine- tuned on synthetic data (Li & Ellis (024). Models that are large enough to exhibit in m--oonext learn- ing abilities, such as the GPT family (Brown et al., 2020 OpenAl, (024). can program by example through prompts. One can use chain-of-thought prompting too by first asking the model to describe the transformation problem in natural language (Wang al. 2024).
LIMITATIONS AND FUTURE WORK
Empirical, small-scale experiments show that older (like tut-3o- and smaller models (like CodeLlama (Roziere et al., 2023)) perform significantly worse, because they either do not adhere to the instruction generate code line by line because they are unable to properly reason about code and comments. For this reason, we did not perform experiments on these models. A potential solution is fine-tuning these smaller models a policy, for example, on straight-line programs obtained by a teacher model on synthetic data (Li & Ellis, 2024).
Our implementation considers straight-line line code generation, which provides a controlled environ- ment for evaluating different search strategies. Extending within-prompt search to any code requires streaming access to the language model, which allows dynamically stopping when a full operation is sampled, and special care for control flow statements, where can take inspiration from previous work on teaching LLMs to reason about code execution for program repair (Ni et al. 2024
Within-prompe search can be applied to other problems, such as program repair (Ni al. 2024) or code completoto in environments where inputs are available, like spreadsheets (Chen et al, 2021b) or data science notebooks (Huang et al.) 2024). As there is test for soundness, the model then also serves as an implicit reward model when stopping the search.
7 CONCLUSION
We introduce execution guided within-prompt search for programming-by -xxemmll with LLMs, where the premise is to sample multiple atomic operations, combine them into single program, and repeat the process from that combined program. Sampling multiple operations, where the model acts policy that explores different next states, allows to perform search. Combining operations into a single program enables the search to happen within one expanding prompt. This allows the model to act a value function that evaluates which of these operations are promising candidates to extend in next iterations. We evaluate this approach on five datasets and different baselines using the aligned pass@A ls rate, which aligns & according to the token consumption for each method. Our evaluation shows that within-prome prompt search performs consistently well across benchmarks for the same token budget. If allow more budget, explicitly computing the value of completions for an out-of- of-orompt search (which corresponds to tree-of seeeoff-houghhe thought) achieves a better pass @ rate.
REFERENCES
David H Ackley, Geoffrey E Hinton, and Terrence J Sejnowski. A learning algorithm for boltzmann machines. Cognitive science, 91):1477-699 1985.
Rajeev Alur, Rastislav Bodik, Garvit Juniwal, Milo MK Martin, Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. IEEE, 2013.
Rajeev Alur, Arjun Radhakrishna, and Abhishek Udupa. Scaling enumerative program synthesis via divide and conquer. In International conference on tools and algorithms for the construction and analysis of systems, pp. 319-336. Springer, 2017.
10

---

Published as a conference paper at ICLR 2025
Rajeev Alur, Dana Fisman, Saswat Padhi, Rishabh Singh, and Abhishek Udupa. Syntax-guided ott.at/w.....aaoooooooooooo//o/a
synthesis competition. 2019/PBE SLIA Track, 2019.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry. Quoc Le, et al. Program synthesis with large language models. arXiv preprini S.Kiv2208.007755 2021.
Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference on Learning Represen- tations, 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilaa Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901, 2020.
Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representutions, 2018.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde De Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained code. arXiv preprint arXiv:2107.03374 2021a.
Xinyun Chen, Chang Liu, and Dawn Song. Execution- Execution-guided neural program synthesis. In Interna- tional Conference on Learning Representations, 2018.
Xinyun Chen, Petros Maniatis, Rishabh Singh, Charles Sutton, Hanjun Dai, Max Lin, and Denny Zhou. Spreadsheetcoder: Formula prediction from semi-structured context. In International Conference on Machine Learning, pp. 1661-1672. PMLR, 2021b.
Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. In The Twelfth International Conference on Learning Representations, 2023.
Andrew Cropper. Playgol: learning programs through play. In International Joint Conference on Artificial Intelligence, 2019.
Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In International conference on machine learning, pp. 990-998, 2017.
Kevin Ellis, Lucas Morales, Mathias Sablé-Meyer, Armando Solar-Lezama, and Josh Tenenbaum. Learning libraries of subroutines for neurally- guided bayesian program induction. Advances in Neural Information Processing Systems, 31, 2018.
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. Advances in Neural Information Processing Systems, 32, 2019.
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Lue Cary, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreameoder: Bootstrapping in- ductive program synthesis with wake-sleep library learning. In International Conference on Pro- gramming Language Design and Implementation, pp. 835-850, 2021.
Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In
Principles of Programming Languages, pp. 317-330, 2011.
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. Program synthesis. Foundations and Trends@ in Programming Languages, 4(1-2):11119, 2017.
11

---

Published as a conference paper at ICLR 2025
Junjie Huang, Daya Guo, Chenglong Wang, Jiazhen Gu, Shuai Lu, Jeevana Priya Inala, Cong Yan, Jianfeng Gao, Nan Duan, and Michael R Lyu. Contextualized data- eata-wrangling code generation in computational notebooks. In Proceedings of the 39th IEEE/ACM International Conference Automated Software Engineering, pp. 1282-1294, 2024.
Wen-Ding Li and Kevin Ellis. Is programming by example solved by Ilms? arXiv:2406.0831/ 2024.
arXiv preprint
Microsoft. PROSE public benchmark suite.
https://github. t
Text
Accessed: 2025-02-28.
Ansong Ni, Miltiadis Allamanis, Arman Cohan, Yinlin Deng, Kensen Shi, Charles Sutton, and Pengcheng Yin. NExt: Teaching large language models to reason about code execution. In Forty- first International Conference Machine Learning, 2024. URL https://openrevieet net/
Borumiid=B1W71200
Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton, and Hanjun Dai. Bus- tle: Bottom-up program synthesis through carning-guided exploration. International Confer- ence on Learning Representations, 2021.
OpenAl. Gpt-4 technical report, 2024.
Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Push- meet Kohli. Neuro-symbolic program synthesis. In International Conference on Learning Rep- resentations, 2017.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Romain Sauvestre, Tal Remez, et al. Code llama: Open foundation models for code. arXiv preprint arXiv:2308. /2950, 2023.
Joshua Rule, Steven Piantadosi, Andrew Cropper, Kevin Ellis, Maxwell Nye, and Joshua B Tenenbaum. Symbolic metaprogram search improves learning efficiency and explains rule learn- ing in humans. Nature Communications, 15(1):6847, 2024.
Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. Crossbeam: Learning to search in bottom- up program synthesis. In International Conference on Learning Representations, 2022.
Kensen Shi, Hanjun Dai, Wen-Ding Li, Kevin Ellis, and Charles Sutton. LambdaBeam: Neural program search with higher-order functions and lambdas. In Conference on Neural Information Processing Systems, 2023.
Ruocheng Wang. Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hypothesis search: Inductive reasoning with language models. In International Conference Learning Representations, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, al. thaouutf- prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-244 24837, 2022.
Frank F Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn. A systematic evaluation of large language models of code. In Proceedings of the 6th ACM SIGPLAN International Sympo- sium on Machine Programming, pp. 1-10, 2022.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Ad- vances Neural Information Processing Systems, 36, 2024.
12


Reviews:
[{"review_id": "xpW5y4iF8t", "reviewer": "Reviewer_7p18", "summary": "This paper builds on past work on program synthesis, in particular at the intersection of language model guided synthesis and execution guided synthesis. The authors propose a synthesis technique called *execution-guided within-prompt* search. It is execution-guided in that after each line of Python code is written by the language model, it is executed and the result is appended as a comment to the line. And the *within-prompt* technique is based on the idea of taking several single-line completions from the model, concatenating them into a sequence of lines (despite being completions for a single line – of course renaming is done to avoid conflicts), so that at the next step of search the language model will implicitly pick which one (or more) values to use downstream. They evaluate the model and ablations on a range of datasets and find considerable benefits.", "questions": "- 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.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The core ideas are interesting and useful. The idea of appending execution information makes sense, and is very related to past work (which the authors cite) on guiding synthesis using execution results of program prefixes – it's surprisingly not an idea that I have seen used with LLMs in particular, where the execution information can be shown as a string for many data types, but it makes a lot of sense to do it and is found to be beneficial here.\n    - Some more related work: ExeDec (Shi et al 2024) is a relevant piece of related work – they don't use the execution of the program prefix to guide execution, rather they predict the execution result of the next step (\"subgoal\") they want to accomplish in the program and then write code conditioned to try to achieve that. Generally work on code repair is also very related – while it involves writing whole functions at once and seeing their execution results and error messages, it's still quite related. \n- The within-prompt search idea is also interesting – and it's intriguing that it sometimes uses more than one intermediate value produced in a single step downstream. It's also nice how the model can recover when it messes up by implicitly backtracking just by building on some earlier execution result.\n    - It wasn't obvious to me that this search strategy would work well, given that this is not at all a style of coding that I would expect to see much of in internet training data (often *all* intermediate variables are used, developers don't write extra unused variables too often) – so it's nice to see that it works.\n- Figure 4 is nice – it's helpful to see how execution leads to more backtracking, presumably because the model has seen its mistake through the execution result and takes a different approach\n- A quite wide range of benchmarks are used, a solid set of benchmarks for a synthesis paper", "weaknesses": "- The within-prompt search idea is interesting, but it'd be nice to see it compared to other methods for performing the search, where the execution information is still included. One very simple baseline that's not even a search would be to have the LLM explicitly pick which completion to keep, at which point the others are discarded from the context, and the program is written in this new context (as opposed to having all the other choices in the context still). That would produce rollouts instead of a search, but is still a good baseline to have. There is other work, like Tree Of Thoughts (Yao et al 2023) and Stream of Search (Gandhi et al 2024) that have focused on using LLMs for tree search. Comparisons to other methods, whether it's those ones or other tree-search baselines, would strengthen the evaluation. Even if just relatively simple LLM-search-based baselines were used, it would help with making it clear what sorts of alternatives exist to within-prompt search and how it measures up to them (or why none of them apply – but I expect some other simple form of search would apply). In short, it'd be helpful to have experiments that compare within-prompt search to outside-prompt search, to clarify the advantages of this contribution.\n\n> ...if the policy is certain and samples with less diversity, the model is more likely to solve a problem in the end. Conversely, if the policy samples many diverse lines, it is less likely to solve the problem in the end. This indicates that the model does behave like a policy.\n- While I agree that the LLM is certainly a policy (it's sampling the next action), this explanation confused me. Correlation between diversity and success rate doesn't mean something behaves \"like a policy\" – you could certainly have a policy that doesn't have this behavior, and through temperature you can modulate how much diversity you have in a policy, but that's separate from whether it behaves \"like a policy\". Maybe the authors meant it behaves like a certain kind of policy?\n\n> ...keeps on sampling until we have k = 4 syntactically unique operations. Having more possibilities requires the model to act as a better value function. For 4 out of 5 datasets, the performance slightly increases, reinforcing our intuition that the model correctly picks which option to continue from\n- I also agree that the model is implicitly acting as a value function, as it picks what to extend, which is interesting. But I don't follow the statement that having more possibilities \"requires\" acting as a \"better\" value function. Having more low-quality options requires a better value function to weed out the bad ones, but having more from the same distribution shouldn't have that effect. Having more of the same quality options *does* require a good value function in order to *benefit* from the extra examples – and this might be what the authors meant, and the wording just confused me.\n  - That said, the improvements in Figure 6a are fairly small. 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). \n\n- 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.\n- 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.\n\n- The approach is limited to working with straightline code – but could perhaps be extended to write whole units of code at once containing if statements or loops as long as they're all done in one completion, and there are other interesting directions to build off of there\n- The statements about soundness guarantees in the abstract are confusing – and soundness is mentioned far more in the abstract than the paper. The soundness guarantees come from executing the programs to check correctness, which is done when testing programs generated by LLMs, whether or not they were constructed iteratively through the suggested approach here or all at once – that doesn't change the soundness in my understanding.\n- line 31: \"grail\" -> \"holy grail\"\n > We leverage pre-trained language models to perform programming-by-example without restrictions on the domain (specific language).\n- 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)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nW74Fmf8oJ", "reviewer": "Reviewer_MDTt", "summary": "The paper presents “within-prompt search” method to enable LLMs to reason about the syntax and semantics of programs concurrently. This approach is a novel instantiation of PBE with execution guidance specifically designed for LLM-based program synthesis. The within-prompt search technique encodes multiple candidate code completions within a single prompt. This enhances the likelihood of producing syntactically and semantically accurate code.\n\nThe authors position the role of the LLM as a policy to generate code and as a value function to evaluate previously generated code based on its semantics (concepts from reinforcement learning theory where the policy guides generation and the value function assesses the quality of partial solutions). The value of these partial programs is determined simply by syntactic validity and consistency with given examples.\n\nTwo baselines are used for comparison: an unrestricted baseline without any search constraints or execution annotations and a second baseline where straight-line constraints are imposed, but search and annotations are disabled. The experimental results show a significant improvement in accuracy and consistency with the within-prompt search method.", "questions": "1. Does this approach work only for imperative programming? It seems it might be more suited for functional or recursive code structures.\n2. 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?\n3. 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? \n4. Since the paper uses standard PBE benchmarks, it would be beneficial to include comparative results from other approaches (e.g., traditional program synthesis methods) on these benchmarks.\n5. How does the method handle dead ends—situations where intermediate results do not align with any possible valid completion? A deeper discussion on techniques like pruning unpromising paths or resetting to prior valid states would improve your paper.\n6. What do the confidence belts represent in Figure 5?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The proposed method is straightforward, yet the experimental results demonstrate substantial improvements over the baselines.\n2. The paper is well-written and easy to follow.", "weaknesses": "1. Since partial programs are imperative, the semantic annotations include the results of executing each line of code on example inputs, which can grow combinatorially. The paper does not address the limitations of this approach, particularly given the limited window size in LLM prompts and the increased risk of hallucination as prompt size grows.\n2. The baselines, which use unrestricted and straight-line constraints without search or annotations, may not fully highlight the method's advantages. Incorporating other PBE or LLM-based synthesis techniques with integrated search mechanisms could be helpful. \n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1DxxCg6Uqx", "reviewer": "Reviewer_vi7p", "summary": "The paper proposes a framework to solve PBE by searching for programs by generating lines of code in straight-line program style. When generating the next lines, they consider the partial program generated so far and its corresponding execution state to generate the next line. The LLM here acts as a policy to generate the next action, i.e., line of operation. They show that LLMs with this framework can increase both solving rate and consistency of solving.", "questions": "- It is not clear how the LLM determines which states (partial programs) to expand. Could you lay out the algorithm of the propose framework so it can be less ambigous? Are all the partial programs being expanded with k actions in the default policy setting?\n- \"Without execution, the model backtracks less, as it does not realize that the current operations $o_{<i}$ are dead ends, and as such performs worse (see Figure 2).\" Can you clarify the mechanism of backtracking? Does backtracking only happen when pruning based on the most recent `k` operations? How is the pruning parameter `k` set?\n- How do you ensure that there are no statements with side effects modifying the states, e.g., v3 = (v2=1) then v2 is modified?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* The paper demonstrates that the search and execution improve the performance on different datasets across lists, strings, and basic python programming\n* The paper's framework is clean and can be generalized to other programming languages or domains where execution state can be compactly represented", "weaknesses": "* Issues with the baselines and comparison\n  * There is a simple LLM PBE baseline: search by sampling entire programs and then executing to find the right program satisfying the input-output assertions. For the baseline LLM results (\"Free\" in the figure), they did not do multiple samples and execution. Because the paper proposes to use line-by-line search/generation and execution to find the program satisfying the input-output, it would be better to know how it compares against a simple entire program resample and execute approach without the proposed line-based search.\n  * Other neural or symbolic baselines not presented: they use PBE benchmarks from the symbolic methods literature (flashfill++, playgol, list) but their performance is not listed, so readers would not know if using LLM as a search policy is actually better than traditional methods doing program search.\n* The paper only uses one model to perform experiments (GPT-4). It would be nice to add results for other models, especially open models or smaller ones, to see if open models can reproduce the results and whether the model size/capability would affect the effectiveness of the approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IYJK4ffClG", "reviewer": "Reviewer_g8hP", "summary": "This paper targets a form of program synthesis called programming by example (PBE). The setup includes a specification, given via assert statements that encode the input and their respective outputs. The paper proposes an execution-guided technique to guide the synthesis of the program using LLMs by executing each statement of the generated code and providing the result in the prompt itself to inform the generation of the next statement. The paper compares this technique with standard prompting techniques and show that the execution and search strategy improves program accuracy using GPT-4o as the base LLM.", "questions": "These are mainly questions to clarify issues I have from section 3, but please also respond to the concerns from the Weakness section.\n\n1. What is the concrete definition of a policy and a value? And what is the difference between an actual value and a value network?\n2. What does an operation mean as far as actual code is concerned? i.e. is it a token, statement, code snippet, etc?\n3. What is the difference between P(x) and P_j? And is P_j a partial program or a representation of the entire explored search tree at this point?\n4. At each stage, you generate operation o_j as per 3.1. But you calculate expectation wrt P_T, which \"is a sequence of operations sampled from the (prompted) policy\". So is P_T actually sampled at each point on top of o_j, or is P_T just a statistical notion of the possible ways to complete the current program P_{j-1} o o_j?\n5. What constitutes an iteration? Is it the entire process included in steps 1--4 from Figure 1 or is it the generation of a single operation?\n6. How is the search space explored? Is it more of a BFS search or a DFS search? I notice mentions of backtracking in 3.4 so I assume it is a form of DFS, but in this case how does the backtracking work? At each point does the LLM generate just the response to one unexplored node or responses for all unexplored nodes? and what is the size of the search tree in general? I'd assume it blows up in complexity for large target programs which is why there is the pruning used. Furthermore what do you mean by \"operations not used\" as far as pruning is concerned? In general I think you can do a better job in section 3 by grounding each step with an example, or at least referring back to Figure 1 on top of a general algorithm.\n7. Do you have any safeguards against executing problematic/malicious code? How about results of for loops, incomplete branches, and more complex control flows that may not necessarily terminate?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "In general, I really like the idea of enabling PBE-style code synthesis with LLMs, especially the implications if we combine PBE with typical NL specifications. I also think the overarching contribution of specifying individual execution results within the prompt is good, and it allows for more fine-grained feedback while generating lines of code.", "weaknesses": "I feel that while the core ideas proposed are neat, the paper lacks clarity and depth in terms of explaining the technique proposed and evaluating it. I'll describe my major complaints below.\n\n## Technique\n\nThis section does not do a good job explaining the proposed technique clearly. The text is dense and filled with technical notation, but understanding how they interact and play with each other is not easy. It would have been better to include a diagram of all the phases that contained more details than Figure 1, or even better, an algorithm defining each phase and the steps within the phase along with supporting text.\n\nThere are also several poorly defined terms and inconsistencies in notation (defining what a policy, value, program, function, operation, etc. are). Furthermore, the cyclic nature of the technique shown in Figure 1 is not explained in Section 3, so I have no idea how the search space is represented within the prompt, how it grows with each response from the LLM, how it is pruned, to what extent can it be pruned, how backtracking works here (the text doesn't describe backtracking but instead describes operations being pruned).\n\nIn summary, section 3 provides some context and details but getting the full picture of the system is very difficult. The paper is significantly under the page limit, so it should be able to clearly detail the entire system without sacrificing the details it already presents.\nI have asked specific clarifying questions in the Questions section.\n\n## Evaluation\n\n### Baselines and Benchmarks\n\nThe evaluation in this paper is lacking. Even before getting into the details, this paper only evaluates its technique over a single base LLM model. At minimum, I would expect more LLMs of varying techniques and sizes to show up in the evaluation. Also, I would like a more in-depth evaluation of different prompting techniques: standard prompting is just not enough. At minimum, chain-of-thought prompting needs to be there, since it is a pretty standard approach, and I would appreciate other baselines that may directly compare with this paper (some alternate PBE techniques are mentioned in the background section). 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.\n\n### Metrics\n\nThe 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.\n\n### Results\n\nI would like a bit more insight drawn from the results. For instance, why does SyGuS have a lower performance for +S+X versus +X? Is there any reason SyGuS and Playgol  have higher accuracies for +X versus +S, while for other datasets it is lower? Also how does standard CoT prompting perform here?\n\nIn figure 3, what do the horizontal lines indicate? What exactly does a backtrack mean for Figure 4? What is the difference between WPS and Straight/Free? And in Figure 5, what does it mean by average number of sampled operations? I thought in each case a fixed number of operations were sampled?\n\n## Miscellaneous\n\nIn general, there are several grammatical mistakes throughout the paper that make reading it a bit difficult. This is not as major from a technical standpoint, but it is important to correct them.\n\nI also think the background section and related work can be explored more. Especially in related work, explain how your technique contrasts with those existing techniques, and why they are not included in the evaluation. I also think there needs to be a section that talks about LLMs for code generation as well, not just PBE.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)