Is Programming by Example solved by LLMs?

Authors: wen-ding  li
kevin  ellis
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:12:59

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.

Main paper: 
 introduction: 
 Programming-by-Example (PBE) systems solve a challenging task: Given input-output examples of a hidden algorithm, they seek to construct the source code of the underlying function [1, 2] . PBE is deployed to millions of users [3, 4, 5, 6] , lies near the heart of core AI challenges [7, 8, 9, 10] , and is a qualitatively different problem from the bulk of recent work on LLM code generation, because rather than generate source code from natural language [11] , 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-language 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 Turing complete languages like Python, unlike the restricted domain-specific 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 LLMs 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 [15, 16, 12, 17] . 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 an algorithm for taking a small unlabeled dataset of problems and adapting the LLM to it, which we find narrows this domain gap.The resulting recipe allows PBE over Turing-complete languages across three qualitatively different domains (Fig. 1 ): algorithms on vectors of numbers, string manipulation macros, and graphics programs in 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 models such as GPT4 [18] . 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. 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.We used a 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.We selected 50 To facilitate graphics input inference with code language models, we converted logo graphics into ASCII-represented strings, as shown in Figure 5 . For each input image, we cropped a 512x512 section from the center and then divided it into 32x32 blocks, each with a size of 16x16. We counted the number of black pixels in each block, calculated their density ( num black pixels 16•16), and quantized this density value into 10 levels, represented by the ASCII numbers 0-9. By representing each block with an ASCII number, an input image is represented with a 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 a minor modification of changing the 'embed' function to use a '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, we directly use images as inputs. (See Section A.5.8 for the prompt template.)We present the dataset generation and training parameters in Table . 2 and Table. 3.For adaptation experiments, we generally followed the settings described above, with a few specific differences detailed below.To induce a domain gap (easier problems in Sygus compared to the harder, noisier problems in the Prose Benchmark), we first fine-tuned a 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), we adopted a setting where we utilized all the test cases to select which problems were solved and then used them as the seed programs for adaptation. This resulted in 64 solved problems out of the 100 problems in the benchmark.To obtain the finetuned in-distribution result in Fig. 8a , 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.For LOGO adaptation experiments, we induce domain gap by using the shorter programs (LoC ≤ 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.We present the results of both our 7B and 33B models on the LambdaBeam benchmark in Figure 10 . We observed that even without fine-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] . 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 or structure .Your task is to draw simple black and white with the custom library . DO NOT USE THE BUILT -IN TURTLE LIBRARY . You will use a custom turtle library , similar to the built -in turtle library , which is sufficient for all tasks .Here are all the available functions in the custom 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 -teleport (x , y , theta ) : move to position (x , y ) with angle theta -heading () : get the current angle of the turtle -isdown () : check if the pen is down -forward ( x ) : Move forward x pixels . 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 be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
background: 
 Programming by Example considers synthesizing a program ρ given a vector of inputs X and corresponding outputs Y . Typically the program is expected to exactly fit the provided examples, ρ(X i ) = Y i , ∀i, where i indexes examples. The program ρ is drawn from a (potentially infinite) language L. Typically L is a domain-specific language designed for a specific PBE system, not a general-purpose programming language. For example, the PBE system FlashFill synthesizes string manipulation macros designed to automate common spreadsheet edits [2] . FlashFill's domainspecific language L includes commonly occurring regular expressions, together with string slicing and concatenation, and restricted forms of loops. The language L is also designed to allow polynomialtime construction of programs consistent with input-output examples. FlashFill's goal, like most PBE systems, is to generalize to hold-out test cases: inputs X ′ with (hidden) target outputs Y ′ .Pick a program ρ from {ρ ∈ L : ρEQUATIONIn 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] , a key enabler of practical PBE systems is the design of a carefully restricted domain-specific language L. The domain-specific language effectively hardcodes symbolic knowledge, focusing the system on what programs the human engineer thinks are most promising, but at the expense of the wider set of computable functions expressible in general-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 a program that reproduces the output data). Therefore, a truly general solution to PBEone which could express its solutions in general purpose programming languages, and cover most practically relevant problems-would be broadly applicable to many inductive inference problems, a point that has been long appreciated [9] .LLMs for solving programming problems have been recently very successful [11, 23, 24, 25, 26] . These systems typically input a prompt describing a 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 ρ k ∼ p LM (•|prompt). Pick a ρ ∈ {ρ k : ρ k (X i ) = ρ k (Y i ), ∀i} . Success: ρ(X ′ j ) = ρ(Y ′ j ), ∀j Unlike PBE, the primary driver of program generation is a natural language prompt, although inputoutputs may also be in the prompt [27, 28] . Recent work using LLMs to synthesize programs solely from examples has either obtained negative results [16, 12] , or focused on simple and/or nonstandard problems [29, 30, 31] , leaving the extent to which PBE is 'solved' by LLMs an open question.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 a 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 on 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 a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not 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 to address problems of privacy and fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
