PaperlayerView exact revision on arXiv

Source-linked AI summary

Language Models Can Teach Themselves to Program Better

Patrick Haluptzok, Matthew Bowers, Adam Tauman Kalai

arXiv:2207.14502v4cs.LGcs.AI

TL;DR

The paper asks whether language models can generate programming problems that improve their own problem-solving, addressing the limits of human-authored problems and English descriptions that require vetting. It uses programming puzzles and an interpreter to generate and verify synthetic data for fine-tuning; fine-tuned Neo models solve 2–5 times as many puzzles as the baseline. The authors identify transfer to broader code generation and possible catastrophic forgetting as open constraints.

  • Problem

    The paper asks whether an LM can design its own programming problems to improve problem-solving, while English descriptions and hidden tests still require human vetting.

    Source: §1 · pp. 1–2

  • Method

    The LM generates programming puzzles and solutions, a Python interpreter filters for correctness, and the model is fine-tuned on the resulting synthetic data.

    Source: §1 · pp. 1–2

  • Results

    Fine-tuned Neo models solve 2–5 times as many puzzles as the baseline on Pass@100, with performance increasing as the model size that generated the data increases.

    Source: §4.3 · p. 7

  • Takeaways & Limitations

    The work demonstrates that LMs can generate novel, instructive problems and verified-correct solutions that improve their own performance on held-out problems.

    Source: §1 · p. 1, Results · p. 2

    Transfer from puzzles to broader code generation is difficult, and fine-tuning on synthetic puzzle solutions may cause catastrophic forgetting of other concepts such as English.

    Source: §5 · p. 9

Abstract

from arXiv · show

Recent Language Models (LMs) achieve breakthrough performance in code generation when trained on human-authored problems, even solving some competitive-programming problems. Self-play has proven useful in games such as Go, and thus it is natural to ask whether LMs can generate their own instructive programming problems to improve their performance. We show that it is possible for an LM to synthesize programming problems and solutions, which are filtered for correctness by a Python interpreter. The LM's performance is then seen to improve when it is fine-tuned on its own synthetic problems and verified solutions; thus the model 'improves itself' using the Python interpreter. Problems are specified formally as programming puzzles [Schuster et al., 2021], a code-based problem format where solutions can easily be verified for correctness by execution. In experiments on publicly-available LMs, test accuracy more than doubles. This work demonstrates the potential for code LMs, with an interpreter, to generate instructive problems and improve their own performance.

1 Introduction

The paper asks whether language models can use self-play to create programming problems that improve their own problem-solving. It introduces interpreter-verified puzzle generation and reports gains from fine-tuning, alongside a distinction from earlier augmentation approaches.

1 Introduction

  • The motivating question is whether an LM can design its own programming problems to improve its problem-solving, rather than relying only on human-authored code.The paper notes that human-authored problems and variants are limited by their creators’ accuracy and effort.Source: §1 · pp. 1–2
  • Programming puzzles are used instead of English descriptions because they are code-based and can be checked for correctness and efficiency by execution.The paper also presents puzzles as expressive enough to represent any P or NP problem.Source: §1 · p. 2
  • The approach generates diverse programming puzzles and solutions, verifies them with a Python interpreter, and fine-tunes the same model on the resulting data.The prompting strategy asks the model to generate problems similar to a small training set.Source: §1 · pp. 1–2

Results.

  • Fine-tuned models more than double their own test-puzzle accuracy on synthetic datasets, and the work releases 1M synthetic puzzle-solution pairs.The authors describe the problems as instructive because the model that generates them can improve on held-out problems.Source: Results · p. 2
  • Figure 1 illustrates Codex-generated puzzles ranging from a simple equation to a palindrome task requiring 4,600 copies of each listed substring.The figure caption identifies these as illustrative puzzles and solutions synthesized by Codex.Source: Figure 1 · p. 3

Related work.

  • Earlier augmentation approaches synthesize tests or input-output pairs from human-authored problems, whereas self-play generates problems and verified-correct solutions.The paper characterizes earlier augmentations as retaining human errors and blind spots or being limited in diversity.Source: Related work · p. 3

2 Background on Programming Puzzles

Programming puzzles specify a verification function and ask for a solution function whose output passes that verifier. Their code-based form allows direct execution-based checking, while prior work used few-shot prompting and interpreter checks to evaluate candidate solutions.

