Source-linked AI summary
Natural Language to Code Translation with Execution
Freda Shi, Daniel Fried, Marjan Ghazvininejad, Luke Zettlemoyer, Sida I. Wang
TL;DR
Selecting one correct program from multiple outputs remains difficult for pretrained code models that do not explicitly use execution semantics during training. The paper introduces MBR-EXEC, which selects a candidate by agreement in execution results, and reports consistent improvements over execution-unaware selection methods across datasets. It also identifies alternative MBR metrics when execution or test inputs are unavailable.
Problem
Selecting a single correct program from a generated set remains challenging for natural-language-to-code systems.
Method
MBR-EXEC samples programs from a pretrained code model and selects a candidate using execution-result-based Bayes risk, requiring execution only at inference time.
Results
MBR-EXEC significantly outperforms no-execution baselines across all considered datasets, even without execution during training or access to ground-truth outputs.
Takeaways & Limitations
Execution-based selection is an effective algorithm for selecting programs from pretrained language-to-code model outputs.
Takeaways & Limitations
The study applies selection methods on top of a frozen pretrained code model and leaves joint execution-based training for future work.
Abstract
from arXiv · showhide
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. We open-source our code at github.com/facebookresearch/mbr-exec and data at dl.fbaipublicfiles.com/mbr-exec/mbr-exec-release.zip
1 Introduction
Pretrained code models can translate natural-language descriptions into executable code, but selecting one correct program from multiple generated candidates remains difficult. MBR-EXEC addresses this by using execution results at inference time to select a consensus candidate.
- Approach: The selection criterion chooses a candidate with minimal execution-result-based Bayes risk, without requiring ground-truth program outputs.Figure 1 illustrates sampling programs, executing each on one test case, and selecting the candidate with the lowest risk.
- Motivation: Pretrained code models achieve strong natural-language-to-code performance after training on large code corpora, but generated programs can still contain obvious mistakes.They may obtain relatively high execution accuracy while remaining below the quality of code written by intermediate-level human programmers.
- Motivation: Choosing a single correct program from a generated set remains challenging.
- Approach: MBR-EXEC samples programs from a pretrained code model and selects one by agreement with other samples on execution results.The approach uses execution results from a limited number of test inputs only at inference time.
- Results: MBR-EXEC significantly outperforms no-execution baselines across all considered datasets, despite using no execution during training or ground-truth outputs.The evaluation considers settings where only one program can be submitted as the solution.
2 Related Work
Prior work established strong pretrained and prompt-based approaches for code generation and minimum Bayes risk decoding. This paper studies execution-based candidate selection for few-shot natural-language-to-code generation across multiple programming languages.
- Pretrained code models: Recent Transformer-based pretrained code models show strong generation performance across programming languages.
- Evaluation setting: The paper evaluates MBPP, Spider, and NL2Bash, covering Python, SQL, and Bash.
- Prompting: Few-shot prompting conditions a pretrained code model on task-related examples before generating code for a new description.The paper uses Codex with a fairly programming-language-agnostic prompt format.
- Minimum Bayes risk decoding: Minimum Bayes risk decoding selects a structured output by minimizing expected loss under a probability model and explicit loss function.It has been applied across structured prediction tasks including parsing and machine translation.
- Prompting: The prompting template substitutes natural-language descriptions and code snippets, with optional information such as function identifiers and example calls.
- Execution-based selection: In this work, execution-based MBR loss functions are used to select code candidates by examining discrepancies between programs.The method seeks a consensus candidate with low loss relative to other candidates.
3 Proposed Approach: MBR-EXEC
MBR-EXEC samples multiple programs from a pretrained code model and selects a consensus candidate using execution-based minimum Bayes risk. It compares candidates by their execution results on available test inputs, with likelihood used to break ties.
- 3 Proposed Approach: MBR-EXEC: The framework collects candidate programs with few-shot prompting and selects one using minimum Bayes risk decoding.Its two stages are sample collection and candidate selection.
- 3 Proposed Approach: MBR-EXEC: MBR-EXEC selects the candidate with the lowest loss relative to the other sampled programs.This consensus-based implementation is an unbiased estimation of the corresponding MBR objective.
- 3 Proposed Approach: MBR-EXEC: The prompting pattern is designed to avoid programming-language-specific information and works across programming languages on Codex.
- 3 Proposed Approach: MBR-EXEC: The execution-based loss assigns zero loss when two programs produce identical outputs on all considered test inputs.A program that fails on a test case is treated as equivalent to none of the other programs.
- 3 Proposed Approach: MBR-EXEC: When multiple candidates attain the same MBR loss, the method selects the one with the largest likelihood.
4 Experiments
The experiments evaluate MBR-EXEC and comparison methods across three programming-language datasets using few-shot Codex samples. They use execution-based evaluation where feasible and simulated execution for NL2Bash.
- 4.1 Datasets and Evaluation Metrics: The evaluation covers MBPP, Spider, and NL2Bash, spanning Python, SQL, and Bash programming tasks.
- 4.1 Datasets and Evaluation Metrics: MBPP contains 974 basic Python problems, including 500 test problems, and evaluates programs by whether all three test cases pass.
- 4.1 Datasets and Evaluation Metrics: Spider evaluates text-to-SQL commands by execution accuracy, counting a command as correct when it returns the same result as the ground-truth command.
- 4.1 Datasets and Evaluation Metrics: NL2Bash estimates execution-result similarity with token-level BLEU-4 because Bash commands are difficult to execute in a sandbox.Commands that bashlex cannot parse are considered unexecutable.
- 4.1 Datasets and Evaluation Metrics: Samples use 15 training examples for few-shot prompting, collected through five prompts with three examples each and temperature 0.3.Candidates from the five prompts are combined for selection.
- 4.1 Datasets and Evaluation Metrics: Figure 2 reports average performance as lines and standard deviations as shaded regions across five sample groups for each sample size.All samples are collected from Codex with temperature 0.3.
- 4.1 Datasets and Evaluation Metrics: For execution on MBPP and Spider, the method uses only the first provided test input to calculate Bayes risk.
4.3 Primary Results
MBR-EXEC consistently improves program selection by using execution results or execution proxies, while performance depends on sampling temperature, prompt construction, and candidate executability. Additional analyses identify when semantic comparison helps and where its execution assumptions limit coverage.
- Primary results: MBR-EXEC significantly outperforms no-selection and baseline selection methods across datasets, especially on MBPP and Spider with execution-based evaluation.The evaluation uses one test case per problem and dataset-specific metrics.
- Primary results: BLEU-based MBR remains consistently strong across datasets, supporting consensus selection when direct execution is unavailable.The method selects candidates with generally low discrepancy from other samples.
- Sampling temperature: Temperature 0.3 sampling matches or outperforms greedy decoding, while temperatures approaching 1.0 sharply reduce MBPP and Spider performance.Temperatures below 0.5 usually provide reasonably good MBR-EXEC performance; NL2Bash differs, with MALL improving at higher temperatures.
- Prompt construction: Different groups of 3-shot prompts clearly outperform concatenating all 15 examples on MBPP and NL2Bash.The results support collecting candidates from varied smaller prompts followed by post-hoc decoding.
- Executability versus execution results: Executability checks substantially improve non-semantic selection methods, and on Spider, machine learning over executable commands outperforms MBR-EXEC across sample sizes.This ablation separates filtering for successful execution from comparing execution results.
- Soft loss and test cases: With multiple MBPP test cases, performance improves over one test case, but neither hard versus soft loss nor two versus three test cases differs significantly.The soft loss compares programs by the number of test cases receiving the same output.
4.5 Oracle Performance
The oracle analysis defines expected Pass@K by whether any sampled program passes all test cases, and shows that reasonable sample sizes can exceed supervised state-of-the-art performance.
- Expected Pass@K counts a problem as solved when at least one candidate passes every associated test case.Dataset-level expected Pass@K averages this quantity across problems.
- Supervised comparisons use all available training data, including 374 MBPP training examples, current Spider state-of-the-art results, and GPT-2 finetuning for NL2Bash.
- Effective inference algorithms may help translate natural language to code in real-world applications because pretrained models can generate correct programs.
5 Discussion
The discussion finds that execution-based selection substantially improves generated programs, especially under execution-based evaluation, while offering BLEU-based MBR as an alternative when execution is unavailable.
- Execution-based selection substantially improves pretrained code models, including when only test inputs or an executability checker are available.
- MBR-EXEC performance is examined across sample sizes on MBPP, where parentheses indicate the number of test cases used per problem.
- When programs cannot be executed or test inputs are unavailable, the authors suggest MBR-BLEU as an alternative selection algorithm.
Limitations
The study applies all selection methods on top of a frozen pretrained code model and leaves joint execution-aware training or finetuning for future work.
- All selection methods operate on a frozen pretrained Codex model, while incorporating execution information during training or finetuning remains future work.
A Example Prompts and Codex API Responses
The appendix provides example three-shot prompts and corresponding Codex responses for the three datasets, using a unified formatting pattern and greedy decoding.
- The examples cover three-shot prompts and Codex responses for the three experimental datasets.
- The prompts follow the formatting patterns from Table 1, and the displayed responses use greedy decoding with temperature = 0.
B Full Analysis on Executability vs. Execution Result
The analysis compares selection methods applied to all candidates with versions restricted to executable candidates. An executability checker improves execution accuracies for both MBPP and Spider, alongside comparisons involving MBR-EXEC.
- Executability vs. execution result: An executability checker improves execution accuracies for both MBPP and Spider when combined with MBR-tokenBLEU or MALL.The comparison covers MBR-tokenBLEU and MALL, as well as their combinations with executability checking.
- Executability vs. execution result: Figure 8 compares applying selection methods to all candidates with applying them only to executable candidates.The figure labels executable-only variants as executability-X, where X is the selection criterion.
- Executability vs. execution result: The analysis includes MBR-EXEC curves as a comparison point alongside the executable-only and all-candidate methods.