Program Synthesis with Large Language Models

Introduction

Program synthesis is a longstanding goal of artificial intelligence research (Manna and Waldinger, 1971; Waldinger et al., 1969; Summers, 1977; Shaw et al., 1975; Pnueli and Rosner, 1989; Manna and Waldinger, 1975), dating as far back as the 1940s and 50s (Copeland, 2012; Backus et al., 1957). There has been a recent resurgence of interest in techniques (both symbolic and ‘neuro-symbolic’) for synthesizing programs (Balog et al., 2017; Devlin et al., 2017; Ellis et al., 2018, 2020; Odena et al., 2020), but these techniques have largely been applied to restricted domain-specific languages (DSLs) (Gulwani, 2011) or to languages that are more fully featured but that nevertheless are designed specifically with synthesis in mind (Odena and Sutton, 2020). Modern general-purpose languages like Python or C++ have mostly been out-of-reach as targets. This is unfortunate, because it materially restricts the set of possible downstream applications. Synthesis methods that target problems across domains in general purpose languages have the potential to enable new tools that benefit the workflows of both novice and expert programmers.

Two emerging themes from the research literature point to a possible new approach for this problem (for a more detailed review, see Section 8). First, large language models have shown impressive new abilities to generate natural language text (Brown et al., 2020; Raffel et al., 2019) and to solve a rapidly expanding set of modeling and reasoning tasks (Devlin et al., 2019; big-bench collaboration, 2021). Second, over the past decade, machine learning approaches have been applied to source code text to yield a variety of new tools to support software engineering (Allamanis et al., 2018a). This work has included pre-trained deep models such as CuBERT (Kanade et al., 2020), CodeBERT (Feng et al., 2020), PyMT5 (Clement et al., 2020), code2vec (Alon et al., 2019), and other T5 models trained on code (Mastropaolo et al., 2021).

Combining these two themes raises the question of whether large language models for natural language can be brought to bear to synthesize code in a general-purpose language. Such models emit code in ‘token-space’, and so it is not necessary to explicitly encode the grammar of the underlying language—they learn it from data. Furthermore, these models can be trained on large quantities of code, so they can learn about how various libraries interact with each other and what idiomatic, human-readable code looks like. Finally, large language models allow us to consider a more flexible type of program specification: in contrast to classical work on program synthesis that specifies the program using logical constraints or input-output examples (Gulwani et al., 2017), a program can be specified by a short natural language description, possibly combined with a few (e.g., 2 or 3) input-output examples.

In this paper, we study how a collection of large Transformer language models performs when applied to the synthesis of short programs written in general purpose programming languages. Examples of problems and model output are shown in Figure 1 and Figure 2.

In particular, this paper makes the following contributions:

We introduce two datasets to test Python code synthesis. The first is a new dataset called Mostly Basic Programming Problems (MBPP). It contains $974$ short Python functions designed to be solved by entry-level programmers, text descriptions of those programs, and test cases to check for functional correctness (Section 2.1). This dataset consists of a large set of crowd-sourced questions and a smaller set of questions edited and hand-verified by the authors. The second is a Python synthesis dataset, containing $23914$ problems, produced by rewriting the solutions to a subset of the MathQA dataset (Amini et al., 2019) into Python (Section 2.2). We call this dataset MathQA-Python. These two datasets exercise different points in the space of synthesis tasks: MBPP contains more usage of imperative control flow such as loops and conditionals, while MathQA-Python contains more complex natural language descriptions.

On both datasets, we show that a large language model performs surprisingly well at few-shot synthesis of Python programs from a prompt (Sections 4 and 7). Fine-tuning further on each of the datasets yields a further increase in synthesis performance. This is especially notable for MBPP because the fine-tuning set is extremely small (374 synthesis problems). We evaluate the model performance at scales ranging from 244M to 137B parameters, finding that performance continues to improve with increased model size. The largest models that we consider can synthesize solutions to 59.6% of the problems from MBPP using few-shot learning. For most model sizes, fine-tuning increases performance by about 10 percentage points. On the smaller, hand-verified MBPP dataset, we observe that the synthesis task is indeed easier: For the 100 problems that occur in both the original and edited datasets, few-shot model performance increases from 63% on the original dataset to 79% on the edited dataset. On the MathQA-Python dataset, the largest model achieves few-shot accuracy of 33.4% while fine-tuning it leads to a very high accuracy of 83.8%.

Going beyond single-step program synthesis, we study the model’s ability to engage in dialog about code and improve its performance in response to natural-language feedback from humans (Section 5). We find that the model is able to incorporate short natural language hints to repair its outputs and clarify under-specified prompts, increasing few-shot performance from 30% without human feedback to 65% with four turns of dialog, yielding a 50% error reduction (Section 5.1).

We explore the semantic grounding of our models, investigating the extent to which these models can execute code given specific inputs (Section 6). We find that even our largest models are generally unable to predict the output of a program given a particular input, whether few-shot (Section 6.1) or with fine-tuning (Section 6.2). This suggests a large gap between what these models are doing and what we would consider “understanding.”

We analyze sensitivity of performance to a variety of factors, including model size, number of examples in the prompt, the identity of examples in prompt, sampling technique, etc. Furthermore, we investigate two potential criticisms of synthesis from large language models: First, we find that solutions tend to generalize to held-out test cases, rather than simply parroting the answers in the prompt (Section 4.4), although there are occasional exceptions (Section 4.5). Second, we find that the overlap between the solutions in MBPP and the pre-training set is small, reducing the chance that our synthesis results are due to memorization (Section 4.8).

Our work is closely related to two recent efforts. The first is the APPS dataset (Hendrycks et al., 2021), which is a dataset of 10,000 problems from coding competitions. Hendrycks et al. (2021) evaluate large language models on this data, specifically finetuned GPT-2 (Radford et al., 2019) and GPT-Neo (Black et al., 2021), as well as few-shot prediction with GPT-3 (Brown et al., 2020). Additionally, several datasets have been proposed to train and evaluate program synthesis methods based on data from programming competitions (Section 8.3). However, performance on these benchmarks has generally been poor. We conjecture that this is because programming competition problems are written in a style that obfuscates the underlying algorithms necessary to solve them. By contrast, our Mostly Basic Programming Problems dataset is designed to contain a more basic, literal description of the problems. We believe this shifts the focus more toward capabilities directly related to generating and understanding code.

Secondly, and independently, Chen et al. (2021) have presented Codex, a Transformer LM on code following the GPT-3 architecture, evaluating its synthesis performance on a new benchmark of simple programming problems. The main differences are in the specifics of the pre-training data, and in the way that we investigate the model’s performance. First, the training set for our models somewhat oversampled web pages that contain code, such as programming question and answer sites (see Section 3), but unlike Chen et al. (2021), the results reported in this paper do not include a further fine-tuning step on a large corpus of open-source code. Second, while the HumanEval benchmark introduced by Chen et al. (2021) is nominally similar to our MBPP, there are some differences: A small difference is in the type of prompts; while the HumanEval dataset generally contains I/O examples of the desired functions, their number and formatting is not consistent, in a way that mimics docstrings of professional software. In contrast, our dataset consistently contains three I/O examples, written as assert statements. We also evaluate our models on the MathQA dataset, which is completely different in character. Third, we report synthesis results for models of size up to 137B. We find that even our general LM, without code fine-tuning, has non-negligible performance on few shot synthesis, and we find that fine-tuning that model on a very small (374 items) set of examples is already enough to dramatically improve performance on synthesis tasks. Fourth, and perhaps most interestingly, we analyze the extent to which our LMs can be used as interactive tools, and present results showing that humans can interact with these models to significantly improve their success rate. Finally, in keeping with our goal to explore and understand the performance of general-purpose language models on this task, we also explore whether these models can evaluate the code that they generate, and whether they are equally effective at generating code that solves traditional mathematical word problems.

Datasets

We construct two new datasets: one entirely new and the other modified from an existing benchmark. The first, Mostly Basic Programming Problems (MBPP), is an entirely new crowd-sourced programming dataset. The second is derived from the MathQA dataset (Amini et al., 2019) but casts the problem solutions as short Python programs.

The Mostly Basic Programming Problems dataset contains $974$ short Python programs constructed by crowd-sourcing to an internal pool of crowdworkers who have basic knowledge of Python. We asked crowd-sourcing participants to write a short problem statement, a single self-contained Python function solving the problem specified, and three test cases that check for semantic correctness of the function. Participants also provided a ground-truth solution that passes all three test cases. Participants were instructed to write descriptions concrete enough that a human would be able to translate them into code without clarifications. They were also instructed to write code that is self-contained (that is, it runs by itself) and that does not print any results to the console. Use of internet references was allowed.

The problems range from simple numeric manipulations or tasks that require basic usage of standard library functions to tasks that require nontrivial external knowledge, such as the definition of particular notable integer sequences. Figure 1 shows an example problem statement with the associated test cases and a sample from our largest model prompted with that problem statement. To further characterize the contents of the dataset, we randomly sampled 100 of the questions and assigned one or more descriptive tags to each question. Of these questions, 58% were mathematical in nature (e.g., calculating the volume of a sphere), 43% involve list processing, 19% require string processing, 9% involve integer sequences, and 2% center around the use of other data structures. We did not impose any restrictions on the number of lines of code in the reference solution. The average, median, and maximum number of lines of code are 6.8, 5, and 50 respectively. The natural language descriptions are typically short, usually one sentence each.

While inspecting the dataset, we observed that some questions used uncommon function signatures (such as passing in a list and its length as two separate arguments to a function), lacked detail, were somewhat ambiguous (e.g., “Write a python function to count the number of squares in a rectangle.”), or performed unexpected operations in a function that were paired with the provided tests (e.g., casting a float to an int before returning it, with the test performing integer comparisons). Given this, we manually inspected, edited, and pruned a subset of the questions, yielding $426$ hand-verified questions, which we refer to as the edited dataset. For each question in the edited dataset, we ensured it had a standard Python function signature, that it was unambiguous to a human, and that its test cases accurately reflected the text description. We conduct most experiments on the full dataset, but analyze the effect of the curation of the edited dataset in Section 4.9.

In the experiments described later in the paper, we hold out $10$ problems for few-shot prompting, another $500$ as our test dataset (which is used to evaluate both few-shot inference and fine-tuned models), $374$ problems for fine-tuning, and the rest for validation. For evaluations involving the edited dataset, we perform comparisons with $100$ problems that appear in both the original and edited dataset, using the same held out $10$ problems for few-shot prompting and $374$ problems for fine-tuning. We have programmatically checked that all reference code passes all tests under Python 3.6, and we have open-sourced all of the problems.111https://github.com/google-research/google-research/tree/master/mbpp

2 MathQA-Python

Compared to the short natural language descriptions in MBPP, our second dataset is representative of a different kind of program synthesis task. The MathQA dataset (Amini et al., 2019) is a dataset where each data point consists of a mathematical word problem, multiple-choice answers for that problem, and a program in a domain-specific language that produces the correct answer. To evaluate whether pre-training on source code is useful for this task, we translate this dataset into a Python program synthesis dataset by translating the ground-truth programs from the domain-specific language given in the paper to Python code. We refer to the converted dataset as MathQA-Python. Compared to MBPP which contains more usage of imperative control flow such as loops and conditionals, MathQA-Python contains mostly straight-line code, but more complex natural language descriptions. An example from this dataset is shown in Figure 2. Both the Python code and DSL code are used for fine-tuning and few-shot experiments. For the few-shot experiments, in the prompt we provide four examples of MathQA problems with their Python (or DSL) solutions. The model is tasked with returning Python or DSL code that computes the ground truth answer. We execute the sampled code to check for semantic correctness. This method of checking correctness forced us to filter the MathQA dataset to keep only those problems for which the code evaluates to the declared numerical answer, resulting in us removing 45% of problems. After this filtration we are left with $23914$ problems, of which we use $19209$ for training, $2822$ for validation and $1883$ for testing. The translation between DSL and Python is straightforward and we supply code that can be used to perform it.222https://github.com/google/trax/blob/master/trax/examples/MathQA_Python_generation_notebook.ipynb

Model and Methods

The models we use in this paper are dense left-to-right decoder-only Transformer language models (Vaswani et al., 2017) trained on a combination of web documents, dialog data, and Wikipedia. Our experiments were conducted using models with non-embedding-parameter-counts ranging from 244 million to 137 billion. The pre-training dataset for the model contains 2.97B documents, which were tokenized into 2.81T BPE tokens with a vocabulary of 32K tokens using the SentencePiece library (Kudo and Richardson, 2018). This data included web sites with both computer code and text, such as question and answer sites and tutorials, but source code files themselves were not specifically included, except where code appeared in other web sites. These web sites with code and text comprised about 13.8M documents containing 18.7B BPE tokens out of the pre-training data.

We test synthesis capabilities for both MBPP and MathQA-Python under two regimes: First, we use few-shot prompting as in Brown et al. (2020). We hold out several example problems for the prompt and concatenate them, resulting in a longer version of the prompt seen in Figure 1 (or Figure 2 in the case of MathQA-Python). We then feed this prompt to the pre-trained model for completion. Second, we fine-tune the model on a training set. For MBPP, the training set is quite small (374 examples), so we fine-tune with a small learning rate (3e-5 for the largest model) for only 100 steps. For MathQA-Python, we fine-tune for longer. We generated the execution results using roughly analogous methods; see Section 6 for more details.

For all synthesis experiments, we measure functional correctness of the sampled code rather than some proxy for code quality like token accuracy or BLEU (see Section 4.7 for more about this). For the MBPP synthesis experiments, we check whether the code passes a set of test cases when executed (see Figure 1 for example test cases). For each problem in the test dataset, we use temperature sampling (with temperature 0.5) to generate 80 samples of code and then execute the code contained in the samples against tests for semantic correctness. The MathQA synthesis experiments are analogous.

For the MBPP execution experiments, we check whether the model produces exactly the same results as executing the code. We use greedy decoding (temperature set to 0.0) to generate a single approximate most likely generation, and compare this to the string generated by executing the code.

MBPP Synthesis Results

Our primary results on MBPP are shown in Figure 3 and Figure 4. We show absolute performance and scaling behavior with model size for both few-shot (in the sense of Brown et al. (2020)) and fine-tuning across nearly three orders of magnitude. We find that samples from our models are able to solve a large fraction of the problems in the dataset, in the sense that the sampled code passes the three given test cases, and that synthesis performance scales approximately log-linearly with model size.

We measure performance as a function of parameter count in two different ways: the fraction of problems that are solved by any sample from the model and the fraction of samples that solve their respective problem. The fraction-of-problems metric is a natural notion of correctness, because if this model were to be used in practice, we could automatically filter out model samples that do not pass the test cases. The fraction-of-samples metric, by contrast, gives a sense of the overall reliability of the model. We find that performance according to the fraction-of-problems metric is quite predictable while performance according to the fraction-of-samples metric is less so.

We observe limitations on the types of problems these models can solve (some are simply unsolvable) and many solved problems tend to have only 1 or 2 (out of 80) samples which solve the task. We examine this and other limitations in later sections. We also find that our results are not strongly sensitive to the number of examples (asserts) shown to the model, but do depend strongly on the specific examples provided as prompts.

We measure synthesis performance at various model sizes, from 244 million parameters up to 137 billion. As explained above, performance is measured in two different ways: First we measure—for each problem independently—whether that problem was solved by any of the samples drawn from the model for that problem. Performance on this metric scales predictably with model size: the fraction of tasks solved is linear in the logarithm of the model size. The largest model can solve roughly 60 percent of the problems it sees given 80 samples. For this metric, fine-tuning seems to give a roughly constant boost in performance across model sizes. See Figure 3 (left) for more details. Second, we measure – across all samples generated for all problems – the fraction of samples solving their respective task. This corresponds to the area under the curve in Figure 4 and is depicted in Figure 3 (right). Performance on this metric improves as model size increases, but it scales up less predictably than does performance on the first metric. For this metric, fine-tuning tends to improve performance, but the relationship between fine-tuned performance and few-shot performance is much more variable as a function of model size than for the other metric.

Additionally, we analyze the types of errors made by the models: Figure 6 shows the breakdown of error types as a function of model size for the few-shot experiments. We define runtime errors as any errors (other than syntax or type errors) that cause the program not to produce a result. For most model sizes, runtime errors are more common than syntax errors; even the smallest models can write syntactically correct Python code around 80% of the time. However, type errors and other syntax errors do represent the majority of samples drawn from the smallest model. As model size increases, the frequencies of both run-time and syntactic errors decrease dramatically. For the largest (137B) model, over 63% of all failures are due to failing the test assertions, as opposed to run-time or syntactic errors.

2 Synthesis Performance is Insensitive to Number of Test Cases in Prompt

The example prompt in Figure 1 shows all three of the test assertions that the model output will be checked against. We measured whether including less than 3 of the assertions in the prompt would result in a serious drop in performance. Interestingly, it did not: the model with 3 asserts in the prompt solved only 3 extra problems compared to the model with 1 assert only. This suggests that the model is mostly not using those test cases to reason about semantics. More specifically, it also suggests that, even though we prompt the model with all three test asserts, the model is in general not “overfitting” to test-cases (though we explore exceptions in Section 4.5).

3 Performance is Sensitive to Prompt Examples

While model performance is not strongly sensitive to the number of test cases included in the prompt, few-shot performance is quite sensitive to the particular examples given in the prompt. We measure this sensitivity in Figure 6, where each seed corresponds to a particular, distinct choice of prompting examples. We find that while one set of examples (seed 14) is able to solve 60% of tasks, many other examples solve far fewer.

The large influence of these prompt examples is also noticeable qualitatively: failed synthesis attempts often include references to e.g. a data structure that was instantiated in one of those examples in the prompt. These results suggest that methods such as prompt-tuning (Li and Liang, 2021; Lester et al., 2021) could yield substantial performance improvements in this domain.

One failure mode for the poorly performing prompts is that they lead to long, repetitive samples. Often, very long prompts produce many samples that do not fit with the 512 token context window (even with a context window of 1024 tokens, this failure mode is still pronounced). Qualitatively, we notice that short prompts with compact examples that make use of external libraries lead to the best synthesis performance.

We also find that the set of problems solved with one prompt seed is not always a strict subset or superset of another: for example, seed 13 solves 19 problems (39, 62, 100, 168, 188, 206, 209, 233, 254, 315, 340, 365, 368, 382, 400, 434, 471, 474, 497) which are not solved by seed 14. Ensembling these prompts by counting a problem as solved if it is solved by any of the seeds boosts the percentage of problems solved from 59.6% to 66.4%.

4 Solutions Typically Generalize to Held-Out Test Cases

Consider task 11 from MBPP, which asks the model to "Write a python function to remove first and last occurrence of a given character from the string.". All of the solutions emitted by our best model pass all three test cases, but the test cases do not fully test the function’s semantics (as shown in Figure 7).

None of the test cases use strings which contain more than than two of the specified character. Upon inspection, we realized that all of the sampled solutions would simply delete all occurrences of the specified character. To estimate how widespread this phenomenon was, we sampled 50 of the 500 test programs and wrote ‘adversarial’ tests cases for them. On those 50 problems, 33 had solutions solving all of the normal test cases, and 29 had solutions solving all of the normal test cases and all of the ‘challenge test cases’, for solution rates of 66% and 58% respectively. Thus, we can roughly estimate that something like 12% $((66-58)/66)$ of what we are counting as solutions (e.g. in Section 4.1) would fail to satisfy adversarially generated test cases. This is a nontrivial fraction, but it also means that almost 90% of solutions will generalize in the sense measured here.

5 Programs Sometimes Overfit to Assert Statements

Very occasionally, the model will produce a solution that passes the test cases trivially by reading the assert statements and trying to hard-code an if-expression that passes them. For example, one of the problems asks for a function that checks if a given integer is a Woodall number (that is, a number belonging to the sequence $1,7,23,63,159,383,895,...$). This problem includes three asserts (see Figure 8), only one of which specifies a number that is actually a Woodall number: 383. The model simply emits a program that returns True if the input is 383 and False otherwise, which is not correct.

This is interesting and perhaps somewhat alarming, though it also highlights that the model does have some abstract notion of the relationship between the test cases and the generated program. We can infer from the results in Section 4.2 and 4.4 that this “overfitting” to the test cases is not a widespread problem.

6 Sampling Strategy is Critical for Good Performance

Since tests or input-output examples can be machine checked, it is standard (Devlin et al., 2017) for synthesis algorithms to generate and evaluate many samples (often even enumerating and checking all possible programs). We investigate the scaling performance of our largest model with the number of samples evaluated across different sampling strategies: temperature sampling with varying temperatures and beam search. Figure 10 shows the number of tasks solved by the 137B model as the number of samples increases. We find that lower temperatures (more greedy decoding) perform better with only a single evaluation allowed, but higher temperature, less greedy strategies begin to solve more tasks within a budget of 10 samples. We also find that beam search performs extremely poorly, worse than any of the temperature settings considered – empirically we found this was due to beam search often producing results that looped or repeated lines of code endlessly.

7 Synthesis Performance Correlates Poorly with BLEU Score

As noted by Hendrycks et al. (2021) and Chen et al. (2021), we find that BLEU score between generated samples and reference programs does not correlate well with synthesis performance. Figure 10 shows two curves: the fraction of samples which solve a given task and the average BLEU score of samples compared to the reference program. We find little correlation between the two. This can be explained by the fact that semantically identical programs can potentially have very low $n$-gram overlap; for example, because of identifier renaming.

8 Pre-train / Test Overlap Seems to be Minimal

A common concern about results on large language models is that the models are likely to have seen something substantially similar to the test data in their very large training set, causing the test accuracy to overstate performance in practice (Brown et al., 2020). Even though we created this dataset from scratch, it is still possible that this is an issue for some tasks for two reasons. First, some tasks are very simple (e.g. ‘reverse a string’) and so surely will be represented in the training data in some way. Second, crowd-sourcing participants may have made use of reference materials from the internet that could also have appeared in the pre-training dataset for our models.

To quantify this concern we investigated how many lines of code appear in both the training data for our models and the ground-truth programs for the Mostly Basic Programming Problems. We examined each document in the pre-training data (excluding non-English documents and conversational data) and counted the number of lines that overlap with the ground-truth program for each problem. We then found the document with the most matching lines and the number of matching lines in MBPP. We stripped whitespace at the beginning and end of the line. We excluded lines from this analysis which appear more than twice anywhere in MBPP, as these are likely to be common Python keywords such as return or continue.

Figure 11 contains a visualization of the results. Broadly speaking, there was not much overlap. Only 32 of 974 problems (3.3%) had more than half of their lines matched somewhere in the pre-training data and 91.5% had only one or two lines of code that overlapped with the training set.

9 Comparing Performance Between the Original and Edited Questions

As described in Section 2.1, we created a subset of the larger MBPP dataset consisting of questions that were manually inspected and edited for consistency. We then ran experiments on 100 questions that appear in both the original dataset and this edited dataset. In this set of 100 questions, 56% of the questions’ text was edited, 30% of the test cases were edited, and 71% included edits to either the questions or test cases. Using this dataset, we ran experiments using few-shot prompting for models with 8B, 68B, and 137B parameters.

Table 2 summarizes model performance on the original and edited dataset. As can be seen, model performance increases when using the edited dataset for each experiment. Table 3 shows that 16-19% of the problems can be solved using one dataset, but not the other, across model sizes. Within this same subset of problems, for 81-100% of the problems, the model is able to produce a correct solution using the edited version of the question, rather than with the original version (across model sizes tested). However, within this subset of questions, 12-31% had no differences in either the question text or test cases for the three model sizes, indicating general variability in model performance.

We manually examined each of the 38 problems for which model responses (on the sanitized and unsanitized data) were not both right or both wrong. In these 38 problems, 15 included edits to the problem text, but not the test cases, 7 problems included edits to the test cases but not the problem text, 7 included edits to both the problem text and test cases, and 9 problems had no edits to either the problem text or test cases.

For the 15 problems whose problem text was edited, but had no changes to the test cases, 11/15 included more detail in the problem text (e.g., specifying that a list should be flattened and summed, where the “flatten” detail was previously omitted). 4/15 of the edits included details related to the function’s signature (e.g., specifying that a list of lists should be returned), 2/15 removed requirements (such as the requirement to use a regex in the solution code), and 2/15 rewrote the problem text. For the seven problems with edits to both the problem text and test cases, 5/7 included more details and 2/7 added details related to the function’s signature.

For the 7 problems with differences in the test cases, but no differences in the problem text, 3/7 edited test cases modified the problem’s function signature (e.g., changing it to return a list rather than a string representation of a list), 2/7 problems attempted to perform comparisons between floating point numbers directly (rather than testing whether the numbers were approximately equal), one set of test cases tested floating point equality for a function that returned integers, and one problem added an additional test case. For the seven questions with edits to both the problem text and test cases, 3/7 changed the function signature of the test, 2/7 created a more robust test (comparing sets rather than lists, when order was not important for a function returning a set of unique values), 1/7 corrected floating point comparison issues, 1/7 fixed an error in a test case, and 1/7 added a test case.

In general, these observations suggest the importance of specificity and details in the natural language request sent to the model, with more details seeming to lead to a higher likelihood of the model being able to produce correct code (as might be expected). Having a function signature that matches conventions also seems to be important (which is also expected).

10 Qualitative Analysis of Error Modes

To deepen our understanding of model behavior and error modes, we conducted a qualitative error mode analysis by examining hand-verified problems for which most samples were incorrect, culminating in several themes (Table 4).

First, difficult problems (as measured by model performance) often had multiple constraints or multiple implicit sub-steps. For example, the question “Write a function to find the maximum difference between the number of 0s and number of 1s in any sub-string of the given binary string” involves not only counting 0s and 1s, but also finding substrings. Likewise, “Write a function to find the longest palindromic subsequence in the given string” requires both finding palindromic subsequences and determining the longest one. In contrast, easy problems tended to be shorter and more atomic (e.g. “Write a python function to find the sum of an array.”). In multiple-constraint problems, the model often generated a partial solution that addressed only a sub-component of the problem. For instance, in the digits example above, one model solution correctly counted 0s and 1s but did not do so over all substrings. In the palindrome problem, the model merely recorded indices of mirror-imaged letters, but did not use those indices to find palindromic subsequence and did not write logic to find the longest one. This suggests that the model may struggle more with complex, multi-part problems that combine many atomic operations.

Problems with more-common siblings:

Relatedly, some low-performing problems appeared to have variants that are more common, resulting in the model solving a more common version of the problem. For example, given the problem “Write a python function to find the largest number that can be formed with the given list of digits.”, the model found the largest number among the list of digits, rather than the largest number that can be formed from them. A similar error occurred when a complex problem asked for the “maximum difference” but the model computed the “maximum” instead. Given the plethora of problems on the internet that involve finding the largest number from among a list, this model behavior is perhaps not surprising. However, given that the model may latch onto keywords found in ubiquitous programming problems, this does pose a unique challenge for the long tail of problems that may be closely related to (or have keywords in common with) typical programming problems. We might consider these types of errors “linguistic off-by-one” errors, where a small change in words might lead to a large semantic difference.

Miscellaneous errors:

Other miscellaneous error patterns included difficulty solving advanced math problems (e.g. “Write a function to find the nth hexagonal number”), producing incomplete skeleton code rather than the code itself, or a failure to apply common-sense reasoning (e.g. “convert a list to a tuple” led the model to convert each item of the list into a tuple).

Human-Model Collaboration Results

While large language models are impressive program synthesizers in some respects, they are far from being able to reliably solve difficult engineering problems without intervention. This raises the question of whether these models can be useful as interactive tools that can refine or correct their predictions in response to user feedback. We are specifically curious about two possible forms of collaboration:

Whether a human and model together are able to solve tasks that are challenging for either alone.

Whether human feedback can help a model refine its outputs, especially in the presence of initially ambiguous or under-specified requests.

In this section, we conduct preliminary experiments to measure the extent to which these forms of collaboration are possible. For concurrent work that addresses these topics, also see Jiang et al. (2021).

We select 50 problems from the edited MBPP dataset (see Section 4.9) and assign human participants to collaborate with the model to solve these tasks using only natural language dialog. The model is prompted as in the experiments in Section 4, but with few-shot examples and priming asserts given as dialog turns: for instance "I need to write a function called [function name]. Here’s a description: [docstring].". The model sees several examples of collaboration in this few-shot prompt, after which the dialog with the participant begins. Participants were instructed to provide one-sentence hints or corrections to the model that would guide the model toward finding the correct solution. The hints were allowed to contain references to Python identifiers, but not large snippets of code, and participants were limited to a maximum of four hints. The full set of instructions given to participants can be found in Appendix A.2.

The results of this experiment (Figure 13) support the hypothesis that these models can improve or correct code based on human feedback. Counting all four dialog turns, the fraction of problems solved is increased from 30% to over 65%, and counting only one, from 30% to 55%. The purple horizontal line in Figure 13 corresponds to the fraction of problems solved when the model is allowed to use five samples instead of 1, so there is a sense in which a one-sentence human correction is worth more than a five-fold increase in the number of samples allowed. Furthermore, human feedback allows the model to solve 10 problems that it was totally unable to solve without human assistance. There are, however, diminishing marginal returns to human feedback, as might be expected.

Figure 14 shows two example interactions with the model which allowed it to solve previously unsolved problems. In the first, a human was able to point out mistakes the model had made as a result of an under-specified natural language prompt (mistakes a human was able to infer by looking closely at the assert statements). In the second example, the model predicts an overly complicated solution, which a human is able to tweak and correct over a number of follow-up turns.

2 Qualitative Analysis of Human-Model Dialogs

To gain a better understanding of how useful large models can be as assistive tools, we conducted a qualitative analysis of success and failure modes using the interactions collected for the above experiment, resulting in the following broad themes:

Humans are able to clarify under-specified prompts by examining test cases. Many problems do not precisely specify every detail of the semantics of the desired program. For example, one question in the original dataset asks the user to "write a function to count the most common words in a dictionary", but the test cases make clear that the function should only return the 4 most common words, and in descending order by frequency. The model, even when given these test cases, was unable to ‘understand’ those requirements. A human was able to tell the model to sort the output, reverse its order, and return only the top 4, which allowed the model to solve the problem. This interaction is shown in Figure 14 (Left).

Humans can often correct small context errors (often import and identifier errors). The model also frequently makes import or identifier errors, for example by forgetting to import a module it used in its code. Typically, a single dialog turn was enough for humans to help the model correct these errors (for example, by saying "Great, but you never imported the re module."). Humans also tended to help the model fix variable misuse errors (in which, for instance, an un-defined variable is referenced) in one turn. We also observed the model returning True instead of False, which a single dialog turn could correct.

The model can lose track of context or previously referenced code. We observed several cases where the model modified its code in an incorrect way in response to user feedback, but struggled to revert it or incorporate pieces of prior results. For instance, it rarely responded well to "No, please go back to the previous response." or "Great, but you need to use the function signature from your first response.". This problem became more pronounced as the number of dialog turns increased.

Program Execution Results

A common criticism of language models like the ones we use in this paper is that they learn statistical correlations between tokens without an underlying world-model or mechanism for systematic reasoning, and therefore do not understand the meaning of what they are describing (Bender and Koller, 2020). On the other hand, recent work has provided evidence that, in some natural language contexts, pre-trained Transformers are able to implicitly construct approximate representations of the semantics of the worlds they describe in text (Li et al., 2021). We would like to ask a related question for code: Do pre-trained language models understand the underlying semantic state of the code they are synthesizing? Computer programs are an especially promising domain for this kind of analysis, because unlike natural language, the semantics of a program can be defined precisely, by specifying the result of its execution.

In this section, we investigate to what extent our models have this understanding by asking them to predict the result of executing the ground-truth programs from MBPP on test inputs. We also study how this execution ability is related to synthesis performance.

We are specifically interested in the following questions:

Can models execute Python functions, and how does execution performance depend on what information is in the prompt?

How does fine-tuning on execution tasks impact the performance of execution?

How does fine-tuning on execution tasks impact the performance on synthesis tasks?

In asking these questions, we are inspired in part by previous work that specifically trains deep architectures to learn how to execute programs (Zaremba and Sutskever, 2014; Bieber et al., 2020). In contrast to that work, our goal is to use the learning-to-execute problem as a lens to understand the capabilities of large language models over source code, rather than to obtain the best model of program execution per se. To answer these questions, we conduct a series of experiments, focusing on our largest model (137B).

In our first experiment, we evaluate the few-shot performance of our 137B model on code execution. For each task, the MBPP dataset contains ground truth source code, a natural language description, and three input-output examples. We task the model with predicting the output of the ground truth program if it is run on one of the given test case inputs. Since this performance might be sensitive to details of the prompt, we investigate how execution performance depends on that information. Specifically, we ablate the presence or absence of the ground truth code, natural language description, and test cases in the prompt. This results in seven different prompt configurations, as shown in Table 5.333 We note that the prompt types which do not contain source code should probably not be referred to as execution tasks; for example, the case where only input-output examples are included is equivalent to what has been dubbed “neural program induction”. (Devlin et al., 2017) The prompt templates for each prompt condition can be found in Listing 1 in the Appendix. We query models using a sampling temperature $T=0.0$, which is equivalent to greedy decoding.

In our first set of experiments (Table 5, left), we evaluate correctness on a single test case. For prompt configurations requiring test cases, we use the two remaining test cases. Overall execution performance is relatively poor, with accuracy never exceeding 29% for any prompt type. Results indicate that including test cases in the prompt seems to help more than any other individual component. Including test cases and natural language descriptions in the prompt lead to the highest overall performance—higher than using the code itself. Because the code unambiguously describes the semantics, whereas test cases do not, this suggests that models are in some sense not really “reading” the source code and using it to execute. Models trained on general text corpora may be better at inducing patterns from as few as two input-output examples than they are at predicting the execution of code.

Evaluating on only one test case might provide a noisy overestimate of functional correctness. Therefore, our second set of experiments (Table 5, right) investigates whether the models can correctly infer the output for multiple test cases. For this experiment, we only judge a sample correct if it gives the correct output for both test cases. Accuracy for testing on two examples is lower than for one example. For the prompt configurations in Table 5 that do not include test cases, the prompt does not change between this experiment and the last one, so the drop in performance across these configurations must be due to the model failing to generalize across test-inputs when predicting the execution result.

2 Fine-tuning on Execution Slightly Improves Execution Performance

To test the effects of fine-tuning on execution performance, we construct a fine-tuning corpus for execution, built using the 374 training and 90 validation tasks used for synthesis fine-tuning (Section 2.1). For each task, we include an execution trial for each of the 7 prompt configurations from Section 6.1. We also vary the number of test cases in the prompt and test cases to test on (also as in Section 6.1). This gives a total of 14 related data-points for each task. Overall, this fine-tuning corpus consists of $14\times 374=5236$ training data-points and $14\times 90=1260$ validation data-points. We fine-tune for 100 steps using a batch size of 8192 tokens per batch.

Our fine-tuning results are shown in Table 5. Our results indicate that fine-tuning improves the performance of code execution, but that this improvement is not present when test cases are part of the prompt. In particular, there is a positive difference between fine-tuned and few-shot performance only for prompts which contain source code but do not contain test cases.

3 Fine-tuning on Execution has a Small Effect on Synthesis Performance

We also investigate how models fine-tuned on execution perform on the program synthesis task which is the main focus of this paper. We perform the few-shot program synthesis evaluation from Section 4 on the models fine-tuned on execution from Section 6.2 above. As in Section 4, we perform few-shot prompting with $k=3$ example synthesis tasks in the prompt, and include all three example asserts for each task.

We perform this experiment using the 8B, 68B, and 137B models (Figure 15). For the 8B model, fine-tuning on execution prompts does not increase performance beyond the few-shot performance. Performance of the 137B model shows a small improvement when fine-tuned on the execution dataset, of about 2.3% more samples per problem solving the task and 3.6% more tasks solved by any sample, compared to fine-tuning on the synthesis dataset). We suspect that training on more detailed execution data (Zaremba and Sutskever, 2014; Bieber et al., 2020) may further improve performance.

MathQA Results

We also evaluate our models on the MathQA and MathQA-Python datasets. The code in the MathQA dataset is different from MBPP, making less use of control flow and of the Python standard library, while the natural language is more complex. We experiment with both the domain-specific-language of the formulas in the original MathQA dataset, which we call MathQA-DSL, and the MathQA-Python dataset described in Section 2.2. As on the MBPP data (Section 4), we evaluate synthesis performance in both the few-shot prompting and the fine-tuning setting. We report accuracy in terms of functional correctness, that is, whether the program output by the model returns the correct answer to the word problems.

The results are summarized in Table 6. We find that the few-shot accuracy is 33.4% for the 137B model on the Python-formatted dataset. The fine-tuned models achieve very high accuracy: the best-performing model (137B on the DSL-formatted dataset) achieves 83.8% accuracy; see Table 6. Further, as with MBPP we can interpret the percentage of samples solving each task as a measure of the model’s confidence in its predictions. In Figure 18, we see that the finetuned models tend to have higher confidence, and the few-shot models much less so.

The few-shot models perform better on MathQA-Python compared to MathQA-DSL, which is expected because the MathQA DSL is unlikely to be similar to anything in the pre-training set. In contrast, the fine-tuned models achieve slightly higher accuracy on the DSL-formatted dataset compared to the Python-formatted dataset, indicating that the fine-tuning dataset we use has sufficiently many examples for the model to overcome its lack of familiarity with the DSL. This has promising implications for tasks like trying to teach a new programming language to a pre-trained model.

We also conducted an initial qualitative exploration of whether the model could respond to hints and explain its reasoning. Figure 16 shows an example for which the model is capable not only of solving MathQA-style problems, but also of carrying on a dialog about the proposed solution. Figure 17 shows how providing a hint to the model can in some cases increase the fraction of samples that solve the problem. Namely, without the hint (“calculate the volume of acid in the solution”), the 137B model fine-tuned on the Python code was able to solve the problem in fewer than 10% of samples. With the hint, the model samples correct answers 40% of the time. Moreover, we can elicit a line-by-line explanation of the solution with appropriate prompting (see blue section in Figure 17). Though we think these results are promising, we do not claim to have done a thorough evaluation of them here. They are presented more as a jumping-off-point for future work.

Related Work

Our work is inspired by the long line of previous work on neural language models of natural language text (Mikolov et al., 2010; Sutskever et al., 2011; Józefowicz et al., 2016; Dai and Le, 2015; Peters et al., 2018; Howard and Ruder, 2018), especially recent large Transformer models (Radford et al., 2018; Brown et al., 2020).

In the long history of program synthesis, methods have included deductive approaches, approaches based on enumerative and stochastic search, and constraint solving; for surveys, see Gulwani et al. (2017); Solar-Lezama (2018). One important application of these methods has been in end-user programming, for example, to synthesize string manipulation programs in spreadsheets (Gulwani, 2011). Many current systems rely on reducing the synthesis problem to a satisfiability problem, for example, Solar-Lezama et al. (2006) and Torlak and Bodik (2013).

Machine learning methods for program synthesis aim to learn cues from the problem description or from corpora of existing programs that help to write programs. Balog et al. (2017) use a neural network to predict properties, such as which functions will be called, of the target program from the input-output examples; these predictions can then be used to guide a search over programs. Devlin et al. (2017) treated program synthesis as a sequence-to-sequence problem, mapping from the problem description to a description of the program in a spreadsheet domain. DreamCoder (Ellis et al., 2020) relaxes the requirement of defining a DSL, by learning a library that is useful for solving a training set of synthesis problems. Execution-guided synthesis methods execute the partial programs produced during synthesis, using the intermediate values to guide the search; learning methods for execution-guided synthesis include Zohar and Wolf (2018); Chen et al. (2019a); Ellis et al. (2019); Odena et al. (2020).

Many methods for program synthesis, both logic-based and learning-based, have been restricted to DSLs, but there have been some exceptions. For example, BAYOU generates API-heavy code in Java using a latent-variable probabilistic model (Murali et al., 2018). Also, several different methods have been proposed for the problem of mapping a natural language description to code in general-purpose languages like Python (Ling et al., 2016; Yin and Neubig, 2017; Iyer et al., 2018).

Neural program induction methods are deep network architectures that aim to learn algorithms from input-output examples, by structuring the network in a way that corresponds to mathematical models of computation like Turing machines (Graves et al., 2014; Kaiser and Sutskever, 2016; Kurach et al., 2016; Graves et al., 2016). This is a very different line of work from program synthesis, because program induction methods do not attempt to produce a program. Instead, they learn a neural network that maps directly from the input of the desired program to its output.

2 Machine Learning for Software Engineering

Over the past decade, a line of work has explored machine learning for software engineering, which applies machine learning methods to large corpora of source code, with the aim of using the models to develop tools for various tasks in software engineering. For an overview of machine learning methods applied to source code, see Allamanis et al. (2018a), or the more recent living literature review website (Allamanis, 2021).

