Language Models Can Teach Themselves to Program Better
Authors: Patrick Haluptzok
Matthew Bowers
Adam Tauman Kalai
Venue: ICLR 2023 poster (2023)
Keywords: deep learning
natural language processing
program synthesis
large language models

Abstract: 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.

Published as a conference paper at ICLR 2023
LANGUAGE MODELS CAN TEACH THEMSELVES TO PROGRAM BETTER
Patrick Haluptzok Microsoft Research haluptzokelive..om
Matthew Bowers"
Adam Tauman Kalai Microsoft Research adam@kal ai
MIT mlbowers@mit.ent edu
ABSTRACT
Recent Language Models (LMs) achieve breakthrough performance in code generation when trained on human-authored problems, solving some conpetitix-programming problems. Self-play has proven useful in games such as Go, and thus it is natural to ask whether LMs 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 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], code-based problem format where solutions can easily be verified for correctness by execution. In experiments on publicly-availabl This work demonstrates the potential for code LMs, with an interpreter, to generate instructive problems and improve their performance.
LMs, test accuracy more than doubles.
INTRODUCTION
Recent Language Models (IMss pre-trained for code generation [Chen et al., 2021; Chowdhery et al., 2022; Li et al., 2022; Austin et al., 2021| produce useful code and even achieve trivial performance in human programming competitions [Li et al., 2022]. LMs that solve programming problems may help make algorithmie breakthroughs in computer science, such as factoring large integers or designing faster algorithms for multiplying large matrices (useful in ML). However, LMs are generally trained on human-authored code which contains bugs and inefficiencies that are reproduced by LMs [Chen et al., 2021], with ambiguous specifications usually in English by example.
Inspired by the AlphaZero's success using self-play in Go (Silver et al., 2018], it is natural to ask whether self-play could be used for learning a programming language such as Python, by which we mean: Can an LM design its own programming problems to improve its problem- solving ability? This paper demonstrates how LMs, together with an interpreter, can be used to generate diverse datasets of verified-correct correct code problems and solutions, which can then be used improve the LMs themselves through fine-tuning. These synthetic curricula. are not only correct but. instractive in the sense that the test. performance of the L.Ms increases once fine-tured on these diverse datasets of synthetic coding problems and solutions. Because programming is universal aspect of computing, it is important (and also perhaps surprising) to discover that these LMs are capable of generating novel and instructive problems, in addition verified-correct solutions.
In addition to solution correctness, diversity is a key desideratum synthetic problems. One could create dataset of trillions of addition problems such as assert 173288 291124 == y but such dataset would be useless outside of arithmetie. Similarly, one function f could be used to create infinite variations by renaming its variables. but this would only teach variable naming and f. One could do the same with more problems and transformations,
Work done while at Microsoft: Research

---

Published as a conference paper at ICLR 2023
but any set of human-authored problems (and variants) is inherently limited by the accuracy and effort of human creators. AI systems have the potential to go beyond templates and superficial changes to generate vast quantities of novel challenges and innovative solutions. Moreover, self-play might be necessary to one day surpass human code quality, just as AlphaZero surpassed human Go play.
The first challenge in self-play for code LMs, unlike Go where the win-condition is clearly evaluable, is that the goal in code generation is not obvious. How should problems be specified? Programming problems are often described in English and examples and evaluated with hidden test cases in programming competitions and code-generation benchmarks such as CodeContests [Li et al., 2022], HumanEval [Chen et al., 2021], and APPS [Hendrycks et al., 2021]. While LMs have in fact been shown to be capable of generating largely-correct English programming problems [Sarsa et al., 2022], human oversight is still required for vetting the descriptions and test cases.
Self-play using programming puzzles. Our approach is simple but powerful: rather than using English problem descriptions which are ambiguous and hard to verify, we generate progromming puzzles [Schuster et al., 2021] and solutions. Programming puzzles have been shown to be useful for evaluating the code generation ability of LMs. Puzzles are illustrated in Figure 1 and formally described in Sec. 2, but here note some key features of puzzles as a problem representation:
Machine verifiable. Like unit tests, puzzles are code-based, and any solution can be easily machine verified for correctness and efficiency by execution.
Expressive. Puzzles can represent any P NP problem, which includes both easy and hard problems requiring all major algorithmic tools. Surpassing human performance on puzzles would lead to algorithmic and mathematical breakthroughs.
Useful benchmarks. IMS can solve puzzles, with more powerful LMs solving more puzzles, and puzzle-solving also correlates with coding experience among humans.
In this work, we show that. LMs can generate myriad of instructive programming problems in the form of puzzles. We show that it is possible for an LM to generate puzzles and machine-verified solutions which are, in turn, useful for improving that same LM. In our case, puzzlcs are written in Python and a Python interpreter is used for verification. Our strategy for generating instructive problems that improve test performance is to prompt the LM to generate problems similar to those in a small training set.
We evaluate approach and measure performance gains a held-out set of human-authored test puzzles using three GPT-Nco models [Black et al., 2021]. We find that these LMs can synthesize correct code in the form of novel puzzles and solutions that are machine-verifior to solve the puzzles within an allotted time.
Results.
These models more than double their own accuracy on test puzzles when fine-tuned on their own synthetic datasets. We also generate synthelic code using the Codex API, filtered for correctness and efficiency by the interpreter. While the Codex API does not currently provide fine-tuning, the code it generates proves even more valuable for improving the Neo models. We also perform an ablation study to compare the value of filtering with the Python interpreter. Finally, a diversity analysis suggests that the larger models generate puzzles of greater varicty and coverage.
Contributions. There are three contributions of our work'. First, we introduce procedure that can generate a diverse set of programming puzzles with solutions that are verified correct and efficient in that they execute within a given time bound. Second, we release datasets of 1M synthetic puzzles and solutions along with the source code for our work?. Third, we show that the problems are instructive, namely that the LM that generates the problem can improve its own performance on held-out test problems. Our work opens the door to the further research using self-play to improve code generation and other problems.
Preliminary version presented at DLAC 2022 Phttps://Gsi //GttHub. www//oi http://www......eeteeoooo//////a
httpr//iwwwwwee//mmnnmmmmm fo HScx010--- in ICT.22023 directory
2

---

Published as a conference paper at ICLR 2023
def f(c: int): return e + 50000 174653
def gO: return 174653 50000
assert {(g()
def f(x: str, chars=
Hello', ('elloo'' 'there' 'you! '1, n=4600):
return x x[::-1] and all ([x. count (c) == all([x.cuut(()
for с chars])
def g(chars- HeHllo', 'there', 'you!'], m-460)); "" joon [ctn for in chars]) return a[::-1]
assert {g())
Illustrative puzzles and solutions that were synthesized by the Codex language model: the first is simple equation; the second requires finding palindrome (string same forwards and backwards) with exactly n=4600 copies of each of given list of substrings.
Figure 1:
Related work. Data augmentation is not new to code generation as multiple works have synthesized tests for human-authored code fe.g. Li et al., 2022; Roziere et al., 2021]. However, data augmentation for test coverage still relies on human-authored problems and has human errors and blind spots, unlike self-play where AT system problems and verified-correct solutions. Input-output pairs have also been synthesized for program synthesis and code generation [Balog et al., 2017; Shin et al., 2019; Alet et al., 2021; Li et al., 2022], though again those augmentations are similarly unverified and limited in diversity. The analogy to games illuminates the difference between self-play and other approaches, as discussed in further related work (Appendix A). For instance, human-in- in-t-iiithhhe.. loop approaches are like learning Go by playing against humans, learning from human data is like learning from human games, and learning from templates other lypes of external (non-LM) synthetic data is like learning from static synthesizers rather than self self-play.
generate comprehensive
2 BACKGROUND ON PROGRAMMING PUZZLES
A Programming Puzzle [Schuster et al., 2021| is specified by verification function x) which may have zero or more input arguments æ. A solution to the puzzle a function g such that (() True. Thus, given an input the solution g(z) must generate output that satisfies the verifier ʃ for the particular input x. Examples generated by our systems are given in Fig. 1. The task of a code synthesizer is to produce the code for a solution function given the source code for the puzzle f and the inputs æ.
(syuthetic) puzzles
The open-source P3 dataset of Python Programming Puzzles demonstrates that programming puzzles can capture this wide range of challenges from various domains, from trivial string manipulation to longstanding open problems in algorithms and mathematics. Many problems currently used in the evaluation of Codex, AlphaCode, and PaLM-Coder have been rewritten as puzzles. Furthermore, puzzles include numerous classic algorithms such as Towers of Hanoi. Puzzles circumvent the aforementionel ambiguities of natural-language and hidden test cases, because the validity of puzzles and solutions can be directly verified by simply executing code. Our work uses the P3 puzzles but not their solutions.
Schuster et al. [2021] introduced puzzles and showed how to use LMs to solve them. In particular, they construct few-shot learning prompt consisting of five examples of puzzles interleaved with their solutions and the puzzle to be solved appended, and provide this as input to the LM to generate candidate solution. This candidate is readily checked for correctness and efficiency by rumning a Python interpreter with a given timeout. Multiple attempts made by sampling k: > times from the LM, at fixed temperature.
3

---

Published as a conference paper at ICLR 2023
Training (155 puzzles)
propeses puzzies
Synthelic Puzzles
LM propeses solutions
Synthetic Puzzles Proposed Solutions
Verify solutions
Verified Synthetic
Data
5. Repeat
Fine-tune
Language Model (LM)
Figure 2: Data Generation Pipeline, used to iteratively generate data and fine-tune the LMs.
3 SHLF-IMPROVEMENT PIPELINE
The inputs to our system are sets of training (and test) puzzles, five examples of puzzles and solutions used in the the few-shot learning prompt construction, the number 2 1 of iterations, the number of attempts a 2 1 per puzzle, and the maximum m 2 1 number of synthetic solutions per puzzle. The following four steps are repeated n times:
1. LM proposes puzzles. This is done by few-shot learning strategy: set of puzzles is randomly sampled from the train set and concatenated together, without solutions. The sequence is chosen of such a prompt is shown in Fig. 3. The number of puzzles is chosen so that its concatenated length remains within the context window size of the LM, while leaving space for one more queried, and completes the prompt by generating additional puzzles. The generated puzzles checked for syntactic validity and also filtered to remove puzzles with "trivial" solutions, such as small constants.
random, without replacement. An example
puzzles to be generaled. The language model is then
2. LM proposes solutions. The valid new puzzles are solved using the "medium prompt" of Schuster et al. [2021] in few-shot learning approach with constant number of attempts per puzzle. This prompt shown Fig. in Appendix C.
3. Verify solutions. The generated solutions then verified with the python interpreter. Among the correct solutions, a maximum m correct solutions per puzzles are selected (if more than m correct solutions are generated, the shortest m are selected).
4. Fine-tune. The LM is fine-tuned on this synthetic dataset of filtered puzzle-solution pairs.
Our approach for generating puzzles is motivated by the fact that test and train puzzles are from the same distribution, hence we aim to generate similar synthetic puzzles. While may be natural to try to generate "hard" problems, they may not be useful if they from a very different distribution. In each of the n iterations, the LM is used for generation and then the LM is updated by fine-tuning it the generated data. We next describe our experiments, including how many puzzles were generated, the data, models, constants, and evaluation. We emphasize that human hand-written solutions evaluation (other than the five illustrative examples used in the medium prompt for few-shot learning to solve puzzles). An overview of our pipeline for data generation and fine-tuning is depicted in Fig. 2.
used for fine-tuning or
4 EXPERIMENTS
At the time writing, the P3 repository contained 397 programming puzzles with 155 puzzles marked train and 228 test, well as Codex-generated solutions to those puzzles. Experiments measure the utility of this process based on how well the LM performs at solving the held-out test puzzles. To this end, synthesize four datasets of 1 million (1M) puzzle-solution pairs that are verified correct. Each dataset synthesized using a different T.M. The largest model is Codex [Chen et al., 2021] which is accessed via API. Codex
4

---

Published as a conference paper at ICLR 2023
def finds: List[int], 1i=[42, 18, 21, 103, 2, 11], target=[2. 21, 42]); i, J, inds return 1i[i:j:k] == target
def (path: List [List [int]], m=8, n=8, target=35): def legal_move (m)
(a, b), (i, j) =m
return {abs a), abs(j b)} == {1, 2}
def f(
Figure 3: An example prompt for generating puzzles. For each request for prompi. completion, the LM would generate a new puzzle.
a GPT-3-like transformer model [Brown al., 2020] that has been trained on large corpus of code and smaller corpus of standalone programming problems. The other three models we generate data from are open-souree GPT-Neo 125M 1.3B and 2.7B models [Black el al., 2021] (henceforth referred to Neo). Neo is GPT-3-like model which has been pre-trained on the Pile [Gao al., 2020] dataset including English and Git code.
We first describe how we run the pipeline above to generate the four datasets of 1M verified- correct synthetic puzzle-solution pairs. We then evaluate test performance of the Neo models, after being fine-tuned these datasets. Since fine-tuning Codex is not yet publicly available, we instcad fine-tune just the three smaller Neo models on each these four synthetic datasets and mcasure test improvements. The baselines pretrained Neo models.
In two additional experiments, we also evaluate alternative strategies for our studies. The first is Neo fine-tuned on just the 155 P3 training puzzles with hetic solutions without any additional synthesized puzzles. Second, we fine-tune Neo on a set of 1M unverified synthetic puzzle-solution pairs without correctness filtering. This second baseline enables us to evaluate the effect of automatic correctness filtering.
Neo in
Pass@k solving metric. Consistent with prior work, results are presented using the Pass@k metric [Chen et al., 2021]. Here k is a parameter indicating the number of allempls to solve puzzle. For each test puzzle, k solutions are generated and the index of the first correct solution obtained for each problem recorded. Pass@k indicates how many problems had correct solution generated within the first h solutions. Higher values for A result in solving more problems. We expect Pass@1 performance to improve at lower temperatures, but single temperature was used to conserve resources. To reduce variance, we in fact generate 256 candidate solutions per puzzle and report results for k = 1 to 100 and use the unbiased estimator of Chen et al. [2021].
4.1 FOUR DATASETS OF 1M PUZZLE-SOLUTION PAIRS
Since we did not have the ability to finc-tune the Codex model, the 1M puzzles are all generated in single iteration
1 of our pipcline. For the three Neo models, run only n 2 iterations. The first iteration went slowly as the models produced many invalid puzzlesoolutions pairs. In particular, from each model in that iteration. However, the fine-tuning greatly increased accuracy and sped up the data generation rate in the second iteration, where we generated 1M unique muzzle/soluttin samples from each model. This resulted in four datasets of 1M puzzles each, produced by the four different LM's. We refer these datascts by the model that generated them. After fine-tuning on these 1M new puzzles, we stopped at = 2 iterations as further iterations were costly and the performance increase from iteration to 2 was modest, as can be seen in Figure 7, compared to the generat ion cost. Possible strategies for generating even more instructive puzzles in later iterations are discussed in Section 5. Neo models were pre-trained by Al (MTT-licensed), and numbers parameter counts.
generated 25K unique puzzle/solution /solution samples
5

---

Published as a conference paper at ICLR 2023
fine-tune dataset
Verified
Puszles
Solutions (Count)
Tokens
Pass@100
BASELINE
N/A
No puzzles
No solutions (0)
7.5%
HUMAN
Yes
Human
Synthetic (635)
74K
10.5%
VERIFIED-125M
Yes
Synthetic
Synthetic (1M)
74M
15.4%
VERIFIED-L.31B
Yes
Synthetie
Synthetic (1M)
65M
18.9%
VERIFIED-2.7B
Yes
Synthetic
Synthetic (1M)
66M
20.6%
UNVERIFIED-CODEX
No
Syuthetic
Syuthotic (1M)
113M
21.5%
VERIFIED-CODEX
Yes
Syuthetic
Synthetic (1M)
98M
38.2%
Table 1: Test performance after fine-tuning the datasets used in our experiments, Pass0 100 shown for epoch of fine-tuning the Neo-2.7B model on the dataset.
Puzzle generation. In order to generate puzzles, created simple prompt which consisted a sample of training puzzles as large as possible for the LM while leaving room for new puzzle to be generated as illustrated in Fig. 3 (for Codex specifically given the API token limit, this was a median of 43 puzzles). We then applied filtering, eliminating duplicate puzzles, puzzles with an invalid argument type-hint," puzzles which did parse in Python, and puzzles which had a "trivial" solution, as detailed in Appendix C. For example, puzzle took an int solution, we tested to ensure that it did not have a solution in {-10, -9.... 100}. In total, approximately half of the generated puzzles were eliminated during this pre-firterig process.
Puzzle solving. We then used the LM to attempt to solve each of these puzzles, with the same few-shot learning prompt used in P3, which consists the five tutorial sample puzzles and solutions appended with the puzzle to be solved. The exact prompt is shown in Fig. 9. For each puzzle, a = 128 attempted solutions were generated by the Neo and Codex models. Each of these candidates solved the generated puzzle, using the P3 judging code which includes a one-sccond timcout. We then take the solutions judged to be correct, with up to maximum of 8 distinet solutions per puzzle, taking the shortest 8 for the puzzles that had more than 8. Further details including temperatures for generation and solving are in Appendix C.
judged correct incorrect based whether it
Finc-tuning. Each of the 3 Neo model sizes was fine-tuned for 1 epoch (1 pass through the generated data) using each of the 4 different datasets of 1M synthetic verified puzzlc-solution pairs, yielding 12 fine-tuning runs. The format of the fine-tuning data mirrors that of the few-shot solving prompt discussed above and shown Fig. 9, which is an interleaving of puzzles, solutions, and assertions that the solution is correct for the puzzle. We did not fine-tune the Codex model.
4.2 KNOWLEDGE-DISTILLEO
ABLATION STUDY
When Codex-generatie puzzles are used to fine-tune Neo model, the smaller model may be learning both from the larger Codex model (a form what is called knowledge distillation [Hinton et al., 2015; Gou et al., 2021J) well from the interpreter which filters puzzles for correctness (which might called interpreter distillation). This presented an opportunity for an ablation study to disentangle the effects of the two. To this end, construct set of 1M unverified synthetic puzzle-solution pairs from the Codex generations without correctness filtering. To distinguish these two datasets, VERIFIDD-CODEX We fine-tune the Neo models on both of these datasets. This second baseline enables evaluate the effect of automatic correctness filtering.
refer to them UNVERIFIED-COME CODEX and
A valid puzzle has single required argument with type that must be bool, float, int, str, List 's thereof, nested arbitrary depth.

---

Published as a conference paper at ICLR 2023
45%
409
40%
3356
33%
555
33%
305
305
25%
-foor Dodec -12
--rodine -odde 2.78 1138 125M
-Baidine Codes 2278 -1.3 123M
(a) GPT--Neo 125M Model
(b) GPT--No 1.3B Model
(c) GPT--No 2.7B Model
Figure 4: The graph shows how each model fine-tuned on data generated by the different models (Codex and the three Neo models) impacts Pass@kk with h in log-scale on the horizontal axis. Data generated from the larger models helps more, as larger models appear able to distill more knowledge into the data they generate.
GPT-Neo 125M
GPT-Neo 2.7B
Codex
P3 training puzzles
Figure 5: 2D visualization of the puzzles a sample of 10K puzzles for three of the 1M-puzzle datasets, using Codex embeddings and UMAP dimensionality reduction. Puzzles from larger models have greater coverage (less clumpy) than those of smaller models. Of course, there many fewer embeddings for the 155 human-authored training puzzles.
4.3 RESULTS
We measured how successfully the Neo models solved the 228 test programming puzzles in the few-shot regime (using the same prompt used to solve puzzles during generation), with the Passuk metric. Each BASELINE model was Neo before fine-tuning. We also considered a HUMAN dataset consisting of correct solutions to 95 puzzles out of the 155 P3 training puzzles. These 635 solutions were generated by Codex model, as in the original work Programming Puzzles [Schuster et al., 2021], and verified in the same fashion as described above (See. 4.1) for solving the synthetic puzzles. Fine-tuning
that dataset only modestly improved the Lest accuracy of Neo, presumably because it was so small.
Table 1 shows the Pass@100 performance of Neo-2.7 on all these datasets, well the number of tokens in each dataset. Neo, once fine-tuned on any one of the four 1M verified synthetic puzzle-solution pairs, solves 2-5 times many puzzles as the baseline model, with performance increasing as the model size that generated the data increases. Interestingly, the performance of Neo-2.7B improves even when trained on code generated by Neo-125M because the Neo- Nco-125M data has been filtered by a Python interpreter for correctness; effectively Neo-2.7B learns from the "watching its smaller sibling interact with the interpreter."
Fig. 4 shows the significant performance increase in fine-tuning each of the three Neo models on each of the four final 1M datasots. Figure 7 shows a large benefit from the first iteration and small benefit from the second iteration of our pipeline. Due to the small improvement, the process was terminated at n = 2 iterations due to cost considerations. discuss possible directions to improve the results during later iterations. Nonetheless the significant gains from the 25K puzzles are interesting as the fact that problems generated by larger models seem to be more instructive. The gains, broken down by P3 puzzle domain, are given in Table 3 (page 23). One possible explanation for this is the greater diversity of the puzzles generated by larger models, analyzed below.
Section 5, we
7

---

Published as a conference paper at ICLR 2023
Data Generation
GPT Neo
Evaluation
Evaluste
Training Data (155 puzzles)
Solves 7.5%
heldout test puzzlas
Synthetic
Model propeses puzzies
Data
Unverified Synthelic
Synthetic Puzzles
Data
Fine tune GPT-Neo
Solves 21 5% helddut test puzzles
1M suzzle-solution pairs
Model proposes solutions
Verified Synthetic
Synthetic Puzzles Unverified Solutions
Verify solutions
Data puzzle pairs
Fine-tune GPT-Neo & Evaluate
Salves 38 2% of heldout puzzles
Figure 6: Overview of the Codex ablation experiment and results. Generating and fine-tuning on verified synthetic puzzles and solutions, is shown in green, while using unverified puzzles is shown in red. The Neo baseline is shown in ycllow. All performance results are from the 2. model after one epoch fine-tuning.
Datasct diversity. To better understand the diversity present in the synthetic puzzles and how it varies across model size, use OpenAI Codex API's code embedding feature to generate a 2,048-dimensional embedding of puzzles (nol solutions). For each of our four 1M puzzle-solutions dalasets, we embedded sample of 10,000 puzzles. For visualization, construct 2D embeddings using the UMAP [Mclnnes, Leland, 2020] dimensionality reduction library (default parameters, densmap=Trrue on these 40,000 samples in 2048D. UMAP [McInnes et al., 2018| is dimensionality reduction technique similar to t-SNE [van der Maaten and Hinton, 2008). Fig. shows these four datasets, with each point being a puzzle. The puzzles from the smaller models appear more densely clustered, while the puzzles from the larger models seem to be more spread out. To quantify this clustering effect, in Appendix D we define an entropy-based diversity metric, given specific number of clusters C, and evaluate it for each of the datasets. As seen Figure (left), across all numbers of clusters, larger models produce higher entropy (more diverse) results.
Comparing synthetic puzzles train and test sets. In addition comparing the synthetic puzzles to each other, we also compare them to the training and test puzzles. We measure Euclidean embedding distance between puzzles, which would be 0 for identical puzzles and is inversely related to cosine similarity, since embeddings are unit length. We determine which training and test puzzle are closest to each of the 10,000 sample puzzles for each of the 1M puzzle datasets. Fig. 8 (right) shows the distribution of distances to nearest train versus test puzzle for two datasets. No training puzzles were duplicated and small fraction of synthetic puzzles were significantly closer to training puzzles than test puzzles, with this discrepancy being more pronounced for puzzles generated by smaller models. Appendix E. provides detailed comparison.
Ablation studies. The setup and results of the knowledge distillation experiment are summarized in Fig. 6. for Neo-2.7B. The results indicate that significant part of the performance boost is due to the filtering by the interpreter. The results of Table indicate how much gain is due to differences in model size for the model generating the puzzles. Further details and figures about the ablation are deferred to Appendix G. As shown in the unverified data improved the Pass@k performance
Fig. 13 (page 22), fine-tuning across all models, and verified data gave a considerable boost to performance. Appendix G gives the results of further experiments performed better understand the results.
8

---

Published as a conference paper at ICLR 2023
20%
275
15%
1.3
10%
125
58
2%
09
0%
0%
10
100
30
-darrise -2i0-tanuned -iM-Bhanneed
3M
-Goddine 228cleettane + -1Minntteeed
(a) GPT-Neo 125M Model
(b) GPT-Neo 133 Model
(c) GPT-Neo 2.7B Model
Figure 7: Passuk for the three Neo models after fine-tuning the self-generated and verified data in the 1st iteration (25K samples) and the 2nd iteration (1M samples) of the data generation pipeline. Small gains in iteration suggest that performance may have plateaued.
Diversity number of clusters
Squared distances (Neo 125M)
Souared distances (Noo 1.28)
P3
diversity bits of entropy)
Codex
27B
4-
1.3B
125M
3.
Squered tNeo 751
Squeree distences (Covex)
4
16
64
C. number of clusters (log-scale)
0.0 0.1 0.2
0.3
3.4
0.5
0.5
0.3
0.2
0.5
0.4
Figure 8: Left: Diversity metrics for the original human-authored P3 dataset and each synthetic 1M dataset, we vary the number of clusters from 4 to 64 (averaged over 10 runs). Right: Distribution of embedding distance? from each puzzle of to their closest puzzles in the training and test scts, across the same four 1M-puzzle datasets.
5 FUTURE WORK
Our unsupervised self-improvement pipeline demonstrates that code LMs can improve themselves at solving programming puzzles, using only Python interpreter and set of illustrative puzzles (without solutions). LMs synthesize novel puzzles and solutions that lead to self-improvement on test puzzles. It raises several interesting questions for future work.
First, can this approach be improved to the point that LMs generate better code than humans for solving puzzles? Many complex algorithmic challenges be written puzzles, e.g., the P3 test set has 150 puzzles derived from the HumanEval benchmark [Chen et al., 2021]. The holy grail here would be solving mathematical problems in the P3 dataset, such as the RSA factoring or Collatz puzzles. Future work could use reinforcement learning improve the generation and filtering stages of the pipeline. While our model's Pass@k performance plateaus when trained on it's own self-generated data, there is no clear limit to what an LM could learn using an interpreter.
of the longstanding open algorithmic or
An excellent question is how one could use synthetic puzzles to improve code LMs more broadly, e-g., generating code from English descriptions. Transfering gains from one domain to another is a difficult challenge, and simply fine-tuning on millions of synthetic puzzle solutions may make the model "catastrophically forget" [French, 1999] other concepts such as English which are not useful for solving puzzles. Moreover, benefits may only be realized once the synthetic code of a higher quality.
The idea of self-play may also be useful in other areas where synthesis and verification can be intertwined, such as theorem proveinnrrovig..... Self-play offers a possible workaround to the data bottleneck for LMs [Hoffmann al., 2022], since there are significantly larger natural language corpora available for training LMs than source-code repositories. Finally, our self-play pipeline could be combined with other search strategics for code generation.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Ferran Alet, Javier Lopez-Contred Contreras, James Koppel, Maxwell Nye, Armando Solar-Lezama, Tomas Lozano-Perez, Leslie Kaelbling, and Joshua Tenenbaum. 2021. A large-scale benchmark for few-shot program induction and synthesis. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 189), Marina Mcila and Tong Zhang (Eds.). PMLR, 175-186. https: nttps://proceeddins.. mlr. www.prees/v1333 alea2ia..taaaaaa.aaaaaaaa. htmll
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carric Cai, Michael Terry, Quoc Lc, and Charles Sutton. 2021. Program Synthesis with Large Language Models. arXie preprint orXiv: 07732 (2021).
arXiv:2108.0773 [cs.PL] attps://arxiv... org/abs hbs///b//// wabs//108.000 07732
Eser Aygün, Zafarali Ahmed, Ankit Anand, Vlad Firoiu, Xavier Glorot, Laurent Orseau, Doina Precup, and Shibl Mourad. 2020. Learning to prove from synthetic theorems. arXiv preprint or arXiv:2006. 11259 (2020).
Matej Balog, Alexander L. Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. 2017. DeepCoder: Learning to Write Programs. In International Conference on Representation Learning (ICLR).
Sid Black, Leo Gao, Phil Wang, Connor Lealy, and Stella Biderman. 2021. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh- Tensorflow. https://8oi. org//0........... 5281/zenodo 5551208
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla. Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Matousz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alee Radford, Πlya Sutskever, and Dario Amodci. 2020. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems, Vol. 33. 1877 1901.
Mark Chen, Jerry Tworck, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Greichen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hessc, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojeiech Zaremba. 2021. Evaluating Large Language Models Trained on Code. arXio preprint arXiv:2107.0m 0070033744 (2021). arXiv:2107.06: 003744
[cs.LG] actps://arxiv: org/ ab1//10/ 03374
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thammaaayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowyez, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstere Douglas Fck, Jeff Dean, Slav Petrov,
10

---

Published as a conference paper at ICLR 2023
and Noah Fiedel. 2022.
PaLM: Scaling Language Modeling with Pathways. arXiv preprint arXiv:2204.022 023111 (2022). arXiv:2204.02311 2204.0231
[cs.C]] attps://arts http://xxxvv..o//raa// org/abs/
Karl Cobbe, Vincet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiihhro Nakano, Christopher Hesse, and John Schulman. 2021. Training Verifiers to Solve Math Word Problems. (2021).
arXiv:2110.14168 |es.LG]
Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sablé-Meyer, Lucas Morales, Luke Hewitt, Luc Cary, Armando Solar-Lezama, and Joshua B. Tenenbaum. 2021. DreamCoder: Bootstrapping Inductive Program Synlhesis with Wake-Sleep Librury Learning. Associalion for Computing Machinery, New York, NY, USA, 835 850. https://don org/10...//0 10///10.11 1145/
3453483. 34844833445480
Robert M French. 1999. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences 3, (1999), 128-135.
Lco Gao, Stella Biderman, Sid Black, Lanrence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, al. 2020. The Pile: An 800GB Dataset of Diverse Text for Language Modeling, arXiv preprint arXiv:2101.000 00007 (2020).
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. 2021. Knowledge Distillation: Survey. International Journal of Computer Vision 129, 6 (2021), 1789 1819. htttp::/ddo.orr/100// 1t10//000000/11122--2------10000
Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al. 2017. Program synthesis. Founda- lions and Trends in Programming Languages 4, 1-2 (2017), 1-119.
Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, and Jacob Steinhardt. 2021. Measuring Coding Challenge Competence With APPS. (2021). arXiv:2105.0990 [cs.SE]
Gcoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. 2015. Distilling the Knowledge in a Neural work. CoRR abs/ 2a4/1503.02531 (2015). 1xX::1150300231 http://arxiv.cr org/ abs/1503.022 025331
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, Tom Hennigan, Eric Noland, Katie Millican, George van den Driessche, Bogdan Damoc, Aurelia Guy, Simon Osindero, Karen Simonyan, Erich Elsen, Jack W. Rae, Oriol Vinyals, and Laurent. Sifre. 2022. Training Compute-Optinall Large Language Models. arXin preprint or arx::2203. 15556 (2022). https://arsii //tpsi///xxvv... org/ hts//bbs/20033 15556
Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hu- bert, Peter Choy, Cyprien de Masson d' d'Aute Igor Babuschkin, Xinyun Chen, Po- Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. 2022. Competition-Level Code Generation with Alpha- Code. https://storage. googleapie s. com/ deepminddddnn// deepmind-medial media/ / Level_Lode__gnerratinn..iii alphacode pdf
Leland McInnes, John Healy, and James Melville. 2018. UMAP: Uniform Manifold Approxi- mation and Projection for Dimension Reduction. arXiv e-prints, Article arXiv:1802.03426 (Feb. 2018), arXiv:1802.03:22 pages. arXiv:1802.03426
|stat.ML]
McInnes, Leland. 2020. GitHub Imcinnes/umuinnn Uniform Manifold Approximation and Projection (UMAP). https://gi http://ttt......iiiiooeeeeeeeeee wwwm/mmiinee//mmmmemmieacmi
Yu Meng, Jiaxin Huang, Yu Zhang, and Jiawei Han. 2022. Generating Training Data.
with Language Models: Towards Zero-Shot Language Understanding. arXio preprint ar Xin:22002.00 04538 (2022). https://arxiv.. wwwaaaawwiw....raeeeeeeeee htrg/abs/2200
222/222222222288 04538
11

---

Published as a conference paper at ICLR 2023
Aditya Krishna Menon, Omer Tamuz, Sumit Gulwani, Butler W Lampson, and Adam Kalai. 2013. A Machine Learning Framework for Programming by Example. In ICML. 187-195.
F. Podregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Griscl, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825 2830.
Stanislas Polu and llya Sutskever. 2020. Generative Language Modeling for Automated Theorem Proving. https://doi.org 10. 48550/ ARXIV. 2009.03393
Marco Tulio Ribciro and Scott Lundberg. 2022. Adaptive Testing and Debugging of NLP Modcls. In Proceedings of the 60th Anmual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, Dublin, Ireland, 3253 3267.
org/10. 1tw.1/.11633//11/// acl-long. 230
Baptiste Roziere, Jie M Zhang, Francois Charton, Mark Harman, Gabriel Synnaeve, and Guillaume Lample. 2021. Leveraging automated unit tests for unsupervised code translation. arxi preprint Xiv: 0at:22100.0100 10.06773 (2021).
Sami Sarsa, Paul Denny, Arto Hellas, and Juho Leinonen. 2022. Automatic Generation of Programming Exercises and Code Explanations Using Large Language Models. In Proceedings of the 2022 ACM Conference on International Computing Education Research Volume 1 (Lugano and Virtual Event, Switzerland) (ICER '22). Association for Computing Machinery, New York, NY, USA, 27 43. attps://doi.ors org/
10. 10.00.1455// 1145/3501181..... 35439557
Timo Schick and Hinrich Schütze, 2021. Generating Datasets with Pretrained Language Models. arXiv preprint arXiw:2104.075. (2021). https://arxiv org/ 2////2104...7
Tal Schuster, Ashwin Kalyan, Alex Polozov, and Adam Tauman Kalai. 2021. Programming Puzzles. In Thirty-fifth Conference Neural Information Processing Systems. https: //openreview http:/oormmmidffeehcheee
Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. 2019. Synthetic Datasets for Neural Program Synthesis. https:
//openreview
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. 2018. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 6419 (2018), 1140 1144.
Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE, Journal of Machine Learning Research 9 (2008),
Peter West, Chandra Bhagavatula, Jack Hessel, Jena D. Hwang, Liwei Jiang, Ronan Le Bras, Ximing Lu, Sean Welleck, and Yejin Choi. 2021. Symbolie Knowledge Distillation: from General Language Models to Commonsense Models. (2021). arXiv:2110.0711 [cs.CL]
Yuhuai Wu, Markus Rabe, Wenda Li, Jimmy Ba, Roger Grosse, and Christian Szegedy, 2021. LIME: Learning Inductive Bias for Primitives of Mathematical Reasoning. https: //doi. 48550/ ARXIV ARXIV.210....... 06223
Maksym Zavershynskyi, Alexander Skidanov, and Illia Polosukhin. 2018. NAPS: Natural
Program Synthesis Datasct. CoRR Abss/1807.0111 (2018). arXiv:1807.08s 03168 http:
//arxiv.or .rgg httg//bs/180..031ee 03168
12

---

Published as a conference paper at ICLR 2023
A RELATED WORK
Until recently, much work in program synthesis is on Programming by Example (PBE) in Domain-Specific Languages (DSLs), where problems are specified by input-output pairs. This has proven useful in applications such as string manipulation [sce, e.g., the survey by Gulwani et al., 2017]. Like English descriptions, PBE is inherently ambiguous. Recent work on massive transformer based LMs [Chen et al., 2021; Schuster et al., 2021; Austin et al., 2021; Li et al., 2022] has enabled synthesis in general-purpose prograrnming languages like Python. Many works have studied data augmentation by synthesizing input-output examples le.g,, Balog et al., 2017: Shin et al., 2019; Alet et al., 2021; Li et al., 2022]. Other works have generated additional tests on top of human-written source code such as Roziere et al. [2021]. Bootstrapping has also boen studied in sxample-based program synthesis [e.g., Menon et al., 2013; Ellis et al., 2021]. However, these works do not consider the AI system itself generating new problems (with verified solutions) as in self-play. LMs such as Codex have been shown to be capable of generating largely-correct English programming problems [Sarsa et al., 2022]. However, human oversight is still required for vetting the descriptions and test cases, and thus their generated datasets are scall-scale and contain errors and ambiguities.
To facilitate evaluation, many related datasets of programming problems have been curated, including especially relevant standalonc programming challenges described in English and code IZavershynskyi et al., 2018; Hendrycks et al., 2021; Austin et al., 2021; Chen et al., 2021; Li et al., 2022]. Schuster et al. [2021] and similarly Li et al. [2022] make an important distinction between two lypes of programinng problems: those that only involve translation and those that require problem-solving Translation problems, such as "Add up all the odd numbers in array x," " require the LM to translate procedure from natural language to code. Problem-solving is required when the description does not state how to solve the problem. For example, "Find path of length at most 17 between nodes and 2 in graph x" conveys the problem to solve but not how to go about finding a path. Puzzles focus on problem-solving rather than translation.
In knowledge distillation [Hinton et al., 2015] a student model is trained to imitate the behavior of a teacher model on some data, and in the dala-free paradigm the training data itself is hetchetically generated. Related work on knowledge distillation can be found in the survey of Gou et al. [2021]. Recent work in problem solving Cobbe et al. [2021] and commonsense knowledge graphs West et al. [2021] has explored filtering language model outputs for quality during knowledge distillation using a neural filter. This shares the filtering aspect of our work, but given the ambiguity of their natural language task they can't 't evaluate correctness directly, unlike in the programming puzzle paradigm.
In NLP, various works have considered using data generated by one LM to improve another [Schick and Schütze, 2021; Meng et al., 2022]. Since there no interpreter to evaluate correctness of natural language, this is more like our ablation sowwweeg-diisillatioo study than self-play. Ribeiro and Lundberg [2022] use a
approach to NLP co-generation of datasets, where in some sense the humans can function in place of interpreter. In the self-play analogy, this would be like humans playing against an AI system as it learns, which still suffers from quality and effort limitations of humans.
In theorem- proving and math-problem solving, [Aygün et al., 2020; Wu et al., 2021; Polu and Sutskever, 2020] show potential value in learning to prove theorems or solve problems from synthetic math problems, though these theorems are not generated by LMs. In the game-play analogy, this is like training an Al system by having play against other types of bots rather than self-play, and it is unclear whether the goal of beating those bots will lead to improved general performance.
B BROADER IMPACT
The automation of writing code may enable software engineers to be more productive and produce higher value products for society. However, increasing software engineer's productivity does risk impacting the total number of software engineers needed, so substantial gains are made, care would need to be taken when releasing it. Also, automated
13

---

Published as a conference paper at ICLR 2023
software development has serious risks if bugs (e.g., security holes) that are common in the code samples used for training the LM will be reproduced in the LM's output. We refer readers to Chen et al. [2021] and Li et al. [2022] for extensive discussions of the broader implications of code generation.
The approach presented here focuses teaching the model to solve problem described in code. Although many natural language problems can be described as a programming puzzle that verifies solution, some problem descriptions are not easily translatable into code. Also training exclusively on Programming Puzzles would likely hurt the model's ability to understand natural language. The approach in this paper leverages a deterministic verifier, which isn't 't available in most problem domains outside code generation, so other approaches like Cobbe al. [2021] must. be used to enable successful filtering for LLM data generation in such domains.
While we do not have access to the data that these models were trained on, given their massive sizes it is possible that they include some Personally Identifiable Information. Despite care taken in their curation, it is also almost certain that they contain offensive content. One symplom of this is the fact that source code of the puzzles we generale contains occasional expletives, not present in P3.
C FURTHER DETAILS OF PUZZLE GENERATION AND SOLVING
Fig. 9 shows the prompt used to solve puzzles: the same prompt used (a) in P3 to solve the training puzzles, (b) to solve the generated puzzles, and (c) to solve the test puzzles. worth noting that. fewer than 1% of puzzles were duplicates. The fixed temperature of 0.9 from prior work [Schuster et al., 2021] was used in all puzzle-solving for generating fine-tuning data, where temperature of 0.8 was used for testing the fine-tuned model per Chen et al. [2021].
In solving puzzles, both synthetic puzzles and P3 puzzles, we use the same judging code from the P3 repository: Their evaluation identifies syntax errors and aborts infinite loops using timeouts. Their judge prevents some malicious instructions from being executed by automated code checks, though other judging systems perform full sand-boxing of the computation to prevent a generated code sample from doing harm like deleting files.
To test of whether puzzle is trivial or not, we check whether any of the following inputs makes it return True.
For int inputs, we lest the integers (-10, -9, -9,...,1000 100)..
For float inputs, we test [-100. 0, -10.0, -2.0, -1.0, -0.5, -0.1, 0.0, 0.1, 0.5, 1.0, 2.0, 10.0, 100.00 o].
For str inputs, we test ["cat", "dog", "aa", "ab", "foo", "bar", "baz", "].
For list inputs, we test lists of 0-3 items as follows. For lists of int, the items are {-3, 22... ......3), 3). For lists float, the items are [-1.0, -0.1, 0.0, 0.1, 0.5, 1.0, 2.0]. For lists of str, the items are ["a", "b", "foo", "bar", "baz"].
For lists of bool, the items are False.
All Boolean-input, puzzles are deemed trivial because they can be solved by the trivial algorithm that tries both inputs.
D FURTHER DIVERSITY ANALYSIS
In this section, we present a detailed diversity analysis. First, Figure 10 shows the embeddings of the puzzles after iteration 1 (a sample of 10K puzzles of the 25K generated puzzle-solution pairs) and the similar embeddings for iteration 2 (a sample of 10K puzzles out of the generated
'ee additionally set the PYTHONHASHSEED environment variable to 0 to make Python set functions deterministic.
14

---

def f2(s: str): Published as a conference paper at ICLR 2023
from typing import List
def fi(s: str):
return "Hello " "Hello world"
def g1()
return "world"
assert fi(g1))
return "Hello s[::-1] == "Hello world"
g20:
return [vorld[[:--1]
assert f2(g())
def 13(x: List(int]):
return lxn(x) = 2 and aum(x) ==
def g3():
return [1,
assert f3(g3()
def f4(s: List[strl): return len (set (s)) 1000 and all ((x. count x. count("b") and ('b x) for x in s)
def g4():
return (1*"* for range (1000)]
assert 1)(g(()
def f5(n: int):
return str(n n) .atartttttth ("12345688)))
def g5()
return (nnt (" ("123456789" "0"*9) 0.5)
assert f5(g5()
def f6(inds: List [int], "errin""Ssubbberisiinn"" return inds (inds)) and "" j..ji for in inds) "substring"
def g6(string "suussuusssssubbbbssssssn"g"""""
An example of the prompt used for solving puzzles, identical the "medium prompt" of P3 |Schuster et al., 2021, Figure C.3]. The first five example puzzles f1-f5 are always the same. The puzzle to be solved also provided in the prompt as f6, and the solution function signature is provided as g6.
Figure 9:
15

---

Published as a conference paper at ICLR 2023
1M puzzle-solution pairs), compared to the human-written puzzles and sample of 10K puzzles from the 1M Codex generated puzzle-solution pairs.
GPT-Neo 125M (iter) 1)
GPI--Neo 1.3B (iter 1)
GPTTNee 2.7B (iter 1)
P3 training puzzles
GPT-Neo 125M (iter2) 2)
GPT-Neo L.3B (iter 2)
GPT-Neo 2.7B (iter 2)
Codex
Figure 10: Expanded version of Figure 5 to include the same 2D embeddings of puzzles in sample 10K puzzles for the three 25K-puzzle datasets (top, after iteration 1) compared to the three IM-puzzle datasets (bottom, after iteration 2). Also repeated are the embeddings of the 155 training puzzles and sample of 10K puzzles from the 1M Codex-generated puzzles.
Figure 8 (left) presents an empirical measure of diversity, among the four 1M datasets, in which the puzzles generated by larger models more diverse. We later illustrate the embeddings of puzzles by showing puzzles from different chusters. Our diversity metric aims to capture the fact that there are many "kinds" of puzzles, and that the distribution over kinds should be diverse within a dataset. The metric depends on a the number of clusters C, which vary, shown in Fig. 8 (left)).
Our diversity metric is computed in two steps. First, we assign each the puzzles to one of C' clusters. To do this, used K-means clustering (from scikit-learn [Pedregosa et al., 2011], default parameters) to cluster the 2048D embeddings of the 397 P3 puzzles (puzzles only-not not including solutions) into C' clusters. As illustrated below, the clusters appear to be semantically meaningful.
Given any synthetic (or P3) puzzle, we assign to the cluster whose centroid is closest to the puzzles Codex embedding use the closest of the C' cluster centroids to assign a cluster. Sample assignments are also shown the end of this section.
Once we have assigned puzzles to cluster center, we compute the distribution over closest cluster center for the 10,000 puzzles the dataset, call it p; for cluster center The total number of puzzles is 10,000 for each dataset (except P3 which only has 397 puzzles). The results are illustrated below for clustering into 8 clusters, with random seed
Dataset
Cl. 1
CL.
2
Cl. 3
Cl. 4
Cl. 5
Cl.
CL. 7
Cl. 8
Entropy
P3
9
42
80
60
71
39
48
48
2.85
Codex
43
1,201
1,737
763
2,918
1,390
1,063
885
2.69
Neo-2.7B
8
1,017
1,375
430
3,149
1,728
864
1,429
2.60
Nco-1.30
1
862
706
303
3,019
2,748
1,763
598
2.45
Neo-125M 2
1,806
354
176
2,105
4,011
532
1,014
2.28
The counts can be normalized to be interpreted probability distribution over C' clusters, with pj being the fraction of puzzles closest to cluster centroid i. The metric is the entropy 1 of this distribution. We report this the four datascts, well as the original E, log p: P3 dataset. Note that if the K-means clustering created C identically-sized clusters, then
16

---

Published as a conference paper at ICLR 2023
this metric would be log C on P3, is reflected in the plot in Fig. 8 (Left). As hypothesized, the larger models generally produce puzzles with greater entropy across all values of C, indicating greater diversity of puzzles and more uniform coverage of the kinds of puzzles in P3.
We now illustrate puzzles from the first cluster of the C 8 clustering above. For each dataset, we show the three puzzles closest to its centroid. In P3, the first two puzzles are from the human_eval module.
# P3, puzzles closest to center of cluster def f fmatches: List [int], (O))
(matches, for i, (j, c) in enumerate (zithmathhes, parens)):
assert parens [j] != and matches [j] i and all(i matches [k] for range(i 1, j))
return len (matchees) len (parens))
def f (matches: List [int],
for in range (len (brackets)):
j matches [i]
brackets
assert [j] !- and matches [j] -- i and all (i matches [k] j for
in range + j))
return (en(tachea) len (brackets))
def f(t: str, ==")) (Ade) ) parens to (balance (O (O) (me! !ne!) (((()):
for in range (1en(t) + 1)
depth t[:i] count ("(") t[::).count"))) co)
assert depth
return depth and s in
# Codez, 3 puzzles closest to center of cluster 1: def f(s: str):
return (" in and ")" and count (") count(") and not i. startavith(")") and not e.endwwith("(() for in s.s))i(("()))
def f(s: str):
return s. cocut(("") s. count (") and "(" and ") (" not in
def (brackets: pairs=' 0 (<{(>>)));
assert len (brackketa) % 2 == 0 and all([t pairs for in brackets])
return brackets pairs[[:::
# Neo-2. 2.o-2.7B. 7B, 8 puzzles closest to center of cluster 1:
def f(s: str):
return s. count ("(") and count (" (")
def f(s: str):
return count (") >= 2 and len(s) > 5 or s. count("5") >= 3 and s. count (*6") >=
def f(s: str):
return counto ("+") or s. count ")) or count ("/") or s. count ("*") or s.
count("\n") == 0) and all(s[i:i+len(s)
in for i in range()en(s)))
# 1.0-1.3B, 8 puzzles closest to center of cluster 1: def f f(s: str, i=0, length=5):
for i in range(5).
if s[-i] a[-i 1] "" ...joon(((i:ireenghh) for i in range length)):
break return len(s) - length # assert length + len(s) - len(s)
def f str):
17

---

Published as a conference paper at ICLR 2023
s.replacee" ", "") "repace(" (",, "") "replace(()) "") "").replace"""", "") "*)sstrip return s. count ("5")
def f(s: str):
return [ in and a. count("""))
# Neo-125M, 3 puzzles closest to center of cluster 1:
def f(s: str):
return count ("") len(")) != len(s) len(s) >= len(")) and len(s) >= l
") or len(s) len(") <= (en(s)
def fs: str, charg=['o', 'h', 'e', '1', ', 'w', " r', (d for i in range (len(s) 1); for assert c in return True
def f(s: str, si-"a", s2-"b", count-6)
return count (s1) count sum count ("8") and sum(s) s2)
E FURTHER COMPARISON BETWEEN SYNTHETIC AND TRAINING PUZZLES
This section provides more detailed comparison of synthetic and training puzzles. First, we compare the distance between each synthetic puzzle and its closest (rain and lest puzzles. Distances are compuled using the aforementioned OpenAI Codex API's code embedding in 2,048 dimensions, on the same sample of 10,000 puzzles for each dataset. Since the API's code embeddings are conveniently unit vectors (length 1), this means that d2 2(1 -)s s) where is the distance between two puzzles and s is their cosine similarity, becanse for any unit vectors u, u:
||u u11 = 2 2(u v) = cos(,(u, e)).
Thus the findings below reported in distance could equivalently be translated to cosine similarity.
Figure 8 (right) in the body of the paper show histograms depicting the distance distributions in two of the four 1-million puzzle datasets, the smallest and largest Neo models. Histograms for the other models and other iterations these datasets, including both iteration and iteration 2 for the Neo models and the puzzles generated in our unverified Codex dataset. To give sense of puzzle distances, Figure 12 illustrate with examples of puzzles from the 2.7B dataset and their nearest: training puzzles.
similar. Table 2 shows the averages across
Second, Figure 11 compare the length of the puzzles in terms of the number of nodes in their abstract syntax tree. The human generated puzzles tend to be significantly longer. A major effect here that the unsolved syuthetic puzzles were excluded, and longer puzzles are harder to solve. This can be seen clearly in the difference between the Codex verified and unverifidd
Model
Avg dist? train
Avg dist? test Difference
Neo 125M
0.249
0.302
0.053
Neo 1.3B
0.280
0.303
0.022
Neo 2.7B
0.285
0.307
0.022
Codex
0.295
0.314
0.019
Covex-unvrrfiod
0.298
0.313
0.015
Table 2: The mean squared distance (in embedding space) between puzzles in each datasel and the P3 train and test. sets. small amount of "overfitting" is observed that puzzles are bit closer to the training set than the test set, with more overfitting is (greater difference column) observed for smaller puzzles. The numbers in each column are for samples from the 1M puzzle datascts.
18

---

Published as a conference paper at ICLR 2023
Number of nodes in AST tree
10a
Neo 125M
Neo 1.3B
Neo 2.7B
Codex
Codex-unverified
train
Figure 11: Box plots showing the distribution of puzzle sizes (y-axis, as measured by the number of nodes in the Python AST, log scale), across the 1M puzzle datasets and the training puzzles. The verified synthetic puzzles are shorter because puzzles with no solutions were omitted, and longer puzzles are more likely to have solutions.
puzzles, with longer puzzles for the unverified puzzles (in which unsolved synthetic puzzles were not excluded). Additionally, the Codex sovler is significantly larger and more powerful than the GPT-Neo models, which means that harder longer puzzles would be filtered less often.
F FURTHER EXAMPLES OF GENERATED PUZZLES
hand examination was performed on a subset the generated puzzles, where we attempted to understand how the puzzles may originate. We found several concepts repeated from the training, other human concepts such as days of the week, and other puzzles that appear to be derived from programming challenges misused, such as the perimeter a triangle being confused with its side. Additionally input variables sometimes unused, puzzles did not test what they appeared like they should test because of certain issues they contained. Finally, comments were sometimes generated of varying quality.
the web. We found many human concepts
For several puzzles, we attempted to delve deeper to understand the origin for the puzzle. For instance, f2 from Fig. 1 seems similar in spirit (but not identical) to several of the training problems. Here is a P3 training problem that is somewhat related:
def train str, substrings= [ ['oo"', 'bar', 'baz return all (sub in and sub[::-11 in for sub in substrings)
Both involve testing palindromes and substrings.
More surprisingly, the following sophistieated problem generated:
def f (n: int, target=20151120)-
assert 0 <= <= 1e14
next lambda x: (x 252533) 33554393
seen set ()
now 20151120
while not in seen: seen. add (now)
next (now)
19

---

Published as a conference paper at ICLR 2023
# Squared distance: 0.049
# Synthetic puzzle: def f {stampa: List [int], target=80, _ax_saam options= [10, 32, 50, 30, 41, 70, 45, 23, 100, 2, 38]): for in stampa: assert s in options return (sttmsam <= max_stamps and sum(stamps) target
# Closest training puzzle: def f fsstapps: List [int], target=80, max max_staa stamps-4, options- [10, 32, 81):
for in stamps: assert in options
return 1en (stamps) max_stamps and sum (smtmmaps) target
# Squared distance: 0.246
# Synthetic puzzle: def f(s: str, strings-("sande ("aadd,, "water", "fish", "sun"), n-4): return s in strings and (ee(
# Closest training puzzle:
def f(s: str, parings=['catt: 'dog', 'bird', Ifly', 'moose' I)): return S in strings and sum(t s for t in strings)
# Squered distance: 0.275
# Synthetic puzzle: def f(: str, "azer""dabcbaacbaae"") assert len(s) >= len(target)
return len (set (s)) = (en (ttrrget))) and a11 == target[x] for x in range len(s))
# Closest training puzzle: def f(t: str, s="abbbcabbac", target=7);
i 1-0
for in
while s[il:
+
+= 1
return len(t) >= target and at][t[i] I= t[i + 1] for i in range (len(t) 1))
# Squared distance: 0.306
# Synthetic puzzle: def f (string: str): for in ["hey", "cool", "what", "you", "ok", "keep"]:
if in string:
return True
return False
# Closest training puzzle: def f(a: str, chars=['o', 'h', 'e', '1', ", Iw' 121, 'r', 'd')): for in chars: if c not in 8: return False
return True
Figure 12: Puzzles from the Codex 1M dataset and their distance to the nearest training example. In this first pair, the only difference is the options input list. That was the closest. pair in the entire dataset. Only a 0.003 fraction of the puzzles have squared distance < 0.1.
20

---

Published as a conference paper at ICLR 2023
if target: return n 0
-
return False next lambda (x * 252533) % 33554393
now = 20151120
n 0
while next (now) != target:
now next (now)
return n
This problem requires computing discrete log. While the discrete log problem is notoriously difficult and is the basis of numerous cryptography systems, the number is small enough that it can be solved by a simple loop. The P3 dataset does contain discrete log problem but is in the test set. While we could not find the exact code above, the problem itself does appear to be equivalent to the English challenge stated on this programming challenge website: https:/ //a/v/vvvtoofoooooooo code. com wtt.ccocmmc///eeccc 2015/day/25. It is still unclear how exactly the system generated this code.
The following puzzle asks for list of triangles of perimeter 5, but uses the variable name side, suggesting that may understand the difference between perimeter and side. The puzzle has an additional constraint which is clearly poor programming as it refers to undefined variables al and a2. Consequently, solving this requires finding list of a single triangle of perimeter 5, such as [[2,2,1].
def f(ss: List [intl] a-24, b-16, e424, target=None, side=5): for a, b, in 1s:
assert a <= side and b <= side and <= side and a + b + c == side, "Invalid triangle"
if not target:
target 1s[-1]
def legal_move (m)
(a, b, c), (i, J. k)
and a and a2) or a2 a return ((a side or al and a != +
a1, a2, a3 = target (zsp 1s(1:]))
return all [1ogaal_move
move(m) for in moves)
return c] for in range(side+1) for in r1) for c in range(side-a-bt1) if a b + c == side and (a == side
== b c)]
Several puzzles included concepts (like vowels) and specific strings (like the famous pangram below) that appeared in the training data.
def f(:: str, z-"The quick brown fox jumps over the lazy dog", n-2): return w. count ("a") c.count""e") voooun(("i") w. count o*)") + w. count count("ul ("u") -- and in z and w !-
Many puzzles were not particularly interesting such as the below, which involve finding string of given length containing given substring, and finding a list of 21 numbers between 1-9 that sum to 100.
def f(s: str, t="rrme", length-14);
return len(s) == length == len (set (p.er ())) and upper () in upper ()
21

---

Published as a conference paper at ICLR 2023
def fli: List(int]): return (en(li) and all(i in for range(1, 10)) and sum (11) 100
Other puzzles involved very human-like strings:
def f fm: str):
assert i.startssiit("Helll Salif") assert "But, but.... in m assert m. endewwiith ("You' rre great!")
return (mn(m) = 282
def g0:
return "Hello, Salif. But, but... friend ever said hello to me, wonder where are you from? A freaky fellow? Are you from a freaky galaxy?" + or are from a freaky universe or freaky planet? The answer is no: I'm megalomaniac!"
know because don't translate meaning. You're re great!"
Other puzzles involved human concepts such as the day of week which did not appear the training data:
def (days: List [strl, x="tue", k=3, n=4): nums ("mon": 0, "tue": 1, "wed": 2, "thu": 3, "fri": 4, "sat": 5, "sun": 6}
numx = nums [x]
return (len (days)) <= k and (n len (set (days)) * (1 (n 1) // // 2 and numx != nums [days [n // 2]] and numx nume [days [o]] and numx nums [-y3[- # right half of week is weekdays
x) and numx
[ay//:n//2] # left half of week is weekends
The comments that generated sometimes useful and sometimes incorrect..
G FURTHER EXPERIMENTS ON CODEX DATA
Figures 13, 14, 15, and 16 show further results when fine-tuning GPT-Neo on the Codex- generated data. Fig. 14 compares our results to the Codex model on our test set, after varying number of epochs of fine-tuning. The Davinci model outperforms the much smaller Neo models. Second, one might expect that fine-tuned models could learn in zero-shot manner. We tested this hypothesis, but, as in Fig. 15, the fine-tuned models benefit from few-shot learning. Even after extensive fine-tuning on the puzzle problem format for over 1 billion tokens, the LM still performed better when prompted with the five examples of puzzles/ /solutions to prime the model. Third, we performed a temperature sweep to test the sensitivity to temperature, as shown in Fig. 16.
40%
405
47%
35.
35%
35%
30%
30%
35%
25%
25%
25%
20%
20%
22%
15%
15%
53%
10%
10%
226
5%
59
0%
76
(a) GPT-Neo 125M Model
(b) GPT-Noo 1.3B Model
(c) GPT-Neo 2.7B Model
Figure 13: Pass@k for the three Neo models showing the results of fine-tuning the unverified and verified data generated by Codex. Data verified correct by the Python interpreter improved accuracy significantly more.
22

---

Published as a conference paper at ICLR 2023
87%
375
5076
73%
725
717
62%
072
1075
93%
975
42%
47%
33%
57%
25%
52%
-Dwird --Calman -2.0 -1100 -1220
-Dcerd -Exstean -2/8 -1.0 12M
Deend -Cotmmmn .27 1.33 225M
(a) Baseline no fine-tuning
(b) After epoch
(c) After 10 epochs
Figure 14: Pass@k for the Neo models during fine-tuning, shown comparison to the Codex models which we were not able to fine-tune (Davinci is 175B, Cushman is 12B in size). Our prompts match the medium prompt style used for baselines in Schuster et al. [2021]. The Neo models were fine-tuned on the 1 million verified puzzles generated by Codex.
50%
50%
50%
havgrce
30%
Rayub
30%
90%
20%
10%
10%
10%
10
11
Epocts of Finsuning
Epriche of Finetuniing
Epochs of Finctuning
--Fow Zoro
(a) GPT-Neo 125M
(b) GPT-Neo 1.3B
(c) GPT-Neo 2.7B
Figure 15: Few-shot vs. zero-shot and fine-tuning epochs. Across all 3 model sizes, testing Neo in few-shot beats zero-shot significantly even after 11 epochs fine-tuning which over 1 billion tokens of Codex Codex-generated generated penzzleproblem/sohuee solution pairs. The LM still benefits from providing the P3 tutorial puzzle prompt..
Puzzle Type
Puzzle Count
Normalized Baseline
Normalized Finetuned
human eval
150
1.04
5.23
user study
15
1.85
6.60
trivial inverse
12
1.34
8.47
classic
11
0.19
0.91
codeforces
1.21
4.90
hother)
31
0.54
2.72
(all)
228
1.00
4.95
Table 3: In the table above show the Pass 100 accuracy the baseline model and the finetuned model for the different domains. The pass rates are normalized by the average Pass@100 (00 for the bascline. The overall test performance improved by 4.95 factor. The improvement in pass rates from finetuning is the ratio of the two columnss.
35%
10%
15%
20%
10%
12%
66
5%
5%
0%
0%
0%
02
0.4
0.6
0.8
12
14
1.5
0.2
0A
0.5
0.8
3
3,2
1.4
3,5
0.
044
0.6
2.5
3
3.1
5A
1.
Sohe lomprrature
Solv Terpertture
Solve Tongrrature
Sendine
- Unsenfad
Werfee
Bosfre -ireanniee Varifel
Beudin
Uisanifad Werffed
GPT-Neo 125M
(b) GPT-Neo 1.3B
(c) GPT-Neo 2.7B
Figure 16: Temperature controls the amount of diversity in the code solutions generated by Neo. All experiments in our paper were done with a fixed temperature 0.8, based on the recommendation for Pass@100 in Chen et. al. [2021]. A hyper-parameler sweep temperature across all model sizes verified that. 0.8 was also optimal for our model and dataset at a 0.2 search step size for maximizing @ 100 which is the percentage of problems solved at least once with 100 generated code solutions per problem. Neo was fine tuned for 1 epoch (f-92 million tokens) in these graphs.
23


Reviews:
[{"review_id": "djWiwtxArL3", "reviewer": "Reviewer_qoTN", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a method to improve a language model's (LMs) ability to generate programming puzzles. The primary contribution of the paper is algorithmic. Other contributions include the creation of an open-sourced large set of programming puzzles as well as experiments demonstrating the benefits of self-play (where a LM generates puzzles and then fine-tunes on them for improved test-set performance).", "summary_of_the_review": "The paper tackles an interesting and important problem. Ideas are mostly clear and experiments show improvements. Some aspects (algorithmic novelty, program space of $f$) need clarification which are reflected in my scores (and open to revision depending on author feedback).", "strength_and_weaknesses": "Strengths\n  * The paper investigates an interesting and important problem involving LMs. Techniques for improving LM code-gen performance without significant labeling effort will have broad impact.\n  * The paper is well written. The main ideas (e.g., prompt setup) of the paper are described carefully with illustrative examples. I enjoyed reading the paper.\n  * The main algorithmic ideas are intuitively clear. The paper is technically sound.\n  * The experiments demonstrate the utility of the main algorithmic ideas (generation, verificationnn, fine-tuning) on the test set puzzles.\n\nWeaknesses\n  - A more detailed characterization of the program space representable by $f$ would be appreciated. It seems like f is a large subset (if not all) of Python but I'm not sure.\n  - The paper could better identify the novel algorithmic contributions. For example, is the prompt generation idea novel?\n  - While the paper does some analysis of the generated data via embeddings and UMAP, I would have liked to see a more detailed analysis and discussion of the generated puzzles. For example, how similar or different are they to the P3 train and test sets? Any overlaps?\n  - Although Figure 7 makes it clear that fine-tuning has plateaued, it is not clear why. A deeper analysis of this in conjunction with the analysis of the generated puzzles would have been nice (but outside the scope of the paper). Overall, this seems like an important line of work as the paper states and leaves for future work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "73C2ZBuj6q", "reviewer": "Reviewer_bB2P", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to perform data bootstrapping by using a performant language model generate prompts that specify puzzles and finetune models such data (after filtering for correctness). ", "summary_of_the_review": "Overall, this is a nice method where the performance on the data bootstrapping method is quite expected. For completeness, the paper can push a bit further on studying the general code generation abilities after finetuning of puzzles, as described in the section above.", "strength_and_weaknesses": "Pros:\nThis method has some potential to augment data in order to improve model's general code understanding, generation and reasoning abilities. It is however similar to what Codex paper describes in their data generation process based on filtering with integration tests. However, this work focuses on puzzles.\n\nQuestions:\n- The format of such puzzles are quite specific. That is, it expects f(.) and g(.) such that f(g(x)) returns True. This format can also be simplified since g() seems to take no argument and returns a value. The simplified format can be 'assert f(' as prompt, then ask the model to generate the actual values. Or is the f(g(x)) format used for something more general? The paper shows a general function f that takes multiple arguments in Figure 3. Are the extra arguments simply ways to take in values? \n\nCons:\n- The experiments can be a bit more thorough. It makes sense that if we finetune on such puzzles, the performance on a held-out set of puzzles will be improved. While it is valid to focus on such puzzle generation as one of the tasks for evaluation, a more important question is whether it translates to general coding abilities. \n- A better experiment setup is to perform data bootstrapping; that is, we can generate samples and verify, then finetune on the puzzles, then measure the performance on the general code generation benchmarks such as HumanEval or MBPP. \n- What of type guardrails are used to detect that the puzzles are not trivial? For example, if the function looks complicated but due to some reason it always goes to the branch that returns true, then any function g() would solve such puzzle.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6zAQ8BkcCf", "reviewer": "Reviewer_cLPb", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Authors propose using LMs to generate programming problems and solutions. These synthetic problems and solutions then are used to fine tune LMs for program generation task. This approach leads to improved test accuracy in program generation task. ", "summary_of_the_review": "I believe the work presented here is useful for improving language model ability to generate programs. It seems to be novel, and it achieves marked improvements when used to fine tune LMs. There is a reasonable expectation that this research could improve state of the art results and also be applied in further advancing language model-based program generation. I recommend accepting this paper.", "strength_and_weaknesses": "Strengths:\n\n- A novel approach to improve LM-based program generation by first generating synthetic problems and solutions and then finetuning LMs on the generated problems.\n- Highly improved test results\n- Ablation studies of model and interpreter distillation\n\nWeaknesses:\n\n- Authors cannot finetune Codex and therefore there are no results for using the authors' approach to improve state of the art results for the problem. See Figure 12 for the gap of the Neo models even with fine tuning vs Codex models. It is possible (likely?) that Codex models will benefit from finetuning using the additional synthetic problems/solutions, but we don't know for sure. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6QxBAHe0V-u", "reviewer": "Reviewer_t8tu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper argues that programming puzzles and their machine verified solutions generated by a Language Model (LM)  can be used to improve the performance of the same LM. It presents a “data generation pipeline” where puzzles for a training set are used as a prompt for the LM to generate new puzzles that complete the prompt. A filtered set of the generated puzzles are used as parts of another prompt for the LM to generate solutions for those puzzles. The generated puzzle-solution pairs are then verified to create a larger training set. Evaluation results show that GPT Neo models fine-tuned with this larger dataset provide improved results measured using the Pass@k metric.\n", "summary_of_the_review": "This work explores a potentially effective idea of improving language models for code. The proposed solution seems effective at improving models performance at python based programming puzzle task. However, the proposed data generation pipeline lacks  some details (e.g., determining number and quality of the generated samples, selection of fine-tuned LM in each iteration ). Also, the evaluation could be more informative if accuracy across the domain of problems are discussed. ", "strength_and_weaknesses": "Strength\n\n- This work explores an interesting concept of using ‘self-play’-like strategy to improve language models for code generation and leverages existing work on programming puzzles to propose a method to demonstrate the effectiveness of the idea.\n- Dataset of 1M synthetic puzzles shared by this work could potentially help future research along this direction.\n\nWeakness\n\n- The data generation pipeline does not specify when to stop generating puzzles or solutions in a single iteration. During evaluation 2 iterations are used for Neo-models and 1 for Codex (due to fine-tuning limitations). The overall approach seems adhoc. How to determine the quality of generated puzzles?\n- It would be interesting to see if the performance improvements are tied to specific domains of problem.  This would also reflect on the generalizability of the proposed approach over problem instances.\n- “In each of the n iterations, the same LM is used for both generation and fine-tuning” -  is the fine-tuned version replaces the base version in each iterations (i.e., is fine-tuned version always expected to be better in each iteration?)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster