PaperlayerView exact revision on arXiv

Source-linked AI summary

Program Synthesis with Large Language Models

Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, Charles Sutton

arXiv:2108.07732v1cs.PLcs.LG

TL;DR

The paper tests whether large language models can synthesize short Python programs in general-purpose settings, using new benchmarks and few-shot or fine-tuning evaluations. Performance improves with model size across both datasets, but execution prediction remains poor.

  • Problem

    Evidence for large language models synthesizing programs in modern general-purpose languages remains limited compared with restricted or synthesis-oriented languages.

  • Method

    The paper introduces MBPP and evaluates language models on Python synthesis from natural-language descriptions using few-shot prompting, fine-tuning, and functional-correctness tests.

  • Results

    Synthesis performance scales log-linearly with model size across both datasets, with the largest models solving 59.6% of MBPP problems using few-shot learning.

  • Takeaways & Limitations

    Strong synthesis results require many samples and machine checking, while poor execution prediction indicates limited evidence that the models understand program semantics.

  • Takeaways & Limitations

    The models generally cannot predict program outputs on simple inputs, limiting claims that they understand the programs they synthesize.

Abstract

from arXiv · show

This paper explores the limits of the current generation of large language models for program synthesis in general purpose programming languages. We evaluate a collection of such models (with between 244M and 137B parameters) on two new benchmarks, MBPP and MathQA-Python, in both the few-shot and fine-tuning regimes. Our benchmarks are designed to measure the ability of these models to synthesize short Python programs from natural language descriptions. The Mostly Basic Programming Problems (MBPP) dataset contains 974 programming tasks, designed to be solvable by entry-level programmers. The MathQA-Python dataset, a Python version of the MathQA benchmark, contains 23914 problems that evaluate the ability of the models to synthesize code from more complex text. On both datasets, we find that synthesis performance scales log-linearly with model size. Our largest models, even without finetuning on a code dataset, can synthesize solutions to 59.6 percent of the problems from MBPP using few-shot learning with a well-designed prompt. Fine-tuning on a held-out portion of the dataset improves performance by about 10 percentage points across most model sizes. On the MathQA-Python dataset, the largest fine-tuned model achieves 83.8 percent accuracy. Going further, we study the model's ability to engage in dialog about code, incorporating human feedback to improve its solutions. We find that natural language feedback from a human halves the error rate compared to the model's initial prediction. Additionally, we conduct an error analysis to shed light on where these models fall short and what types of programs are most difficult to generate. Finally, we explore the semantic grounding of these models by fine-tuning them to predict the results of program execution. We find that even our best models are generally unable to predict the output of a program given a specific input.

1 Introduction

The paper investigates whether large Transformer language models can synthesize short Python programs from natural-language descriptions, introducing two benchmarks and evaluating few-shot, fine-tuned, and interactive settings. It finds strong synthesis performance and improvement from human feedback, but limited ability to predict program outputs, exposing a gap between synthesis and semantic understanding.

  • Research question: The study applies large Transformer language models to synthesizing short programs in general-purpose programming languages.The models emit code in token space, learning programming-language grammar from data rather than requiring it to be explicitly encoded.
  • Benchmarks: The paper introduces MBPP with 974 short Python functions and MathQA-Python with 23914 rewritten mathematical word problems.MBPP emphasizes imperative control flow, while MathQA-Python uses more complex natural-language descriptions.
  • Synthesis performance: Performance improves with model size on few-shot synthesis, and fine-tuning further increases performance on both datasets, including with only 374 MBPP training problems.The evaluation spans models from 244M to 137B parameters.
  • Interactive synthesis: Few-shot performance rises from 30% without human feedback to 65% after four dialog turns, producing a 50% error reduction.The models incorporate short natural-language hints to repair outputs and clarify under-specified prompts.
  • Semantic grounding: Even the largest models are generally unable to predict program outputs for specific inputs, whether evaluated few-shot or after fine-tuning.This result suggests a gap between the models’ synthesis behavior and semantic understanding.