Early work applied statistical $n$-gram models (Hindle et al., 2012; Allamanis and Sutton, 2013a) and neural networks (Maddison and Tarlow, 2014; Raychev et al., 2014) to code. Raychev et al. (2015) presented a method to predict program properties using a graph-structured conditional random field, which they applied to deobfuscate Javascript code by predicting names and a small set of types. Subsequent research over the following decade introduced deep learning methods for a variety of software engineering tasks.

Code completion has been a particular focus of interest (Raychev et al., 2016; Karampatsis et al., 2020; Svyatkovskiy et al., 2020; Kim et al., 2020). Methods aim improving code readability by asking a model trained on a code corpus with good style to predict names of variables and methods in new code (Raychev et al., 2015; Allamanis et al., 2014; Alon et al., 2019). Several methods have been proposed to do machine learning for type inference, for example, to add types to untyped code, such as when converting Javascript to Typescript (Hellendoorn et al., 2018; Pandi et al., 2020; Pradel et al., 2020; Wei et al., 2020). Models trained over natural language and code have been applied within tools for improving comment quality and relevance (Louis et al., 2020; Panthaplackel et al., 2021). Porting programs across languages has been treated as a learning problem similar to machine translation (Roziere et al., 2020; Nguyen et al., 2013; Karaivanov et al., 2014). Program repair is the problem of automatically fixing bugs in programs, often based on a test suite (Le Goues et al., 2012; Long and Rinard, 2016). Many learning methods have been proposed for program repair (Allamanis et al., 2018b; Tarlow et al., 2019; Hellendoorn et al., 2019; Dinella et al., 2019; Yasunaga and Liang, 2020; Chen et al., 2019b; Pradel and Sen, 2018).

Several pre-trained models for code have shown to be effective for transfer learning across software engineering tasks, including CuBERT (Kanade et al., 2020), CodeBERT (Feng et al., 2020), PyMT5 (Clement et al., 2020), code2vec (Alon et al., 2019), and other T5 models trained on code (Mastropaolo et al., 2021).

3 Benchmarks for Machine Learning over Source Code

Broadly, we identify three kinds of benchmark suites for machine learning over source code. First, closed-domain benchmarks for program synthesis ask systems to generate programs in a domain-specific language from a specification such as a logical formula or input-output examples. The most notable of these is the SyGuS competition (Alur et al., 2013), which includes tasks such as generating string transformations and bit-vector manipulations. Although the restriction to domain-specific languages is useful for building tractable systems, our benchmarks aim to evaluate program synthesis methods for general-purpose programming languages used by people to develop software.

Benchmarks for machine learning for software engineering are often assembled from corpora of open source projects, such as from Github. Benchmarks have been proposed for software engineering tasks including code completion (Raychev et al., 2016; Allamanis and Sutton, 2013b), clone detection (Svajlenko et al., 2014), code search (Husain et al., 2019), predicting readable names to describe functions (Allamanis et al., 2016), and generating function text from docstrings (Iyer et al., 2018). Multi-task benchmarks for these tasks have been collected into CodeXGlue (Lu et al., 2021). Although these benchmarks are useful for evaluating ML support for a wide variety of important software engineering tasks, our goal is different: we seek to evaluate whether methods can learn to generate small, self-contained programs from a description of the task.

Finally, a third class of research benchmarks are collected from online programming competitions, such as CodeForces, TopCoder, and AtCoder. Such datasets include the Natural Program Synthesis (NAPS) dataset (Zavershynskyi et al., 2018), the Search-based Pseudocode to Code (SPoC) dataset (Kulal et al., 2019), the APPS dataset (Hendrycks et al., 2021), the ProgRES dataset (Alet et al., 2021), and the CodeNet dataset (Puri et al., 2021). These datasets are similar in the source of programs, but differ in the kinds of natural language and code included in the dataset. Most notably, the SPoC dataset includes a pseudocode description which is a relatively literal line-by-line English transcription of each problem, while the APPS and CodeNet datasets include natural language descriptions of the program and test cases for each problem. The ProgRES dataset consists of problems built from sub-expressions of C++ CodeForces solutions, each specified by a large number of input-output examples. A different type of competition-like programming challenge is the programming puzzles dataset (Schuster et al., 2021), in which a problem is defined by a predicate that must be true of the desired program’s output, for example, that a given path is indeed the shortest path between two nodes in a graph, or that a set of moves is a valid solution to a towers of Hanoi puzzle.

Although our benchmark tasks are similar in spirit to these programming competition datasets, they represent a different point in the design space, and one that we would suggest is complementary to previous work. Programming competition problems are often written so that the description includes a story which is engaging and makes identifying the algorithmic idea more challenging. In contrast, the natural language in Mostly Basic Programming Problems is a simpler description of the code’s intended function. Therefore we hope both that this benchmark focuses more directly on the capabilities required to generate and understand code, and also that it a useful stepping stone to generating larger programs with more complex specifications.

Risks and Limitations

Chen et al. (2021) provide a detailed overview of risks and potential harms of large language models over code, discussing potential concerns that include over-reliance on generated outputs, misalignment, poisoning attacks (Schuster et al., 2020), and others. More broadly, Bender and Koller (2020) and Bender et al. (2021) discuss risks and potential harms of large language models for natural language. In this section, we limit our discussion to risks and limitations that are specific to our work.

The models we use in this paper have not been treated for safety, hence additional analysis of model outputs for potential harms is necessary before the use of the model in practice. For example, it is now increasingly understood that large language models can learn undesirable (e.g. biased) behavior from unlabeled training data, e.g., Bender and Koller (2020) and Bender et al. (2021), or can reveal training data, as well as sensitive information in the training data (Carlini et al., 2020). It is possible that these risks are increased for an interactive use-case such as we described in Section 5.1. Further analysis of such risks and how to mitigate the risks for program synthesis are important directions for future work.

The energy cost and carbon footprint of the pre-training step for the models used in this paper are 451MWh and 26 tCO2e respectively. Because our fine-tuning datasets are relatively small in comparison, the estimated additional cost for the fine-tuning experiments in this paper is comparably very small.

Several limitations of our current model point toward interesting directions for future work:

Our benchmark programs are short and simple, and the programs solved by the model are the shortest and simplest among them. In other words, our benchmark has not yet captured the breadth and complexity of program synthesis.

Even when the model solves a task, it often does so with only one or two out of 80 samples. On the one hand, this is an acceptable limitation for downstream tasks, because we can machine-check the outputs against tests for semantic correctness. Additionally, if these capabilities are used in systems with a human in the loop, the sometimes incorrect output may be sufficient to support a user who can make the corrections necessary to put the generated code to use. On the other hand, this points toward a significant difference between the way the model is solving the problems and the way a human might. Possibly this can be fixed by further training the model to increase the probability of the outputs that pass the tests, but this seems more like a ‘band-aid’ than a deep fix.