2 Background on Programming Puzzles

  • A puzzle defines a verifier f(·, x), and a solution g(x) is correct when f(g(x), x) = True for the given input x.A code synthesizer receives the puzzle source code and inputs and produces the solution function.Source: §2 · p. 3
  • Executing puzzles and solutions permits direct verification, avoiding ambiguities from natural-language descriptions and hidden test cases.The P3 dataset spans domains from string manipulation to open problems in algorithms and mathematics.Source: §2 · p. 3
  • Prior puzzle-solving work used few-shot prompts with five puzzle-solution examples, then checked sampled candidate solutions with a Python interpreter and timeout.Multiple attempts were sampled at a fixed temperature.Source: §2 · p. 3

3 Self-improvement Pipeline

The pipeline iteratively generates puzzles and solutions, filters them through validation, and fine-tunes the LM on the verified pairs. It aims to generate problems resembling the train and test distribution rather than simply maximizing difficulty.

3 Self-improvement Pipeline

  • The process repeats for n iterations, with the LM generating data and then being updated through fine-tuning.The approach seeks puzzles similar to the train and test distribution because harder problems from a different distribution may not be useful.Source: §3 · p. 4
  • Each iteration prompts the LM with randomly sampled training puzzles without solutions, then filters generated puzzles for syntactic validity and trivial solutions.The prompt length is constrained by the LM context window while leaving room for new puzzles.Source: §3 · p. 4
  • The LM proposes solutions for valid new puzzles; a Python interpreter verifies them, up to m correct solutions are selected per puzzle, and the LM is fine-tuned on the filtered pairs.If more than m correct solutions are generated, the shortest m are selected.Source: §3 · p. 4
  • The authors state that no human-written solutions are used for fine-tuning or evaluation, apart from five illustrative examples in the few-shot solving prompt.Figure 2 is identified as an overview of the data-generation and fine-tuning pipeline.Source: §3 · p. 4

4 Experiments

The experiments construct verified synthetic puzzle-solution datasets and test whether fine-tuning Neo models on them improves held-out puzzle solving, alongside analyses of filtering and dataset diversity.

4.1 Four Datasets of 1M Puzzle-Solution Pairs

  • The four 1M-puzzle datasets were generated by Codex and Neo-125M, Neo-1.3B, and Neo-2.7B; Codex was not fine-tuned.Codex fine-tuning was unavailable, so only the three Neo models were fine-tuned on each dataset.Source: §4 · pp. 4–5

4.3 Results

  • Neo models generated 25K unique samples in iteration one and 1M in iteration two, but modest second-iteration gains led the authors to stop at n = 2 because of cost.Figure 7 shows only small gains in the second iteration.Source: §4.1 · p. 5, §4.3 · p. 7, Figure 7 · p. 9
  • Pass@100 for Neo-2.7 on any of four verified synthetic datasets solves 2-5 times as many puzzles as baseline, with gains increasing with generator model size.Table 1 reports Pass@100 after one fine-tuning epoch.Source: Table 1 · p. 6, §4.3 · p. 7

4.1 Four Datasets of 1M Puzzle-Solution Pairs

  • Prompts use sampled training puzzles; generated puzzles are filtered for duplicates, invalid types, parsing failures, and trivial solutions before candidate solutions are interpreter-checked.Up to eight distinct correct solutions are retained per puzzle, and each Neo model size is fine-tuned for one epoch on each dataset.Source: §4.1 · p. 6

4 Experiments

  • Neo models are evaluated with Pass@k on 228 held-out puzzles; fine-tuning on 635 human-set solutions yields only modest test-accuracy gains.Pass@k counts puzzles solved within the first k generated attempts.Source: §4 · p. 5, §4.3 · p. 7

4.3 Results

  • Interpreter filtering accounts for a significant part of the performance boost: unverified data improves all models, while verified data gives a considerable additional boost.Figure 6 distinguishes verified synthetic data, unverified data, and the Neo baseline.Source: Figure 6 · p. 8, §4.3 · p. 8
  • Larger-model datasets show higher diversity across cluster counts, while synthetic puzzles are sometimes closer to training than test puzzles, especially for smaller generators.The diversity comparison uses an entropy-based metric; no training puzzles were duplicated.Source: §4.3 · p. 8, Figure 8 · p. 9

5 Future work

The paper presents interpreter-assisted self-improvement on programming puzzles and identifies extensions and boundaries for future work. These include plateauing Pass@k, uncertain transfer beyond code-described problems, and possible uses in other synthesis-and-verification settings.

Future work

  • The proposed pipeline improves puzzle solving using a Python interpreter and illustrative puzzles without solutions, but whether it can produce code better than humans remains an open question.The authors point to 150 HumanEval-derived puzzles in the P3 test set and name RSA factoring and Collatz puzzles as examples of difficult targets.Source: §5 · p. 9
  • Pass@k performance plateaus when the model trains on its own generated data, though the authors see no clear limit to what an LM could learn using an interpreter.They suggest reinforcement learning could improve the generation and filtering stages.Source: §5 · p. 9
  • Transfer from synthetic puzzles to code generation from English is difficult, and puzzle-only fine-tuning may cause catastrophic forgetting of other concepts such as English.Benefits may also depend on synthetic code being of higher quality.Source: §5 · p. 9
  • The self-play pipeline could be combined with other code-generation search strategies, and synthesis intertwined with verification may also suit theorem-proving.The authors describe self-play as a possible workaround for the LM data bottleneck, noting larger natural-language corpora than source-code repositories.Source: §5 · p. 9

A Related Work

Prior work covers programming-problem datasets, synthetic data, and filtering, but the paper distinguishes its approach by having an LM generate new problems with verified solutions. It situates programming puzzles as machine-verifiable problem-solving tasks rather than mere translation.

A Related Work

  • Earlier program-synthesis work often used input-output examples in domain-specific languages, while newer transformer LMs enabled synthesis in general-purpose languages such as Python.Programming by Example is described as inherently ambiguous, like English descriptions.Source: A Related Work · p. 13
  • Prior work synthesized input-output examples, generated tests for human-written code, or bootstrapped example-based synthesis, but did not have the AI system generate new problems with verified solutions.The passage cites data augmentation work [Balog et al., 2017; Shin et al., 2019; Li et al., 2022], generated tests [Roziere et al., 2021], and bootstrapping.Source: A Related Work · p. 13
  • Prior LM-generated English programming problems still required human vetting of descriptions and test cases, leaving generated datasets small-scale and error-prone.Sarsa et al. [2022] is cited for largely-correct English problem generation.Source: A Related Work · p. 13
  • Programming puzzles emphasize problem-solving: they state a goal, such as finding a short graph path, without specifying the procedure as translation problems do.The distinction is attributed to Schuster et al. [2021] and Li et al. [2022].Source: A Related Work · p. 13
  • Synthetic math-problem work studied learning from generated problems, but the problems were not LM-generated and it remained unclear whether beating other bots would improve general performance.The passage cites Aygün et al. [2020], Wu et al. [2021], and Polu and Sutskever [2020].Source: A Related Work · p. 13

B Broader Impact

The broader-impact discussion notes possible productivity benefits alongside employment and software-safety risks. It also limits the approach to code-described problems and flags possible privacy and offensive-content issues in model training data.

B Broader Impact

  • Automated code writing may raise software-engineer productivity and product value, but substantial gains could affect how many engineers are needed.The passage says care would be needed when releasing such systems if substantial gains occur.Source: B Broader Impact · p. 13
  • Bugs, including security holes common in training samples, may be reproduced in generated code.The authors refer readers to Chen et al. [2021] and Li et al. [2022] for broader discussion of code-generation implications.Source: B Broader Impact · p. 14
  • The approach targets problems described in code; some natural-language problems do not translate readily into puzzles, and puzzle-only training would likely harm natural-language understanding.The approach also relies on a deterministic verifier, which is unavailable in most domains outside code generation.Source: B Broader Impact · p. 14
  • The authors lacked access to the models’ training data, which may contain personally identifiable information and almost certainly contains offensive content.Occasional expletives appeared in generated puzzle source code, though they were absent from P3.Source: B Broader Impact · p. 14

C Further details of puzzle generation and solving

The appendix reports settings for puzzle generation and solving, including duplicate handling, temperature choices, and the evaluation judge. It also describes input-based checks used to screen trivial puzzles.

C Further details of puzzle generation and solving

  • Fewer than 1% of puzzles were duplicates; generation-data solving used temperature 0.9, while testing used 0.8.The 0.9 setting followed Schuster et al. [2021], and 0.8 followed Chen et al. [2021].Source: C Further details of puzzle generation… · p. 14
  • The P3 judging code identifies syntax errors and aborts infinite loops with timeouts, while preventing some malicious instructions but not providing full sandboxing.The passage contrasts this with systems that fully sandbox computation to prevent actions such as deleting files.Source: C Further details of puzzle generation… · p. 14
  • To screen for triviality, the authors test whether any selected representative input makes a puzzle return True.The tested inputs include specified integer, float, string, and short-list values.Source: C Further details of puzzle generation… · p. 14
  • All Boolean-input puzzles are classified as trivial because trying both possible inputs solves them trivially.Source: C Further details of puzzle generation… · p. 14

D Further diversity analysis

Across the four 1M datasets, puzzles from larger models are more diverse, with greater entropy indicating more uniform coverage of puzzle kinds. The analysis clusters puzzle embeddings and compares the resulting distribution with P3.

D Further diversity analysis

  • Figure 10 compares puzzle embeddings after iteration 1 for 25K-puzzle datasets and after iteration 2 for 1M-puzzle datasets.It also shows embeddings for the 155 training puzzles and a 10K sample of the 1M Codex-generated puzzles.Source: D Further diversity analysis · pp. 14, 16, Figure 10 · p. 16
  • Larger models generate more diverse puzzles across the four 1M datasets, with greater entropy indicating more uniform coverage of P3 puzzle kinds.The diversity metric varies the number of clusters and measures the entropy of the distribution over cluster assignments.Source: D Further diversity analysis · pp. 16–17
  • The analysis clusters 2048D embeddings of 397 P3 puzzles with K-means, then assigns synthetic puzzles to their nearest cluster centroid.The clusters appear semantically meaningful; the distribution is estimated from 10,000 puzzles per dataset, except P3, which has 397.Source: D Further diversity analysis · p. 16
  • Entropy of the normalized cluster counts measures diversity: equally sized clusters yield the maximum entropy, log C.The analysis reports this metric across four synthetic datasets and P3, varying the number of clusters C.Source: D Further diversity analysis · p. 16

E Further comparison between synthetic and training puzzles

The comparison measures synthetic puzzles’ embedding distances to training and test puzzles and compares their abstract-syntax-tree sizes. Synthetic puzzles are somewhat closer to the training set, while verified puzzles are shorter in part because unsolved puzzles are excluded.

E Further comparison between synthetic and training puzzles

  • The comparison uses 2,048-dimensional Codex code embeddings to measure each synthetic puzzle’s distance to its closest training and test puzzles.Because the embeddings are unit vectors, squared distance is equivalent to 2(1 − cosine similarity).Source: E Further comparison between synthetic… · p. 18
  • Figure 8 shows distance distributions for the smallest and largest Neo models, while Table 2 reports averages across datasets and iterations.Histograms for other models and iterations were similar; the table also includes unverified Codex-generated puzzles.Source: E Further comparison between synthetic… · p. 18
  • Synthetic puzzles are somewhat closer to the P3 training set than the test set, with a larger difference for smaller puzzles.Table 2 reports mean squared embedding distances for samples from the 1M puzzle datasets.Source: Table 2 · p. 18
  • Verified synthetic puzzles are shorter than human-generated puzzles because unsolved puzzles are excluded, and longer puzzles are more likely to be unsolved.Unverified Codex puzzles are longer; the authors also note that Codex is larger and more powerful than GPT-Neo, so harder or longer puzzles may be filtered less often.Source: E Further comparison between synthetic… · pp. 18–19, Figure 11 · p. 19

F Further examples of generated puzzles

Generated puzzles range from training-related patterns to puzzles using human concepts or challenge-like computations, but hand examination also found errors and uneven comment quality.

F Further examples of generated puzzles

G Further experiments on Codex data

Further experiments found higher accuracy with interpreter-verified than unverified Codex data, while Codex Davinci outperformed smaller Neo models. Few-shot prompting remained beneficial after extensive fine-tuning.

G Further experiments on Codex data

  • Interpreter-verified Codex data improved accuracy significantly more than unverified generated data.Source: Figure 13 · p. 22
  • Codex Davinci outperformed the much smaller Neo models on the test set, while Neo was fine-tuned on 1 million Codex-generated verified puzzles.Source: G Further experiments on Codex data · p. 22, Figure 14 · p. 23
  • Few-shot testing beat zero-shot testing across all three Neo model sizes, even after 11 fine-tuning epochs totaling over 1 billion Codex-generated tokens.The models still benefited from the P3 tutorial puzzle prompt.Source: G Further experiments on Codex data · p. 22, Figure 15 · p. 23
  • 4.95 factor: overall test performance improved after fine-tuning, according to the reported Pass@100 accuracy comparison.Source: Table 3 · p. 23
  • A temperature sweep found 0.8 optimal for Pass@100 across all three model sizes at a 0.2 search step size.The plotted models were fine-tuned for one epoch, about 92 million tokens.Source: Figure 16 · p. 23
Loading 2207.14502v4…