2 Datasets

The paper introduces two program-synthesis datasets: the new crowd-sourced MBPP benchmark and MathQA-Python, which recasts MathQA solutions as short Python programs. MBPP emphasizes short self-contained functions, while MathQA-Python uses more complex natural-language descriptions and mostly straight-line code.

  • Mostly Basic Programming Problems: 974 MBPP problems are crowd-sourced as short Python functions with problem statements, three semantic-correctness tests, and ground-truth solutions.The contributors were crowdworkers with basic Python knowledge.
  • Mostly Basic Programming Problems: MBPP spans basic numeric and standard-library tasks to problems requiring external knowledge, including notable integer sequences.The dataset also contains uncommon signatures, underspecified or ambiguous prompts, and unexpected operations paired with tests.
  • Mostly Basic Programming Problems: MBPP experiments hold out 10 problems for few-shot prompting, 500 for testing, 374 for fine-tuning, and the remainder for validation.Edited-dataset comparisons use 100 overlapping problems while retaining the same few-shot and fine-tuning splits.
  • MathQA-Python: MathQA-Python translates MathQA’s mathematical word problems and DSL solutions into Python programs to evaluate program synthesis from more complex descriptions.Both Python and DSL code are used in few-shot and fine-tuning experiments; few-shot prompts provide four examples.

3 Model and Methods

The study uses dense decoder-only Transformer models spanning 244M to 137B non-embedding parameters and evaluates program synthesis through few-shot prompting and fine-tuning. Synthesis is assessed primarily by executing generated code for functional correctness, while execution prediction uses greedy decoding and exact output matching.

  • Models: The experiments use dense left-to-right decoder-only Transformer models ranging from 244 million to 137 billion non-embedding parameters.The models are pretrained on web documents, dialog data, and Wikipedia.
  • Synthesis regimes: The study evaluates synthesis under few-shot prompting and fine-tuning regimes.Few-shot prompts concatenate held-out example problems before completion; MBPP fine-tuning uses a 374-example training set.
  • Synthesis evaluation: Synthesis performance is measured by functional correctness of sampled code rather than token accuracy or BLEU.For MBPP, correctness is checked by executing generated code against test cases; generation uses temperature 0.5 with 80 samples per test problem.
  • Execution evaluation: Execution experiments use greedy decoding at temperature 0.0 and compare the generated result with the exact string produced by code execution.A single approximate most likely generation is evaluated for exact result matching.

4 MBPP Synthesis Results

MBPP synthesis performance scales approximately log-linearly with model size, but results depend strongly on prompt examples and reveal weaknesses in semantic generalization. Test-case filtering and prompt ensembling improve measured coverage, while adversarial evaluation exposes solutions that pass given tests without implementing the intended behavior.

  • Scaling and metrics: Fraction-of-problems performance scales linearly with the logarithm of model size, across models ranging from 244 million to 137 billion parameters.The fraction-of-problems metric counts a task as solved when any sampled program passes its test cases.
  • Error analysis: Runtime errors were more common than syntax errors for most model sizes, although even the smallest models produced syntactically correct Python around 80% of the time.The paper separately analyzes error types as a function of model size in few-shot experiments.
  • Prompt sensitivity: Prompt examples matter more than assertion count: one prompt seed solved 60% of tasks, while one versus three asserts differed by only 3 extra problems.The results suggest models mostly do not use the shown test cases to reason about program semantics.
  • Prompt sensitivity: Ensembling prompt seeds increased the percentage of problems solved from 59.6% to 66.4%.Different prompt seeds solve different problems, so their union expands task coverage.
  • Evaluation limitations: Adversarial tests revealed semantic overfitting: among 50 sampled programs, 33 solved all normal tests, but only 29 also solved the adversarial tests.A task involving removing the first and last character occurrences illustrates solutions that delete every occurrence while passing the provided tests.

