Is Programming by Example Solved by LLMs?
Authors: Wen-Ding Li
Kevin Ellis
Venue: NeurIPS 2024 poster (2024)
Keywords: programming by example
program synthesis
LLM
code generation
Primary area: generative_models
TL;DR: We explore methods for doing PBE with LLMs

Abstract: Programming-by-Examples (PBE) aims to generate an algorithm from input-output examples.
Such systems are practically and theoretically important:
from an end-user perspective, they are deployed to millions of people, and from an AI perspective, PBE corresponds to a very general form of few-shot inductive inference.
Given the success of Large Language Models (LLMs) in code-generation tasks, we investigate here the extent to which LLMs can be said to have "solved" PBE.
We experiment on classic domains such as lists and strings, and an uncommon graphics programming domain not well represented in typical pretraining data.
We find that pretrained models are not effective at PBE, but that they can be fine-tuned for much higher performance, provided the test problems are in-distribution.
We analyze empirically what causes these models to succeed and fail, and take steps toward understanding how to achieve better out-of-distribution generalization.
Collectively these results suggest that LLMs make strong progress toward solving the typical suite of PBE tasks, potentially increasing the flexibility and applicability of PBE systems, while also identifying ways in which LLMs still fall short.

Is Programming by Example Solved by LLMs?
Wen-Ding Li Cornell University w1678@cornell.eem
Kevin Ellis Cornell University ke kellis@cormell.co edu
Abstract
(PBE) aims to generate algorithm from input-output examples. Such systems are practically and theoretically important: from an end-user perspective, they are deployed to millions of people, and from AI per- spective, PBE corresponds to a very general form of few-shot inductive inference. Given the success of Large Language Models (LLMs) in code-generaile investigate here the extent to which LLMs can be said to have 'solved' PBE. We experiment classic domains such as lists and strings, and an uncommon graphics programming domain not well represented in typical pretraining data. We find that pretrained models not effective PBE, but that they can be fine-tuned for much higher performance, provided the test problems are in-distribution. We analyze empirically what causes these models succeed and fail, and take steps toward understanding how to achieve better out-of-distribttion generalization. Collectively these results suggest that LLMs make strong progress toward solving the typical suite of PBE tasks, potentially increasing the flexibility and applicability of PBE systems, while also identifying ways in which LLMs still fall short.
tasks, we
Introduction
Programming-be -y--xamplleeee (PBE) systems solve challenging task: Given input-output examples of a hidden algorithm, they seek construct the source code the underlying function
2
PBE
deployed to millions of users 3 4
6 lies near the heart of core Al challenges α
I0 and is
qualitatively different problem from the bulk of recent work on LLM code generation, because rather than generate source code from natural language [1]] PBE is instead fundamentally about few-shot inductive inference: Given a handful of examples, inferring the program that will generalize to new inputs, or which captures the true latent regularity, without relying on natural-languaae guidance.
We investigate here the extent to which large language models pretrained on source code can solve PBE. If they can, this unlocks the ability to do PBE in general-purpose purpose Turing complete languages like Python, unlike the restricted domain-speeific languages which have so far dominated PBE [4 12 13 14] i.a.), thereby increasing the scope and power of this paradigm. If LLMs cannot perform PBE, then this highlights a deficit of inductive reasoning and problem solving, and suggests LLMMs lean too heavily on natural language cues to generate code.
We find that pretrained and instruction-tuned models serve as poor PBE systems, a finding also supported by recent work [1 16, 12] [7]. But our investigation further finds that LLMs can be fine-tuned for significantly higher performance, provided they are not asked to generalize far beyond the fine-tuning data. To address this failure of generalization we give algorithm for taking a small unlabeled dataset of problems and adapting the LLM it, which we find narrows this domain gap.
The resulting recipe allows PBE over Turine-complete languages across three qualitatively different domains (Fig. Th: algorithms vectors of numbers, string manipulation macros, and graphics programs LOGO/Turtle. In every case, our final model is at least as effective as custom symbolic search algorithms operating over domain-specific languages, and surpasses powerful closed-source
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

models such as GPT4 [8 We also find that the resulting system can cover broader scope of problems than classic symbolic methods, owing to the use of Turing-complete language, which, at least theoretically, allows learning any computable function.
DOMAIN: lists
DOMAIN: graphics
provided examples
generated progran
provided exanple
generated program
INPUT
OUTPUT
Check if the list La enpty
for in range (
if not ingut_ _ist:
with fork ()
4,2,8
2,8,6
return input_ 1ist
sange
Find nin nunber in the list
(2sward(2*
9,9,9,9
0,0,0,8
(input_ [ist] [num
19ft
-7,0,2
0,7,9
for input list]
DOMAIN: text editing macros
provided examples
generated program
INPUT
original time datetime strptine (imput_ stc, 1NR AM: 6PM to 8PM
OUTPUT
hous original tine. hour
18:25:57
stast hour hour (hour 2) end start,
end hour end hour 12
87: :20
6AM to BAN
start aarnn "AM if start hour else "PM
end argn "AM if end hour 12 or end hour 24 else "PM"
23:34:17
18PM to 12AM
zeturn E" (stact, hour 12) (atast, arpa] to and hour 12) (ead arrgon)
Figure 1: Domains, including standard ones that resemble programs found in pretraining data, as well as a less common graphics domain, which is likely less represented in LLM pretraining data.
2 Background
Programming by Example considers synthesizing program given a vector of inputs X and corresponding outputs Y. Typically the program expected exactly fit the provided examples, p(X.) Yi, vi, where i indexes examples. The program is drawn from (potentially infinite) language L. Typically
domain-specific language designed for specific PBE system, not general-purpor purpose programming language. For example, the PBE system FlashFill synthesizes string manipulation macros designed automate common spreadsheet edits 22. FlashFill's domain- specific language C includes commonly occurring regular expressions, together with string slicing and concatenation, and restricted forms of loops. The language time construction of programs consistent with input-output examples. FlashFill's 's goal, like most PBE systems, is generalize hold-out test cases: inputs X' with (hidden) target outputs Y'.
also designed to allow polynomial-
Pick a program P from EpEL p(X,) = p(Y)), (V))),)) Vi). Succeed if p(X)) = p(Y)), (1)
In its simplest forms, PBE can be accomplished by guess-and-check enumeration until a program is found that is consistent with the examples. Although there exist more sophisticated search algorithms, including those accelerated by neural guidance 19 20 21 22). key enabler of practical PBE systems is the design of a carefully restricted domain-specific language L. The domain-specinfe language effectively hardcodes symbolic knowledge, focusing the system on what programs the human engineer thinks are most promising. but at the expense the wider set of computable functions expressible in general-purpose purpose languages.
The PBE setup covers other cases as well, such as sequence extrapolation (the inputs are indices into the sequence), as well as data compression (the input is null, and the data is compressed by synthesizing program that reproduces the output data). Therefore, truly general solution to PBE- one which could express its solutions in general purpose programming languages, and cover most

---

practically relevant boollls-wooudd be broadly applicable to many inductive inference problems, point that has been long appreciated (
LLMs for solving programming problems have been recently very successful
26
These systems typically input prompt describing problem in natural language, then sample candidate programs, and optionally filter those samples by checking them against input-output test cases, with the goal of passing holdout tests:
Draw Pk (-pommpp)mp.t). Pick a p (pr Pa (x();) pk (Y;), Vij. Success: p(X;) = p(y)); Vj
Unlike PBE, the primary driver of program generation is natural language prompt, although input- outputs may also in the prompt [2 28). Recent work using LLMs to synthesize programs solely from examples has either obtained negative results [16 [2]. focused simple and/or nonstandard
problems 29 30 31. leaving the extent to which PBE is 'solved' by LLMs an open question.
3 Methods
Basic prompting the most straightforward way of performing PBE with a pre-trained model: Given input-output examples (X, Y) prompt is constructed and K programs generated. Programs filtered by the I/O examples, and a random satisfying program is returned:
Sample Pk ~ pIM((-prroppll Y)), for k from 1..K
Pick a from {Pk Pk (x;) Pk: (Vi), vi)
Fine-tuning improves the above approach in a conceptually straightforward way. Given a dataset comprising tuples of programs and I/O examples, {(p. X, Y)), fine-tune the LM predict program from its input-outputs. But this dataset is hard to come by: Although there are web-scale corpora of naturally occurring source code, there is analogous dataset of runnable code snippets paired with representative input-output examples, and this data deficit is especially true for new or unusual applications of PBE, such the graphies programs we consider.
To assemble large dataset of (p, X, triples we start with a small manually-constructee seed programs and inputs X by prompting an LLM with members of D The output Y comes from running on X. The seed dataset effectively defines a prior over (p, X). notated G in Fig. 2 We sample from G to collect many program-ing use program execution to predict Y. not an LLM. The resulting dataset, which we call D is used train an L.MM generate programs when prompted with input-outputs. As this fine-tuned LLM effectively learns to do probabilistic inference the graphical model shown Fig. P (right), we write this fine-tuned LLM as qo Y). This inference network is trained maximize
dataset, Dsced. and then randomly generate
pairs, but
max log qe (p) X, Y), where Xp G(Dsced) and Y p(X)
(4)
This method is closely related to self-instruct 32 and wake-sleep Like self-instruct, we use prompting to bootstrap a large dataset from small manually one. Our method differs by using the LLM to generate hidden latent variable (the program) while a different generative process produces observed variable (the program outputs). Like wake-sleep, from generative model to train an inference network, but we do not further train the generative model itself. Next, we will see that bringing the method much closer to wake-sleep by updating the generative model plays an important role when deploying the system on out-of-distributin problems.
use samples
defines
samples
trains
Diced
Drune
G
X
Figure 2: Left: Data generation pipeline. Right: The fine-tuned network learns to do inference in graphical model where the prior over programs, G. is defined by prompting an LLM with example code in D while the likelihood p(Ylp, X) is defined by program execution.

---