methods: 
 Basic prompting is the most straightforward way of performing PBE with a pre-trained model: Given input-output examples (X, Y ) a prompt is constructed and K programs are generated. Programs are filtered by the I/O examples, and a random satisfying program is returned:EQUATIONFine-tuning improves the above approach in a conceptually straightforward way. Given a dataset comprising tuples of programs and I/O examples, {(ρ, X, Y )}, we fine-tune the LM to predict a 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 no 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 as the graphics programs we consider.To assemble a large dataset of (ρ, X, Y ) triples we start with a small manually-constructed seed dataset, D seed , and then randomly generate new programs ρ and inputs X by prompting an LLM with members of D seed . The output Y comes from running ρ on X. The seed dataset effectively defines a prior over (ρ, X), notated G in Fig. 2 . We sample from G to collect many program-input pairs, but use program execution to predict Y , not an LLM. The resulting dataset, which we call D tune , is used to train an LLM to generate programs when prompted with input-outputs. As this fine-tuned LLM effectively learns to do probabilistic inference in the graphical model shown in Fig. 2 (right), we write this fine-tuned LLM as q θ (ρ|X, Y ). This inference network is trained to maximizeEQUATIONThis method is closely related to self-instruct [32] and wake-sleep [33] . Like self-instruct, we use prompting to bootstrap a large dataset from a small manually-constructed one. Our method differs by using the LLM to generate a hidden latent variable (the program) while a different generative process produces an observed variable (the program outputs). Like wake-sleep, we use samples from a 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-distribution problems. Adaptation. One of the most powerful features of source code as a 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 a basic approach to adapting to a 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 to 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 a generated program has correct behavior. This means we have an unlabeled dataset D adapt comprising input-outputs (X, Y ), as well as a labeled seed dataset D seed comprising triples (ρ, X, Y ). Adaptation proceeds by iterating between pretraining with G(D seed ), testing on D adapt , and adding back into D seed 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 i:train model:EQUATIONThe equations can be seen as a wake-sleep algorithm where "dreaming" corresponds to training q 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 on each iteration actually solving new problems from the unlabeled dataset. Theoretically this is guaranteed given enough inference-time compute (large K above). We explore in Sec. 4.3 the extent to which this holds in practice.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer Justification: We provide the information in the appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as 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 or failed experiments that didn't make it into the paper). 
experiments: 
 We study different LLM-approaches to programming-by-examples across three domains (Fig. 1 ):1. List functions is a PBE domain meant to model a "programmer's assistant". It concerns discovering algorithms that transform lists of numbers, given input-output examples. This problem statement has a long history within program synthesis [13, 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 spreadsheets or other documents. From string-to-string examples, the system generates edit macros for tasks such as reformatting dates, extracting fields from semistructured text, etc. [2, 37, 38, 4] . 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 [22] -which are easier-and PROSE [39] problems, which constitute the most challenging dataset of its kind [38] .3. LOGO/Turtle graphics is a domain whose goal is to synthesize a program that generates a target image. 1 Systems of this kind can be used both for high-level visual reasoning and for helping artists make structured edits to images [40, 41] . We use a dataset of geometric designs expressed as LOGO/Turtle [42] programs-where the programs move a simulated pen over a canvas-taken from Wong et al. [43] . To allow the LLM to visually perceive the input image, we convert the image to ASCII-art style strings; see Fig. 5 and Appendix. A.1.3.We prepare seed datasets for each domain, synthetically generate a large training set, and then fine-tune a DeepSeekCoder LLM [44] that was pretrained on source code. 2 For list functions we seed with 50 problems from Rule et al. 2024 ; For text editing, we consider seeding with either SyGuS or a 40-problem subset of PROSE; for LOGO we seed with 200 training-set problems in Wong et al. [43] .The resulting fine-tuned models are 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. 3a ), surpasses the best neurosymbolic search method from Shi et al. (Appendix Fig. 10 ), and surpasses GPT4. It also solves 100% of the list to list benchmark problems from λ 2 (a well-known symbolic synthesizer), shown in Appendix Tbl. 4: although plausibly, many λ 2 problems are in the pretraining data. On text editing, it surpasses the performance of FlashFill and approaches the level of FlashFill++ (Tbl. 1, Fig. 3b ). On LOGO, it solves 90% of the test set (Fig. 3c ), surpassing systems such as DreamCoder [45] , which introduced the first version of these LOGO problems. It also solves more problems than LILO 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 not use any language clues, generating purely from the image. In 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. 4 ). A problem is solved if the predicted program generates correct outputs on the holdout inputs. Metagol [47] , RobustFill [20] , and Fleet [48] results taken from [17] gen. accuracy oracle accuracy FlashFill 33% -FlashFill++ -≈100% ours, 33B 82% 88%Table 1 : Generalization accuracy: % problems where the program makes correct predictions on every holdout test. Oracle accuracy: % problems where a 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. 3There are caveats to the above results. First, the fine-tuned model essentially never produces a correct program on the first try: It requires tens or hundreds of samples, each of which is compared against the ground-truth input-outputs, and discarded if it contradicts the examples. On a GPU like the one we use (an Nvidia A6000) this rejection sampling takes on the order of a few minutes to solve a given problem. However, compared to classic enumerative program synthesizers [13, 49] , or even compared to those with neural guidance [35, 22] , proposing a few thousand programs is relatively little, and could not plausibly cover a significant fraction of the exponentially large search space. The second caveat is that the model degrades when tested out-of-distribution. An example of this degradation is illustrated in Fig. 6 , which tests the LOGO graphics model on hand drawings (after training on clean computer graphics). On the out-of-distribution hand drawing the model mostly samples programs that do not fit the data, but its accuracy does not fall to zero, meaning that with enough compute budget, it does actually generate reasonable programs. This foreshadows the results in Sec. 4.3, which more systematically studies out-of-distribution behavior.✅ Classic symbolic approaches to PBE, when they are based on enumeration, tend to 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 domain-specific language. What predicts success for these LLM approaches?To answer this question we investigate several hypotheses. First, potentially the success is determined 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 ρ, is -log p LM (ρ|G(D seed )). Description length under the prior would be a good predictor of success if the fine-tuned model engages in blind guess-and-check: simply learning the distribution G(D seed ), 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 q θ (ρ|X, Y )), which would be the case if the fine-tuned model attends closely to the input-outputs and reshapes its distribution accordingly, instead of defaulting to the prior. To test these hypotheses we calculate the average compute budget needed to solve each problem, and compare it with these different variables. Fig. 7 shows that posterior description length is more predictive than program size and prior description length: unlike classical methods, metrics of program length correlate poorly with problem difficulty, and there is no evidence that the fine-tuned model's behavior can be characterized as blind guess-and-check. (See also Fig. 5 ). . Using these splits we also measure the ability of the adaptation method in Sec. 3 to improve out-of-distribution generalization. 4Fig. 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 of 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. 8b ).We further perform the adaptation method described in Sec. 3 in order to measure the extent to which it can narrow these domain gaps. In every case it allows solving more out-of-distribution problems, increasing absolute performance by around 10% or 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).0 500 1000 1500 2000Search Budget (Num Samples) To better understand the dynamics of adaptation, we visualize the specific problems solved before and after adaptation on LOGO graphics (Fig. 9 ). Before adaptation, only a handful of out-of-distribution problems are solvable, and only with a 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 Before Adapt Solved After Adapt Solved when also trained with long programs  
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 an LLM to 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 is incorporated into future prompts. We similarly generate a dataset D tune by prompting an LLM with D seed , but (1) do not recursively prompt the LLM with its own outputs and (2) combine the LLM generations with program execution to make program outputs. This gives a different mathematical interpretation to our data generator. First, the programs are samples from a prior, G, defined by D seed , which would not be a valid interpretation if the LLM was repeatedly fed its own outputs. They use domain-specific 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 [4, 2] .LLMs as inductive reasoners. Using an LLM to perform inductive reasoning-to generate abstract hypotheses from concrete specific examples-has been explored by several recent works [29, 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-Debugging, 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, 65, 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.Ranking LLM-generated code. Past work considers a variety of ways to select an output from a collection of LLM-sampled programs [23, 59, 68, 11] , many of which are 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. 
limitations: 
 Our work has important limitations. From an engineering perspective, using a 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 one-off tasks. For this reason, true deployment to end-users 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 to 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, it also just pushes the question back one stage further: What exactly about specific problems causes the neural network's approximate posterior to put more or less probability mass on correct solutions? While in classic PBE one can obtain sharp answers as to why a certain problem was solved or not, this is a 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 symbolic baselines we know of, even for uncommon domains such as LOGO graphics. Why is that? Fundamentally, the neural network only needs to 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-distribution 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 misleading when those benchmarks do not capture the long tail of naturally-occurring tests. Furthermore, all AI systems present tradeoffs, and a neural system'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.A Appendix / supplemental material A. 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: The paper conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration 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]Justification: The paper focuses on narrow domains of PBE problems and has limited impacts on society.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 or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification: The paper poses a low risk.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.This is PBE with a single example and null input, effectively compressing the image into a program.We prefer DeepSeek because it is roughly LLaMA-level, but has fully open training details.The FlashFill results were obtained using Microsoft Excel for Mac.We 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 to run. 
 
 Appendix:  


Decision: 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?

Reviews: review: paper_summary: paper_summary: This paper investigates whether the long-studied programming by example task is "solved" by large language models with Turing-complete languages like python.
Their evaluation is on three domains: lists, strings, and LOGO/Turtle graphics.
They 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.
Compared to several symbolic, neurosymbolic, and LLM baselines, the proposed approaches perform better.
The analysis of the correlation between different aspects of the target program indicates that the fine-tuned model is beyond blind guess-and-check.
strength_weakness: strength_weakness: 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?
questions: 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?
2. 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: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: - CoT and other simple prompting methods are not evaluated
- While there is an extensive amount of experiments and comparisons, we find that the outcome is relatively predictable.
- 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.
- 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.
questions: questions: - (Typo) line 150, there should be a space between (Tbl. 1,Fig. 3b)
- (Typo) figure 6a “Sygus” -> “SyGuS” 
- (Grammar) last sentence of Figure 4 caption has grammar mistakes
- (Grammar) last sentence of Table 1 caption has grammar mistakes
- Appendix A.2 is empty
- 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: limitations: N/A
paper_summary: paper_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.
The 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.
The 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.
strength_weakness: strength_weakness: 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").

1. 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.

1. 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).

1. 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).
The paper also mentions that:
>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.

And 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.

6. 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?
questions: 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.
1. 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?
1. 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?
1. 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.

## Summary
Overall, 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - In the experiments, there are no LLM competitors in the graphics domain. Any reasons?

- Why are only FlashFill and LambdaBeam compared in the experiments of Figure 6?

- 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. 

- The examples used in the experiments are relatively weak and do not closely resemble real-world programming tasks.

- 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.

Typos:
in abs: potentially increasingly the flexibility -> potentially increasing the flexibility
questions: questions: - How does GPT-4 perform on the entire PROSE dataset?

- Would the key factors that lead to the success or failure of LLMs differ across problems in three different domains?
limitations: limitations: NA

