Natural Language to Code Translation with Execution

Introduction

The recent success of large pretrained language models (Radford et al., 2019; Brown et al., 2020) has extended to translating natural language descriptions into executable code (Chen et al., 2021; Austin et al., 2021; Li et al., 2022, inter alia). After pretraining on large corpora of code with a simple language modeling objective, the models demonstrate the ability to follow few-shot prompts (Radford et al., 2019; Brown et al., 2020) to translate natural language to various programming languages. While code sampled from such models obtains surprisingly good BLEU scores against ground-truth programs and relatively high execution accuracies, it often includes obvious mistakes, and is of much lower quality than the code written by intermediate-level human programmers (Li et al., 2022). In addition, choosing a single correct one from a set of generated programs remains challenging.

In this work, we translate natural language to executable code with awareness of execution results on a limited number of test case inputs, which we require only at inference time. Our approach is built on the hypothesis that a pretrained code model spreads probability mass over multiple semantically-equivalent code forms that implement the same functionality. Given a text description of a desired program function, we (1) sample a set of programs from a pretrained code model (§3.1) and (2) select a single candidate program using execution-result-based minimum Bayes risk (MBR) decoding (§3.2). Intuitively, we score each sampled program using its agreement to other samples in terms of execution results, and select a program with maximal overall agreement.

Our evaluation focuses on a challenging setting where only a single program can be submitted as the solution to a given problem. We show that the execution result–based selection method (i.e., MBR-exec) significantly outperforms all no-execution baselines across all considered datasets, despite having never executed any code during training and even when it has no access to ground-truth outputs. In addition, we show that MBR decoding with a BLEU-based risk function performs consistently well across datasets, and can be considered as a promising alternative when we are not able to execute.

Related Work

With the progress of neural network–based language modeling and conditioned text generation, there has been much work exploring natural language to code generation with end-to-end neural model architectures (Xiao et al., 2016; Ling et al., 2016; Rabinovich et al., 2017; Dong and Lapata, 2018; Suhr et al., 2018; Xu et al., 2020; Lachaux et al., 2021, inter alia). Recently, large Transformer-based (Vaswani et al., 2017) pretrained code models have shown surprisingly strong generation performance across programming languages (Chen et al., 2021; Austin et al., 2021; Li et al., 2022, inter alia). In this work, we explore selection (i.e., inference) methods to apply to these pretrained models, showing that selecting programs using their execution results can greatly improve program generation.

Multiple benchmarks have been proposed to evaluate code model performance (Miceli Barone and Sennrich, 2017; Yin et al., 2018; Hendrycks et al., 2021; Lu et al., 2021, inter alia). In this work, we evaluate on three text-to-code datasets: MBPP (Python; Austin et al., 2021), Spider (SQL; Yu et al., 2018) and NL2Bash (Bash; Lin et al., 2018), covering a range of programming languages.

2 Prompting Pretrained Language Models

The GPT-2 (Radford et al., 2019) and GPT-3 (Brown et al., 2020) models have shown strong prompting performance: after conditioning on a task-related prompt, the language models are often able to make accurate output predictions for unseen inputs. These results lead to prompt-based approaches for few-shot or zero-shot text classification (Shin et al., 2020; Gao et al., 2021; Min et al., 2021, inter alia), question answering (Khashabi et al., 2020), machine translation (Radford et al., 2019), and evaluation of generated text (Yuan et al., 2021), where no more than a few examples are used to construct the prompts. Few-shot examples are usually formatted into natural language prompts and continuations generated by the models for these prompts are then converted to task-specific predictions. The prompt formatting can be either manually designed (Jiang et al., 2020) or automatically learned (Li and Liang, 2021; Lester et al., 2021). Recently, Wang et al. (2022) find that self-consistency based decoding improves chain-of-thought prompting (Wei et al., 2022). We refer the readers to Liu et al. (2021) for a more comprehensive survey.

In this work, we prompt a pretrained code model (Codex; Chen et al., 2021) in a few-shot setting (§3.1) and perform execution-based selection over the samples. We also find that the Codex model performs well with a fairly programming-language-agnostic prompt formatting (Table 1).