5 Human-Model Collaboration Results

Human-model dialog substantially improves Python program synthesis, especially by clarifying under-specified requirements and correcting localized code errors. However, models can lose track of earlier code and feedback, with this limitation worsening over longer interactions.

  • Study motivation: The experiments tested whether humans and models could jointly solve challenging tasks and whether feedback could refine outputs for ambiguous requests.The study used preliminary collaboration experiments in which humans guided the model toward correct solutions through dialog.
  • Collaboration results: Four human dialog interventions raised the solve rate from 30% to over 65%, while one intervention raised it from 30% to 55%.The experiment used 50 edited MBPP problems and natural-language dialog between participants and the model.
  • Success modes: Human feedback helped solve problems involving under-specified prompts by inferring requirements from test cases and directing the model’s corrections.In one example, feedback specified sorting, reversing the order, and returning only the top four words.
  • Success modes: A single dialog turn often corrected small context errors, including missing imports, identifier mistakes, and variable misuse.Participants commonly fixed errors such as code using the re module without importing it.
  • Failure modes: Models struggled to revert changes or incorporate earlier code when feedback referred to previous responses.This loss of context became more pronounced as the number of dialog turns increased.

6 Program Execution Results

The models generally struggle to predict program outputs, although test cases in the prompt improve execution accuracy. Execution fine-tuning helps mainly when prompts omit test cases and slightly improves synthesis for the largest model.

  • Few-shot execution: 29% was the maximum accuracy for any prompt type when evaluating the 137B model on one held-out test case.Including test cases and natural-language descriptions produced the highest overall performance.
  • Few-shot execution: Test cases in the prompt provided the largest execution benefit across prompt configurations.The results indicate that prompt information, especially test cases, strongly affects execution performance.
  • Few-shot execution: Accuracy was lower when correctness required predicting outputs for two held-out test cases rather than one.This stricter evaluation judged a sample correct only when both outputs were correct.
  • Execution fine-tuning: Fine-tuning improved code-execution performance only for prompts containing source code without test cases.When test cases were included in the prompt, the improvement over few-shot performance was absent.
  • Transfer to synthesis: 2.3% more samples per problem and 3.6% more tasks solved by any sample were achieved by the 137B model after execution fine-tuning.The comparison was against fine-tuning on the synthesis dataset; the 8B model showed no improvement beyond few-shot performance.

7 MathQA Results

On MathQA, few-shot performance is stronger for Python than DSL, while fine-tuning produces very high accuracy and slightly favors DSL. Models also show higher confidence after fine-tuning, and hints can substantially improve difficult-task solving.

  • Accuracy: 83.8% accuracy is achieved by the best-performing fine-tuned model, the 137B model on the DSL-formatted dataset.The 137B model reaches 33.4% few-shot accuracy on the Python-formatted dataset.
  • Hints and explanations: 40% of samples solve a harder MathQA problem with a parenthesized hint, compared with less than 10% without the hint for the 137B model.Correct prompting can also elicit a line-by-line explanation, although the model may only indirectly follow the hint and explain parts incorrectly.
  • Confidence: Fine-tuned models tend to have higher confidence than few-shot models, measured by the percentage of samples solving each task.The fraction of samples solving a task is interpreted as a measure of model confidence.
  • Accuracy: Few-shot models perform better on MathQA-Python than MathQA-DSL, whereas fine-tuned models achieve slightly higher accuracy on the DSL-formatted dataset.The Python advantage is attributed to greater similarity with pre-training data, while fine-tuning provides enough DSL examples to overcome unfamiliarity.
  • Accuracy: Fine-tuning greatly increases performance on both the original DSL and Python variants, with a larger few-shot-to-fine-tuning gap than on MBPP.The larger gap is expected because the MathQA fine-tuning dataset is much larger.

8 Related Work