Comments: title: Response to authors
Response to authors
comment: Thank you for your support and for helping us improve our work!
Thank you so much for your support and for your help in improving the paper; we will revise accordingly. We're very encouraged by your comments on the paper's potential impact on the program synthesis community!
Thanks for the responses, which have addressed some of my concerns. I have increased the score.
Thank you for the clarifications.

I am not convinced by the novelty of the wake-sleep algorithm, and I do not think that this is a significant part of the paper.
It could have been much easier for me to accept the paper if it was presented as an evaluation paper, without trying to claim novelty on the algorithm. I think that the paper can be more easily accepted by the audience as well if it was presented as an evaluation paper, so if I were the authors I would tone down the novelty of the algorithm.

However as an evaluation paper, it is a good paper, and I hope that it will finally convince the rest of the program synthesis community to work with realistic LLMs and Python.
I increased my rating from 4 to 6, good luck!
Thank you for your engagement. Our biggest disagreements concern the novelty of the methods and whether the empirical results are surprising. Please see below.

## **Methodological Novelty**

> So, what is the difference between this paper and [self-instruct, wake-sleep]?

Our adaptation algorithm is a novel hybrid of self-instruct and wake-sleep. Unlike self-instruct it can update its prior using new (unlabeled) data. Unlike wake-sleep it can adapt from few examples, via in-context learning. Mathematically this can be understood by looking at Equation 5 and making the following observations---which we’re revising to include right after Equation 5:

> Equation 5 should be seen as a wake-sleep algorithm where "dreaming" corresponds to training $q$ on fantasy data (first equation) while "waking" corresponds to running inference and updating the prior $\mathcal{G}$ (by updating the seed, second pair of equations).

Thank you for pushing us to clarify the writing concerning the novel conceptual aspects of our work. The revision will include the above two paragraphs.

(Last, you should think of adaptation as wake-sleep: finetuning is like only having the sleep phase.)

## **Significance of Empirical Results**