Adaptation. One of the most powerful features of source code as representation is its ability to efficiently express a wide range of computations. Therefore it is of interest to study the ability of fine-tuned LLMs to extrapolate to PBE problems outside the distribution of the fine-tuning data.
We consider basic approach adapting different distribution of problems, assuming access to problems drawn from the testing distribution, but without labeled program solutions. This mimics the deployment of PBE systems end-users who may have their own idiosyncratic distribution of problems they care about, and who do not provide ground-truth programs, but who can provide feedback on if generated program has correct behavior. This means we have an unlabeled dataset Dudipt comprising onput-outputs (X, Y), as well as labeled seed dataset Dseed comprising triples (p. Y). Adaptation proceeds by iterating between pretraining with ((Dseed). testing on D Padape and adding back into ssed any program solutions found on the adaptation problems, which then become seeds for the next iteration. This produces a sequence of fine-tuned models, indexed below by é:
train model:
O' arg max log go (o|pX, (xXYY Y), where (p, X) ~ G(Dinsa) and Y = p(X)
run inference:
Pk X.Y qo (p|x, Y) for (X,Y) E Datupe and is from 1..K
update seed:
Di+1 = D'' (Ph x. X,Y) (X,Y) Dadapt & E [K] if X.Y (X) = =r}
(5)
The equations can be seen as a wake-sleep algorithm where "dreaming" corresponds to training g on fantasy data (first equation) while "waking" corresponds to running inference and updating the generative model G (by updating the seed, second pair of equations). Ideally, each cycle of this wake-sleep adaptation solves more out-of-distribution problems, which tugs the generative model G toward the target distribution, unlocking solutions to more out-of-distribution problems, etc. This hinges each iteration actually solving new problems from the unlabeled dataset. Theoretically this is guaranteed given enough inference-time compute (large K above). We explore Sec. the extent to which this holds in practice.
4 Experiments
We study different LLM-approaches to mnogramming-b--exaapee across three domains (Fig. D
1. List functions is a PBE domain meant to model a "programmer's 's assistant". It concerns discovering algorithms that transform lists of numbers, given input-output examples. This problem statement has long history within program synthesis [33 34], and was popularized within machine learning by DeepCoder (35). We consider two modern list function datasets created by Rule et al. 2024 [17] and Shi et al. 2023 [12, which both involve higher-order functions and nontrivial procedures such as map, filter, and sort. Rule et al. was recently added to BigBench [36].
2. Text editing is a domain where a program synthesizer assists an end-user edit their spread- sheets or other documents. From string-to-string examples, the system generates edit macros for tasks such as reformatting dates, extracting fields from semistructured text, Text editing is the most prominent commercial success of PBE: The FlashFill PBE system ships in Microsoft Excel and is used by many millions of people [6]. We consider two text editing datasets: SyGuS problems which are easier-and PROSE (39] problems, which constitute the most challenging dataset of its kind 38
etc. 2 37 38 4
3. LOGO/Turtle graphics is domain whose goal is to synthesize program that generates a target image Systems of this kind can be used both for high-level visual reasoning and for helping artists make structured edits to images 40
We use dataset of geometric designs expressed as LOGO/Turtle 42 programs where the programs move simulated pen over canvas- taken from Wong et al. 43 To allow the LLM to visually perceive the input image, we convert the image to ASC style strings; see Fig. 5 and Appendix, A.1.3
TTis is PBE with single example and null input, effectively compressing the image into a program.

---

4.1 How well does the fine-tuned model perform?
We prepare seed datasets for each domain, synthetically generate large training set, and then fine-tune a DeepSeekCoder LLM [4]] that was pretrained on source roder list functions we seed with 50 problems from Rule et al. 2024: For text editing, we consider seeding with either SyGuS or 40-problem subset of PROSE; for LOGO we seed with 200 training-set problems in Wong et al. [43
The resulting fine-tuned models surprisingly effective within their respective PBE domains. On list functions our finetuned model surpasses the best symbolic search baselines reported in Rule et al. (Fig. Bap, surpasses the best neurosymbolic search method from Shi al. (Appendix Fig. 10.. and surpasses GPT4, It also solves 100% of the list to list benchmark problems from X (a well-known symbolic synthesizer), shown in Appendix Tbl. although plausibly, many X problems are in the pretraining data. On text editing. it surpasses the performance of FlashFill and approaches the level of FlashFill++ (Tbl. Fig. Bbp. On LOGO, it solves 90% of the test set (Fig. Bep. surpassing systems such as DreamCodes 45 which introduced the first version of these LOGO problems. It
also solves more problems than LIIOO and Regal 43 46], which are LOGO program synthesizers that input natural language describing how the image should be drawn. In contrast, our model does use any language clues, generating purely from the image. addition to quantitatively solving more problems, we note that there are qualitative improvements to the breadth of problems that can be solved in the first place because the LLM can generate Turing-complete code spanning a much broader space of computations (Fig.
80
70
Flleet
80
Problems Solved
60
60
Regal
50
DreamCoder
FlashFill
LILO
40
40
40
Metagol
30
ours-33b
RobustFill
30
ourS-33b
ours-7b
ours-7b
20
ours-33b
gpt-4-turbo
20
gpt-4-turbo
ours-7b
gpt-4-turbo CoT
gpt-4-turbo CoT
gpt 4a
10
deepseek33b
10
deepseek338
gpt-4o-mini
100
200
0
100
200
200
400
Search Budget (Num Samples)
Search Budget (Num Samples)
Search Budget (Num Samples)
(a) Lists
(b) Strings
(c) Graphics
Figure Test performance. problem is solved the predicted program generates correct
outputs on the holdout inputs. Metagol 47 RobustFill 20), and Fleet (48) results taken from [7
There are caveats the above results. First, the fine-tuned model essentially never produces correct program the first try: It requires or hundreds of samples, each of which is com-
gen. accuracy
oracle accuracy
pared against the ground-trun -truthhhhhhhhh input-outputs, and discarded if contradicts the examples. On
FlashFill FlashFill++
33%
~ 100% 88%
a GPU like the one we use (an Nvidia A6000) this rejection sampling takes on the order of few minutes to solve a given problem. However, compared to classic enumerative program syn- thesizers [I3 49), or even compared to those with neural guidance [35] (22). proposing a few thousand programs relatively little, and could not plausibly cover significant fraction of the exponentially large search space.
ours, 33B
82%
Table 1:
Generalization accuracy: % problems where the program makes correct predictions on every holdout test. Oracle accuracy: % prob- lems where correct program was generated (even if incorrect programs were also generated that also passed the training input-outputs). Flash- Fill++ 38 only reports oracle accuracy.
We prefer DeepSeek because roughly a. but fully open training details.
Thhe FlashFill results were obtained using Microsoft Excel for Mac.
5

---

INPUT
OUTPUT
generated program
lines text. text. splitlines ()
Many had little lamb Its fleece white...
1:Mary had little lamb
2:Its fleece white...
reault
1, line enumerate (lines)
Twinkle, twinkle, How I wonder what you... Up above the world so... Like diamond in the...
1: Twinkklee, twinkle,
result + f" 1): (line) \n"
2:How wonder what you...
3:Up above the world 4:Like diamond in the...
return result[:-]
generated program
INPUT
OUTPUT
states
NY
New York
"AL": "Al abama
"AK", "Al "Alaska"
CA
California
Alaska
[text]
Figure 4: PBE with LLMs allows using
programming languages which can mix
string and numerical operations in ways not allowed by domain- -speciic languages [38] (top). and allows world knowledge to inform code generation (bottom). I/Os and code partly elided for space.
provided example
ASCII representation
generated candidate figures
00000000003100000000000000000000
00000000000033000000000
08900023200053220000000
000001100300033022200000
00000120000020000000000000
0000001000211200000000000
00000033228322255000000
0000010000122000000000000
000003000000000022000000
0800021002100222112000000
00000022330002330000000
0000000000000000000000000
00000000133300000000000
Figure 5: ASCII representation of 1.OGO graphics. Average pixel intensity indicated by numbers 0--9
The second caveat is that the model degrades when tested out-of-distribution. An example of this degradation is illustrated in Fig. 66| which tests the LOGO graphics model on hand drawings (after training on clean computer graphics). On the out-of-distribute samples programs that do not the data, but its accuracy does not fall zero, meaning that with enough compute budget, it does actually generate reasonable programs. This foreshadows the results which more systematically studies out-of-distribution behavior.
hand drawing the model mostly
Sec. 4.3
provided drawing
figures generated from graphics program samples
Figure 6: Example LOGO test: inferring graphics program from hand drawing.
See also Appendix Fig.

---

4.2 What causes the fine-tuned model to succeed or fail?
Classic symbolic approaches to PBE, when they are based on enumeration, tend succeed whenever the target program is syntactically small. Approaches based on clever dynamic programming, such as the FlashFill family 4.. succeed when the program is representable in the nomain-speciff language. What predicts success for these L.M approaches?
To answer this question investigate several hypotheses. First, potentially the success is deter- mined by program size, and degrades as programs grow longer. Second, as a more refined notion of size, we instead measure the description length under the prior, which for a program p. is Description length under the prior would be good predictor of success if
- -log the fine-tuned model engages in blind guess-and-check simply learning the distribution ((ssed), and sampling from this prior while ignoring the input-outputs. Third, one possibility is that success is predicted by description length under the approximate posterior (- log (p(p) (p) X. Y)), which would be the case if the fine-tuned model attends closely to the upput-ouiputs and reshapes its distribution accordingly, instead of defaulting to the prior. test these hypotheses we calculate the average compute budget needed to solve each problem, and compare it with these different variables. Fig. shows that posterior description length more predictive than program size and prior description length: unlike classical methods, metrics of program length correlate poorly with problem diffi- culty, and there is no evidence that the fine-tuned model's behavior can be characterized as blind guess-and-check. (See also Fig. 5
10"
R = 0.02
Negative Log Program Posterior
1024
R = 0.32
R² = 0.10
Negative Log Program Prior
10
1020
Program Ast Size
60
1025
1016
1049
50
10
1043
10a
40
107
10a
30
10a Search Budget
10a
10a
102 Search Budget
10a
10a
10a
102
10a
Search Budget
Figure 7: Compute budget needed to solve problem is best predicted by description length under the approximate posterior, not program size or prior description length, suggesting that the fine-tuned model is not engaging in blind guess-and-check.
4.3 Out-of-distribution generalization
One advantage of classic symbolic PBE methods is that they do not make statistical assumptions about their test problems. Indeed, some classic methods can, within their domains, synthesize programs perfectly (i.e. always find program that fits the training input-outputs). In contrast, neural networks can struggle to generalize beyond the training distribution.
We therefore consider train/test splits that force the model to generalize beyond the distribution of its training data (beyond Dwed)). On text editing, seed with SyGuS problems, and perform out- of-distribution testing on PROSE problems (PROSE much harder than SyGuS). On list functions, seed with problems from Rule et al. 2024 and test Shi et al. 2023 (the Shi dataset contains unusual combinators, such as Scan). On LOGO, we seed with short programs (S 12 lines of code), and test long programs (> 12 lines of code). Using these splits also measure the ability of the adaptation method in Sec. 3 to improve -iitr---iitiitttion generalization! 4
Fig. 8 shows that there is nontrivial degradation when testing out of distribution. For example, a 7B model seeded with PROSE problems and tested on a different subset PROSE has an accuracy of 76% (Fig. 3b). but this degrades to 59% when seeded with SyGuS problems, which follow a different distribution and are generally simpler and easier than PROSE (Fig. (b).
WWe work here with 7B models because Sec. 4.1 found that fine-tuned 33B models are only slightly better than 7B, and 7B is cheaper
7

---

We further perform the adaptation method described in Sec. B order to measure the extent to which can narrow these domain gaps. In every case allows sol solving more out-of-distribution problems. increasing absolute performance by around 10% more in all domains, which is a relative increase of about 16% for text/list and a relative increase of about 190% for LOGO (approximately tripling the number of solved LOGO problems).
80
60
% Problems Solved
% Problems Solved
Problems Solved
50
60
40
30
before adaptation
30
before adaptation
20
adaptation
adaptation
before adapation
finetuned in-distribution
20
finetuned
adaptation
in-distribution
finetuned in-distribution
1000 1500
200
400
2000 Search Budget (Num Samples)
Search Budget (Num Samples)
Search Budget (Num Samples)
(a) Rule adapted to Shi
(b) SyGuS adapted to PROSE
(c) LOGO short adapted to long
Figure Out-of-distribation generalization and adaptation to new test distribution.
To better understand the dynamics of adaptation, we visualize the specific problems solved before and after adaptation on LOGO graphics (Fig. (.. Before adaptation, only a handful of out-of-distribution problems solvable, and only with significant search budget. Adaptation allows the system to quickly solve similar out-of-distribution problems in the future, but does not allow the system to generalize to problems very unlike those originally solvable by the fine-tuned model. In principle, expanding the inference-time compute budget should allow successful adaptation (large K in Eq. 5) Another more compute-efficient approach would be to increase the amount of adaptation data by introducing 'steppingstone' problems in the adaptation set that give a gentler transition from the original training distribution.
Solved After Adapt
Solved when also trained with long programs
Solved Before Adapt
Figure disttib-ittiitio LOGO problems (requiring long programs with 12 lines of code). We show example problems that are solved by the original model fine-tuned on short programs, which then become training data for next round of adaptation. Adaptation allows consistent solving of problems similar to those that the original fine-tuned model could sometimes solve, but is not panacea: Problems dissimilar to those solved by the initial model are not ever correctly generated, despite the fact that they solvable by model fine-tuned in-distribution.

---

5 Related Work
Automatic data generation with LLMs, such as self-instruct (32, WizardCoder [50], and many others [51 52 53 i.a.), works by prompting LLM produce outputs which are then used for later learning stages such as fine-tuning. These approaches are applied recursively to their own output: Previously generated data incorporated into future prompts. We similarly generate dataset Dune by prompting an LLM with soodd but (1) do not recursively prompt the LLM with its own outputs and (2) combine the LLM generations with program execution make program outputs. This gives a different mathematical interpretation to our data generator. First, the programs are samples from a prior, G, defined by Dwed, which would not be valid interpretation if the LLM was repeatedly fed its own outputs. Second, there is an observation model or likelihood function, p(Y p, X). which is defined not by the LLM, but by a Python interpreter. In this way, our data generator constructs training examples for fine-tuning that teach the network how to invert the execution process of the Python interpreter.
Machine learning applied to PBE has often sought to accelerate search: to find any program at all consistent with the I/O examples [19] 20
45 21 35| 22 12] [54] [55]]6], which is nontrivial due to the
combinatorial nature of the search, even after confining to domain-specifee programming language. complementary line of research explores inductive biases that favor programs likely to generalize
to new inputs, such as learning prior or ranking function [57] 41 58 59 Our work should be seen within the tradition of learning to search for programs, We show that finetuned models serve as an effective yet simple foundation for accelerating search in PBE, allowing search to be tractable over much richer and more expressive languages such as Python.
Classic PBE. Traditional approaches to programming progranning-b-eexxnless by-examples operate by symbolically search- ing or solving for programs consistent with the input-output examples [13 49 2 (37 (]. They use domain-specifee programming languages that are designed to either enable efficient search and/or bias the system toward functions that are likely to generalize new inputs. Search for programs can even be polynomial time when this domain-specific language has a special structure (roughly, when every function can be 'inverted'), ), a key enabler of FlashFill, the first commercial success of PBE 2
LLMs as inductive reasoners. Using an L.M to perform inductive reasoning- to generate abstract hypotheses from concrete specific examples- has been explored by several recent works 22 30 60 61], all of which has found significant value in translating these hypotheses into programs, and all of which have worked by prompting pretrained GPT-style models. Our work can be seen as helping answer a natural question posed by these previous works: Given that LLMs can generate hypotheses from examples, can they produce programs of the nature and complexity demanded by PBE? We find this is largely the case after fine-tuning, both for classic PBE domains and unusual ones.
Self- Self-Debuggnng, Refinement, and Self-repair. One way of improving the code generation abilities of an LLM is to have it attempt to debug its own code whenever the initially generated code does not pass the provided test cases [62 63 64
66 24 67]. We did not explore this strategy, however, because a more basic approach that simply regenerated a new program from scratch already surpassed the prior state of the art (both symbolic and neural baselines), provided we finetune. However, further pushing the boundary of PBE may benefit from self-debugging strategies.
65
Ranking L.M--geerrtted code. Past work considers a variety of ways to select an output from a collection of L.LM-saepled programs 2 59 68 11], many of which more sophisticated than simply filtering by the examples, which is what we do here. Like with self-debugging, integrating these techniques should be synergistic with our approach.
6 Limitations
Our work has important limitations. From engineering perspective, using 7B-33B neural network to perform PBE is not practical for most end-users, who may be doing PBE on their laptop or desktops in order to accomplish small onc-off tasks. For this reason, true deployment to end-usen may require

---

investigating the effectiveness of much smaller neural networks (not an LLM), and it may also be valuable to study the effect of network compression and distillation upon our finetuned models.
From the perspective of understanding where and why our system succeeds and fails, we have shown that neither program size nor likelihood under the prior suffice predict success, finding the posterior likelihood is a better predictor, albeit an imperfect one. Although this allows us to discard the hypothesis that the system is merely sampling from the prior, also just pushes the question back one stage further: What exactly about specific problems causes the neural network's i approximate posterior to put more or less probability mass on correct solutions? While in classic PBE one can obtain sharp answers as to why certain problem was solved or not, this is much harder question with neural networks, whose workings are more opaque.
Discussion
PBE with fine-tuned LLMs is surprisingly effective, surpassing many of the best neural and sym- bolic baselines we know of, even for uncommon domains such as LOGO graphics. Why is that? Fundamentally, the neural network only needs act as a heuristic proposer of solutions, because we can check against the input-outputs, Therefore, one possible explanation is that the tendency of language models to over-generate, hallucinate, and cover the long tail of possibilities is actually an asset, instead of a liability. And although there is a degree of degradation on out-of-sample problems, the degradation is not so severe that out-of -otto--iistrittiionn problems become utterly unsolvable: Instead, they merely become harder to solve, a phenomenon that allows adaptation to work in the first place.
Simultaneously one should be hesitant about claiming that PBE is 'solved.' Optimistically, current PBE benchmarks exist to test the frontier of what is possible, and so doing well on those benchmarks might just mean that the frontier has moved. More realistically, determining if an AI system truly works in the wild requires more than just pushing benchmark numbers, which can be mislcading when those benchmarks do not capture the long tail of naturally-oceurring tests. Furthermore, all Al systems present tradeoffs, and neural system's 's unpredictability. high computational cost, and out-of-distribution fragility should be weighed against whatever high benchmark numbers they may achieve. Despite these caveats, we are optimistic about the promise of tuning LLMs for PBE, and believe that it has the potential to dramatically expand the scope of solvable problems and even solvable domains.
Acknowledgements. We are grateful for assistance from Joshua Rule in the processing of the list functions data, and for feedback from Yewen Pu on the manuscript. This work supported by an NSF CAREER grant as well as gifts from Google and Cisco.
References
[1] Henry Lieberman. Your wish is my command: Programming by example. Morgan Kaufmann, 2001.
[2] Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium Principles of Programming Languages, POPL '11, page 317-330, New York, NY, USA, 2011. Association for Computing Machinery. ISBN 978 1450344900. doi: 10. 10.1145/1923385.19266
URL
https://doi. org/1/....gg1... wtt.r///...../1111111 /111///913385... 1926423
[3] Sumit Gulwani. Automating string processing in spreadsheets using input-output examples. SIGPLAN Not. 46(1):31731333 jan 2011. ISSN 13400 doi: 10.1145/1925444.19226
URL. htl.:tttt:://dd..rrgg// 11t.:o......1111111111 1926423
[4] Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. SIGPLAN Nor., 10710))177-126 oct 2015. ISSN 0362-13400 doi: 145/288988. 2814310. URL httpttttp///o..... org/10. 10. 11.....1111211..5... 2814310
[5] 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 Machine Learning, pages 1661-1672. PMLR, 2021.
10

---

[6] Sumit Gulwani, José Heráández-Orane Emanuel Kitzelmann, Stephen H Muggleton, Ute Schmid, and Benjamin Zorn. Inductive programming meets the real world. Communications of the ACM, 58(1 1)990999, 2015.
[7] François Chollet. On the measure of intelligence, 2019.
[8] Stephen H Muggleton, Ute Schmid, Christina Zeller, Alireza Tamaddoni-Nezhad, and Tarek Besold. Ultra-strong machine learning: comprehensibility of programs learned with ilp. Machine Learning, 107(7):1119-1))
2018.
[9] J Solomono Raymond. A formal theory of inductive inference i. Information and Control, 7: 1-22, 1964.
[10] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350(6266) 2015.
[11] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling. Felix Gimeno, Agustin Dal Lago, et al. Competition-level code generation with alphacode. Nature, 2022.
[12] Kensen Shi, Hanjun Dai, Wen-Ding Li, Kevin Ellis, and Charles Sutton. Lambdaheam: Neural program search with higher-order functions and lambdas. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. URL QVMPXXX4FR
[13] John K. Feser, Swarat Chaudhuri, and Isil Dillig. Synthesizing data structure transformations from input-output examples. In Proceedings of the 36th ACM SIGPLAN Conference Programming Language Design and Implementation, PLDI '15, page 229-239, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450334686. doi: 10.1145/ 2737924.2737977. URL httpt:ttt/oooiiiio org/ 10 1et.e.114//278810 2737977
[14] Nathanaël Fijalkow, Guillaume Lagarde, Théo Matricon, Kevin Ellis, Pierre Ohlmann, and Akarsh Nayan Potta. Scaling neural program synthesis with distribution search. In Proceedings of the AAAI Conference Arlificial Intelligence, volume 36, pages 6623-6630, 2022.
[15] Kensen Shi, Joey Hong, Yinlin Deng, Pengcheng Yin, Manzil Zaheer, and Charles Sutton. Exedec: Execution decomposition for compositional generalization neural program synthesis. In International Conference on Learning Representations, 2024.
[16] 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, 2024.
[17] Joshua S. Rule, Steven T. Piantadosi, Andrew Cropper, Kevin Ellis, Maxwell Nye, and Joshua B. Tenenbaum. Symbolic metaprogram search improves learning efficiency and explains rule learning in humans. Nature Communications, 2024.
[18] OpenAl. Gpt-4 technical report, 2023.
[19] Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateck Jain, and Sumit Gulwani. Neural-guided deductive search for real-time program synthesis from examples. arXiv preprint arXiv:1804.0 186, 2018
[20] Jacob Devlin, Jonathan Uesato. Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML 17, page 990-998. JMLR.org, 2017.
[21] Xinyun Chen, Chang Liu, and Dawn Song. Execution-guided neural program synthesis. In International Conference Learning Representations, 2018.
[22] Kensen Shi, Hanjun Dai, Kevin Ellis, and Charles Sutton. Crossbeam: Learning to search in bottom-up program synthesis. In International Conference Learning Representations, 2021.

---

[23] Bei Chen, Fengji Zhang, Anh Nguyen, Daoguang Zan, Zeqi Lin, Jian-Guang Lou, and Weizhu Chen, Codet: Code generation with generated tests. ICLR, 2023.
[24] Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven Hoi. CodeRL: Mastering code generation through pretrained models and deep reinforcement learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL httthttt::///peeeeeeee wttp:/iwwwwwwweeeeeeeeeee formm?dd WaGvb70zySA
[25] Eric Zelikman, Qian Huang, Gabriel Poesia, Noah Goodman, and Nick Haber. Parsel: Algo- rithmic reasoning with language models by composing decompositions. Advances in Neural Information Processing Systems, 36:31 0431166-333 165-31523, 2023.
[26] Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. Measuring coding challenge competence with apps. NeurlPS, 2021.
[27] 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 on code. arXiv preprint (Tti::100.0037744 2021.
[28] Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang. and LINGMING ZHANG. Is your code generated by chatGPT really correct? rigorous evaluation of large language models for code generation. In Thirty-seventh Conference Neural Information Processing Systems, 2023. URL httpps://ppenrevier... wttp:riiwwweeeeetonnnnnreeeeeee woreet/fooummiite htt.://rrmmmm111111110110110
[29] Linlu Qiu, Liwei Jiang, Ximing Lu, Melanie Sclar, Valentina Pyatkin, Chandra Bhagavatula, Bailin Wang, Yoon Kim, Yejin Choi, Nouha Dziri, and Xiang Ren. Phenomenal yet puzzling: Testing inductive reasoning capabilities of language models with hypothesis refinement. ICLR, 2024.
[30] Kevin Ellis. Human-like few-shot learning via bayesian reasoning over natural language. NeurlPS, 2023.
[31] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah D. Goodman. Hypothesis search: Inductive reasoning with language models. ICLR, 2024.
[32] Yizhong Wang, Yeganeh Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannaneh Hajishirzi. Self-instruct: Aligning language models with self-generated instruc- tions, 2023.
[33] Geoffrey E Hinton, Peter Dayan, Brendan J Frey, and Radford Neal. The" wake-sleep" algorithm for unsupervised neural networks. Science, 1188511)) 1995.
[34] Peter-Michael Osera and Steve Zdancewic. Type-and-exampl--direedd program synthesis. ACM SIGPLAN Notices, 50(6): 2015.
[35] Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In International Conference Learning Representa- tions, 2017. URL
[36] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv22206.046111 2022.
[37] Tessa Lau, Steven A Wolfman, Pedro Domingos, and Daniel S Weld. Programming by demon- stration using version space algebra. Machine Learning, 53:1 11-156, 2003.
[38] José Cambronero, Sumit Gulwani, Vu Le, Daniel Perelman, Arjun Radhakrishna, Clint Simon, and Ashish Tiwari. Flashfill++: Scaling programming by example by cutting to the chase. Proceedings of the ACM on Programming Languages, 7(POPL)952-988L 2023.
12

---

[39] Microsoft prose public benchmark suite, 2022. Available at https//githbb.ccommmrrroo//ppppp benchmarks.
[40] Jiayuan Mao, Xiuming Zhang, Yikai Li, William T. Freeman, Joshua B. Tenenbaum, and Jiajun
Wu. Program-Guided Image Manipulators. In International Conference on Computer Vision, 2019.
[41] Kevin Ellis and Sumit Gulwani. Learning to learn programs from examples: Going beyond program structure. IJCAI, pages 1638-1645, 2017.
[42] David D. Thornburg. Friends of the turtle. Compute!, March 1983.
[43] Catherine Wong, Kevin Ellis, Joshua B. Tenenbaum, and Jacob Andreas. Leveraging language to learn program abstractions and search heuristics. In JCML, 2021.
[44] Daya Guo, Qihao Zhu, Dejian Yang, Zhenda Xie, Kai Dong, Wentao Zhang, Guanting Chen, Xiao Bi, Y. Wu, K. Li, Fuli Luo, Yingfei Xiong, and Wenfeng Liang. Deepseek-coder. When the large language model meets programming the rise of code intelligence, 2024.
[45] Kevin Ellis, Catherine Wong. Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezamaa, and Joshua B. Tenenbaum. DreamCoder: Bootstrapping Inductive Program Synthesis with Wake-Sleep Library Learning, page 835-850. Association for Computing Machinery, New York, NY, USA, 2021. ISBN 9781450383912. URL https 1eee1111/34443 3454000
[46] Elias Stengel-Eskin, Archiki Prasad, and Mohit Bansal. Regal: Refactoring programs to discover generalizable abstractions. arXiv preprint arXiv:2401.16400 2024.
[47] Stephen H. Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretivee learning of higher-order dyadic datalog: Predicate invention revisited. Mach. Learn., 100 (1):49-73, jul 2015. ISSN 0885-6125. doi: 10.10077s10994444444447777 URL https
aodoi.org/I0 1007/510994001445477777
[48] Steven Piantadosi. Fleet. https://ggtab..ccmmpaaaaaaalll 2023. [Online GitHub repository].
[49] Rajeev Alur, Rastislav Bodik, Juniwal, Milo MK Martin, Mukund Raghothaman, Sanjit A Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. Syntax- guided synthesis. IEEE, 2013.
[50] Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma. Qingwei Lin, and Daxin Jiang. Wizardcoder: Empowering code large language models with evol-instruct, 2023.
[51] Jiacheng Ye, Jiahui Gao, Qintong Li, Hang Xu, Jiangtao Feng, Zhiyong Wu, Tao Yu, and Lingpeng Kong. Zerogen: Efficient zero-shot learning via dataset generation. arXiv preprint arXiv:2202.07992. 2022.
[52] Ajay Patel, Colin Raffel, and Chris Callison-Burch, Datadreamer: A tool for synthetic data generation and reprodueible Ilm workflows, 2024.
[53] Yu Meng, Jiaxin Huang, Yu Zhang, and Jiawei Han. Generating training data with language models: Towards zero-shot language understanding. Advances Neural Information Processing Systems, 35:462-477 477, 2022.
[54] Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, execute and debug: learning to repair for neural program synthesis. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS '20 Red Hook, NY, USA, 2020.
Curran Associates Inc. ISBN 978171.35 713829546..
[55] Shraddha Barke, Hila Peleg, and Nadia Polikarpova, Just-in-time learning for bottom-up enumerative synthesis. Proc. ACM Program. Lang., 4(0OPSLA), nov 2020. doi: 10.1 14.1 3428295. URLhttps: httphhtt///// :/doii org/10..111 1145/3428295
13

---

[56] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Joshua B. Tenenbaum, and Armando Solar- Lezama. Write, Execute, Assess: Program Synthesis with a REPL. Curran Associates Inc., Red Hook, NY, USA, 2019.
[57] Rishabh Singh and Sumit Gulwani. Predicting correct program in programming by example. 2015), July 2015. URL https://www micmosoft......mmmmmmmmm.m http//////eeeeearrpppuiiiieeeeee predicting a correct- program in aan-poggraminng
27th International Conference on Computer Aided Verification (CAV
eyy-exmplle//
[58] Percy Liang, Michael I. Jordan, and Dan Klein. Learning programs: a hierarchical bayesian approach. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, page 639-646, Madison, WI, USA, 2010. Omnipress. ISBN 175558977777.
[59] Jeevana Priya Inala, Chenglong Wang, Mei Yang. Andres Codas, Mark Encarnación, Shu- vendu Lahiri, Madanlal Musuvathi, and Jianfeng Gao. Fault-aware neural code rankers. In Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 13419-13432. Curran Associates, Inc., 2022. URL httpp/////pprreednnnnnnnnniiiice nwwrips. ceappp.. patccppppr_ffes______p_ee__eseee files/ pappr//022/fileee 0tw.000000077000002000002022--ee
pdf
[60] Wasu Top Piriyakulkij and Kevin Ellis. Doing experiments and revising rules with natural language and probabilistic reasoning. CogSei, 2024.
[61] Ruocheng Wang, Eric Zelikman, Gabriel Poesia, Yewen Pu, Nick Haber, and Noah Goodman. Hypothesis search: Inductive reasoning with language models. In The Twelfth International Conference on Learning Representations, 2024. URL hattps://oppereeeee wwwprrvvviieene/founnnn.. net/forum? id=G7UtIGQmjm
[62] Xinyun Chen, Maxwell Lin, Nathanael Schärli, and Denny Zhou. Teaching large language models to self-debug. arXiv preprint arXivv2304.05128, 2023.
[63] Sean Welleck, Ximing Lu, Peter West, Facze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. ICLR, 2023.
[64] Theo X. Olausson, Jeevana Priya Inala, Chenglong Wang, Jianfeng Gao, and Armando Solar- Lezama. Is self-repair silver bullet for code generation?, 2023.
[65] Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303.11366 2023.
[66] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information P Processing Systems, 36, 2024.
[67] Hao Tang, Keya Hu, Jin Peng Zhou, Sicheng Zhong, Wei-Long Zheng. Xujie Si, and Kevin Ellis. Code repair with 11ms gives an exploration-exploiaaee tradeoff. arXiv, 2024.
(68) Ansong Ni, Srini Iyer, Dragomir Radev, Ves Stoyanov, Wen-tau Yih, Sida Wang, and Xi Victo- ria Lin. Lever: Learning to verify singuage-t--code generation with execution. In Proceedings of the 40th International Conference on Machine Learning (3CML223), 2023.
j jina- mahaa-embediings-ee boge-bas-coom code, Accessed: 2024-05-22.
14

---

A Appendix supplemental material
A.1
Experiment Details
We used temperature of 1.0 for sampling in our experiments unless otherwise stated. All experiments were performed on single-node machines (8xA6000 or 8xA100, etc.) without a multi-node distributed computing setup.
A.1.1 List Tasks
We selected 50 problems from Rule et al. as our seed set, reserving the remaining problems for testing. To ensure comparability with Rule al., we tested on the first 100 problems (excluding those in the seed set), resulting in 77 test problems. We consistently used 10 input-output examples, with the remaining 54 examples serving as a held-out test set. When filtering duplicate synthetic data, we employed an open code embedding model [69] available on Hugging Face. As a sanity check, we also use 10 list list problems from X² benchmark and shown the model can effectively solve them in Table
A.1.2 String Tasks
We utilized 100 ttring-t--strnngnul transformation problems from the prose-benchmark. When available, we used 10 puput-uupput examples, always reserving least one example as a hold-out test set. This ensures the generalization of our synthesized programs, as the benchmark did not provide held-out data.
For the FlashFill baseline, we used Microsoft Excel for Mac version 16.8. We opened each individual xlsx file containing the test problem examples and manually triggered the FlashFill function by pressing Ctrl+E.
A.1.3 Logo Tasks
To facilitate graphics input inference with code language models, we converted logo graphics into ASCll-represented strings, as shown in Figure 5 For each input image, we cropped 512x512 section from the center and then divided it into 32x32 blocks, each with a size of 16x 16. counted the number of black pixels in each block, calculated their density (aum black pixels and quantized this 16-16
density value into 10 levels, represented by the ASCII numbers 0-9. By representing each block with ASCII number, an input image is represented with string of 32 lines, and each line has 32 numbers.
For the turtle graphics program, we adopted the Python turtle graphics program from Regal 46 with minor modification of changing the 'embed' function to use 'with context manager instead, calling it 'fork_state" This allows for equivalent but more readable code.
For the GPT-4o and GPT-4o mini multimodal baselines, directly images inputs. (See Section A.5.8 for the prompt template.)
A.2 Syntheic Dataset Generation and Training Parameters
present the dataset generation and training parameters Table. 2 and Table.
A.3
Adaptation Implementation Details
For adaptation experiments, we generally followed the settings described above, with few specific differences detailed below.
A.3.1 String Tasks
To induce domain gap (easier problems in Sygus compared to the harder, noisier problems in the Prose Benchmark), we first fine-tuned model using Sygus problems and then tested it on the Prose Benchmark. Due to the noisy nature of the Prose Benchmark (some problems have very few examples), adopted a setting where utilized all the test cases to select which problems were
15

---

List
String
Seed Dataset Source
Rule et al.
Prose (FlashFill++)) Problems
Seed Dataset Size
50
40
Synthetic Data Generator
deepseckcodeer-33-innttt
deepseckcooder333--mme
Synthetic Dataset Size
10k
10k
Sampling Tempereature
0.8
1.0
Similarity Filter
code embedding model
Filter Ratio
around 1/3 (threshold=0.93)
Synthetic Data Prompt
4-otot examples
10-shot examples
LoRA Finetuning
Model Used
deepseekcoder-
deepseekcoder-1..5
LoRA Rank
1024
256
LoRA
1024
256
Learning Rate
2.00E-04
2.00E-04
LR Schedule
cosine
cosine
Warmup Steps
10
Epoch
1
Batchsize
32
16
LoRA
33b Model Used for FT
deepscckcoder:33-iiitttee
doepseckkooder:33--nntrr
LoRA
256
128
LoRA a
256
128
Learning Rate
2.00E-04
2.00E-04
LR Schedule
cosine
cosine
Warmup Steps
10
10
Epoch
1
Batchsize
32
32
Table List task and String task synthetic dataset generation and finetuning parameters.
solved and then used them the seed programs for adaptation. This resulted in 64 solved problems out of the 100 problems in the benchmark.
A.3.2 List Tasks
To obtain the finetuned in-distribution result in Fig. Sa we fine-tuned on a synthetic dataset generated by seeding with 20 out of 100 problems from LambdaBeam, and tested on the remaining 80 problems.
A.3.3 LOGO Tasks
For LOGO adaptation experiments, we induce domain gap by using shorter programs (LoC S 12) of the training set, and tested on the longer programs (LoC > 12). The shorter programs training seed consists of around 80% problems (156 out of 200) from the original training set. The test set consists of 31 problems out of 111 problems from the original test set.
A.4 Model Performance on LambdaBeam Benchmark
We present the results both our 7B and 33B models on the LambdaBeam benchmark in Figure I0 We observed that even without min-tuning for this specific benchmark, and instead fine-tuned for the list-to-list problems from Rule et al., our models performed exceptionally well, surpassing the state-of-the-art results specifically designed for the LambdaBeam problems [12]
A.5 Prompts Used in the Experiments
A.5.1
Syntheic Data Generation Prompt
List
16

---

Logo
Seed Dataset Source
Regal Python Logo Programs
Seed Dataset Size
200
Synthetic Data Generator
deepseckcoder-333-ineee
Synthetic Dataset Size
32k
Similarity Filter
Filter Threshold
Synthetic Data Prompt
6-shot examples
LoRA Finetuning
Model Used
deepseekcoder- 1.5-7b-instruct
LoRA Rank
512
LoRA
512
Learning Rate
2.00E-04
LR Schedule
cosine
Warmup Steps
20
Epoch
3
Batchsize
64
LoRA Finetuning
Model Used
deepseekcoder--3---isttee
LoRA Rank
512
LoRA
512
Learning Rate
2.00E-04
LR Schedule
cosine
Warmup Steps
50
Epoch
3
Batchsize
64
Table 3: Logo task synthetic datasets generation and finetuning parameters
70
LambdaBeam
60
% Problems Solved
50
RobustFill
L2
ours-33b
10
ours-7b
0
250
500
750
1000
Search Budget (Num Samples)
Figure 10: Performance on LambdaBeam problems from Shi et al. 2023
17

---

are CS professor. You are providing set chal Challenging and diverse integer list to integer list function puzzle for your student solve.
Puzzle
Python function: input list of integers and return list of integers
"'python
(PROGRAM EXAMPLE 1}
Test cases:
Puzzle 2:
Python function: input list of integers and return list of integers
"'python
(PROGRAM EXAMPLE 2}
Test cases:
Following the above format, please provide functions each follow by 10 random test cases to check the function's 's correctness full coverage
String
Excel just introduce a new feature that allows user to use Python to perform data transformation.
Please generate a csv file with two columns. The first column the second column contains the contains the input data output data.
Following accompanying python function which showcasing the transformation of the input data to the output data.
Here 10 challenging examples showcaing the features
Example < csv
{INPUT OUTPUT EXAMPLE 1} <cr
Here is the Python function that help transform the first column to the second column.
..' ''python
{PYTHON EXAMPLE 1}
Example
csv
{INPUT OUTPUT EXAMPLE 2}
Here the Python function that help transform the first column to the second column.
".. "pyyhon
{PYTHON EXAMPLE 2}
18

---

heading (): get the current angle of the turtle Following the above format, please provide CSV file with two columns, containing between to 10 rows of data showing transformation from the first column to the second column. This csv data should illustrate a challenging and complex example, similar to the above examples. Following that, create a Python function designed to process this data. Be aware that this function will be tailored to not only accommodate the current data but also any future data that follows the same format structure.
Logo
Your task is to draw simple black and white graphics with the custom library. NOT THE BUILT TURTLE LIBRARY. You will use a custom turtle library, similar to the built-in turtle library, which sufficient for all tasks.
Here are all the available functions the custon turtle library:
forward(x): move forward x pixels
left(theta) rotate left by theta degrees right (theta): rotate right by theta degrees penup(): stop drawing
pendown (): start drawing (eleport y, theta): move to position (x, y) with angle theta
isdown (): check if the pen is down forward(x): Move forward pixels.
left (theta): Rotate left by theta degrees.
right (theta): Rotate right by theta degrees. penup (): Stop drawing.
pendown (): Start drawing.
teleport
theta): Move to position (x, y) with angle
theta.
heading() (): Get the current angle of the turtle. isdown (): Check if the pen down.
with fork_state A context manager that runs the code in the block using the current context and restores the original state afterwards. Allows you to nest programs. Internally, fork_state saves the turtle state (is_down, x, y, heading), executes the block, then restores the original state.
Graphic
Python program: draw an interesting graphic using our own custom turtle library the following program draws {PROGRAM EXAMPLE 1}
Graphic 2
Python program: draw interesting graphic using custom turtle library
the following program draws (PROGRAM EXAMPLE 2}
Following the above format, please provide more programs using our custom drawing library.
19