3 Minimum Bayes Risk Decoding

In structured prediction, Minimum Bayes risk (MBR) decoding (Bickel and Doksum, 1977) selects a structured output that minimizes the expected errors in the structure by introducing an explicit loss function to the decision criterion. This method has outperformed the maximum a posteriori (MAP) method on many tasks, including syntactic parsing (Titov and Henderson, 2006; Shi et al., 2019; Zhang et al., 2020), statistical machine translation (Kumar and Byrne, 2004; Zhang and Gildea, 2008), and neural machine translation (Eikema and Aziz, 2020, 2021).

where $\mathcal{E}_{h}$ is the hypothesis space, and $\mathcal{E}_{e}$ is the evidence space: both are sets of possible translations.

We define execution based MBR loss functions, and show that they are crucial in the sample selection processes for natural language to code with a pretrained large language model.

Proposed Approach: MBR-exec

Our execution-based framework consists of two parts: (1) collecting samples from a pretrained code model (§3.1) and (2) selecting the best candidate using minimum Bayes risk decoding (§3.2).

To obtain the corresponding code, we query the pretrained code model with few-shot prompts followed by the text description, using a unified mark-up style few-shot prompting template (Table 1).While existing work on prompting language models usually requires a task-specific design of prompts (Shin et al., 2020; Zhong et al., 2021; Gao et al., 2021, inter alia), we find that a fairly general pattern (Table 1), which does not involve any programming language–specific information, works well across programming languages on Codex. In addition to the generated programs themselves, most existing models also allow us to have the associated probability of generating each generated token $w_{i}$ conditioned on the prompt tokens $C=\langle c_{1},\ldots,c_{n}\rangle$ and all the previously generated tokens $w_{1},\ldots,w_{i-1}$, denoted by $P(w_{i}\mid C,w_{1},\ldots w_{i-1})$.

2 Execution-Based MBR Decoding

Given a problem in its natural language description $C$, we sample a set of programs $\mathcal{P}=\{p_{i}\}_{i=1}^{N}$ using the method in §3.1. We formulate the execution-based MBR (MBR-exec) decoding by selecting

We introduce the following execution result–based loss function:

There may be multiple programs receiving the same MBR loss $\mathcal{L}_{\textit{MBR}}(\cdot;\mathcal{P})$, which are all minima. We break any ties by selecting the program with the largest likelihood among them.

Experiments

We evaluate (§4.3) and analyze (§4.4) the performance of MBR-exec, starting with introducing the datasets and evaluation metrics (§4.1), as well as non-execution-based baselines (§4.2) for MBR-exec. Finally, we show and discuss oracle performances on the considered tasks (§4.5).

We consider three datasets that cover a range of programming languages: MBPP (Python; Austin et al., 2021), Spider (SQL; Yu et al., 2018), and NL2Bash (Bash; Lin et al., 2018).

The MBPP dataset (Austin et al., 2021) https://github.com/google-research/google-research/tree/master/mbpp consists of 974 basic Python programming problems, with 500 of them used for testing and the rest for training or few-shot prompting. There are ground-truth program and three assertions (i.e., test cases with input and ground-truth output) associated with the description of each problem. When collecting the samples, we use one assertion as the extra information ([INFO]; Table 1).The main goal of [INFO] in MBPP is to inform Codex about the desired function name for easier evaluation – while the assertions are not a necessary part of prompt, we use them as [INFO] for simplicity and compatibility with past work (Austin et al., 2021). Programs are evaluated with execution accuracy, where a program is considered as passing if all three test cases are correct.

The Spider dataset (Yu et al., 2018)https://yale-lily.github.io/spider is a text-to-SQL dataset, which requires a model to translate text descriptions into SQL commands. There are 7,000 examples for training and 1,034 for development. When prompting models to produce candidate commands, we concatenate the corresponding SQL table and column names as the [INFO]. Commands are evaluated with the execution accuracy, where a command is considered as passing if it returns the same result as the ground-truth command when being executed on the same database.

