Natural Language to Code Translation with Execution (2022)

Abstract: Generative models of code, pretrained on large corpora of programs, have shown great success in translating natural language to code (Chen et al., 2021; Austin et al., 2021; Li et al., 2022, inter alia). While these models do not explicitly incorporate program semantics (i.e., execution results) during training, they are able to generate correct solutions for many problems. However, choosing a single correct program from a generated set for each problem remains challenging. In this work, we introduce execution result–based minimum Bayes risk decoding (MBR-EXEC) for program selection and show that it improves the few-shot performance of pretrained code models on natural-language-to-code tasks. We select output programs from a generated candidate set by marginalizing over program implementations that share the same semantics. Because exact equivalence is intractable, we execute each program on a small number of test inputs to approximate semantic equivalence. Across datasets, execution or simulated execution significantly outperforms the methods that do not involve program semantics. We find that MBR-EXEC consistently improves over all execution-unaware selection methods, suggesting it as an effective approach for natural language to code translation.

## introduction the recent success of large pretrained language models @xcite has extended to translating natural language descriptions into executable code @xcite @xcite . after pretraining on large corpora of code with a simple language modeling objective, the models demonstrate the ability to follow few-shot prompts @xcite to translate nat-figure 1 : illustration of mbr-exec on translating natural language to python code: we (1) sample programs from codex @xcite , (2) execute each program on one test case, and (3) select the example with the minimal execution result-based bayes risk. numbers around dotted lines denote the 0/1 matching loss between execution results, while the bayes risk of a program is defined by the sum of the loss between itself and other examples. in the figure, either code #1 or code #3 can be selected. ground-truth program output is not needed for selection. 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 noexecution baselines across all considered datasets, despite having never executed any code during training and even when it has no access to groundtruth 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. ## 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). ## 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). ## 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.