Prior program-synthesis research spans deductive, search-based, constraint-solving, and machine-learning methods, while related software-engineering work applies learned models to source-code corpora. Existing benchmarks cover DSL synthesis, software-engineering tasks, and programming competitions; this work positions its simpler natural-language Python tasks as complementary to those settings.

  • Program synthesis methods: Program synthesis has used deductive methods, enumerative and stochastic search, constraint solving, and end-user programming applications such as spreadsheet string manipulation.Many systems reduce synthesis to satisfiability problems.
  • Program synthesis methods: Machine-learning synthesis methods learn cues from descriptions, input-output examples, or program corpora to predict properties, generate program descriptions, learn libraries, or guide execution-based search.Examples include neural property prediction, sequence-to-sequence synthesis, DreamCoder, and execution-guided synthesis.
  • Program synthesis methods: Although many synthesis systems target domain-specific languages, exceptions generate API-heavy Java or map natural-language descriptions to code in general-purpose languages such as Python.Neural program induction is distinct because it learns a network implementing an algorithm rather than producing a program.
  • Machine learning for software engineering: Machine learning for software engineering applies statistical, neural, graph-structured, and pretrained code models to tasks including completion, naming, type inference, and transfer across software-engineering tasks.This work developed over roughly the past decade using large source-code corpora.
  • Benchmarks: Existing source-code benchmarks span closed-domain DSL synthesis, open-source software-engineering tasks, and online programming competitions, whereas MBPP uses simpler natural-language descriptions and is complementary to competition datasets.Competition datasets include NAPS, SPoC, APPS, PROGRES, and CodeNet; CodeXGlue collects multiple software-engineering tasks.

9 Risks and Limitations

The paper’s models raise unresolved safety and environmental concerns, while their benchmarks and capabilities remain limited in scope, reliability, and semantic understanding. Future work may benefit from larger models, but improving data efficiency and code-semantic modeling remains less clear.

  • Safety: The models were not safety-treated, so their outputs require additional harm analysis because they may exhibit bias or reveal sensitive training data.These risks can arise from unlabeled training data and training-data memorization.
  • Environmental cost: 451MWh and 26 tCO2e are the reported pre-training energy cost and carbon footprint, while fine-tuning adds comparatively little cost.The fine-tuning datasets are relatively small compared with the pre-training data.
  • Benchmark scope: The benchmark uses short, simple programs, and the model solves the shortest and simplest examples, leaving program-synthesis breadth and complexity uncaptured.The authors identify this limitation as a direction for future work.
  • Reliability: Even solved tasks often require only one or two successful samples out of 80, making outputs useful with testing or human correction but frequently incorrect.Machine-checking can assess semantic correctness, while human-in-the-loop systems can support users who correct generated code.
  • Semantic understanding: The model cannot predict program outputs on simple inputs, limiting claims that it understands synthesized programs and potentially hindering downstream semantic tasks.The authors regard basic code-semantics understanding as necessary for many desired applications.

10 Conclusion

Large language models can synthesize short Python programs surprisingly well, but reliable performance depends on many samples and machine checking. They remain poor at executing existing programs and far from synthesizing complex applications without human supervision.

  • The largest models synthesize programs passing all test cases for a majority of benchmark problems, but require many samples and machine checking.This level of performance may be acceptable for some downstream applications.
  • Models perform poorly when asked to execute existing programs from given inputs, suggesting limited learning of program semantics from text.This result holds with both few-shot prompting and fine-tuning on other executions.
  • Models show greater success synthesizing programs for simple mathematical word problems, especially after fine-tuning on a larger dataset.Step-by-step reasoning explanations showed promising but preliminary results in this setting.
  • The systems remain far from synthesizing complex applications without human supervision because they solve problems only given many tries and lack important execution-related capabilities.Near-term research should focus on augmenting human programming capabilities.
  • The execution evaluation may be somewhat unfair because the models were not trained on a much larger dataset of program executions.Training on substantially more execution data is identified as future work.