The NL2Bash dataset (Lin et al., 2018) aims to translate natural language to bash commands. We do not include [INFO] in the sample collection process. Because it is difficult to execute bash commands in a sandbox, we split a bash command with bashlex,https://pypi.org/project/bashlex/ a rule-based bash parser, and use the token-level BLEU-4 score between commands as the estimation of execution result similarity. We consider a command to be unexecutable when bashlex fails to parse it. Following Lin et al. (2018), commands are evaluated with character-level BLEU-4 score.

Across datasets, we use 15 examples from the training set for few-shot prompting. A detailed example showing prompt formatting can be found in Appendix A. Unless otherwise specified, we collect samples by querying Codex with five different prompts, each containing 3 examples, using temperature 0.3. We combine the candidates sampled across the five prompts to get a set of candidate samples to use in our selection methods. For execution on MBPP and Spider, we apply a memory limit of 128GB and a time limit of 10 seconds on a single Intel(R) Xeon(R) CPU E5-2698 v4 @ 2.20GHz CPU, and consider the programs that exceed these limits as inexecutable; unless otherwise specified, we only execute each program on the first test input provided for the example, and use the output for calculating the Bayes risk in the inference process.

2 Baselines

We compare the most basic baselines with no selection, prompting Codex with three examples in Table 1 format:We use the code-davinci-001 engine throughout this work.

Greedy decoding. We perform token by token greedy decoding to generate the output.

Sampling. We sample the output token by token with a fixed temperature, where we set the temperature as 0.3 in all of our experiments.

In addition, we consider the following baseline sample selection methods:

Maximizing likelihood (ML). Given a set of sampled candidate programs, we select the one with the largest log likelihood. Formally, we select

where $n_{p}$ denotes the number of tokens in a generated program $p$, and $w_{p,i}$ denotes its $i$-th token.

Maximizing average log likelihood (MaLL) across tokens. In order to address the practical issue that ML typically favors shorter sequences, we follow Chen et al. (2021) and propose another baseline that uses the average log likelihood across tokens as the selection criterion, where we select

BLEU score based MBR (MBR-bleu). To study the effect of execution based MBR in sample selection, we consider BLEU score based MBR, where the Bayes risk is calculated using the following risk function:

where $\text{BLEU}(p_{i},p_{j})$ is the BLEU score of the two programs. We use character-level (MBR-charbleu) or token-level (MBR-tokenbleu) BLEU-4 in all of our experiments.

3 Primary Results

We evaluate MBR-exec on the three datasets (§4.1) with dataset-specific metric, where we use one test case for each problem. MBR-exec outperforms all baselines without a selection process by a significant margin (Table 2). In addition, we find that MBR-exec outperforms all baseline selection methods (Figure 2), and is especially effective on the two datasets (MBPP and Spider) that use execution-based evaluation. In addition, the MBR-bleu metrics are also strong and robust across datasets, suggesting the effectiveness of finding a consensus candidate that has generally low discrepancy with other samples.

While more samples lead to better performance for most methods, MaLL consistently performs worse with a larger sample size, as we find that MaLL generally favors programs with unnecessary repetitions,This issue has been found in existing open-ended text generation models, while methods such as unlikelihood training (Welleck et al., 2020) may help reduce degeneration (i.e., the generation of unnecessarily repetitive output). and a larger sample size generally leads to a larger chance to have such a sample.

4 Analysis

We analyze the performance of MBR-exec from the following perspectives: the effectiveness across different sample collection temperatures (§4.4.1), the effectiveness of using groups of 3-shot prompts (§4.4.2) and the contribution of using execution results instead of simply checking the executability of programs (§4.4.3).

We first compare sampling with temperature 0.3 to greedy decoding (i.e., temperature $\tau=0$) from the Codex model (Table 3). When having the same number of examples, MBR-exec on sampled candidates with temperature 0.3 consistently reaches competitive or better performance than that on greedy decoded candidates.

We plot the performance of MBR-exec for various sampling temperatures (Figure 3). Across datasets, we find that MBR-exec with a decoding temperature lower than 0.5 usually leads to reasonably good performance. When the temperature approaches 1.0, the results rapidly drop for all considered selection methods on MBPP and Spider; however, MaLL generally achieves higher performance on NL2bash with a higher temperature.