The model cannot predict the outputs of programs on simple inputs (Section 6). This seems to us a prerequisite for claiming that the model ‘understands’ the programs it is synthesizing. Moreover, it seems like having a basic understanding of the semantics of code will be necessary for a wide variety of downstream tasks we might like such models to perform.

Some of the things we can do to address these limitations are clear. For instance, Figure 3 seems to suggest that simply using larger models will give nontrivial performance boosts. On the other hand, it is less clear how these models can be made more data efficient, or how (other than simply adding more relevant data) they can be made to better model the semantics of the code they emit. We hope that future work will address these and other issues.

Conclusion

We have conducted a large-scale study of how large language models perform at synthesis of short Python programs. Broadly speaking, we find that they perform surprisingly well, with the largest models synthesizing programs that pass all test cases for a majority of our benchmark problems. However, this good performance is predicated on being able to draw many samples from the model and machine-check them for correctness. From the perspective of downstream applications, this is perhaps acceptable. From the perspective of deciding whether these models “understand” computer programs in the same way that humans do, it is less so.

In that vein, we also tested whether these models could learn to execute existing programs on a given input. The results were poor, whether with few-shot prompting or when fine-tuning on other executions.444 This evaluation is perhaps slightly unfair, as we have not performed the obvious step of training the model on a much larger dataset of executions. This is an interesting direction for future work. This suggests that — perhaps unsurprisingly — these models have not learned much about the semantics of programs simply by reading their text. This potentially has implications for thinking about grounding outside the program synthesis domain, and likely points toward future work on multi-modal models.

Finally, we tested whether these models could synthesize programs to solve simple mathematical word problems. Here we saw more success, especially when fine-tuning on a larger dataset. We briefly experimented with whether these models could give step-by-step explanations of their reasoning in this context, with promising but preliminary results.

Taken together, these results are exciting, but it is worth emphasizing that we are a long way from models that can synthesize complex applications without human supervision. The system we study here solves the problems it solves only given many tries, and the execution results in Section 6 suggest that there are important capabilities that these models still lack. In the near term, an important line of research is to find ways in which such systems can augment the capabilities of human programmers by acting collaboratively, perhaps by fixing errors or by helping with debugging. The dialog results in Section 5 and the MathQA results in Section 7 – where the model explains a partial solution – give a glimpse of what this might look like. In addition to increasing productivity for existing programmers, this could make programming much more widely accessible, empowering more people to interact with technology to meet their needs.

Jacob Austin did the original experiments on MBPP, wrote much of the experimental code, did many of the MBPP experiments, and helped with paper writing. Augustus Odena wrote much of the experimental code, did many of the MBPP experiments, advised on the execution experiments, and did much of the writing. Max Nye wrote most of the code for the execution experiments, ran those experiments, wrote the execution portion of the paper, performed the error type analysis, and helped run some of the MBPP synthesis experiments. Maarten Bosma created the MBPP dataset, checked for duplication of MBPP data in the training dataset, and gave feedback on the paper. Henryk Michalewski wrote all of the code for the MathQA experiments, created MathQA-Python, ran the MathQA experiments, and wrote the MathQA section of the paper. David Dohan wrote and reviewed much of the code used to run the experiments and gave feedback on the paper. Ellen Jiang helped with early experiments, provided guidance, and performed qualitative analysis of model outputs. Carrie Cai provided guidance and qualitative analysis of model outputs. Michael Terry led the effort to sanitize the dataset and did qualitative analysis of the synthesis results. Quoc Le gave high-level scientific advice and gave feedback on the paper. Charles Sutton gave high-level scientific advice, fine-tuned the MBPP models, and did much of the writing.

Acknowledgements

We thank Daniel De Freitas Adiwardana for support and advice about the MBPP dataset.

References

Appendix A Appendix

Google Research is building a dataset for program synthesis in Python. This means we want to build Machine Learning algorithms which can automatically write small programs based on a natural language description. We are going to be using Google Colab to collect the data. The description should be clear so that a human would be able to write a program without having to ask more questions. Please make sure that the description is using proper English grammar (uppercase the first word of the sentence, the instruction with a period). If unsure, you can copy and paste the description into Google Docs to use the grammar checker. We ask you to put the code in a function. The cell code should not should not have any output (so don’t use print). Instead the function should return the result. This way we can test the function automatically. We ask you to write at least 3 assert statements to test your code (see colab linked below for examples). The test cell should not print anything which indicates that the tests passed. While it would be good to test edge cases this is not a requirement. Imports can be in the global scope, but please import them every time you use them (so each cell should be able to run by itself). If you use a library, reimport it every time so that each solution can run by itself. Please do not define any global variables, but instead define them inside of the function. Please use lowercase_with_underscores to define function names and try to give it a descriptive name if possible. Please make sure that there are exactly 3 cells for each example (description, code and test cases). There is no limit on the number of lines of code. Feel free to work together, but please make sure that your answers are different enough.

1. Well-defined, unambiguous question and test case: Ensure the question is well-defined and unambiguous, given the question and a test case. If the question does not seem to be a good or useful question, flag it for removal. 2. No special conditions: Remove any special conditions specified in the question (e.g., requirements to solve the problem using a regex, printing to the console, or using a lambda function). 3. Function signature looks "normal" (inputs and outputs): Make sure the function signature is not unusual (e.g., one common case was to pass in a list and the length of that list). 4. Make sure the return values are well-specified: Sometimes they return strings indicating success or failure; consider whether it could be changed to a standard Boolean value. If they use strings as enums, define these values in the natural language question. 5. Test cases are accurate: Make sure the test cases contain no errors. 6. Float comparisons are handled correctly: If the function returns floating point values, test using math.isclose(): import math math.isclose(a, b, rel_tol=0.001) 7. Questions asking for $n$ elements of a list may not specify an expected order: disambiguate or adjust tests. If a question asks for a subset of a list (e.g., the largest $n$ numbers), but does not specify an order, add that specification to the question text. 8. Consider whether using sets (set()) in the asserts is the right way to test results

A.2 Instructions for human-model collaboration experiments

Each user will be tasked with attempting 12 problems with at most 5 turns of dialog (including an initial automated turn). Each problem will be tackled by two people. After 5 turns the task is considered failed. If the model passes the test cases at any point, the task is considered solved. Instructions: • Each human prompt is allowed to use one natural language sentence. You can use Python identifiers and expressions, but you can’t use full statements, and it is encouraged to avoid lengthy Python expressions. • For example, say "Close, but it needs to return i if count is equal to len(str)", rather than "You need to return i if count == len(str)". • You can do some practice problems first to experiment with how best to interact with the model. After some experimentation, I’m giving it one problem as a prompt. You can try the practice problems as often as you want. • Once you have finished the practice problems, navigate to the next cell and enter the problems you have been assigned into the input box. This will create the environment repeatedly in a for-loop. Alternatively, you can manually enter a problem ID.

A.3 Prompts for execution experiments

A.4 Additional example human-model interaction samples