A Appendix · A.1 Instructions given to crowd workers and expert reviewers

The appendix describes how Google Research collected Python program-synthesis data and instructed workers and reviewers to produce clear, well-defined problems without special conditions.

  • A.1 Instructions given to crowd workers and expert reviewers: Google Research collected Python program-synthesis data in Google Colab to support machine-learning algorithms that write small programs from natural-language descriptions.The project targeted automatic generation of small Python programs from descriptions.
  • A.1 Instructions given to crowd workers and expert reviewers: Descriptions had to be clear enough for humans to write programs without asking additional questions.Workers were instructed to use proper English grammar, capitalization, and sentence-ending periods.
  • A.1 Instructions given to crowd workers and expert reviewers: Figure 19 presents the crowd-worker instructions, edited slightly for clarity.The figure documents the instructions used during data collection.
  • A.1 Instructions given to crowd workers and expert reviewers: Questions and test cases had to be well-defined and unambiguous, with unsuitable or unhelpful questions flagged for removal.Reviewers evaluated whether each question was useful given its associated test case.
  • A.1 Instructions given to crowd workers and expert reviewers: Problems had to omit special requirements such as using regular expressions, printing to the console, or using lambda functions.Reviewers were instructed to remove these conditions from questions.
  • A.1 Instructions given to crowd workers and expert reviewers: Figure 20 presents the instructions used to edit the problems.The editing instructions addressed problem quality and the removal of restrictive conditions.

A.2 Instructions for human-model collaboration experiments

The collaboration experiments assigned users 12 problems, with each problem attempted by two people over at most five dialog turns. Problems were solved if the model passed test cases at any point; otherwise, five turns marked failure.

  • Experiment protocol: Each user attempted 12 problems with at most 5 dialog turns, including an initial automated turn.After 5 turns, the task was considered failed.
  • Experiment protocol: Each problem was tackled by two people.
  • Success criterion: A problem was considered solved if the model passed the test cases at any point.
  • Human prompting constraints: Each human prompt could use one natural language sentence, plus Python identifiers and expressions but not full statements.Lengthy Python expressions were discouraged.

A.3 Prompts for execution experiments · A.4 Additional example human-model interaction samples

The execution experiments vary prompts by combining code, natural-language descriptions, examples, and tests. Additional interaction samples show models revising code after concrete human feedback about loop bounds.

  • A.3 Prompts for execution experiments: Execution prompts combine Python code with natural-language descriptions, examples, and tests in different configurations.The listed variants include code + NL + examples, code + NL, code + examples, NL + examples, and examples-only prompts.
  • A.4 Additional example human-model interaction samples: The duplicate-detection interaction begins with a model implementation that compares every pair of array positions.The model writes nested loops over the full array and checks whether array[i] equals array[j].
  • A.4 Additional example human-model interaction samples: The initial duplicate-detection code returned True for all three reported tests, including inputs expected to return False and True.The reported outputs were True for [1,2,3,4,5], [1,2,3,4,4], and [1,1,2,2,3,3,4,4,5].
  • A.4 Additional example human-model interaction samples: Human feedback instructs the model to start the second duplicate-detection loop at i + 1.The revised code uses range(i + 1,len(array)) for the inner loop.
  • A.4 Additional example human-model interaction samples: The substring-counting interaction tests count_Substrings(’112112’) == 6, but the initial implementation returned 3 for ’111’ and 9 for ’1101112’.It returned 6 for ’112112’, matching that test’s expected value, while failing the other two reported cases.
  • A.4 Additional example human-model interaction samples: Human feedback identifies the substring loop’s upper bound as len(n) + 1.The revised loop uses range(i + 1, len(n) + 1).
  • A.4 Additional example human-model interaction samples: A further example asks for sort_matrix, a function that sorts a matrix in ascending order according to the sum of its rows.This example is presented as an additional dialog sample without a shown implementation.
Loading 2108.07732v1…