According to the evidences discussed above, we recommend to use sampling with a low temperature (specifically, lower than 0.5) for candidate sample collection, and perform MBR-exec for final program selection for better results.

4.2 Effect of Different 3-shot Prompts

We analyze the necessity of choosing multiple groups of 3-shot instead of simply concatenating the available 15 examples as the prompt (Figure 4).We only include MBPP and NL2Bash results here as concatenating 15 Spider examples usually results in exceeding the token number limit of the pretrained models. We allow different orders of the 15 examples when collecting samples. On both MBPP and NL2Bash datasets, we find that using different groups of 3-shot prompts clearly outperforms concatenating all 15 examples, suggesting that different groups of fewer-shot prompts followed by post-hoc decoding may be more effective than using all available examples for all time.

4.3 Executability vs. Execution Results

We perform an ablation study to identify the contribution of execution results vs. program executability (Figure 5) on the MBPP and Spider datasets.We did not include NL2bash since MBR-exec does not really execute the commands. However, the comparison between MBR-exec and MBR-tokenbleu in Figure 3(c) shows that using an external bash parser as an executability estimator leads to more consistent and generally better performance. We try to execute all candidates on the test cases, and perform baseline candidate methods only on the candidates that successfully execute within the time limit. On both datasets, we find that simply involving executability checking significantly helps improve the performance of all non-semantic feature–based selection methods; on Spider, applying ML over executable commands even outperforms MBR-exec across sample sizes.

4.4 Soft Loss as the Bayes Risk Function

5 Oracle Performance

We report the upper bound performance of all inference methods (Figure 7). Here, we define the expected Pass@K on one problem $q$ by

where $G(t)$ denotes the ground-truth output for test case input $t$. Intuitively, to calculate the performance upper bound, a problem $q$ is considered to be solved if there exists one program in the candidate sample set $P$ that passes all associated test cases $\mathcal{T}_{q}$. The dataset-level expected Pass@K is defined as the average expected Pass@K over all problems.

In addition, we report the supervised performance on these datasets, where all available training data are used for model training or finetuning: for MBPP, the results are from Austin et al. (2021), where they use all 374 training examples to finetune their pretrained code model; for Spider, we compare to the current state-of-the-art result (Scholak et al., 2021); for NL2Bash, we finetune GPT-2 (Radford et al., 2019) with all training examples with the same prompting set up as Table 1.

However, it is worth noting that the upper bounds already outperform the state-of-the-art supervised performances on all datasets by a significant margin, when a reasonable amount of sample is given. This further demonstrates the effectiveness of the pretrained code models, and points out a potential next step in the direction: while such models are able to generate correct programs, designing effective inference algorithm may be a promising way towards translating natural language to code in real world applications.

Discussion

We presented and systematically analyzed MBR-exec, an execution–based inference algorithm for pretrained language to code models, on datasets that cover three representative programming languages. Our results showed that doing execution, even with access only to inputs (not outputs) for test cases, or with only access to an executability checker, substantially helps improve the quality of generated programs especially in the settings that use execution accuracy as the evaluation metric (MBPP and Spider). Given the consistently strong performance, we suggest future work on program synthesis with large pretrained models consider MBR-exec as an effective selection algorithm. When we are not able to execute programs, or there are no test inputs available, our results suggest considering an alternative MBR metric (e.g., MBR-bleu) as the selection algorithm.

Limitations

In this work, all selection methods are performed on top of a frozen pretrained code model (Codex; Chen et al., 2021). We note that incorporating execution information into the training or finetuning process of pretrained models may further help improve the performance. We leave the exploration of joint execution and training to future work.

References

Appendix A Example Prompts and Codex API Responses

We include example 3-shot prompts and corresponding Codex responses that we used in our experiments, on the three datasets (Tables A, A, A), where we format the prompts following the patterns presented in Table 1. Data shown in the tables are collected with the greedy decoding strategy (i.e., temperature = 0), and can be found in the first line of seed 0 in our released data for each test dataset.

We report the comparison between MBR-tokenBLEU and MaLL vs. their combination with executability check (Figure 8; in complementary to Figure 5), where we observe that an executability checker is an effective filter to improve execution accuracies for both datasets (MBPP and Spider).