---

A.5.2 Prompt Template for Finetuning and Zero-Shot Experiments
A.5.3 List
Implement the function solve_puzzle that takes list of integers and returns list of integers. The function should satisfy the following assertions assert solve_puzzle (e.zzle(... ==
assert solve_puzzle (...)
assert solve_puzzle ( (...) =
A.5.4 List (fhain-of-Thhuuhh)
Implement the function solve_ solve_puzzle that takes list of integers and returns list of integers. The function should satisfy the following assertions: assert solve_puzzle (t..puuzzeee... ==
assert solve_puzzle (...)
assert solve_puzzle (eaileee.)) (...) ==
Please observe the relation between input and output and think step by step. Output the function in a markdown format the end.
Solution:
A.5.5 String
Implement the function edit_text that takes string and returns a string. The function transforms the input string to the output string. The function should satisfy the following assertions:
assert edit_text assert edit_text (...) == assert edit_text (...)
A.5.6 String (Chain-of-Thoughtt)
Please implement the function edit_text that takes a string input and returns modified string.
Note that you can import re, datetime, or any built-in Python library to solve the problem.
The function should satisfy the following test cases: assert edit_text (...) == assert edit_ ( (...) ==
assert edit_text ( (...)
Please reason through the problem and think step by step, and finally implement the function and output the full function implementation in markdown code block in the end.
A.5.7 Logo
Here is gray scale images representing with integer values 0-9.
{CONVERTED IMAGE STRING)...
20

---

Please write a Python program that generates the image using our own custom turtle module
A.5.8 Logo (Multimodal Few-shot)
Given the following custom Turtle graphics -like library, Please
use it to write program that draws the given image. "python
from myturtle import Turtle from myturtle import HALF INF, INF, EPS_DIST ANGLE turtle Turtle()
def (orss)
turtle. forward (dist)
def left(angle):
turtle.left (antee (angle)
def right
right (angle)
def
txleport(x, y, theta):
turtle. teleport (x, y, theta) penup():
def
turtle. curtle.penup()
def pendown():
purtle.pendor ()
def position():
return turtle turtle.y heading ():
def
return turtle. heading isdown()
def
return turtle. down def fork_state
Fork the current state of the turtle. Usage:
with fork_
forward (100)
left (90)
Borward(100)
unn
return turtle. TurtleState (turtle)
Below some example programs that draw the given images. <IMAGE>
Here is program that draws the above image. The figure is like a medium 8 gon. " "python
for in range (8)
forward (45.
<IMAGE>
Here program that draws the above image:
The figure is like 5 sided snowflake with medium circle and medium semicircle as arms.
''python
in range(5):
with fork_state ():
()
forward (2)
21

---

left(0.0) pendown
for i in range (HALF, INF): Powward(EPS.. D left (EFS_AAANAGLL for i in range (NL)= Porward(PPS (BFDDT((PS_DIST42))
(eftBAAANNLLE)
penup ()
forward (2)
left (0.0(
pendown ()
for i in range (HALF INF):
(EPS (BT
left (NGLE)
forward (0)
left (72.0)
"..
<IMAGE>
Here is a program that draws the above image. The figure like concentric circles. "''ython
for in range(8):
for in range (HALF_INF)
INF)
(eraardEPPSDDSSSS
left
(oggeHALE for in range (HALF INF): forward (EPS_ ())
STEST_IMAGE:
Output the program that draws the following image. Reason about the given image and write a program that draws it in a markdown code block.
Name
Description
ours-7B
ours-33B
Dedup
Remove duplicate elements from list.
Reverse
Reverse a list.
Droplast
Drop the last element in list. Drop the largest number(s) in list. Duplicate each element of list. Remove the odd numbers from list. Replace every item in list with first item.
Dropmax
Dupli
Evens
Multfirst
Multlast
Replace every item in list with the last item.
Shiftl
Shift all elements in list to the left.
Shiftr
Shift all elements in list to the right.
Table 4: 10 list -> list functions from X 13
22

---

AAAA
CCCCCC
533
0OOO0
COXDOO
AAAAAA
CRECE
Figure 11: All LOGO test problems: problems solved by our finetuned 33b model are marked as green
23

---

Drom
Figure 12: Hand-drawn LOGO test showing every generated sample. We built graphical interface to allow users to draw images as input. The sample budget for this demo is 64.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We provide experiment results to support our claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss several limitations in the limitation section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
25

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
We provide training settings and prompts used in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [No]
Justification:
We provided the detailed training settings and prompts in the appendix.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
icy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuiu wwwiicccguie//eeeeeeeeeis CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide experimental settings and details in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide error bars or confidence intervals when applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
27

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the information in the appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
The paper conform with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[NA]
The paper focuses on narrow domains of PBE problems and has limited impacts on society.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses a low risk.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We credit and follow the license terms properly.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
29

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing or human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "m3BuChX7kA", "reviewer": "Reviewer_CppC", "summary": "This paper investigates whether the long-studied programming by example task is \"solved\" by large language models with Turing-complete languages like python.\nTheir evaluation is on three domains: lists, strings, and LOGO/Turtle graphics.\nThey evaluate three LLM-based approaches, including a self-instruct-like fine-tuning approach that tunes LLMs on synthetic labeled data, and an adaption approach assuming access to problems (not solutions) from the testing distribution.\nCompared to several symbolic, neurosymbolic, and LLM baselines, the proposed approaches perform better.\nThe analysis of the correlation between different aspects of the target program indicates that the fine-tuned model is beyond blind guess-and-check.", "questions": "1. How much does a turing-complete language help in solving PBE, excluding the fact that LLMs have seen lots of python code? Is the expressiveness of a turing-complete language itself helpful?\n2. How far can the adaption go? Right now the adaption discussed is still within the same category of problems (such as lists), I imagine a more general PBE system might be able to adapt to problems that are more different.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The experiments are comprehensive, and the analysis of different predictors of model performance is helpful in understanding the extent to which LLMs solve PBE.\n2. The proposed methods make use of the fact that PBEs problems can be accurately synthesized using model-generated inputs and programs. The experiment results show that they are effective in solving in-domain problems and adapting out-of-distribution ones at test time.\n3. This paper answers some interesting questions regarding the role of LLMs for PBE and points out what researchers might work on in the future.", "weaknesses": "Contamination. As the authors acknowledged on Line 148, the problems could be in LLMs' pertaining data. I wonder if the authors have an idea of how much of a role such potential contamination plays in LLMs' superior performance. Is there anyway to rule out or minimize the impact of that confounder?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review, and for your support. Please see the global review for a PDF with new results (including a fun new LOGO experiment). We address your specific questions below.\n\n> Regarding Contamination\n\nWe avoided contamination as follows:\n1. String dataset: The datasets contain only input/output examples, and thus the program could not be in pretraining data.\n2. List dataset: The dataset from Rule et al. does not include program solutions, and furthermore, the dataset is in BigBench, which is conventionally excluded from LLM pretraining data.\n3. LOGO dataset: The python program LOGO dataset (from Regal) was released within 1 week of the beginning of training of deepseek (the model that we fine tune), so is almost certainly not in pretraining. Just in case, we further tried prompting the model to confirm that it cannot complete a partial ground truth python LOGO program.\n\nWe also tried running our system on new problems that we created by hand, illustrated in Figure 4, and also illustrated in the attached main-response PDF, where we ran the LOGO synthesizer on a hand drawing we made. The system was surprisingly able to handle all of these new problems that could not possibly have been in the pretraining data.\n\n> How much does a turing-complete language help in solving PBE, excluding the fact that LLMs have seen lots of python code? Is the expressiveness of a turing-complete language itself helpful?\n\nWe believe the expressiveness itself is helpful due to the fact that a handcrafted restricted programming language may not be able to capture the space of all user-desired programs, even within a single domain. For example, in Fig 4 (top), we can see that a simple example—numbering the lines of a paragraph—can easily be solved by our model but cannot be solved by FlashFill++. We believe this is a general problem with handcrafted domain-specific programming languages: Although they make the search space smaller and therefore more tractable, they inevitably exclude important computations.\n\nIn other words, LLMs benefit from both massive data *and* expressive Turing-complete programming languages. As a thought experiment, consider an LLM trained on trillions of programs in the FlashFill++ DSL: It would still be utterly unable to solve the problems in Fig 4.\n\n> How far can the adaption go? Right now the adaption discussed is still within the same category of problems (such as lists), I imagine a more general PBE system might be able to adapt to problems that are more different\n\nAdaptation hinges on solving at least some problems in the OOD target, and we have observed that after fine-tuning for domain A, the model can still solve some problems in domain B. We believe this is because LoRA finetuning does not cause *too* much catastrophic forgetting about domain B.\n\nWe’ll update to include experiments of cross domain adaptation (lists task adapt to string task, string task adapt to list task), which could be very interesting as progress toward truly general purpose program synthesis. Thanks for the suggestion!", "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": "5Xm8kEDL7o", "reviewer": "Reviewer_e1ch", "summary": "The paper performs a relatively thorough study on using LLM for example-guided program synthesis tasks. The results presented in the paper suggest that LLMs make strong progress toward solving the typical suite of example-guided synthesis tasks, potentially increasingly the flexibility and applicability of PBE systems.", "questions": "- (Typo) line 150, there should be a space between (Tbl. 1,Fig. 3b)\n- (Typo) figure 6a “Sygus” -> “SyGuS” \n- (Grammar) last sentence of Figure 4 caption has grammar mistakes\n- (Grammar) last sentence of Table 1 caption has grammar mistakes\n- Appendix A.2 is empty\n- I see in the prompt the authors wrote “You are a CS professor”. As far as I know this might not be the perfect prompt for code generation (this is just a joke).", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The PBE problem is interesting and well-motivated. Major papers in the field are well cited and referenced\n- Extensive amount of traditional datasets are being evaluated\n- The insights derived from experiments are somewhat valuable", "weaknesses": "- CoT and other simple prompting methods are not evaluated\n- While there is an extensive amount of experiments and comparisons, we find that the outcome is relatively predictable.\n- While the writing is generally okay and easy to understand, multiple typos and mistakes found in the writing (also mentioned in questions). Please consider fixing them.\n- The LOGO visual examples are converted to an ASCII grid of characters (Fig. 8b). This might not be the most intuitive representation. Details about the transformation is not shown, such as how each number (0-9) is derived, the resolution of the ASCII grid, etc. With this design, it does not make sense for a non-fine-tuned LLM to solve the task. But technically you could still fine-tune GPT-3.5 with these inputs, but I guess it is okay to not include this experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer e1ch for the thoughtful review. Please see the global response PDF for the requested LOGO graphics details, and below for other new experiments and responses to your specific questions.\n\n\n\n> CoT and other simple prompting methods are not evaluated\n\nThanks for the suggestion. We evaluated chain-of-thought and summarized the results below.\n\n- String Domain\n\n| Model           | Accuracy | \n| --------------- | -------- | \n| gpt-4-turbo with CoT | 76.5% | \n| gpt-4-turbo     |  73.9%      |\n| deepseek-33b |  70.6%  |\n| ours-7b | 76.9%|\n| ours-33b|**81.2%**|\n\n- List Domain\n\n| Model           | Accuracy | \n| --------------- | -------- | \n| gpt-4-turbo with CoT | 60.7% | \n| gpt-4-turbo     |  58.7%      |\n| deepseek-33b |  46.3%  |\n| ours-7b | 75.8%|\n| ours-33b|**79.0%**|\n\nWe'll update the manuscript to include these results.\n\n> the ASCII grid [for LOGO], etc. With this design, it does not make sense for a non-fine-tuned LLM to solve the task. But technically you could still fine-tune GPT-3.5 with these inputs, but I guess it is okay to not include this experiment.\n\nMotivated by your observation we ran a new experiment using the multimodal GPT-4o and GPT-4o-mini with a few-shot prompt as a baseline for LOGO. This baseline was prompted with example programs and images and then given a new test image to write a program for. Please see below:\n\n|System |Method Type|Accuracy|\n|---|---|---|\n|Ours-33b  | LLM + Symbolic | 90%|\n|Ours-7b                               | LLM + Symbolic       | 89% |\n|GPT-4o (new result)                        | VLM + Symbolic    | 59%|\n|GPT-4o-mini (new result)                        | VLM + Symbolic    | 25%|\n|Regal (ICML’24)           |LLM + Library Learning | 57%|\n\n> The LOGO visual examples are converted to an ASCII grid of characters (Fig. 8b). This might not be the most intuitive representation. Details about the transformation is not shown, such as how each number (0-9) is derived, the resolution of the ASCII grid, etc. \n\nPlease see the attached PDF, which shows an example of the ASCII transformation with a detailed conversion process in the caption. Interestingly, because the transformation down-samples the image, it is able to somewhat generalize to hand drawings, which we also show in the attached PDF, and would include in a revision.\n\n> Outcome is relatively predictable\n\nPapers in the past year find negative results for LLMs on PBE [1-3], and none try unusual PBE domains like our visual graphics programs. For example, our system beats the neurosymbolic LambdaBeam [3], and in LambdaBeam, they also compare to a strong LLM baseline - a Python fine-tuned LLM internal to Google - finding that the LLM is a poor PBE solver, counter to our findings. Our system also beats systems like DreamCoder [4] on unusual domains such as LOGO, where DreamCoder-like approaches are thought to excel. Our results are not predictable given the state of the recent literature.\n\n[1] Shi et al. ‘24 ICLR [2] Rule et al. ‘24 Nature Comms. [3] Shi et al. ‘23 NeurIPS [4] Ellis et al. ‘21 PLDI\n\n> Typos and grammar mistakes\n\nFixed! Thank you for pointing them out.\n\n> I see in the prompt the authors wrote “You are a CS professor”. As far as I know this might not be the perfect prompt for code generation (this is just a joke).\n\nWe will consider adding to the prompt “You are reviewer #2, please improve the code like how you would improve a paper” (this is just a joke).\n\nThanks again for the review and please let us know if we can answer any further questions.", "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": "cuz0XWgFoP", "reviewer": "Reviewer_mgYE", "summary": "The paper focuses on the classical task of Programming By Example (PBE): given some (input,output) pairs, the goal is to generate a program that \"fits\" these examples (producing the outputs when given the inputs), and also generalizes well to new inputs.\nThe paper evaluates mostly 7B and also 33B LLMs on three PBE tasks. The paper finds that finetuning these LLMs on these tasks further boosts their accuracy.\nThe paper also investigates out-of-distribution (OOD) generalization, and finds that OOD can be improved using a semi-supervised approach, where the model is given (input,output) pairs from the new domain (but not the desired program); then the LLM samples potential programs that solve the (input,output) pairs; if the program is correct (which can be validated) - it is added to the training set and the LLM is trained / finetuned again iteratively.", "questions": "1. Can the authors evaluate the baseline where the \"program\" is the LLM itself? That is, the LLM is trained/prompted to predict output to unseen inputs, without going through an explicit program. I am asking this specifically in light of Figure 4 - the examples there seem to be much more easy to solve directly with an LLM (in a few-shot prompting fashion, possibly with chain-of-thought), than to write an explicit program for.\n1. In L96 the authors write: \"we use samples from a generative model to train an inference network, but we do not further train the generative model itself\" - what does this exactly mean? What kind of model is each of the \"generative model\" and \"inference network\"? Which of them is a pretrained LLM? And why not further training the generative model itself?\n1. What exactly does the \"Search Budget (Num Samples)\" mean in the experimental section? Does that mean \"accuracy@k\" - sample $k$ different outputs, and consider the output as correct if *any* of these $k$ outputs is correct?\n1. In Figure 3 - What temperature was used, and what other temperatures did the authors explore, for their finetuned model and for the baselines such as GPT-4? Since evaluation depends on sampling of up to 200 outputs, the temperature might have a drastic effect on the success of each model. With a proper tuning of temperature, the order of curves in Figure 3 might be different.\n\n## Summary\nOverall, the paper is not wrong and is presented nicely, but its novelty is limited, I'm not sure about the validity of some of the results such as Figure 3, and most of its conclusions are expected. I am thus voting for a borderline reject.", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper is very clear and easy to follow, and it contains many examples that are visualized nicely.\n1. The paper connects modern LLMs with the classical problem of Programming By Example (PBE)", "weaknesses": "1. Undefined, non-scientific, message - the title of the paper is \"Is Programming by Example solved by LLMs?\". This title leads the paper (\"We investigate here the extent to which large language models pretrained on source code can solve PBE\"), but I think that it's an undefined question. What does \"solve\" mean? By construction, and according to the \"no free lunch\" theorem, PBE can never be \"solved\". So \"solving\" PBE just depends on the difficulty of the questions. Even if we could define \"solve PBE\", how would you measure it? Is 90% considered \"solved\"? Is 80% \"solved\"? This problem is further expressed in L214: \"absolute performance in LOGO remains poor\" - 16% accuracy is not \"poor\" when you do not compare it to anything. Any accuracy number below 100% is considered as \"unsolved\" as any other number, and 100% is not possible on a hard enough dataset (because of \"no free lunch\").\n\n1. Novelty - this is mostly an evaluation paper, that does not introduce any new approach or technique. Further, from the empirical evaluation, the answer to the question \"Is Programming by Example solved by LLMs?\" is, as expected, is \"somewhat, but not quite\": nothing in the empirical results was surprising or unusual: (a) finetuning LLMs on task-specific data works well; (b) semi-supervision on OOD data helps; (c) using Python as the output programming language works much better than the DSLs of classical work, because modern LLMs were trained on much more Python data than niche DSLs.\n\n1. The OOD claim is a bit weak, because only in the relevant section it is said that \"assuming we have access to problems drawn from the testing distribution\" (without their labels, but these labels can be sampled and validated).\n\n1. The paper compares its approach (a finetuned LLM) to classic symbolic, DSL-based (non-learning / non-neural) approaches several times throughout the paper, and speaks in favor of the LLM-based approach. This comparison to classic approaches is a bit of a strawman, since it is quite obvious that 33B LLMs are much more powerful than Flashfill (which is a paper from 2011) (Table 1).\nThe paper also mentions that:\n>We also find that the resulting system can cover a broader scope of problems than classic symbolic methods, owing to the use of a Turing-complete language, which, at least theoretically, allows learning any computable function.\n\nAnd I think that such claims completely miss the point: the reason that LLMs are better than classic symbolic methods is **not** the use Turing-complete languages. LLMs would have been better than classic symbolic methods even if the classic symbolic DSLs were turing-complete as well. The reason is that LLMs were trained on trillions of Python tokens.\n\n6. Another trivial claim: in Section 4.2, the authors find that \"posterior description length is more predictive than program size and prior description length\". Simplifying the paper's claim, without using words from probability, basically says: the perplexity of the desired output sequence is predictive of its accuracy on downstream tasks. I think that this claim is quite trivial, and is very common in practice in LLM training: measuring perplexity on a validation set is usually closely correlated with success on downstream tasks.  Isn't this posterior iexactly what the model was *trained* to predict?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. We really believe that our responses and new experiment can address your concerns, and hope that you will agree. Please see below.\n\n> empirical results was not surprising or unusual\n\nPapers in the past year find negative results for LLMs on PBE [1-3], and none try unusual PBE domains like our visual graphics programs. For example, our system beats the neurosymbolic LambdaBeam [3], and in LambdaBeam, they also compare to a strong LLM baseline - a Python fine-tuned LLM internal to Google - which was found to *not* do well on PBE. Our system also beats systems like DreamCoder [4] on unusual domains such as LOGO, where DreamCoder-like approaches are thought to excel. Our results should surprise the cited authors, and are unusual in that sense.\n\n[1] Shi et al. ‘24 ICLR [2] Rule et al. 2024 Nature Comms. [3] Shi et al. ‘23 NeurIPS [4] Ellis et al. ‘21 PLDI\n\n> does not introduce any new approach or technique\n\nA core part of the paper is a wake-sleep inspired algorithm for OOD generalization. Would you mind pointing us to a citation that we can refer to which previously introduced our specific approach/technique for adaptation?\n\n> The OOD claim is a bit weak... \"assuming we have access to problems drawn from the testing distribution\" (without their labels, but these labels can be sampled and validated).\n\nDeployed PBE systems are presented with a stream of \"testing problems\" generated by end users. In the wild, the requisite data is available for our adaptation technique.\n\n> What does \"solve\" mean?\n\nWe’ll revise to make explicit our different definitions of solve:\n1. Beating SOTA on mainstream benchmarks, including those used for deployed real world PBE systems [we solve in that sense]\n2. Beating SOTA on unusual benchmarks very different from pretraining data [we solve in that sense: LOGO]\n3. Achieving 100% success rate [we don’t solve in that sense, no free lunch]\n4. Being practical for deployment [we don’t solve in that sense]\n5. Generalizing out of distribution [partly: see our response above to \"The OOD claim is a bit weak\"]\n\n> “absolute performance in LOGO remains poor\" - 16% accuracy is not \"poor\" when you do not compare it to anything\n\nWe compare against 3 baselines (Fig 3)\n\n> Can the authors evaluate the baseline where the \"program\" is the LLM itself?\n\nThanks for the suggestion. Please see below for the result of your proposed baseline, which does well on strings but not on lists.\n\n- Strings\n\n|Model|Accuracy|\n|--|--|\n|gpt-4-turbo (LLM as program)| 74.0%|\n|gpt-4-turbo (Python program)|73.9%|\n|deepseek-33b (LLM as program)| 49.0%|\n|deepseek-33b (Python program)| 70.9%|\n|ours-7b|76.9%|\n|ours-33b|81.2%|\n\n- Lists\n\n|Model|Accuracy|\n|--|--|\n|gpt-4-turbo (LLM as program)| 45.5%|\n|gpt-4-turbo (Python Program)|58.6%|\n|deepseek-33b (LLM as program)| 23.4%|\n|deepseek-33b (Python program)|46.2%|\n|ours-7b|75.8%|\n|ours-33b|79.0%|\n\n> Another trivial claim: in Section 4.2, the authors find that \"posterior description length is more predictive than program size and prior description length\"... basically says: the perplexity of the desired output sequence is predictive of its accuracy on downstream tasks\n\nThank you for catching an error in the writing: By posterior we meant the marginal probability of solving the task under $q$ (marginalizing over sampled programs we found that pass), not evaluating perplexity of a single gold-truth target sequence. While it’s unsurprising this marginal is *at least* as predictive as the prior, it is noteworthy that it is *more* predictive than the prior, showing the LLM does not engage in blind guess-and-check, and did not merely learn to sample from the self-instruct distribution.\n\n> the reason that LLMs are better than classic symbolic methods is not the use Turing-complete languages... The reason is that LLMs were trained on trillions of Python tokens\n\nLLMs benefit from both massive data *and* expressive Turing-complete programming languages. As a thought experiment, consider an LLM trained on trillions of programs in the FlashFill++ DSL: It would still be utterly unable to solve the problems in Fig 4.\n\n> In L96 the authors write: \"we use samples from a generative model to train an inference network, but we do not further train the generative model itself\" - what does this exactly mean?\n\nWe sample from the generative model $\\mathcal{G}$, defined by prompting an LLM with seed problems (see L86). The inference network $q$ is our fine-tuned model (see L91). The prior $\\mathcal{G}$ is a function of the seeds, so by holding the seeds fixed, we don’t update/train the generative model further, deferring such updates to Eq 5 (Adaptation).\n\n> What exactly does the \"Search Budget (Num Samples)\" mean in the experimental section?...  [Do you] sample different outputs, and consider the output as correct if any of these outputs is correct?\n\nThanks for inviting this clarification. We model PBE in-the-wild where we commit to a single program and must run it on new unseen test inputs. This means we sample $k$ programs (the search budget), filter by the training input-outputs, pick a program randomly if more than one passes that filter, and finally report success only if that program correctly predicts all test input-outputs (following Eq 1). We will revise to clarify.\n\n\n> What temperature was used… Since evaluation depends on sampling of up to 200 outputs, the temperature might have a drastic effect on the success of each model\n\nThe first sentence of the appendix gives the temperature ($T=1$). We used this somewhat high temperature (by the standards of code generation) because we wanted more diversity in the outputs, and did not tune this parameter because of the high cost of our experiments.\n\nPlease let us know if you have further questions.", "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": "iZpqbEYUE9", "reviewer": "Reviewer_k14y", "summary": "This paper investigates the effectiveness of Large Language Models (LLMs) in solving Programming-by-Example (PBE) tasks. Evaluations are conducted on three classic PBE domains including lists and strings, as well as a graphics programming domain. The findings suggest that while pretrained LLMs are not inherently effective for PBE, fine-tuning significantly enhances their performance on in-distribution tasks.", "questions": "- How does GPT-4 perform on the entire PROSE dataset?\n\n- Would the key factors that lead to the success or failure of LLMs differ across problems in three different domains?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Thorough evaluation and detailed analysis.\n\n- Clear cases and illustrations.\n\n- Addressing the challenge of small datasets for fine-tuning LLMs.", "weaknesses": "- In the experiments, there are no LLM competitors in the graphics domain. Any reasons?\n\n- Why are only FlashFill and LambdaBeam compared in the experiments of Figure 6?\n\n- The adaptation method used to improve out-of-distribution performance exposes the model to the test set content beforehand. Especially in string tasks, directly selecting the adaptation seed program from all test cases may be unfair. \n\n- The examples used in the experiments are relatively weak and do not closely resemble real-world programming tasks.\n\n- If the adaptation's seed program is not provided, even after fine-tuning, the out-of-distribution generalization ability of LLMs still appear to be quite weak.\n\nTypos:\nin abs: potentially increasingly the flexibility -> potentially increasing the flexibility", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review. Please see below for a new experimental results that you suggested we run, together with our responses to your questions.\n\n> In the experiments, there are no LLM competitors in the graphics domain. Any reasons?\n\nThank you for your suggestion! We added the GPT-4o and GPT-4o-mini multimodal model results with image input. We summarize the results on the graphics domain as below:\n\n|System |Method Type|Accuracy|\n|---|---|---|\n|Ours-33b  | LLM + Symbolic | 90%|\n|Ours-7b                               | LLM + Symbolic       | 89% |\n|GPT-4o                        | VLM + Symbolic    | 59%|\n|Regal (ICML’24)           |LLM + Library Learning | 57%|\n|LILO (ICLR’24)             | LLM + Symbolic  | 41%|\n|DreamCoder (PLDI’21) |Neurosymbolic             | 31%  |\n|GPT-4o-mini                        | VLM + Symbolic    | 25%|\n\n(We updated our LOGO results because we found a small code issue post-submission; fixing that issue significantly improved our system, hence why our system's numbers above are better from the original submission, but the qualitative conclusions are the same.)\n\n> The examples used in the experiments are relatively weak and do not closely resemble real-world programming tasks.\n\nWe disagree for the following reasons:\n\n1. Text editing PBE is used *millions of times every week* [1]\n\n2. PBE is not about e.g. repo-level edits, but is instead about creating individual subroutines, including for users that can't even program. Accordingly the datasets we use cover real-world situations where an individual subroutine is desired. For example, the Shi et al. List dataset comprises 100 programming tasks manually designed to be interesting and useful in practice, while PROSE/SyGuS test common spreadsheet operations.\n\n3. Our benchmarks are typical ones for PBE on neural/symbolic systems, allowing comparisons of LLMs against the recent neurosymbolic literature, done as follows:\n\n\n|Domain| Work|               Venue|\n|---|----|----|\n|List |  LambdaBeam| NeurIPS ‘23|\n||Fleet|Nature Comms ‘24|\n|LOGO| LILO|               ICLR ‘24|\n||  Regal|              ICML ‘24|\n|| DreamCoder | PLDI ‘21|\n|String| FlashFill++|   POPL ‘23|\n\n[1] https://blog.sigplan.org/2021/09/14/the-story-of-the-flash-fill-feature-in-excel/\n\n> Why are only FlashFill and LambdaBeam compared in the experiments of Figure 6?\n\nFor lists, LambdaBeam is the primary comparison because it was designed specifically to solve the list benchmark Fig 6 evaluates on (and it does well on that benchmark).\n\nFor strings, FlashFill is the primary comparison because we are evaluating on holdout test inputs, and FlashFill++ does not report numbers for holdout tests (and FlashFill++ is not publicly available so we can't run it ourselves).\n\n> The adaptation method used to improve out-of-distribution performance exposes the model to the test set content beforehand. Especially in string tasks, directly selecting the adaptation seed program from all test cases may be unfair.\n\nMotivated by your comment we ran the OOD-adapted model on a random sample of never-before-seen PROSE problems (unseen during adaptation). We see that the domain gap is approximately halved:\n\n|strings| train SyGuS, test PROSE|\n|----|----|\n|before adaptation  |57.7%|\n|after adaptation  | 65.2%|\n|finetune in-distribution | 72.5% |\n\n> If the adaptation's seed program is not provided, even after fine-tuning, the out-of-distribution generalization ability of LLMs still appear to be quite weak.\n\nYes! Without (unlabeled) adaptation data, out-of-distribution generalization is quite weak. We hope to paint a nuanced picture of LLM abilities rather than claim LLMs are universally better along every dimension.\n\n> Would the key factors that lead to the success or failure of LLMs differ across problems in three different domains?\n\nPrimarily if the problems are in-distribution, which is why we focus on OOD adaptation methods.\n\nThank you for your input and please let us know if you have any further questions.", "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:
Thank you all for the helpful reviews. Please see your individual responses, but here we wish to include a PDF illustrating:
1. The conversion to ASCII art requested by reviewer e1ch. Interestingly, we also found that by down sampling the image to ASCII, it is able to somewhat generalize to hand drawings (also shown).
2. New baselines including a multimodal model for graphics programming (GPT-4o and GPT-4o-mini), chain-of-thought prompts, and others. (Our LOGO results are now higher than in the original submission because we fixed a small programming issue that was degrading performance)

Meta-review: This paper presents an evaluation of a variety of programming by example (PBE) by LLMs and "traditional" symbolic approaches. This work finds that off-the-shelf pretrained LLMs are not effective but can be tuned to achieve acceptable performance. This work further showcases a method for helping LLMs solve OoD with a "lightweight" adaptation.

Overall, this work considers an interesting problem and presents a good evaluation of different techniques for PBE and shows gaps in many LLMs. Since PBE requires core reasoning skills it shows gaps in existing systems. While there are a few additional evaluations that have been asked by the reviewers (which would be nice to see in a camera-ready), I believe that it would be valuable to publish this paper at this time.


### Minor
* Self-repair (ie multi-turn with execution feedback) is not included in the baselines and I believe it would be useful to compare to.
* A better discussion of (inference) cost vs accuracy is needed. If a symbolic system was given as much budget as an LLM needs (CPU-dollars vs GPU-dollars) to which extent would the results change?
Decision: Accept (poster)