To avoid subjectivity, it’s helpful to consult the literature to understand what those in the area would find surprising/noteworthy/significant. Papers in the last year find negative results on LLMs for PBE:
1. [ICLR ‘24, from DeepMind](https://arxiv.org/pdf/2307.13883) pg 7: **"LLMs in general perform poorly on program synthesis tasks specified only through I/O examples"**, *even for PaLM2 Unicorn, the largest PaLM2 model*
2. [Nature Comms. ‘24, Rule et al](https://www.nature.com/articles/s41467-024-50966-x): see Fig 3
3. [ICLR ‘24: Hypothesis Search](https://arxiv.org/abs/2309.05660) evaluates on ARC **finding GPT4 underperforms older symbolic solvers** (see [here](https://arxiv.org/abs/2402.03507) and [here](https://arxiv.org/pdf/2103.05823))
4. [NeurIPS ‘23: LambdaBeam](https://arxiv.org/abs/2306.02049): As you point out this compares against a first-gen medium-size PaLM, but the above ICLR ‘24 paper compares against the latest-and-greatest PaLM2 Unicorn and arrives at similar conclusions.

Our findings go beyond merely cheerleading LLMs. We instead show how to train small open models (7B, not RLHF’d) to surpass both bespoke neurosymbolic methods and massive closed-source systems, and also investigate uncommon creative applications such as visual graphics code. (Surprise is subjective, but we were *shocked* when LOGO graphics worked!)

## **Miscellaneous**

> I just said that the OOD argument is a bit weak

Although weakness/strength is subjective/relative, it’s helpful to consult the relevant literature for comparison. OOD for neural program synthesis has been previously studied using [architecture/prompt engineering](https://arxiv.org/pdf/2307.13883) or [handcrafted feature engineering](https://arxiv.org/pdf/1912.12345). Our (wake-sleep$\cap$self-instruct) algorithm instead does unsupervised domain adaptation, requiring **just tens of unlabeled OOD examples**. This is more generic and scalable than handcrafting features/prompts/architectures, hence a major strength of the approach relative to the prior art.

> “absolute performance in LOGO remains poor" - 16% accuracy is not "poor" when you do not compare it to anything.

The full quotation reads: "absolute performance in LOGO remains poor (*compare Fig. 6c to Fig. 3c*)". Contrasting Fig. 6c (OOD) to Fig. 3c (in-distribution) shows LOGO OOD performs poorly (but please see the updated LOGO results in the global response).

> But would it change the downstream results if we improved any DSL to be Turing complete?

Yes, because symbolic systems like FlashFill++ hinge on the clever design of non-Turing complete languages to judiciously restrict the search space. Going Turing-complete destroys the tractability of search and significantly impairs performance for (neuro)symbolic methods. (See [DreamCoder page 13 ](https://dl.acm.org/doi/pdf/10.1145/3453483.3454080): So intractable, search used a *year* of CPU time).

> I would still argue that beating SOTA does not mean that the problem is "solved".

Yes, hence why we propose five different subjective notions of “solve”, instead of merely declaring victory upon beating SOTA. The "scare quotes" were meant to emphasize the subjectivity of the quoted term, but we can revise to avoid "solve", including changing the title of the paper.

## **Parting Words**

Obviously, we’re butting heads. But arguing these points has clarified to us how to communicate precisely what it is that is methodologically novel and empirically significant, and we’re confident that refactoring the writing can make that come through in the final paper. While we’d love to have your support, even if we don’t, thanks for forcing us to communicate these issues more clearly.
Thank you for your response.

>Papers in the past year find negative results for LLMs on PBE [1-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] 

* LambdaBeam compared to PaLM 62B - PaLM is also ~2 years old, and as far as publicly known, pre-RLHF. I am not surprised that the most recent GPT-4 performs significantly better.
* DreamCoder (2020), while being algorithmically clever, was also in the pre-LLM era.
* I'm not sure what is the "Shi et al. ‘24 ICLR" - can you please give a link? I don't think it is cited in your paper.
* I also cannot find a public link to "[2] Rule et al. 2024 Nature Comm" (although it is cited, I can't find a PDF).

>A 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?

As I understand from the paper, the wake-sleep inspired algorithm is explained under standard "finetuning", and "adaptation" starts only later (in page 4). Is the wake-sleep inspired algorithm for finetuning or adaptation?
Further, regarding the novelty of the wake-sleep algorithm, as mentioned in the paper:
>This method is closely related to self-instruct [29] and wake-sleep [30]. Like self-instruct, we use
prompting to bootstrap a large dataset from a small manually-constructed one. Our method differs
by using the LLM to generate a hidden latent variable (the program) while a different generative
process produces an observed variable (the program outputs).

So, what is the difference between this paper and [29,30]? That a **different** model generates the program outputs, instead of being the same model?

>Deployed 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.
It's a similar setting for a variety of machine-learning-based systems (e.g., Google Translate, Siri, etc.). 
If a system depends on "a stream of testing problems generated by end users", how does it respond to the first end-user queries? The authors's argument is almost like saying: "in a real system, we will wait for a few (hundreds? thousands?) queries to be sent, and only then we will be able to respond".

In contrast, a machine learning system that "truly" generalizes OOD, should ideally generalize starting from the first OOD example. 

I know that it's OOD generalization starting from the first OOD example is not trivial and is still one of the open problems in machine learning - I just said that the OOD argument is a bit weak.

>Beating SOTA on mainstream benchmarks, including those used for deployed real world PBE systems [we solve in that sense]

I would still argue that beating SOTA does not mean that the problem is "solved".

>>“absolute performance in LOGO remains poor" - 16% accuracy is not "poor" when you do not compare it to anything

>We compare against 3 baselines (Fig 3)

I don't understand this response - LOGO is "graphics", right? Which means Fig 3(c)? Isn't "Ours" better than the baselines there? So why is performance considered "poor"?

> Please see below for the result of your proposed baseline, which does well on strings but not on lists.
Thank you for these additional results.

>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.

But would it change the downstream results if we improved any DSL to be Turing complete?

>. 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.

Tuning the best temperature for each model separately can significantly affect the results and the order between the models.
This tuning is only needed at test time.