ACES: Generating a Diversity of Challenging Programming Puzzles with Autotelic Generative Models
Authors: Julien Pourcel
Cédric Colas
Gaia Molinaro
Pierre-Yves Oudeyer
Laetitia Teodorescu
Venue: NeurIPS 2024 spotlight (2024)
Keywords: diversity search
code generation
quality-diversity
open-endedness
generative models
evolutionary algorithms
code models
Primary area: generative_models
TL;DR: We introduce a new open-ended algorithm to automate the generation of diverse and challenging programming puzzles to evaluate LLM-based problem solvers.

Abstract: The ability to invent novel and interesting problems is a remarkable feature of human intelligence that drives innovation, art, and science. We propose a method that aims to automate this process by harnessing the power of state-of-the-art generative models to produce a diversity of challenging yet solvable problems, here in the context of Python programming puzzles. Inspired by the intrinsically motivated literature, Autotelic CodE Search (ACES) jointly optimizes for the diversity and difficulty of generated problems. We represent problems in a space of LLM-generated semantic descriptors describing the programming skills required to solve them (e.g. string manipulation, dynamic programming, etc.) and measure their difficulty empirically as a linearly decreasing function of the success rate of \textit{Llama-3-70B}, a state-of-the-art LLM problem solver. ACES iteratively prompts a large language model to generate difficult problems achieving a diversity of target semantic descriptors (goal-directed exploration) using previously generated problems as in-context examples. ACES generates problems that are more diverse and more challenging than problems produced by baseline methods and three times more challenging than problems found in existing Python programming benchmarks on average across 11 state-of-the-art code LLMs.

Generating a Diversity of Challenging Programming Puzzles with Autotelic Generative Models
Julien Pourcel, Inria
Cédric Colas MIT, Inria
Gaia Molinaro
University of California, Berkeley
Pierre- Oudeyer Inria
Laetitia Teodorescu Inria
Abstract
The ability to invent novel and interesting problems remarkable feature of human intelligence that drives innovation, art, and science. We propose method that aims to automate this process by harnessing the power of state-of-the-art generative models to produce a diversity of challenging yet solvable problems, here in the context Python programming puzzles. Inspired by the intrinsically motivated literature, Autotelic CodE Search (ACES) jointly optimizes for the diversity and difficulty of generated problems. We represent problems in a space LLM-generater semantic descriptors describing the programming skills required to solve them (c.g. string manipulation, dynamic programming. etc.) and measure their difficulty empirically Llama-3-708, a state-of-the-art LLM problem solver. ACES iteratively prompts large language model to generate difficult problems achieving diversity of target semantic descriptors (goal-directed exploration) using previously generated problems as in-context examples. ACES generates problems that are diverse and more challenging than problems produced by baseline methods and three times more challenging than problems found in existing Python programming benchmarks on average across 11 state-of-te state-of-the-ars ofe-the-rt art code LLMs.
linearly decreasing function of the success rate of
Introduction
Humans not only talented problem solvers, they are first of all remarkable problem generators generating endless streams of new problems for themselves and others Chu and Schulz [2020], Molinaro and Collins [2023]. We set build problems for others learn, challenges ourselves, [Burton and Hiron, 2008), aggregate problems to train and test Al models [Hendrycks et al., 2020, Chen et al., 2021], and come up with new problems that drive innovation in and science [Gromov, 2018, Chu et al., 2024]. This intrinsic drive to generate problems for oneself - the autotelic property- has further been argued drive the capacity for adaptation and open-ended learning in both human [Chu and Schulz, 2020] and machines [Schmidhuber, 2013, Herrmann et al., 2022, Colas et al., 2022]. Automating this -eeeeeetnnnatiion process would have numerous positive applications: for instance, designing exercises tailored to optimize the learning experience of every human or machine learner (automatic curriculum learning Portelas et [2020]); or facilitating the generation of evaluation protocols (human tests, machine learning benchmarks). It would provide the necessary curriculum for open-ended learning machines [Colas al., 2022] and may key component of automated scientific discovery [Grizou et al., 2020, Etcheverry, 2023].
We propose leverage machine learning - set of tools usually targeted solving problems- automate the generation of diverse set of interesting problems, here in the domain of Python programming puzzles. Programming puzzles indeed represent an open-ended space of problems to
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

somple target cell D. 2)
Generator prompt
Solver proupt
Puzzle solver (LMM
solutions
Tour roke is to create nee
Your role Is to geserate sola- tiona the folloving puzzia:
pazzle with dkills [1, 2]
diffiiuuity
Puzzle generctor (LLM)
der rit, enttrat", *tar3): return lencs(s])
difficulty:
set glentreatt, "eart):
retarn [lonte) for in a3. Lndlex22
return len(s)
def gC::
puzzic
return U. 23
X
def g(entreatt, "rai'>: return Ion(s)
difficulty -
puzzle archive
Fifficuity 21.2
rts, anfeast, betat):
Labeler prompt
g(an("cat", "eat")): return ('aa"
st13 tetat))
now puzzle according to sidll combination [1, 183
rote tell wnich skills required in solu-
(59 solutions total)
lng:
Puzzle labeler (LMM
cef ftl, se("eat", "car"): reture 1entat13) en 3) def sfs-l"eee", "ca"33s
18: Armyy Lecexing
puzzio, solution pair
lobels
oprations
return i. k.tndeo("raa") (ear")
Figure I: Overview of the ACES algorithm. ACES iteratively generates a diverse set of challenging programming puzzles. First, a target cell corresponding to a combination of programming skills is sampled from a puzzle archive (1), and puzzles from filled neighboring cells - prioritized by difficulty - are selected as examples and given to a puzzle generating LLM. It generates a new puzzle with the desired skill combination that LLM solver tries to solve 50 times (2). If never solved, the puzzle discarded. An LLM describes the skills needed to solve the puzzle (3) and the puzzle, along with its computed difficulty score, is added to the puzzle archive.
explore: from simple string manipulations to complex dynamic programming or open mathematical puzzles [Schuster et al., 2021]. We qualify problems as interesting when they are challenging yet solvable. This can be estimated by computing the empirical difficulty of puzzle for particular solver: out of 50 attempts, the solver should solve the problem least once (solvability) but as rarely as possible (difficulty). In contrast with natural language instruction domains, our puzzle domain lets us objectively check the validity of given solution by simply running a Python interpreter. This domain thus affords both an open-ended space to explore (diversity search) and an objective quality measure to maximize.
The standard approach for problem generation simply queries pretrained generative models with few-shot examples or specific instructions [Haluptzok et al., 2022, Honovich et al., 2023, Gunasekar et al., 2023]. This amounts to sampling from a stationary distribution such that the quality and novelty of generated problems reflect those of the problems found in the training data, Instead, we introduce Autotelic CodE Search (ACES), an autotelic generative model that steers pretrained generative models to produce a diversity of challenging puzzles by iteratively reusing previously generated puzzles as examples to guide the production of newer and harder problems.
ACES builds on Map-Elites [Mouret and Clune, 2015]. an evolutionary quality- (QD) method [Pugh et al.. 2016]. In all QD algorithms, the user first needs to define a descriptor function mapping each generated outcome (here, each problem) to a numerical representation that will be used to measure diversity. Programming puzzles are nigh-dimensional objects that we chose to represent by the set of programming skills required to solve them high-level semantic description space that better captures intuitive notions of puzzle diversity than pretrained embedding representations. We obtain these by asking large language model (LLM) to label each problem set of skills from a list of 20 possible ones. Just like Map-Elites, ACES maintains archive of generated outcomes grouped by skill sets (descriptor niches) and optimizes quality (here difficulty) locally within each niche. While Map-Flites randomly mutates solutions sampled from the archive in hopes of discovering a new niche or finding higher-performe
solutions, ACES performs an explicit goal dir--iiee exploration [Colas et al., 2022]. At each iteration, ACES targets goal descriptor, carefully selects relevant and challenging example problems from the archive and, conditioned on these, prompts an LLM to generate more difffcuut problem-solution pair achieving the goal. The new puzzle is labelled, evaluated and, if valid, is added to its corresponding descriptor niche in the archive. Across iterations, the archive gets filled with more diverse and challenging puzzles which provide higher quality examples to guide the generation of yet more diverse and challenging puzzles (see Figure 1).
We show that ACES generates a wider diversity of more challenging problems than both standard generative approaches [Haluptzok et al., 2022, Honovich et al., 2023] and existing algorithms based on Map-Elites [Bradley et al., 2023a]. Finally, we show that generated problems harder to solve
2

---

than those found in existing Python programming benchmarks, this for all the 11 state-of-the-ee LLM-bassd problem solvers we tested. Whereas the HumanEval+ benchmark is starting to saturate (GPT-4-lurbo achieves pass@1 of 86.6%, CodeQwen/.55 /.5-7B- CB-Chhl 78.7%, [Liu et al., 2024j)', the best solver (Mixtral-8x222 8x22B-Instruct-- /) only achieves a pass of 47.3% on our problems. This work paves the way for automating the design of harder benchmarks whose difficulty is calibrated using LLM solvers themselves, eventually allowing evaluations to increase in difficulty as models improve.
2 Related Work
Open-ended exploration algorithms Our puzzle-generating method is the intersection of two research lines: evolutionary computing [Lehman and Stanley, 201 la,b, Mouret and Clune, 2015, Pugh et al., 2016, Cully and Demiris, 2018a, Lehman et al., 2022] and intrinsically-motvval learning [Baranes and Oudeyer, 2013, Etcheverry et al., 2020, Forestier et al., 2022, Colas et al., 2022]. Beginning with novelty search [Lehman and Stanley, 201 Ia,c], the evolutionary approach to exploration expanded with the invention of quality-diversity algorithmss [QD: Lehman and Stanley, lb, Mouret and Clune, 2015, Cully and Demiris, 2018a], a set of methods striving to evolve a diverse population of perfooaaprf solutions via the undirected mutation of existing solutions. A parallel line research introduced goal-directed exploration processes, also called autotelic learning, where agents learn represent and sample their own goal as a way to direct the diversity search [Baranes and Oudeyer, 2013, Forestier et al., 2022, Colas et al., 2022]. Although autotelic methods were first developed model the open-ended development of children in skill learning robots Baranes and Oudeyer [2013], Moulin-Frier et al. [2014], Oudeyer and Smith [2016], they also proved effective in the automatic exploration of complex systems, either simulated [Reinke al., 2019, Etcheverry et al., 2020] or physical [Grizou et al., 2020].
LLM-augmented exploration LLMs can be useful in various parts of quality-diversse and explo- ration algorithms. Their capacity to generate appropriate variations of existing text has been used to implement mutation [ELM: Lehman et al., 2022] and crossover [Meyerson et al., 2023] operators within QD, with applications to neural architecture search [Chen et al., 2023, Nasir et al., 2023]. Following the recent trend in learning from AI feedback [Bai et al., 2022, Lee al., 2023] and using LLM-as-judge methods [Zheng et al., 2024]. recent work has used LLM responses as models of interestingness [Zhang et al., 2023, Klissarov al., 2023, Sachdeva et al., 2024] within RL, while others have augmented Map-Elites with LLM-based quality judgments and semantic descriptors for creative writing [Bradley et al., 2023b] or adversarial prompt generation [Samvelyan al., 2024]. These last two are close to our ELM baseline, but in contrast to these works we use a grounded empirical difficulty metric as quality compared to AI feedback which is less grounded and might be innacurate. ACES additionally uses LLM LLM-augmented goal generation, which echoes recent methods leveraging generative models for open- goal-bases exploration [Colas et al., 2023, Wang et al., 2023a, Du et al., 2023]. In contrast to these works we optimize for both the difficulty and the diversity of the generated puzzles.
LLMs for generating code and instruction datasets This work is also linked to prior approaches for generating synthetic code and instruction data, mostly in data augmentation contexts. Seminal works leveraged a standard generative approach by prompting an LLM to generate new problems using as few-shot examples problems sampled from an existing dataset [Haluptzok et al., 2022, Honovich et al., 2023, Roziere et al., 2023], or problems generated at previous iterations [Wang et al., 2023b]. Closer to the goal- toal-targeting of ACES, Eldan and Li [2023] generates diverse training data by asking an LLM to write stories employing combinations of words randomly sampled from large list. Gunasekar et al. [2023], Abdin et al. [2024] build upon this approach to generate programming textbooks by mixing subjects and audiences, and generates exercises by randomizing the exercise name. Evol-Instruct is an evolutionary method that iteratively generates language or code instructions by applying prompts that modify previously generated problems by, among other things, increasing their difficulty [Xu et al., 2023, Luo et al., 2023]. They do not optimize for diversity and do not use actual difficulty measurements, relying on the LLM's problem modification to increase it. Finally, Skill-Mix (Yu et al., 2023] generates language evaluations for LLMs by generating problems involving combinations of skills in the language domain and grading models using GPT-4; they do not use
hhtps://eeallplss wwwpsiiggttbbbbhdbeeeeeeeeeeeeee html
3

---

def Elss: List [str])
"""Divide the decimal representation of 8 into strings of length eight. "*"
return "" jo.) (8**88) and all (s) for in 1s) def g(:
return [8 [1:1+8] for in range (0, 80, 8)
assert (() - True
Figure 2: Puzzle example. A simple programming puzzle and its solution from the P3 dataset [Schus- ter et al., 2021]. A solution function g must return valid solution such that f (g ()) = True.
any few-shot examples, do not optimize measure difficulty for LLM while generating their problems.
Methods
3.1
Programming puzzles and the P3 dataset
The Python Programming Puzzles dataset (P3) contains 1715 puzzle-solution pairs where each puzzle is defined by short test program f designed verify the validity of solution programs g such that valid solutions satisfy (g) == True when run in an interpreter, see example in Figure [Schuster al., 2021]. P3 puzzles span problems of various difficulties that involve different programming skills: from classic problems (tower of Hanoi) and string manipulations, to factoring problems, dynamic programming. or even open problems in computer science or mathematics. The P3 dataset is split into training and testing datasets (N 636 and 1079 respectively). Both datasets are pre-filtered to examples shorter than 1024 tokens to accommodate for limited context windows in LLMss.
3.2 Generating diverse sets of challenging puzzles
In this work, we aim to generate of puzzles that are collectively diverse and on average as difficult as possible. In this section, we first define the difficulty metric we use, and then how we quantify diversity.
Empirical puzzle difficulty We measure the empirical difficulty a puzzle with respect to a target LLM solver the opposite of the solver's competence on that puzzle. We measure competence using the standard pass@k k metric with k=l: the number of valid solutions generated after k=l attempts (which simply the success rate) [Chen et al., 2021]. We estimate the pass @ competence N = 50 solving attempts and report the empirical difficulty (puzzle fitness F) as its negative success rate rescaled the 0-100 range:
(-- (- pass@ (f,,LLM) + 1) x 100 pass @1 o F(f) = (-o0 otherwise
(1)
The more difficult the puzzle is, the higher its fitness. Puzzles for which no solution is found are considered invalid and are discarded. The prompt used for generating solutions can be found in the Appendix. Compared LLM-based methods of assessing the quality of sample (typically, critic or LLM-as Ludgee methods), this difficulty-based metric measures ground-truth objective: how hard a given puzzle for a target LLM solver. Our experiments found that this difficulty measure mostly transfers across models: a puzzle that is harder for one model is often harder for others (see Section 4.5). Although our difficulty metric is rather expensive to compute, it captures exactly the intended objective and is thus harder to hack or overfit compared to objectives based on L.M feedback [Zheng et al., 2024, Sachdeva et al., 2024]. This said, an existing possibility for hacking the difficulty metric is import random number generator library and to make the f function return True with probability I/50. We have not observed this phenomenon in our experiments.
Skill combination diversity The diversity measure we choose to optimize will have important impact on the distribution of generated puzzles. Ideally, the set puzzles should be diverse their structures and topics. We thus define set of 20 tags corresponding different programming skills

---

and label each programming puzzle with the combination of skills needed to solve it (reminiscent of Skill-Mix [Yu al., 2023]). We then measure semantic diversity as the number of unique skill combinations for which there is at least one representative in our generated set. We refer to a tag combination as niche or a cell the rest of the paper. We sample our 20 tags from a larger list generated by an L.M (GPT-4-0125) and validated against lists of programming topics covered in classic computer science textbooks and competitive programming platforms (LeetCode and HackerRank). The complete list of tags is given in Appendix Section! A.2 and contains items such as Recursion, Geometry and coordinate problems or Hashing. We limit combinations to a maximum of 5 skills out of 20 possible skills, which gives 21,700 total niche combinations. This helps avoid unrealistic skill combinations. We prompt an LLM to label puzzles with a set of programming skills as in Bradley et al. [2023b], Samvelyan et al. [2024].
Embedding diversity The diversity measure is based on an LLM's feedback and is thus subject to inaccuracies, especially if this metric is used as an optimization target. As complemetary measures of diversity, we propose embedding diversity metrics that estimate diversity in variety of pretrained embedding spaces that were not used by the algorithms. This measure is computed as the average pairwise cosine distance between the embeddings of all problems generated in the set.
3.3 ACES: Autotelic CodE Search
In this section we present ACES, an exploration method that samples target niches (sets of descriptors) as goals and prompts an LLM with relevant challenging puzzles sampled from an archive of previously generated puzzles to reach them. Like ELM, which we use as baseline, ACES uses an LLM to generate mutations of existing samples from the archive. Compared with ELM, where the LLM is instructed to produce a variation of a given puzzle without a specific objective in mind, ACES instructs the LLM to generate a new puzzle based on its examples. The generated puzzles are then evaluated for fitness and labeled, and added to the archive before the next generation round. The cells are initialized with the deduplicated P3 train set puzzles. An overview of the algorithm is given in Figure 1.
Sampling a goal and relevant examples First, we sample a cell uniformly, then we look at the 3 closest cells for which there is at least one puzzle (the target cell can be one of them). For each of these neighbor cells, we select one puzzle and add it as an example to the prompt. The prompt (available in the Appendix) instructs the LLM to produce puzzles in the target cell (corresponding to combination of skills) using the 3 sampled puzzles examples. To select examples from one cell, we normalize the range of fitness scores in this cell between 0 and and then sample from a softmax distribution from these normalized fitnesses with temperature of 0.2. To guide the model towards generating harder puzzles, we added the difficulty score D of each puzzle in the prompt (ranging from 0 to 100), instructing the model to reach score between 90 and 100 when generating new puzzles. The intuitions underlying the design of ACES are: to drive discovery of puzzles with novel skill combinations, we rely on the LLM recombining elements from puzzles close to the target cell along with very often selecting target cells without any representatives. To drive discovery of harder puzzles, rely sampling harder puzzles more often as examples and the assumption that harder examples, along with the explicit instruction to create hard puzzles, will lead to more difficult generated puzzles.
Generator and labeler LLMs Once the prompt is built, the generator LLM is instructed to produce five new puzzles following the desired instruction. For each of these generated puzzles, their fitness is computed as the negative success rate over 50 attempts (Equation 1). If the puzzle is not solved by the solver model in 50 attempts, it is considered unsolvable and discarded. For each solvable puzzle, solution is sampled randomly from the valid ones, and the (puzzle, solution) pair is then described by an LLM. This description is a short text explaining what the puzzle is (like docstrings in P3, or instructions in Hvl. The (puzzle, solution, description) triplet is then handed to a labeler LLM that produces the skill tags for the puzzle. The description and labeling prompts can be found in Appendix.
Every P3 puzzle comes in several instances with different arguments. We randomly sample one instance per puzzle, which gives use 155 seed puzzle instances.
5

---

Avoiding label hacking The reason we generate the puzzle description separately from the puzzle itself is that in preliminary experiments. we observed form of label hacking where the generator I.M,, when tasked with generating puzzles with particular combination of skills, generated generic simple puzzles and listed the relevant skills the description even if they were not required in solving the puzzle. These puzzles were then wrongly tagged with rare combination of skills and were thus oversampled as examples for the next generations, leading to the propagation of misleading descriptions. Describing the puzzle independently of all references to desired programming skills mitigates this sort of label hacking. It needs to be noted that all forms of AI feedback, be it for the fitness or for the tags, are susceptible to hacking; all methods relying on the optimization of AI feedback signals should consider and mitigate this form of hacking.
3.4 Baselines and variations
ELM with semantic categories We test an ablation of goal-directedness to study its impact, and this is exactly applying ELM to our task by using the same quality and descriptor function. To create new individuals, cell with at least one representative is sampled at random, an individual is sampled in this cell using the same quality-based sampling mechanism as ACES, and an LLM is instructed to compose a variant of this puzzle using two other random puzzles from the overall archive as few-shot examples what the puzzle domain looks like. The few-shot examples are given so ELM and ACES both use the same number of examples in their prompts. We term this baseline ELM (in reference to Evolution through Large Models which inspired this work), even if the original ELM did not use any form of AI feedback. We study an additional method combining ACES and ELM. This method also mutates a single puzzle, but the LLM is instructed to produce a targeted variation by trying to reach a target cell like in ACES. We term this method ACES-ELM.
ELM with CVT + embeddings We additionally study the impact of using natural language-bass descriptors measure and optimize for diversity, compared with embeddings. Previous QD methods (Vassiliades et al., 2017] aiming to extend their descriptor spaces to larger dimensions used centroidal Voronoi tessellations [CVT: Du et al., 1999] to partition the space into tractable number of cells. In the ELM-CVT baseline, we use the P3 train puzzle embeddings as seeds to generate 40000 points in embedding space by adding Gaussian noise with mean 0 and standard deviation 0.12. We then cluster all these points into 10000 clusters which are used as centroids for our Voronoi cells. ELM-CVT behaves as ELM, but the cells are defined with their Voronoi cells instead of programming skill combinations. Embeddings are computed with the
model.
Static Gen Our final baseline a standard generative method using a static few-shot prompting mechanism for puzzle generation, similar to Unnatural Instructions [Honovich et al., 2023] and Haluptzok et al. [2022]. At each time step, puzzles are randomly sampled from the P3 train set and given as examples to an LLM for generating new puzzles. Generated puzzles are not re-used as examples. Puzzle generation prompts for all methods are available in the Appendix.
Results
4.1
Experimental details
Puzzle generation, solution generation, description generation, and puzzle labeling are all imple- mented with the state-of-the-art open source model Llama 3 70B, quantized in bits, with temper- ature parameter of 3. We repeat all experiments using different random seeds and report the means and standard deviations of the results. Each experiment was performed on I node of 4 Nvidia Tesla V100 SXM2 32 GB, with 160 GB RAM, for about 20 hours using the vLLM library [K won al.. 2023]. Each experiment run for 40 generations, where each generation corresponds 160 puzzles generated by the puzzle generator total of 6400 puzzle generation attempts per run.
Model available at: attps://huggingi.ae www.e//..eee.eeeeeeeeeeeee /Met/ Daaaa-LLamm---3 702- Instruct-GPIQ

---

AC6S-BA BLM
0.30
600
ACES
ELN-CVT
0.37
0.14
BLK
EUH
Sasterdiss
Staticeen
Berkeeddingg
0.35
0.34
EU
0.33
EUN
Rendendes
0.66
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
0000
1000
2000
3000
4000
5000
600D
(b)
(c)
80
ACES-ELM
60000
ACES ELM
ACES
50000
ACES
ELM-CVT
60000
ACSS-ELM-
20000
ACES-
00
30
StaticGen-
(Reess
4ni0 6000
1000
200n
6000
(d)
(c)
Figure 3: ACES generates more diverse and more difficult problems. Diversity (first row): semantic diversity (a), embedding diversity with the codet5p model (b) and the deepseek-coder-1.3
model (c). Fitness (second row): average fitness of valid puzzle generated over the last 160 generation attempts (d), QD-score (e) and distributions of fitness values over whole archives (f). ACES variants outperform baselines in terms of diversity, fitness and QD score (aggregated measure).
4.2 Quality of LLM-generated skill labels
We represent generated problems with skill descriptors generated by an LLM. This allows us to characterize abstract, semantic aspects of the generated problems that would be hard capture with hand-written descriptor functions, and thus lets us optimize diversity in space that is more aligned with human intuitive notions of variations in this programming domain. However, LLM labeling is stochastic and can be mis-aligned with human judgements. To validate the labeling process, we tagged 60 puzzles with semantic descriptors selected from the list of 20 (see Section 3.2) and, using them as ground truth, report a precision of 0.71, a recall of 0.75 and an F1 score of 0.73. Qualitatively. we found the labeler to be generally competent, always detecting the most salient skill descriptor and almost never labeling puzzle with totally irrelevant descriptor-altiee answer quite literally, calling a problem set problem when used Python's set function. Appendix Figure 7 shows that the labeler uses almost all descriptors across the experiments, generally using 2-3 descriptor labels per puzzle.
it did sometimes
ACES generates more diverse and challenging problems than existing approaches
More diverse The ability of an algorithm to generate diversity can be measured as the number of descriptor niches manages fill stronger algorithms can reach more niches. On this metric, ACES and its variant ACES-ELM vastly outperform other baselines, reaching to 700 different niches by the end of the experiment (Figure 3a). This shows that our approach can effectively generate diversity of problems with respect to a target description space provided by the user: here the set of 20 programming skills defined in Section 3.2. Although ELM also leverages the same semantic descriptors, its undirected mutation operator does not seem to optimize diversity effectively the goal-directed generation operator ACES variants.
However, the imperfection of the skill labeling could cast doubts on this result: could it be that ACES variants learn to generate problems that hack the labeler and force generate diverse labels that do not capture the true properties of the problems, this despite our preventive measures (see Section 3.3)? Furthermore, ELM-CVT and StatieGen do not leverage space, which may explain why they generate lower diversity in that space. To validate our results, we also measure embedding diversity metrics in a variety other sentence embedding spaces not used at any point during training. This measure is obtained by embedding all generated puzzles with
semantic representation
7

---

given model, then computing the average cosine distance between all pairs of embeddings in the set. Figures 6a and 3c show these metries for two standard embedding models: codet5p- -eneeddinn and deepseek-coder- 1.3b: ACES and its variant significantly outperform others here too. ELM-CVT represents problems and optimizes for diversity the codet5p embedding space, which explains its ability to generate higher diversity in that space than ELMM (Figure 6a). However, this diversity does not transfer well to other diversity metrics (Figure 3a and Figure 3c), while the semantic diversity optimized by ACES variants does transfer well across diversity metrics (Figures 3a to 3c). Overall, these results show that by directly optimizing for semantic diversity through goal-directed exploration, ACES variants generate problems that more semantically diverse, but also generally more diverse.
More challenging Figure 3d shows the evolution of the average fitness of the puzzles generated over the last 5 iterations (800 attempted puzzle generations). Here we see the ability of ACES variants to continuously generate increasingly challenging puzzles across the experiment, while ELM variants saturate earlier on. StaticGen, a static generation method, consistently generates puzzles with low fitness. Figure 3f shows the distribution of fitness of the whole archive at the end of experiments. These distributions are all bimodal, with problems having either very low fitness (solved most of the time) or very high fitness (solved only couple times out of the 50 solving attempts). While StaticGen mostly generates simple problems (peak in the lowest fitness bin), all the algorithm optimizing for difficulty (all others) seem do so efficiently showing peaks in the highest fitness bin.
Finally, Figure 3e shows the evolution of QD scores, a metric used to evaluate QD methods that sums the fitness of the very best solution found in each filled niche. This metric captures both diversity (more niches means more terms in the sum) and local quality (higher quality solutions means higher terms in the sum). Here again, ACES variants significantly outperform other baselines. All these results are evidence that ACES variants efficiently produce a larger diversity of more challenging problems than existing algorithms.
Finetuning We conducted finetuning experiments using the Llama-3-8b model with datasets generated by WizardCoder (a variant of the state-of-the-art method WizardLM for generating synthetic data[Luo et al., 2023, Xu et al., 2023]), StaticGen (established baselines), and our proposed ACES- ELM method. We then evaluated the model's performance using the greedy pass @ metric on a series of test sets. These test sets were equally composed of puzzles from our method and StaticGen with increasing difficulty levels, generated using a seed different from the training data.
Results revealed that the Llama-3-8b model finetuned with SCES-ELM-- ---eeerrttedd data achieved a remarkable pass@ 1 score of 53.3 on the most challenging test set (see Figure 4b), significantly outperforming both baseline methods and the Llama-3-70B model. While models finetuned with WizardCoder and StaticGen showed improvements over the baseline (achieving pass @ I scores of 49.4 and 41.6, respectively), they consistently underperformed compared to the model. Notably, the performance gap between ACES- ELMM and baseline methods widened as testset difficulty increased, demonstrating ACES-ELM's effecttivnness in preparing models for complex coding challenges and generating high-quality training data.
4.4 ACES scales with LLM size
Diversity We found that ACES could generate more diverse and challenging problems, but what happened if we tried to use larger LLM? We compare ACES archive generated using Llama-3-70b against larger models (Llama 405B model and Mistral large 2). Using those LLMs leads to a better Quality-Diversity score overall (see Figure 5), up 25.6% for Mistral Large and 12.3% for Llama 405B (using Llama 405B and Mistral large 2 both for the difficulty metric and skill labeling). This demonstrates how ACES scales with models of larger size.
difficulty Evaluating Mistral Large and Llama 405B on each other's generated datasets reveals pass@1 I scores of 56.7% and 58%, respectively (Figure 4a). These results demonstrate the effec- tiveness of our method in creating challenging benchmarks, even for state-of- tit-thh-a art models, and highlight the transferability of difficulty measures across models with similar capabilities.
Furthermore, when tested on the archive generated by Llama-3-70B using ACES-ELM, Mistral Large achieved 70% pass@k score, while -amma-3-40BB reached 74%. contrast, Llama-3-70B itself attained a pass @1 I score of 36.8%. These findings underscore the superior problem-solving
8

---

Performance Comparison by Model
80-
2407,
(8)
Bench
60
Code Banch
50-
40-
40-
Lame3-700
20
Lamadd4a flaetused statiction
Ulama3-6 3-4b fleutuned ACES ELN
20
10-
Mistrak Large--tteeeeaee 2440 2407
Meta- satta-laamm3..1 3.1 1-50s--it
CodeDwent. S.de S-70n....78---- Chat
deopseek coder-33b-it
Mixtral--xi288- vt.
Meta-Llama- -la-a-m-m--oo 7-7--1 708-it
deopresk soppeenk-code-dd. 7b-it
dnopseak-coodet 1.36-it
Mata 3-00-jt
codegomma 777--
50
80
85
D Difficulty Level (k)
(b)
Codeewven 5-B--Cyu
Uama-700, ACES-LLM
0.67
0.34
0.31
0.72
damhatz- Sbrehl
Hictral (iiiittth
Laan 4038, ACES-LLE
0.89
0.17
0.57
0.72
0.50
a Meta Liria 2 68 intrrct nodtgeenn 2b11
Mistral-Large-2 A_CES-LEEEM
0.47 0.89
1.0 0.29
0.49
0.83
0.00
Misical Instuct Natul-28 intruce-d.11
Human Eval 0.34
0.37
0.29
1.0
0.53
0.45
-0.58
Code Sench
0.51 0.57 0.69 0.53
1.0
0.8
Live Cede
0.82
0.46
0.0
1.0
Liuma-700 ACES RLM
Liamn 40.3. acEs acES-ELa KLM
Mistrol Large-2, ACED RLM
Humen Eval
Bi Cade Danch
Lvve Code
(c)
Figure 4: (a) Greedy pass scores for various models on datasets generated by ACES-ELM with Llama-3-70b, Llama-3-405B, Mistral, on the HumanEval benchmark, and recent benchmark created to limit contamination and saturation compared to HumanEval (BigCodeBench and Live- CodeBench). Scores not found are represented as O. (b) Greedy pass @ 1, after finetuning Llama-8h -ab on archive generated by WizardCoder, StaticGen, and ACES-ELM, on a series of test sets equally composed of mixtures of puzzles from ACES-ELL -LLM and StatieGen. See rebuttal main text for addi- tional details. (c) Pass @1 competence of all models on HumanEval+ versus on problems generated by our best problem generator (ACES-ELM) Problems that are more challenging for model more generally challenging for others too (similar ranks in (a)). Models in the top left corner of (b) may overfitting to HumanEval+, performance on our generated problems. (d) Correlation matrix of pass I scores of the different datasets. Our method achieves correlation up to 0.83 with Live Code Bench and 0.69 with Big Code Bench, whereas HumanEval has only a correlation of 0.46 and 0.53 respectively.
their strong performance there do not translate into higher
capabilities of Mistral Large and Llama-405B. However, it's noteworthy that even these advanced models have not saturated the benchmark generated by Llama-3-70B, as there remains approximately 30% room for improvement to solve the benchmark fully.
4.5 ACES generates more challenging problems than the ones found in existing benchmarks
ACES variants generate problems that are more challenging than problems generated by other baselines. But how challenging are they really? Here, measure the competence of 10 state-of- the-art LLM problem solvers and compare it to the performance of these same models on existing human-curated benchmarks. Figure 4a reports the pass @ scores for 10 LLM solvers over two existing programming puzzles benchmarks: HumanEval + [Liu et al., 2024], Big Code Bench, Live Code Bench as well as over the of problems generated by ACES variants (with Llama-3- 70b, Llama-3. 1-405b and Mistral Large 2) and other baselines in the experiments presented above. Results for additional models can be found in Appendix Figure 8. Overall, our generated sets are more challenging across models than the HumanEval sets usually used to benchmark code LLMs. CodeQwen 1 1---B-Chhtt, L 70B-instruct and Mixtral Sittrral-&22B--nstruutt
1, one of the best open source models on HumanExal with 78.7, 72 and 72% pass @1 respectively, get considerable drop in pass 1, falling to 15, 47 and 34% respectively on problems generated by ACES-ELM with Llama-3- 3-b (Figure 4c).

---

Our findings demonstrate the transferability of puzzle difficulty across various language models. Models exhibiting lower scores on our datasets generated with Llama 70B also have lower scores on the datasets generated by Llama 405B and Mistral, as well as on LiveCodeBench [Jain et al., 2024] (which specifically designed to avoid contamination) and BigCodeBench [Zhuo et al., 2024]. Figure 4a illustrates this correlation, with HumanEval being the notable exception. This anomaly suggests potential contamination in models optimized for the HumanEval benchmark, particularly in smaller models. Figure 4d presents the correlation between pass @ scores across all datasets, averaged over models. Our method has generated benchmarks that correlate more with uncontaminated benchmarks (LiveCodeBench and BigCodeBench) than HumanEval. Specifically, the Mistral-genat generrtee dataset using SCCES-ELM achieved a correlation of 0.83 with LiveCode In contrast, HumanEval only reached correlation 0.46 with Live Code Bench, underscoring the challenging nature and value of our generated benchmark for comparing L.MMs.
5 Discussion
This paper presented ACES, an autotelic generative algorithm designed to generate a diversity of challenging Python programming puzzles. Our experiments showed that ACES generates problems that are both more diverse and more challenging than the ones generated by existing generative approaches or the ones found in human-curated benchmarks.
Limitations and improvements ACES has several limitations. The algorithm relies on several assumptions: 1) the labeling should be accurate, 2) the generator should be good at reaching its goals, 3) the correlation between the feature (descriptors and quality) of parent and children problems should be sufficiently high (heredity). Although these assumptions are only partially verified (see Section 4.2 and Appendix Figures 9 and 10), our results show that these are good enough for allowing the effective optimization of diversity and difficulty in our domain. We expect that progress along the three lines can be made by harnessing the increasing capabilities of future language models and will automatically translate into higher performing autotelic generative models of problems. The heredity property presents an interesting research question: in principle, it underlies all evolutionary methods making use of LLMs but, in practice, it has not been evaluated or discussed [Bradley et al., 2023a,b].
Creating and releasing challenging LLM benchmarks ACES allows for the automatic generation of programming puzzles tailored to LLM's current capabilities and we demonstrated that we generate puzzle sets that are more challenging than current code evaluations. This brings hope for generating tomorrow's ' next generation of code benchmarks, as today's evaluations are almost saturated. However, important steps need to be performed before this can be done. First, as is done in Schuster al. [2021]. we currently only test solutions with one set of arguments, there should be tests with wide range to measure solution robustness. Empirical difficulty is not the only thing to be expected of exercises: the puzzles need to make sense and be hard for the good reasons. This requires a more complete picture of puzzle's 's quality than difficulty alone, which remains an open problem. Overall, we believe that open endee algorithms will play an increasing role in automatically evaluating LLMs in the future [Samvelyan et al., 2024].
Other applications ACES is general algorithm that can be casily translated to other application domains by letting the user define a new descriptor and quality functioo. Swapping the difficulty metric with more subjective objective estimated by LLM could let ACES generate problems adapted for human students of a specific level in educational contexts, for example. In artificial intelligence, one could envision self-play loop where a learning agent iteratively generates diversity of problems maximizing its current learning progress (quality metric), then trains on them to augment its competence [Sukhbaatar et al., 2017, Silver al., 2017, Colas al., 2022].
Broader impacts Open-ended exploration algorithms in general have wide-ranging implications when scaled up. They could potentially help in discovering harmful artifacts (in code domains, harmful bots or cyberattack programs), as well as help find solutions or red-team existing systems. We note that an evolutionary optimization algorithm such as ACES needs extensive fitness feedback, either limiting its use by bad actors or making them detectable. Positive applications of open- ended exploration algorithms applied to problem generation range from educational technologies to automated scientific discovery, helping shoulder some of the rising needs of the future.
10

---

References
Junyi Chu and Laura E. Schulz. Play, curiosity, and cognition. Anmual Review of Developmental Psychology, 2(1):317-343, 2020. doi: 10.11466aauuee-eeeyyy---00011010 -070000000-00000000-0000 URL https: //doi.org/10/ htw.://ew...n.eeeeeeeraa-------.
Gaia Molinaro and Anne GE Collins. A goal-centric outlook on learning. Trends in Cognitive Sciences, 2023.
Benjamin A Burton and Mathias Hiron. Creating informatics olympiad tasks: exploring the black art. Olympiads in Informatics, 2:16-36, 2008
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and
Jacob Steinhardt. Mcasuring massive multitask language understanding. arXiv preprint
arXiv:2009.03300 03300, 2020.
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda. Nicholas Joseph. Greg Brockman, Alex Ray, Raul Puri, Gretchen 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 Hesse, 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. Evaluating Large Language Models Trained Code, July 2021. htLLttt::/// wwwwvv.ivvvvv./////// wrg/ 03374 4. stXiv:2107.03377 [cs].
Misha Gromov. Great circle of mysteries. Birkhauser, Basel, Switzerland, edition, May 2018.
Junyi Chu, Joshua B. Tenenbaum, and Laura E. Schulz. In praise of folly: flexible goals and human cognition. Trends in Cognitive Sciences, 2024/05/20 2024. ISSN 1364-6613. doi: hiw.bii.iiis222.....0000 URL https: /ttp//cciioo//////// http://ti........../o./. 1.../..111...............
2024. 03. 60
Jürgen Schmidhuber. Powerplay: Training an increasingly general problem solver by continually searching for the simplest still unsolvable problem. Frontiers in psychology, 4:313, 2013.
Vincent Herrmann, Louis Kirsch, and Jürgen Schmidhuber. Learning abstract bit at time through self-invented experiments encoded as neural networks. arXiv preprint 2XX
2022.
Cédric Colas, Tristan Karch, Olivier Sigaud, and Pierre- Yves Oudeyer. Autotelic Agents with Intrinsically Motivated Goal-Conditioned Reinforcement Learning: Short Survey, July 2022. URL
org/ wttp:///...r.///////1..... 09830. arXiv:2012.09830 [cs].
Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre-Yved Oudeyer. Automatic curriculum learning for deep rl: A short survey. arXiv preprint arXiv:2003.0466 2020.
Jonathan Grizou, Laurie J. Points, Abhishek Sharma, and Leroy Cronin. A curious formulation robot enables the discovery of novel protocell behavior. Science Advances, 6(5)xcayy2377, 2020. doi: 10. 10.1126/scaady.aay42333 URL battps:/i htmps::/wwerr /wwww sci weceennnc.... org dol at..///bs/....111.. sciadv. aay4237.
Mayalen Etcheverry. Curiosity-driven Al for Science: Automated Discovery of Self-Organized Structures. PhD thesis, Inria & Labri, Université Bordeaux, 2023.
Tal Schuster, Ashwin Kalyan, Alex Polozov, and Adam Tauman Kalai. Programming Puzzles. June 2021. URL
net. formm? d= So=ff_hhc4Rrrr
Patrick Haluptzok, Matthew Bowers, and Adam Tauman Kalai. Language Models Can Teach Them- selves Program Better. In The Eleventh International Conference on Learning Representations, 2022.

---

Or Honovich, Thomas Scialom, Omer Levy, and Timo Schick. Unnatural instructions: Tuning language models with (almost) no human labor. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pages 14409-14428, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10. 10w.33/1112223.llooooog atttps:/aclaanthoole
URL
wwt////g..22.. aa0-22aacc-oonnn. 806.
Suriya Gunasekar, Yi Zhang. Jyoti Aneja, Caio César Teodoro Mendes, Allie Del Giorno, Sivakanth Gopi, Mojan Javaheripi, Piero Kauffmann, Gustavo de Rosa, Olli Saarikivi, et al. Textbooks are all you need. arXiv preprint arXiv:2306. //44,, 2023.
Jean-Baptiste Mouret and Jeff Clune. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04900 2015.
Justin Pugh, Lisa Soros, and Kenneth Stanley. Quality Diversity: A New Frontier for Evolutionary Computation. Frontiers in Robotics and AI, 3, July 2016. doi: 00.3389//robb.2016.0000//
Herbie Bradley, Honglu Fan, Francisco Carvalho, Matthew Fisher, Louis Castricato, reciprocated. dmayhem93, Shivanshu Purohit, and Joel Lehman. OpenELM, January 2023a. URL https: //github. cwm/coo////oooo Carpaarrpaaaaaaa OpenEIM.
Jiawei Liu, Chunqiu Steven Xia, Yuyao Wang, and Lingming Zhang. Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation. Advances in Neural Information Processing Systems, 36, 2024.
Joel Lehman and Kenneth O Stanley. Abandoning objectives: evolution through the search for novelty alone. Evol. Comput., (9(2):199222) February 201 la.
Joel Lehman and Kenneth O Stanley. Evolving diversity of virtual creatures through novelty search and local competition. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, pages 211-218, 201 1b.
Antoine Cully and Yiannis Demiris. Quality and diversity optimization: A unifying modular framework. IEEE Transactions Evolutionary Computation, 22(2):245-255 2018a. doi: 10.1109/EEV22221.2777778
Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O. Stanley, Evolution through Large Models, June 2022. URL http::/arxiv..or wwwpiiiiorrg//b...oo 2206. 08896. arXiv:2206.0883 [es].
Adrien Baranes and Pierre-Y Yver Oudeyer. Active learning of inverse models with intrinsically moti- vated goal exploration in robots. Robotics and Autonomous Systems, 61(1):99-7,, January 2013. ISSN 0921-8890. doi: r0.00066 008. URL /attps://aee /www.www.. sci sciencedirect. cot.://ciieneaarrrcce////////999
Mayalen Etcheverry, Clément Moulin-Frier, and Pive Oudeyer. Hierarchically organized latent modules for exploratory search in morphogenetic systems. Advances in Neural Information Processing Systems, $3:4846-4853 2020.
Sébastien Forestier, Rémy Portelas, Yoan Mollard, and Pierre-Y Oudeyer. Intrinsically motivated goal exploration processes with automatic curriculum learning. The Journal of Machine Learning Research, 23(1):681 (111))668886888 8-6888, 2022. Publisher: JMLRORG.
Joel Lehman and Kenneth O. Stanley. Evolving a diversity virtual creatures through novelty search and local competition. In Proceedings of the 13th Annual Conference Genetic and Evolutionary Computation, GECCO '11 page 21 1-288, New York, NY, USA, 201 lc. Association for Computing Machinery. ISBN 978 9781450305570. doi: 10.1145/2001576.66
URL
Clément Moulin-Frier. Sao M Nguyen, and Pierre-Yvel Oudeyer. Self-organization of early vocal development in infants and machines: the role of intrinsic motivation. Frontiers in psychology, 1006, 2014.
12

---

Pierre Yves Oudeyer and Linda B Smith. How evolution may work through curiosity-drive develop- mental process. Topics in Cognitive Science, 8(2):492-502, 2016.
Chris Reinke, Mayalen Etcheverry, and Pierre- Yves Oudeyer. Intrinsically motivated discovery of diverse patterns in oelf-ongani systems. arXiv preprint urXiv:1908.0660 2019.
Elliot Meyerson, Mark J Nelson, Herbie Bradley, Arash Moradi, Amy K Hoover, and Joel Lehman. Language model crossover: Variation through few-shot prompting. arXiv preprint 1211: 2023.
Angelica Chen, David M Dohan, and David R So. Eyoprompting: Language models for code-level neural architecture search, arXiv preprint arXiv:2302. 148.238822.4888, 2023.
Muhammad U Nasir, Sam Earle, Julian Togelius. Steven James, and Christopher Cleghorn. Llmatic: Neural architecture search via large language models and quality-diversity optimization. arXiv preprint arXiv:2306.01102 2023.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamie KerT, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer. Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton, Tom Conerly, Tom Henighan, Tristan Hume, Samuel R. Bowman, Zac Satfiel-Dodde Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional AI: Harm- lessness from AI Feedback, December 2022. URL http: http://wwwwwwwwwa///////// 08073. arXiv:2212.0807. [cs].
Harrison Lee, Samrat Phatale, Hassan Mansoor, Kellie Lu, Thomas Mesnard, Colton Bishop, Victor Carbune, and Abhinav Rastogi. Rlaif: Scaling reinforcement learning from human feedback with ai feedback. arXiv preprint arXiv:2309.00267, 2023.
2023.
Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging -in-as---judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36, 2024.
Jenny Zhang, Joel Lehman, Kenneth Stanley, and Jeff Clune. OMNI: Open-endedness via Models of human Notions of Interestingness, June 2023. URL hhttt::/arrrii..rrr/bbb//// 0111. arXiv:2306.0177 117111 [es].
Martin Klissarov, Pierluca D'Oro, Shagun Sodhani, Roberta Raileanu, Pierre-Luc Bacon, Pascal Vincent, Amy Zhang, and Mikael Henaff. Motif: Intrinsic motivation from artificial intelligence feedback. arXiv preprint arXiv:23 10.00066, 2023.
Noveen Sachdeva, Benjamin Coleman, Wang-Chenn Kang, Jianmo Ni, Lichan Hong, Ed H Chi, James Caverlee, Julian McAuley, and Derek Zhiyuan Cheng. How to train data-efficient llms. arXiv preprint arXiv:2402.09661 2024.
Herbie Bradley, Andrew Dai, Hannah Teufel, Jenny Zhang, Koen Oostermeijer, Marco Bellagente, Jeff Clune, Kenneth Stanley, Grégory Schott, and Joel Lehman. Quality-diversity through ai feedback. arXiv preprint arXiv: 2023b.
Mikayel Samvelyan, Sharath Chandra Raparthy, Andrei Lupu, Eric Hambro, Aram H Markosyan, Manish Bhatt, Yuning Mao, Mingi Jiang, Jack Parker-Holder, Jakob Foerster, al. Rainbow teaming: Open-ended generation of diverse adversarial prompts. arXiv preprint arXiv:2402.16822. 2024.
Cédric Colas, Laetitia Teodorescu, Pierre Yves Oudeyer, Xingdi Yuan, and Marc-Alexandre Côté. Augmenting Autotelic Agents with Large Language Models. arXiv preprint arXiv:2305. 12487, 2023.
13

---

Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar. Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An Open Open-Ended Ended Embodied Agent with Large Language Models, May 2023a.
/ arxiv org abs / 2305. 6291. arXiv:2305.1629 [es].
Yuqing Du, Olivia Watkins, Zihan Wang. Cédric Colas, Trevor Darrell, Pieter Abbeel, Abhishek Gupta, and Jacob Andreas. Guiding pretraining in reinforeement learning with large language models. arXiv preprint arXiv:2330..660 2023.
Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, al. Code Ilama: Open foundation models for code. arXiv preprint arXiv:2308. 0ete3308.22990 /2900, 2023.
Yizhong Wang, Yeganch Kordi, Swaroop Mishra, Alisa Liu, Noah A. Smith, Daniel Khashabi, and Hannanch Hajishirzi. Self-instruct: Aligning language models with self gelf-generated instructions. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki, editors, Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 13484 13508, Toronto, Canada, July 2023b. Association for Computational Linguistics. doi: 10.18653/v1/2023..dm aol-long..755 754. URL https: : / acl awwaacllatttoo www.oooothooy....ooooooooooooooa org 2023//222.oom acl-long. 754.
Ronen Eldan and Yuanzhi Li. Tinystories: How small can language models be and still speak coherent english? arXiv preprint arXiv:2305.07754 2023.
Marah Abdin, Sam Ade Jacobs, Ammar Ahmad Awan, Jyoti Aneja, Ahmed Awadallah, Hany Awadalla, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone. arXiv preprint 244212404..4211, 2024.
Can Xu, Qingfeng Sun, Kai Zheng, Xiubo Geng, Pu Zhao, Jiazhan Feng, Chongyang Tao, and Daxin Jiang. WizardIm: Empowering large language models to follow complex instructions. arXiv preprint arXivv2304. 12244, 2023.
Ziyang Luo, Can Xu, Pu Zhao, Qingfeng Sun, Xiubo Geng, Wenxiang Hu, Chongyang Tao, Jing Ma, Qingwei Lin, and Daxin Jiang. Wizardcoder: Empowering code large language models with evol-instruct. arXiv preprint arXiv:2306. 08568, 2023.
Dingli Yu, Simran Kaur, Arushi Gupta, Jonah Brown-Cohen, Anirudh Goyal, and Sanjeev Arora. Skill-mix: A flexible and expandable family of evaluations for ai models. arXiv preprint MrXiv:2310.17561 2023.
Vassilis Vassiliades, Konstantinos Chatzilygeroudis, and Jean lean-Baptiste Mouret. Using Centroidal Voronoi Tessellations to Scale Up the dimei-ddimnsiioall Archive of Phenotypic Elites Algorithm, July 2017. URL http: / rxiv. org/ abs / 1 1610 0 05729. arXiv:1610.05729 [cs].
Qiang Du, Vance Faber, and Max Gunzburger. Centroidal Voronoi Tessellations: Applications and Algorithms. SIAM Review, 41(4))637-676, 1999. URL http: ht:p:://wwww 2653198.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang. Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph E. Gonzalez, Hao Zhang, and Ion Stoica. Efficient memory management for large language model serving with pagedattention. In Proceedings of the ACM SIGOPS 29th Symposium Operating Systems Principles, 2023.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar-Lezama, Koushik Sen, and Ion Stoica. Livecodebench: Holistic and contamination free evaluation of large language models for code. arXiv preprint arXiv:2403.0799 2024.
Terry Yue Zhuo, Minh Chien Vu, Jenny Chim, Han Hu, Wenhao Yu, Ratnadira Widyasari, Imam Nur Bani Yusuf, Haolan Zhan, Junda He, Indraneil Paul, et al. Bigcodebench: Benchmarking code generation with diverse function calls and complex instructions. arXiv preprint arXiv:2406.155 15877 2024.
Sainbayar Sukhbaatar, Zeming Lin, Ilya Kostrikov, Gabriel Synnaeve, Arthur Szlam, and Rob Fergus. Intrinsic motivation and automatic curricula via asymmetric self self-play. arXiv preprint 17X1v:1003.05407, 2017. 2017.
14

---

David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou. Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, al. Mastering chess and shogi by self-play with general reinforcement learning algorithm. arXiv preprint arXiv: 171201188 2017.
Ashvin V Nair, Vitchyr Pong, Murtaza Dalal, Shikhar Bahl, Steven Lin, and Sergey Levine. Visual reinforcement learning with imagined goals. Advances in neural information processing systems, 31, 2018.
Adrien Laversanne-Finot, Alexandre Pere, and Pierre Yves Oudeyer. Curiosity driven exploration of learned disentangled goal spaces. In Conference on Robot Learning, pages 487-504. PMLR, 2018.
Chris Reinke, Mayalen Etcheverry, and Weerr--Yves, Oudeyer. Intrinsically Motivated Discovery of Diverse Patterns in Self- saff-Orgnizzig Systems. In International Conference on Learning Represen- tations (ICLR), 2020.
Antoine Cully and Yiannis Demiris. Hierarchical behavioral repertoires with unsupervised descriptors. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 69-76, 2018b.
15

---

A Appendix
A.1 Additional Related Work
Descriptor spaces for exploration methods all open-ended exploration methods, one must define a Behavioral Characterization (BC) space characterize novelty. The earliest works used predefined low-dimensional descriptors to represent generated artefacts [Lehman and Stanley, 201 la, Baranes and Oudeyer, 2013, Mouret and Clune, 2015], which constrains the search along a handful of features one can code descriptor for. More recent works have relied on gigeer-dimensional Iearned pretrained embedding functions [Nair et al., 2018, Laversanne-Fing et al., 2018, Reinke et al., 2020], and even hierarchies of such spaces, each representing different perceptual features of the generated artefacts [Cully and Demiris, 201 8b, Etcheverry et al., 2020]. Diversity- sometimes need to be adapted to work with such high- high-dimensional spaces whose discretization leads exponential number of cells [Vassiliades et al., 2017]. But the main issue is that they hardly interpretable and might not always align with the dimensions of variation humans find meaningful. With ACES, propose autotelic diversity-produccin algorithm that constrains the search along set of abstract, interpretable and naro-to- features of interest evaluated by LLMs.
algorithms
A.2 Prompts
Here the various prompts for ACES and all baselines.
Skills description.
Skills description used to label problem. see prompt A.2
List of semantic descriptors
0 String Manipulation
1 Mathematical Operations
Conditional Logic
3 Recursion
Brute Force Search
5 Dynamic Programming
Greedy Algorithms
Backtracking
Set Operations
9 Permutations and Combinations
10 Probability and Statistics
11 Pattern Recognition
12- Sorting and Ordering
13 Binary Operations (bitwise shifting, AND, OR)
14 Geometry and Coordinate Manipulation
15 Algorithm Optimization
16 Number Theory (factors, primes, etc.)
17 Graph Theory (paths, edges, vertices)
18 Array Indexing
19 Hashing
Example of puzzle labelling
Puzzle to label:
16

---

def Eis: str) -> bool:\\
"""Find string with 1000 'o's but no two adjacent to's. -
return count ('o') 1000 and cocun ('oo!) 011
def g()
return ('h' + 'o') 100011
assert ((g)))}
Assistant: To solve the problem, we need to understand the logic of the 'f function and how it checks for the presence of 1000 'oss and no adjacent 'o's. We also need to understand the implementation of the function, which generates the string with 1000 'o's.
Based on this understanding, the necessary programming skills are: 1: Counting and combinatorics (to understand the counting of 'o's and 'oo's in the string)
5: String Manipulation understand the string concatenation and searching)
Therefore, the list of indices for the problem is: [1, 5]
Prompt for the puzzle generator ACES. This prompt is used for ACES and all autotelic variants.
ACES
User:
Consider Python Programming Puzzles (P3). P3 consists of two functions: a problem function 'f and its corresponding solution 'g'. The challenge lies in constructing a SAT problem 'f' and function 'g' such that "((0)" evaluates to 'True'
Main Rules:
Each puzzle includes two functions: 'def f(...)' and 'def g(...)'
The first argument of 'f' is always the output from 'g().
Ensure and 'g' have matching argument signatures (e.g., 'def f(solution, arg =
arg2=value2, ...)' and 'def g(argl=value) arg2-value2, ...))). You also need to set the value of argument of (arg1. arrg2.... and g when you define them.
Avoid using 'f' inside 'g', and 'g' inside 'f'
Include any necessary imports your code runs smoothly. Give a clear Puzzle description that must be brief and diverse compared to the other puzzles.
Make sure the puzzle is celf-contained within these two functions.
Make sure that each puzzle have just all required skills (see below)
P3 Format:
Puzzle description: two to sentence summary the puzzle's content. To explain what the problem It, and how you can solve it with 'g'.
17

---

python
def f(solution, args..... bool:
Python code test the solution returned by g. This function is test unit and must return True the solution is correct, and False otherwise.
def (args=...)) -> solution:
Python code generate solution for the problem. The solution should generalize to all possible args. return solution
assert ())
Examples:
Puzzle 0:
Puzzle description: jpuzzle description]
Difficulty score: [puzzle score] out of 100
This puzzle has the following skills: (skillslist]
[Python Programming Puzzle]
Puzzle 1:
Puzzle 2:
Generate 5 P3 similar to previous Examples. Ensure that all puzzles are more challenging than Puzzle from previous examples. You should aim to generate puzzles with Difficulty score between 90 and 100 out of 100.
*Please make sure that new puzzles have JUST ALL the following s"ills"": |list target skills)
New 5 problems:
Assistant:
ACES-ELM
User:
Consider Python Programming Puzzles (P3). P3 consists of two functions: problem function and its corresponding solution 'g'. The challenge lies in constructing a SAT problem and function 'g" such that "((g))' evaluates to 'True'
Main Rules:
Each puzzle includes two functions: 'def f(...)' and 'def g(...)'.
The first argument of is always the output from 'g()'.
Ensure 't and 'g' have matching argument signatures (e.g., 'def f(solution, arg 1
arg2=value2, ...)' and 'def -value,, arg2-value2, ...))) You also need to set the value of argument of (arg1,ag (.rg2.... and when you define them.
Avoid using inside 'g', and 'g' inside 'f.
Include any necessary imports so your code runs smoothly.
Give a clear Puzzle description that must be brief and diverse compared to the other puzzles.
Make the puzzle is self-contained within these two functions.
18

---

Make sure that each puzzle have just all required skills (see below)
P3 Format:
Puzzle description: A two to four sentence summary of the puzzle's content. To explain what is the problem Y, and how you can solve it with 'g'.
python
def (solution, args=...) -> bool:
Python code to test the solut in returned by g.
This function is test unit and must return if the solution is correct, and False otherwise.
def (args=.... -> solution:
Python code generate solution for the problem. solution should generalize return solution
possible args.
assert (()()) = True
Examples:
Puzzle 0:
Puzzle description: jpuzzle description]
Difficulty score: [puzzle score] out of 100
This puzzle has the following skills:
[skills list]
[Python Programming Puzzle]
Puzzle 1:
Puzzle 2:
Generate 5 P3 similar to the last Examples (Puzzle 2). Ensure that all new puzzles more challenging than Puzzle 2. You should aim to generate puzzles with Difficulty score between 90 and 100 out of 100.
**Please make sure that new puzzles have JUST ALL the following skills**: |list target skills)
New 5 problems inspired by Puzzle Assistant:
Prompt for the puzzle generator of Static gen.
Static gen
User: Consider Python Programming Puzzles (P3). P3 consists of two functions: a problem function f and its corresponding solution 'g' The challenge lies in constructing SAT problem 'f' and function 'g" such that "((())) evaluates to 'True'
Main Rules:
Each puzzle includes two functions: 'def f(....' and 'def g(...)'. The first argument of 'f' is always the output from 'g()..
19

---

Ensure 't' and 'g' have matching argument signatures (e.g. 'def f(solution, a arg2=value2, ...)' and 'def g(argt=value1, arg2-value2, --.)). You also need to set the value of argument of (arg1 ,arg?.... and g when you define them.
Avoid using inside gg, and 'g' inside 'f
Include any necessary imports so your code runs smoothly.
Give a clear Puzzle description that must be brief and diverse compared to the other puzzles.
Make the puzzle is self-contained within these two functions.
P3 Format:
Puzzle description: A two to four sentence summary of the puzzle's content. To explain what the problem 't, and how you solve it with 'g'
python
def (ssouuioon args=...) bool:
Python code test the solution returned by g.
This function is test unit and must return True if the solution is correct, and Falsc otherwise.
def g (args-....) solution:
Python code to generate solution for the problem. The solution should generalize to all possible args. return solution
assert ())
Examples:
Puzzle 0:
Puzzle description: jpuzzle description]
Difficulty score: [puzzle score] out of 100
This puzzle has the following skills: [skillslist]
[Python Programming Puzzle]
Puzzle 1:
Puzzle 2:
Generate 5 different P3 similar previous Examples.
New 5 problems: |list target skills)
New 5 problems inspired by Puzzle Assistant:
Prompt for the puzzle generator of ELM and ELM semantic. This prompt is used for non- autotelic baselines.
20

---

ELM and ELM semantic
Consider Python Programming Puzzles (P3). consists of two functions: a problem function f' and its corresponding solution 'g'. The challenge lies in constructing a SAT problem 'f' and function 'g" such that "((()) evaluates to 'True'
User:
Main Rules:
Each puzzle includes two functions: 'def f(...)' and 'def g(...)'
The first argument of is always the output from 'g()'
Ensure I' and 'g' have matching argument signatures (e.g. 'def f(solution, 1rg1=value1,
arg2-value2, ...)' and 'def g(arg1-value1, -value1, arg2-value2, ...))) You also need to set the value of argument of (arg1. .arg..... and when you define them.
Avoid using inside 'g, and 'g" inside f.
Include any necessary imports so your code runs smoothly.
Give a clear Puzzle description that must be brief and diverse compared to the other puzzles.
Make the puzzle is self-contained within these two functions.
P3 Format:
Puzzle description: A two to four sentence summary of the puzzle's content. To explain what the problem 'f, and how you can solve it with 'g'.
python
def (solutioo, args....) bool:
Python code test the solution returned by g.
This function is test unit and must return True the solution is correct, and False otherwise.
def (args=...) -> solution:
Python code generate solution for the problem. The solution should generalize to all possible args. return solution
assert ())
Examples:
Puzzle 0:
Puzzle description: jpuzzle description]
Difficulty score: jpuzzle score] out of 100
This puzzle has the following skills: [skillslist]
[Python Programming Puzzle]
Puzzle 1:
Puzzle (to mutate):
Generate 5 P3 similar the last Examples (Puzzle 2). Ensure that all new puzzles are more challenging than Puzzle You should aim to generate puzzles with Difficulty score between 90 and 100 out of 100.
*Please make sure that new puzzles have JUST ALL the following s* |list target skills)
21

---

New 5 problems inspired by Puzzle 2
Assistant:
Description prompt
A Python programming puzzle is defined by two functions, the problem f(solution, w vrg2-v ..) and the solution. f deffnne an algorithmic puzzle, and the solution solves this puzzle.
User:
You should pay a particular attention that the puzzle solved and only if **((solution) True"
Your role is to write a one or two sentence the description of the puzzle's goal (what the solution should be), remember that the solution that satisfy the goal must be given as the first argument of 'f.
You can start by: 'Find the solution: "arg solution" (describe its type shortly) that should (here you should speak about the solution: "arg solution" and how it should solve the constraints of the puzzle with respect to others args (describe their types shortly)) For example: 'Given a string 'str1', find the length of the longest substring without repeating characters. 'Given two sorted arrays 'nums1' and 'nums2' of size 'm' and respectively, return the median of the two sorted arrays.'
The puzzle is:
Assistant:
Skill labeling prompt
You are a helpful assistant Professor teaching a programming course in Python. The Professor want to give Pyhton programming puzzles to his Computer Science student to teach them Python.
User:
A Python programming puzzle is defined by two functions, the puzzle f(...) and the solution g...... defines an algorithmic challenge, and g solves this challenge. g solution to and only if f(g()= == True.
The Professor want to evaluate the diversity of those puzzles, can you label the following puzzle given the following list of topics, please?
The list of topics
skills list
The puzzle is:
Respond with two or three sentence explaining the topics used in the puzzle. Then summarize your response by giving list from 1 to 5 index corresponding to topics that actually used in the puzzle above in this format: 'The list skill use is: D where the list of index of the topics used the puzzle for example [3,5,6].
Assistant:
Solver prompt
You will be given function. Respond only code with a correct, efficient implementa- tion of the function. You will need to generate the correct solutions (g), for the Problem 2 that satisfies the condition f(g() True.
User:
Problem 0: def f(...
22

---

Solution 0:
def g(...
Problem def f(...
Solution 1:
def g(...
Now you need to give the solution (def g(..)) to the following Problem 2 that satis- fies the condition f()() == True.
Problem 2:
def f(...
Assistant:
Example Generation label
Puzzle to mutate:
from typing import+ def (n: int, 1st-['apple]] 'banana', 'orange', 'grape }] >>
bool:
"""Check if the given element is prefix of any element the 1ist ist
for word in 1st: if word (n) return True
return False
def g [lst=("applet) 'banana', 'orange', 'grape') )
return [1]
assert ())))
Assistant:
from typing import* import math
def f(n: int, 1st=[1, 2,
5]) -> bool:
"""Check if the given list contains any perfect square
number and if it is divisible by n. unn for num in 1st:
if math.iagrt (num) **2 - num:
return &
return False
deř g [1st=|11, 2, 3, 4, 511:
for num in 1st:
if math. isqrt (num) x22 num:
return num return None assert ((g())
23

---

ACES-ELM
70000
ACES
ELM-CVT
60000
ELM
StaticGen
50000
Llama-4058
Ba0ee-4400BAAEEELLM ACES-ELM
QD-score
Settral-aarge-2AAEES-LLL
40000
30000
20000
10000
1
1000
2000
3000
4000
5000
6000
Puzzles generated
(a)
Figure 5: (b) (QD) score updated figure with ACES-ELASE -LMM using state-of-the-ee
open weight LLM (Llama-3-405B and Mistral Large
Distribution of 10 Puzzle Difficulty Levels Over Generations
Difficulty
Difficulty [0, 10]
Difficulty score E [10, 20] Difficulty score E [20, 30] Difficulty [30,
Number Puzzles
80
Difficulty [40, 50]
60
Difficulty score E [50, 60] Difficulty score E [60, 70] Difficulty [70, 80) Difficulty 90] Difficulty score E [90, 100]
40
20
10
15
20
25
30
35
Generation
(a)
Figure 6: (e) Evolution Puzzle Difficulty Distribution generated by ACES: Decile Analysis of Generated Puzzles over generations.
24

---

Number of puzzie
10000
4000
5000
2000
String
Recursior
BF Search
Dynamic Greedy
backtrack.
Pattern
Sorting
Binard
Geometry
Optim.
Number
Array
Hashing
3
Number of skills
Skills
Number of puzzles
10000
4000
5000
2000
String
BF Search
Dynamic
Greedy
backtrack.
Pattern
Sorting
Binary.
Geometri
Optim.
Array
Hashing
3
Number of skills
Skills
Number of puzzies
10000
5000
5000
String
Recursion
BF Search
Dynamic
Graady-
ba backtrack.
Permut,
Pattern
Sorting
Binary
Geometry
Optim..
Array
Hashing
0
3
Number of skills
Skills
Number of puzzles
10000
5000
5000
String
Recursion
BF Search
Dynamic
Greedy
backtrack,
Set-
Pattern
Sorting
Binary
Geometry
Optim..
Array
Hashing
0
Number of skills
Skills
Number of puzzies RandomGen
10000
10000
String
secursion
BF Search Dynamic
Groady-
ba cackrackk
Permit
Pattern
Sorting
Binarg
Geometry
Optim.
Number
Array
Hashing
0
1
3
Number of skills
Skills
Figure 7: Distribution of labeled skills (left) and number of skills labeled (right) for all algorithms (rows).
25

---

dcopseck-oder--... 330-intuuu
dedgseek-coder-
CodeOwen1,55
deledd Spaud
ACED
A0E3
Homen
Ag3
Mostictonn
ACESEUM
6823
dorpseel-coder Bi-lnsttuct
Meta-Lhmma-3 3-88-Instruct
Meta-Elama-3-700 2ate--iiaa--------tteaee 107
80
40-
20
AGE5
RM
tart
AGd
mi cur
RM
RasiGGe
Horel
Aces
Wixtral-9s22B- wnstract-vo.....ooo
7Batral-BBinnstueee
codegemma-2bii
Soneed Apooud
2
Acea
Ra
Statteee
Howe
AGEEE
Rid
Hore
Bucn
tue
Stau of bet
Homen
Wistral-7Bilestruck-uo
ttrchat9-11bbye.
30
20-
10
Aces
ronor
RM
Stetteee
het
Alds
nuecor
REM
Pretecaon
lest
Figure 8: Pass I competence of various state-of-the-art problem solvers on existing benchmarks (HumanEval+ and P3 test) and on problems generated by our algorithms.
A.3
Semantic descriptor diversity
A.4
Performance Comparison
A.5
Heridity
A.6
Examples of generated puzzles
In this section, present few puzzles and solutions generated by our different methods and examine them qualitatively.
26

---

ACES-ELM (R2- 0.044818)
ACES (R2- (02-0.057748)
Difficuity score new puzzle
Difficulty score new puzzle
80
80
60
60
20
20
2.12225xx 47.2890
y-0 28.5107
Difficulty original puzzle
Difficulty original puzzle
ELM (R2=0,088 (R2-0.089553) 0095533)
ELM-CVT (82-0.075376)
100
100
Difficulty score new puzzle
Difficulty scare new puzzle
80
80
y-0.3003x-22.1096
40
40
20
20
Difficulty score original puzzie
Difficulty score original puzzie
RandomGen IR2=0.002182
Difficuity score new puzzle
60
40
20
Difficulty original puzzle
Figure 9: Evolution of the difficulty score from puzzles used as few-shot example generated puzzles based on those previous puzzles.
27

---

ACES-ELM
5.25
ACES
distance to target skills over time
5.00
4.75
4.50
4.25
4.00
3.75
1000
2000
3000
4000
5000
6000
Puzzles generated
Figure 10: Distance to target skills time.
Example generation for ACES
28

---

From typing import List def f (moves: List [List [int]], initial_state-(33 [3, 3, 2, 2, 3,
81) -> bool:
def bot_movell -> bool:
vals = (state, reverse=True)
i_largest index (vals
state(1_
max (vals(00 vals[l],
state initial_statel::
for (i, n) in moves:
assert < <= stateli], '1l [1llegal_ove
state[i] - if (state) return True
(0):
assert any (state), YYu lost!!
bot_move() def (initial_statee [3, 3, 2, 3, 81)
state = Initial_statell
moves = []
def bot_move() ():
bot takes objects from the largest heap make it match the second largest heap vais = (staed, zeverse=True)
i i_aagest = state.index (vais((01) state [t_arre__ - max [vals[0] vals[1], 1) # must take some, take in case of tie
largest heap
def losing (h) # return True if h is losing state xor 0
for i in xor ^=
return xor ==
def optimal_movell
assert not (state)
for range (1en (state)):
for n in range (1, stateli] + 1);
statelil - if losing moves. aoves.append(1. n])
return
state[i] +=
assert False, "Shouldn reachhhhhrare
while True:
move if max (state) == 0:
return
bot_move ()
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: While we do have broad motivations (open-ended problem generation), we make it clear in the abstract and intro that restrict ourselves programming puzzles with a certain format. We accurately report our main numerical findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The limitations of the approach are discussed in a separate paragraph in the Discussion (Section 5).
Justification:
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
30

---

Answer: [NA]
Justification: No theory.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We precisely detail the algorithms used, both our contribution and baselines, and provide all prompts used the appendix with all model ids. While should be possible to reproduce our data generation process from this information alone, the code is available com/ httpa//poppoooeoeeeea/eeeeeeeeee
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
31

---

reproducible, they 5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification: The code is available at
OpenELM/treed haaee////ttre//nnn-ggggiia. imgep-qdaif.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
public/ /wwp//euueeeeeeee Sulem ss ssionPoiccy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /nips... cc/ cccpublic// guides Cooeeoeeeuuue Submis a ciinooolli oiloyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All experimental details are shared in our Method and Result sections (seed dataset, temperature for generation, etc). The complete code will be released with the camera-ready version of the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Standard deviation is reported across seeds on our plots when appropriate.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
32

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We documented the specs of the machines on which we performed our experi- ments the beginning of our Results section. The computational costs of the development phase were not monitored, but we estimate they are negligible in comparison with the cost of our extensive experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https:/ /neuri ps cc/ppbllpcccccccccccccc c/ Ethi caGuidel inss?
Answer: [Yes]
Justification: We have reviewed the code of Ethics and do not find we have violated any principle our research.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss broader impacts in discussion section.
33

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not release any pretrained LLM, image generator, or scraped dataset.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We prominently use the P3 dataset and the Llama 3 open model which are properly credited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
34

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms of use the package should be provided. For popular datasets, papers swi thoode com/ datase has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [No]
Justification: The code released but not yet properly documented; we plan to add a cleaner version that is documented soon as possible.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
35

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "0YkfvXVRHN", "reviewer": "Reviewer_LkwK", "summary": "In this paper, the authors propose a method to automate the generation of challenging coding puzzles. By leveraging quality-diversity (QD) algorithms and defining novel metrics, their approach produces coding puzzles that are more diverse and challenging than existing benchmarks.", "questions": "- How the target cell get selected?\n- I don't fully understand the motivation behind the ablation using ELM with semantic categories. What does \"ablation of goal-directedness\" mean?\n- Since the approach did not include the training of LLMs, do the authors consider using more powerful LLMs like GPT-4 or Claude-3.5?\n- Which variant is the final proposed method? Is it ACES-ELM, ACES, or another variant?\n- Using visualization tools like t-SNE could be beneficial to show the distribution of generated coding challenges. It will be interesting to see the clustering of different skills being tested in these generated problems.\n- Figure 3(f) seems counterintuitive to me. Do the authors have any insights into why the proposed method generates either the most challenging tasks or very easy ones? What happens to the intermediate tasks? Is it the case that the model cannot generate them, or are they rejected after generation?", "limitations": "Limitations are addressed in the Discussion section", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The proposed algorithms and metrics have the potential to be significant and impactful. Generating diverse learning environments and measuring their diversity has been a major challenge for the community. The methods proposed in this paper represent valuable attempts to address these important issues.\n- The validation of the method is solid. For example, the quality of skill descriptors generated by an LLM is evaluated with human assessments, and extensive baselines and model variants are implemented and compared to demonstrate the effectiveness of the proposed method.\n- The proposed method generates more diverse and challenging coding puzzles, which could be highly beneficial for future studies on LLM coding agents.", "weaknesses": "### The presentation could be improved:\n- The authors might consider explaining QD and Map-Elites more clearly. While I am familiar with these methods and did not have difficulty, readers who are not as familiar with these topics might find them challenging to understand.\n- As someone familiar with related topics, I found the proposed method difficult to understand. My current understanding is that the difficulty metric is used as fitness, and two diversity metrics are two dimensions in the Map-Elites archive. Is this correct? Regarding embedding diversity, is it the higher the better (since it's more diverse)? If that is the case, does it make sense to use it as one dimension in the Map-Elites archive?\n- The authors might consider introducing the motivation behind their design choices before explaining them (e.g., P4, L128; the three metrics in Section 3.2). Additionally, for the paragraph at P5, L185, I don't fully understand how the design reflects the intuition.\n- There are some questions in the question section that I do not fully understand.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer LkwK for their thoughtful comments, and are glad they find the problem we study important, and the evaluation solid. We now aim to clarify some points in our response.\n\n> The presentation could be improved. \n\nWe thank you for this feedback. We have modified section 3.4 by being more precise when introducing Map-Elites.\n\n> My current understanding is that the difficulty metric is used as fitness, and two diversity metrics are two dimensions in the Map-Elites archive.\n\nThat is not quite correct, thanks for pointing out that the explanation is unclear. Fitness is the quality metric, and the archive is composed of cells corresponding to a maximum of 5 discrete programming skills (among 20).\n\n> Regarding embedding diversity, [...] does it make sense to use it as one dimension in the Map-Elites archive?\n\nWe have two diversity measures: skill (or semantic) diversity, which is the number of unique skill combinations present in the generated set, and embedding diversity, which is the average pairwise distance between puzzles in an embedding space. These measures are NOT dimensions of the archive. Embedding diversity, which is independent from semantic diversity (and computed with different models than the one used for generation/skill labeling), is used as an independent measure of diversity (since skill labeling is imperfect). The measures agree (see Figure 3).\n\n> The authors might consider introducing the motivation behind their design choices before explaining them.\n\nThank you for your suggestion! The reason for using P3 is twofold:\n* Code LLMs are a focus of the ML community, and for good reason. However, state-of-the-art models are getting so good as to mostly saturate today’s programming benchmarks (see also responses to Reviewer qqHU). Applying QD search with difficulty as a fitness metric is of obvious use there. We manage to create coding datasets that are challenging for current capable LLMs;\n* P3 is a relatively simple, language-based, open-ended domain where one can check the solutions exactly to compute how hard a task is (contrary to the tasks used in QDAIF [1]).\n\nAs for the metrics introduced in section 3,2:\n* **Difficulty**: creating challenging problems was our aim and is important. The reasons for the precise formulation are given in the response to reviewer ESVE, third response to questions.\n* **Skill diversity**: These dimensions of variation across puzzles are intuitive for humans and are useful for downstream applications (benchmark generation, and in possible future work, generation of programming exercises for students).\n* **Embedding diversity**: see previous response.\n\n### Questions:\n\n> How is the target cell selected?\n\nIn ACES (goal-reaching method), we select a cell uniformly at random among all possible cells, filled or otherwise (Section 3.3, second paragraph, as well as Figure 1). In ELM (mutation-based method), we select a cell uniformly at random among the ones that are filled (Section 3.4, first paragraph);\n\n> I don't fully understand the motivation behind the ablation using ELM with semantic categories. What does \"ablation of goal-directedness\" mean?\n\nELM selects an existing solution and applies an undirected mutation to it using the LLM-based mutation operator. ELM with semantic categories extends ELM by storing existing solutions in the skill-based archive introduced in our paper – and we show this improves performance compared to ELM using Voronoi cells. (It is also very similar to QDAIF). ACES replaces the undirected mutation operator by a goal-directed mutation: it first selects a target cell (empty or filled), then tries to fill it by prompting the LLM to generate a new problem characterized by the skills of the target cell. ACES-ELM also selects a target cell, but tries to fill it by mutating an existing puzzle; it is a goal-directed version of ELM. Our hypothesis was that goal-directed mutation is better than undirected mutation. Our hypothesis is confirmed in our experiments as niche coverage grows faster with goal-directed variants (ACES-ELM and ACES) than with non-directed variants (ELM, ELM-CVT). Additionally, the goal-directed variants also produce higher-difficulty puzzles: this might be due to the higher diversity of puzzles which allows the algorithm to find higher-difficulty puzzles as well, as is often the case in QD search. \n\n> [...] Do the authors consider using more powerful LLMs like GPT-4 or Claude-3.5?\n\nThe experiments are somewhat costly to run with the more expensive closed-source API models. We did experiments with the new Llama model and Mistral large 2 that are GPT-4 level (see general reply). See general reply for results.\n\n> Which variant is the final proposed method?\n\nBoth methods exhibit minor variations and yield comparable results. Given that ACES-ELM demonstrates a slight edge in diversity and difficulty, we recommend it as the preferred variation of the method. We have updated section 3.3, and section 3.4, to reflect this.\n\n> Figure 3(f) seems counterintuitive to me. Do the authors have any insights into why the proposed method generates either the most challenging tasks or very easy ones?\n\nWe are not sure. In the beginning of training the only puzzles generated are the easy ones (difficulty close to 0); as generation progresses with ACES, a larger and larger proportion of puzzles are close to maximum difficulty (See new results, Figure 1 (e)). We instruct the model to generate only puzzles of the highest difficulty, by including difficulty scores of the few-shot examples in the prompt. One possibility is that this works so well that it heavily skews the distribution of difficulties. Another explanation could be that we heavily skew sampling of example puzzles based on their difficulty score, leading to creating of puzzles with similar difficulties. \n\n[1] Quality-Diversity Through AI Feedback, Bradley et. al. 2023", "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": "", "extra_scores": {}}, {"review_id": "HACPgTDHQB", "reviewer": "Reviewer_qqHU", "summary": "This paper proposes Autotelic CodE Search (ACES), a method to generate diverse and challenging Python programming puzzles using state-of-the-art generative models. ACES optimizes for both the diversity and difficulty of problems by representing them with semantic descriptors that describe the programming skills required to solve them and measuring difficulty empirically with the pass rate in 50 tries. The method iteratively prompts a large language model to create new puzzles, using previously generated related ones as few-shot examples. ACES outperforms baseline methods, producing puzzles that are more diverse and three times more challenging than existing Python benchmarks, paving the way for automated curriculum learning and scientific discovery.", "questions": "1. Why there are 21700 niches in total? If we combine these tags in various ways, we should be able to come up with $2^{20}-1$ niches.\n2. Some typos: Tesla V100 SXM2 32 Go (GB?), Appendix Section! A.2.\n3. Can the authors test the generated tasks on closed-source LLMs like GPT (it is okay to say no)?", "limitations": "The authors have discussed the limitations well.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The method is reasonable and the experiment results are promising, showing the advantage of this method.\n2. The method proposed appears to be a general approach that can be extended to fields beyond code generation, as long as semantic descriptors can be set.\n3. I believe that automatically generating benchmarks to test the shortcomings of large language models is a meaningful research direction.", "weaknesses": "1. How do the results differ when using different models as solvers? In this paper, the difficulty is measured by how easily tasks are passed by the Llama-3-70b model, making Llama-3-70b an extremely important model for evaluating the capabilities of other models. Any model that does not perform consistently with Llama-3-70b is considered unable to pass certain tasks. Although the authors claim that \"There is a clear correlation between solver performance across different problem sets, which indicates that tailoring problem generation to a specific model (Llama-3-70b) generates problems that are challenging for other models too,\", it seems that this is actually just an assumption. In other words, the authors cannot explain whether the top left corner in Figure 4 (b) is overfitted to HumanEval or simply inconsistent with the Llama-3-70b model. One way to solve this is to present results on more solver models.\n2. How does the author ensure the correctness of the generated test program $f$ (i.e., that the test program and the natural language description of the puzzle are consistent)? A problem can become very difficult if $f$ and the natural language description are inconsistent, and manual checking is challenging to cover all 6400 problems.\n3. Some parts are not clear. (1) I'm confused about which one is your final method, ACES or ACES-ELM? It seems that ACES-ELM is an ablation of ACES (Section 3.4) but it is taken as the main method in experiments like  Figure 4(b). (2) In section 4.2, what do these numbers (F1 scores) represent and which method should they be compared with? I think adding a baseline would help explain this better.\n4. This paper evaluates the quality of the benchmark based on diversity and difficulty (which is actually the passing rate of the LLM, rather than an objective difficulty). However, I believe that difficulty is just one of the criteria for evaluating a benchmark, and this approach is somewhat one-sided. Other criteria, such as whether the benchmark meets practical usage needs (like HumanEval, which is manually designed to ensure that these programming tasks do not appear in the training set and are commonly used in real scenarios), or whether the benchmark covers a broader range of scenarios (like DS-1000, which targets scientific computing scenarios), are also important evaluation standards.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer qqHU for their review. We thank the reviewer for pointing out the experiments are promising, the research direction interesting, and for noting the method is general and applicable to other domains beyond code. We hope to address the reviewer’s concerns.\n\n> How do the results differ when using different models as solvers? [...]\n\nWe have performed additional experiments with Llama 405B and Mistral Large 2. For each new experiment, the LLM is used to generate puzzles, label skills, and to measure difficulty. See the pdf attached to the main response, notably Figure 1 (a), (b) and (c). The results present evidence of transfer of puzzle difficulty across models: models that have low scores on our datasets generated with Llama 70B also have low scores on the datasets generated by Llama 405B and Mistral, as well as on LiveCodeBench [1] (specifically built to avoid contamination) and BigCodeBench [2]. Figure 1 (a) shows that only HumanEval escapes this correlation, suggesting high levels of contamination or models (especially the small ones) optimized to perform well on that benchmark. We have plotted the correlation between scores on all datasets (averaged over models) in Figure 1 (b). The correlation between all dataset scores, save for HumanEval, is clearly visible. We hope this answers your concerns on overly relying on a single solver. As additional evidence, we find good correlation between model size and overall performance on our datasets as well as LiveCodeBench and BigBench, which is what one would expect if coding capability was monotonically and smoothly related to model size.\n\n> How does the author ensure the correctness of the generated test program [...]\n\nWe agree that it is not feasible to manually ensure consistency of the generated puzzles.\nFor now we limit ourselves to ensuring the puzzle has at least one solution, and we generate the description from the puzzle and the solution using a specialized prompt. To increase puzzle-description consistency, we could additionally use a critic LLM, or use human labels as guidance. We also note that for the original P3 dataset, usually the description of puzzles are not given to models (see here https://github.com/microsoft/PythonProgrammingPuzzles/blob/main/notebooks/Intro.ipynb).\n\n> Some parts are not clear. (1) I'm confused about which one is your final method, ACES or ACES-ELM?\n\nACES-ELM is a goal-directed quality-diversity method (as in ACES, we target a cell and instruct the model/choose the examples to be able to reach it), thus not really an ablation. We agree that the presentation could be better (we presented it after ELM because it uses the same mutation mechanism). Because they are goal-directed methods and exhibit similar performance we consider both methods to be our final methods. We changed section 3.3 and 3.4, where we present ACES and ablations respectively, to reflect this.\n\n> In section 4.2, what do these numbers (F1 scores) represent [...]?\n\nThese correspond to skill labeling performance compared with a human-labeled ground truth, considered as a per-skill binary classification process. More precisely, for each puzzle, we have a set of ground-truth human labels. This gives us a classification problem with binary labels (is present, not present) for each skill index. To provide a random classification baseline one could do the following: for each of the 60 puzzle instances we manually assigned labels to, randomly assign 1 to 5 skills and compute the precision $p_0$, the recall $r_0$ and the f1 $f_0$. With 20 random draws of this random classifier we get $p_0 = 0.13$, $p_0 = 0.14$ and $f_0 = 0.12$ on average; well below the LLM judge’s performance. We added a footnote with this result.\n\n> [difficulty] which is actually the passing rate of the LLM, rather than an objective difficulty\n\nUnfortunately we cannot be much more objective than this, and this measure of difficulty is related, in any case, to the metrics the community uses to evaluate code models. We could average on a family of LLM to get an estimate of the difficulty of a puzzle, for LLMs in general. If we want to get difficulty estimates for humans, which might be quite different, there is unfortunately little practical way to collect a large scale dataset to e.g. train a classifier. Any idea you would have is of course welcome!\n\n> However, I believe that difficulty is just one of the criteria for evaluating a benchmark, and this approach is somewhat one-sided.\n\nWe agree! We realize that there is much more than difficulty in a good puzzle. HumanEval was a well-crafted dataset and large amounts of human labor was needed to make a benchmark of this quality. It is now commonly accepted that HumanEval is present in the LLM’s train sets, making the results on this benchmark potentially unreliable. We believe that in the future, synthetic benchmarks will be an important part of LLM evaluation (but not all of it), in the spirit of how chatbot competitions and GPT4-judged responses are used to inform our current evaluations of LLMs. With this work we make a step in this direction, by showing that leveraging insights from the evolutionary computing and intrinsic motivation literature we can optimize for datasets with low pass rate and coverage in a predefined skill space.\n\n### Questions\n\n> Why there are 21700 niches in total? \n\nWe limit to 5 skills max, to avoid targeting puzzles with unrealistic skill combinations.  ($\\sum_{k=0}^{5} \\binom{20}{k} = 21700$) We forgot to report this detail, we have added it in section 3.2.\n\n> Can the authors test the generated tasks on closed-source LLMs like GPT (it is okay to say no)?\n\nSee our results with large open models. \n\n[1] LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code, Jain et. al. 2024\n\n[2] BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions, Zhuo et. al 2024", "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": "", "extra_scores": {}}, {"review_id": "mVXLTZVknC", "reviewer": "Reviewer_NuHw", "summary": "The authors propose Autotelic CodE Search (ACES) to generate programming puzzles, considering diversity and difficulty, borrowing ideas from intrinsic motivation and evolutionary search, relying on the assistance from LLMs for problem representation, skill label generation, diversity characterization, difficulty evaluation, and puzzle generation. \n\nThe authors conduct experiments to study quality of LLM-generated skill labels, and compare diversity and difficulty of the generated puzzles with existing methods and benchmarks.", "questions": "Line 2,\n\"We propose a method that aims to automate this process by harnessing the power of state-of-the-art generative models to produce a diversity of challenging yet solvable problems, here in the context of Python programming puzzles.\"\n\n\nThe proposed approach relies on LLMs for problem representation, skill label generation, diversity characterization, difficulty evaluation, and puzzle generation. \nThe proposed approach does not provide a mechanism to improve the current imperfect LLMs, so that it does not close the loop.\n\n\nLine 30,\n\"It would provide the necessary curriculum for open-ended learning machines [Colas et al., 2022] and may be a key component of automated scientific discovery [Grizou et al., 2020, Etcheverry, 2023].\"\n\nSimilar to above, the feedback loop is not closed, so it is an over-claim. \n\n\nThis can be estimated by computing the empirical difficulty of a puzzle for a particular\n39 solver: out of 50 attempts, the solver should solve the problem at least once (solvability) but as rarely\n40 as possible (difficulty).\n\n\nLine 44\n\"The standard approach for problem generation simply queries pretrained generative models with few-shot examples or specific instructions [Haluptzok et al., 2022, Honovich et al., 2023, Gunasekar et al., 2023].\"\n\nWhy is it the standard approach? There are some papers working this way does not make it the standard way.\n\n\nLine 134,\n\"Both datasets are pre-filtered to examples shorter than 1024 tokens to accommodate for limited context windows in LLMs.\"\nThis is an unnecessary limitation due to relying on LLMs.\n\nLine 147,\n\"Puzzles for which no solution is found are considered invalid and are discarded.\"\nThis is problematic, at least, not ideal.\nLine 202,\n\"If the puzzle is not solved by the solver model in 50 attempts, it is considered unsolvable and discarded.\"\nIt is the limitation of current LLMs, and the authors do not propose a mechanism to overcome it.\n\nLine 150,\n\"this difficulty-based metric measures a ground-truth objective: how hard a given puzzle is for a target LLM solver\"\nIt is not ground-truth: LLM solvers are not perfect, so some measure wrt an LLM is not a ground-truth.\n\n\nLine 151,\n\"Our experiments found that this difficulty measure mostly transfers across models: a puzzle that is harder for one model is often harder for others (see Section 4.4).\" \n\nThis may not say much about transferability, since most LLM models were built with similar methods.\n\n\nLine 164,\n\"We sample our 20 tags from a larger list generated by an LLM (GPT-4-0125)\"\n\nUse an imperfect LLM, namely, GPT-4, as reference has inherent limitations. \n\n\nLine 194,\n\"to drive discovery of puzzles with novel skill combinations, we rely on the LLM recombining elements from puzzles close to the target cell along with very often selecting target cells without any representatives.\"\nAgain, limitations of current LLMs.\n\n\nLine 335,\n\"We expect that progress along the three lines can be made by harnessing the increasing capabilities of future language models and will automatically translate into higher performing autotelic generative models of problems.\"\nIt is not reasonable to postpone the development of key components of a proposed approach to something the authors do not have control of, in particular, \"future language models\".\n\n\nLine 354,\n\"In artificial intelligence, one could envision a self-play loop where a learning agent iteratively generates a diversity of problems maximizing its current learning progress (quality metric), then trains on them to augment its competence [Sukhbaatar et al., 2017, Silver et al., 2017, Colas et al., 2022].\"\nThis is an overclaim and it is misleading.\nIt replies on imperfect LLMs and do not attempt to improve them.", "limitations": "The authors do not discuss enough the limitations of reliance on imperfect LLMs, and do not propose to improve imperfect LLMs.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "+ generate diversified and challenging programming puzzles\n+ borrow ideas from intrinsic motivation, in particular, the autotelic property, and evolutionary search, in particular, Map-Elites, an evolutionary quality-diversity (QD) method\n+ conduct experiments studying quality of LLM-generated skill labels, and comparing with existing methods and benchmarks", "weaknesses": "- rely too much on LLMs\n- follow a questionable approach\n- overclaim\n\nI am aware there are quite some papers following the framework of \"self-generation, self-evaluation, and self-improvement, relying on one or more LLMs\", some of them in the name of LLM-based agent or agentic AI.\nThis approach has a fundamental issue: no current LLM is perfect, so LLMs may make mistakes, and usually there is no mechanism to improve current LLMs in such framework.  \n\nAs a result,  I vote to reject the paper, although it has merit, in particular, the idea for prompting diversity in generating programming puzzles and decent experimental results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and hope to be able to convince them that our assumptions are sound.\n\nReviewer NuHw seems to reject the possibility of leveraging LLMs in any kind of systems, based on the fact that LLMs are sometimes wrong. That LLMs are not perfect at any of the tasks we use them for is of course true, but that does not prevent us from using them in a useful way (here to build diverse sets of puzzles to evaluate itself and other models).\n\nFor each of the components we use LLMs for, they clearly outperform other available options:\n\n* For puzzle generation, other program synthesis methods would hardly give interesting, human-relevant programming puzzles;\n* For measuring diversity (creating niches for our QD algorithm), we tried using voronoi tessellations as is usually done in high-dimensional Map-Elites [1], but it works less well than the skill labels using the LLM (compare ELM-CVT with ELM, Figure 3) and it is less interpretable. The skill labeling performance itself is not so bad, see responses to reviewer qqHU, and section 4.2.\n* For measuring difficulty we need to use LLMs as solvers, since that’s the measure of difficulty we want to measure (and it is linked to pass@k, the measure of success on coding datasets);\n\nIn addition to these considerations, we add checks to ensure our generated puzzles make sense (rejecting puzzles with no solution, see also Section 3.3). We use several measures of diversity, and difficulty with respect to different models, to make sure our evaluations are sound. Can the reviewer provide a more specific description of LLM limitations that would make our approach unsound? What alternative could be considered to implement the puzzle generation, measure diversity or difficulty here?\n\n> overclaim\n\nThe reviewer cites excerpts of our motivation and conclusion and seems to consider we claim these as parts of our contribution, which they are not. Our contributions are listed in the last paragraph of the intro, at the end of the abstract, and at the beginning of our conclusion. \n\n### Questions\n\nWe reply to the reviewer’s comments here, but some of them are not really questions. It would be helpful and constructive for the reviewer to be more specific in their remarks; often the perfectness of LLMs is attacked, and we agree these models are far from perfect; however if alternative methods or fields or studies were mentioned it would help us write more targeted responses.\n\n> The proposed approach does not provide a mechanism to improve the current imperfect LLMs, so that it does not close the loop.\n\nWe do not propose to directly improve LLMs in this paper; not every paper needs to directly improve LLM state of the art. We simply present methods for generating diverse and challenging datasets, and argue that they could be used to evaluate LLMs in the future. Evaluating LLMs on challenging datasets is part of the process leading to their improvement. (and we confirm by the way that combining evolutionary methods with LLMs is fruitful, as was demonstrated in FunSearch [2] or QDAIF [3] among others). Our additional experiments demonstrated that our method significantly enhances the performance of current \"imperfect LLMs.\" The LLM fine-tuned on our approach-generated archive outperformed the base model by a substantial margin, even surpassing larger models.\n\n> Similar to above, the feedback loop is not closed, so it is an over-claim.\n\nThis is part of the motivation of the paper (beginning of the introduction), not its contributions.\n\n> Why is it the standard approach? There are some papers working this way does not make it the standard way.\n\nIt is the standard approach insofar few-shot prompting is a common method for generating domain-specific data with LLMs. If you have another idea/method in mind, we would be interested in hearing about it.\n\n> [on discarding unsolvable puzzles] This is problematic, at least, not ideal.\n\nWe agree that this is less than ideal (see also our response to reviewer ESVE) but we have no principled method for determining whether a puzzle is solvable without generating a solution ourselves. We are of course very open to additional suggestions here.\n\n> This may not say much about transferability, since most LLM models were built with similar methods.\n\nWe report an observation here. This is also confirmed in our new experiments. As for non-LLM solvers, we do not know but consider it interesting to correlate difficulties of puzzles across solver types (and humans).\n\n> [on generating the initial list of skills] Use an imperfect LLM, namely, GPT-4, as reference has inherent limitations.\n\nAs always we agree. That is why we filter the set afterwards to make sure the skills make sense. The alternative is to generate the list ourselves, based on puzzle categories in algorithm books and programming contests. In practice both methods (we tried both) led to very similar lists.\n\n> \"to drive discovery of puzzles with novel skill combinations, we rely on the LLM recombining [...]\" Again, limitations of current LLMs.\n\nCould you be more specific?\n\n> It is not reasonable to postpone the development [...]\n\nThis is not what we meant in L338 (conclusion). We stated that the approach probably scales as the LLMs become better (this is a good property of the method). We confirm this in our new experiments.\n\n> \"In artificial intelligence, one could envision a self-play loop [...]” This is an overclaim and it is misleading. It relies on imperfect LLMs and do not attempt to improve them.\n\nThis is one of our last paragraphs and is future work/discussion! We do not claim to instantiate a self-play loop in this paper.\n\n[1] Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm, Vassiliades et. al. 2016\n\n[2] Mathematical discoveries from program search with large language models, Romera-Paredes et. al. 2023\n\n[3] Quality-Diversity Through AI Feedback, Bradley et. al. 2023", "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": "", "extra_scores": {}}, {"review_id": "CEqEptz49g", "reviewer": "Reviewer_ESVE", "summary": "The paper presents Autotelic CodE Search (ACES), a method for generating diverse and challenging Python programming puzzles using state-of-the-art generative models. Inspired by Quality-Diversity, ACES aims to automate the problem generation process by optimizing for both diversity and difficulty. ACES iteratively prompts an LLM to generate puzzles by using previously generated problems as in-context examples. The generated puzzles are more diverse and challenging than those produced by baseline methods and existing benchmarks, as evaluated across 11 state-of-the-art code LLMs.", "questions": "- What are the practical applications of this framework? Why is generating diverse and challenging puzzles an important problem to address?\n\n- I am uncertain if the difficulty measure is appropriate. I would expect the difficulty measure to be very close to 0 for problems that the target LLM solver cannot solve and very close to 100 for problems it can solve, with almost nothing in-between. Can you provide more details on this aspect?\n\n- What does the shaded area represent on the graphs?\n\n- I don't understand Figure 3(f). The x-axis represents fitness rescaled between 0-100, but what does the color signify?\n\n- OMNI-EPIC [1] utilizes a task archive in a manner similar to your puzzle archive. I believe you should cite this paper to acknowledge the related work appropriately.\n\n[1] OMNI-EPIC: Open-endedness via Models of human Notions of Interestingness with Environments Programmed in Code\n\n# Minor Corrections\n\nL167: There is an inappropriate exclamation mark in \"Appendix Section! A.2.\"", "limitations": "Yes, the authors adequately addressed the limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "- The presentation, writing and clarity of the paper are great.\n\n- The method creatively combines evolutionary algorithms (especially Quality-Diversity algorithms) with LLMs to generate programming puzzles that are both diverse and challenging.\n\n- The proposed approach is simple and effective at generating a diversity of challenging puzzles. Experiments showed that ACES generates problems that are both more diverse and more challenging than the ones generated by existing generative approaches or the ones found in human-curated benchmarks.", "weaknesses": "- My main concern is about the contribution. What are the practical applications of this framework? Why is it valuable to generate a diversity of challenging puzzles? Demonstrating some downstream tasks would be helpful to justify the importance of generating diverse and challenging puzzles. For example, showing how fine-tuning a model on the newly generated data can improve performance would provide a clear motivation.\n\n- The paper states, \"Puzzles for which no solution is found are considered invalid and are discarded.\" I believe this is a limitation because the primary goal of generating new data is likely to enhance training. By only considering puzzles that the target LLM solver can solve, we limit the difficulty of the generated puzzles. This, in turn, restricts the potential benefits of using this new data for training and improving models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank Reviewer ESVE for their review, and especially for appreciating the clarity of the paper, and the simplicity and effectiveness of the method. We hope to be able to convince them of the promise of the method for practical applications.\n\n> What are the practical applications of this framework?\n\n* Generality of the framework. We understand that the formulation of our aims in this paper might seem a bit general (creating sets of diverse and difficult problems) but the applications are quite promising in our opinion! First, ACES transfers to any domain where solutions to problems can be exactly evaluated and where LLMs already have knowledge of several categories of problems (as also noted by Reviewer qqHU). This includes important tasks like formal math or RL environments that can described with code.\n\n* Creating benchmarks. Within the domain we have chosen (programming puzzles), the target task we have in mind for ACES is creating LLM evaluation sets. There are other considerations when creating a benchmark than difficulty and diversity, but getting these right is a necessary condition for it to be useful. Distilling our generated sets into trusted benchmarks usable by the community would require some additional curation, but we believe it to be well within reach.\n\n* Creating finetuning data. In our additional results (Figure 1(d)) we present results of finetuning models with our generated data (see also general response). On tests sets created with a mixture of StaticGen and ACES-ELM data, finetuning on (distinct) ACES-ELM generated data yields strong and consistent improvements compared to finetuning on (distinct) StaticGen-generated data. This is good evidence of increasing capabilities when finetuned on our data.\n\n* Generating open-ended tasks is an important goal in itself. This is precisely the aims of open-ended exploration algorithms (such as OMNI-EPIC you mention later). ACES belongs to that line of works, applies it to an important domain, and contributes algorithmic improvements. Reviewer LkwK also notes that this is an important fundamental topic in itself, beyond the practical applications.\n\n> [...] I believe this is a limitation because the primary goal of generating new data is likely to enhance training.\n\nWe agree! This is a limitation of our current difficulty measure and have added additional discussion in the Limitations section of the paper. This kind of difficulty metric is used to train open-ended agents in other settings. For instance, in Goal-GAN [1], a goal-conditioned RL agent targets position goals that are difficult but solvable, since unreachable positions usually give no feedback at all. This approach is widespread in intrinsically-motivated RL [2, 3]. In the classic case of self-play, the opponent provides feedback by being neither too easy nor too hard to beat by construction. For ACES to implement similar dynamics (and lead to the discovery of puzzles that are truly unsolvable from the point of view of the solver we start with yet solvable in general) one should finetune the solver as the data gets generated. This would not require modifying the difficulty metric we use. We have added additional discussion in the Discussion section.\n\n### Questions\n\n> I don't understand Figure 3(f).\n\nYou are right that this figure could be clearer. This is a figure representing the distributions of difficulties, in discrete fitness bins, for each method, at the end of the generation process. The color represents the number of puzzles whose difficulty falls into each bin (color histogram). The takeaways from this figure are that these distributions are quite peaked towards 0 and 100 and that ACES and ACES-ELM have bigger peaks towards 100 than StaticGen and ELM.\n\n> I am uncertain if the difficulty measure is appropriate. [...] Can you provide more details on this aspect?\n\nWe first recall that high difficulty/fitness (close to 100) corresponds to hard problems (solved once out of 50), and difficulty close to 0 corresponds to easy problems (solved 50 times out of 50).\nThe motivation for this metric comes from observations around pass@k. Pass@k was introduced in the Codex paper [4] and measures the proportion of puzzles which have at least 1 solution found in k solver attempts. It has become a standard measure for evaluating code (or math) models. The interesting part is that as you increase k (with nonzero temperature), pass@k continues increasing logarithmically with k (see [5], Figure 7 for instance). Repeatedly sampling from your LLM is usually an effective, but costly, way of getting solutions to hard problems [6, 7]. To recap: puzzles do not neatly fall in solvable/unsolvable categories; some of them are solved only once every 50 attempts on average. These are the kinds of puzzles we want to generate.\n\nIn our experiments, as outlined in our previous comment, the difficulty distribution is close to 0 for the StaticGen dataset and for ACES a second peak around 100 appears and grows. Of course, we are open to suggestions for improvement of the difficulty metric.\n\n> What does the shaded area represent on the graphs?\n\nThey represent standard deviation, each experiment is repeated 3 times with different seeds.\n\n> OMNI-EPIC [1] utilizes a task archive [...]\n\nOf course! Thanks for pointing this out. We have added the reference.\n\n[1] Automatic Goal Generation for Reinforcement Learning Agents, Florensa et. al. 2017\n\n[2] Learning with AMIGo: Adversarially Motivated Intrinsic Goals, Campero et. al. 2020\n\n[3] Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play, Sukhbaatar et. al. 2017\n\n[4] Evaluating Large Language Models Trained on Code, Chen et. al. 2021\n\n[5] Language Models Can Teach Themselves to Program Better, Haluptzok et. al. 2022\n\n[6] Mathematical discoveries from program search with large language models, Romera-Paredes et. al. 2023\n\n[7] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, Brown et. al. 2024", "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": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their reviews and the time they spent reading the paper, and we hope this rebuttal and the discussion period will be productive, answer questions and overall lead to a better paper.

There are two ways to read this paper, depending on which background one has. The takeaways from the paper will be slightly different in each case.

* **For general machine learning readers with an interest in (code) LLMs**, the contribution of this paper is showing that one can use a measure of puzzle difficulty – as well as LLM judgements of which programming skills are required to solve a puzzle – to create sets of hard and diverse programming problems. We envision this as a step to creating new programming benchmarks for code LLMs. Reviewer ESVE worries about the application of the method, but we think the contribution to generating difficult synthetic benchmarks is quite clear, as Reviewer qqHU also notes in his comments. Reviewer NuHw rejects the approach on the basis that it is built on LLMs, but we note that generating challenging evaluation sets is an instrumental application to create better LLMs in the future.

* **For readers interested in open-ended search**, we present algorithmic improvement over LLM-augmented map-elites (ELM), the baseline method that is extensively used in other papers [1, 2, 3]. We build a goal-directed algorithm that explicitly targets potentially empty cells, instead of using random mutation like Map-Elites-inspired approaches, and we demonstrate that this is helpful. Importantly, the goal-directed property of ACES comes from 1) the few-shot abilities of LLMs, to create a puzzle that resembles puzzles chosen near the target cell and 2) their instruction-following abilities, to create a puzzle in the desired cell (with the right skill combination). The goal-directed evolutionary algorithm underlying ACES could not be implemented without LLMs; this algorithmic improvement takes full advantage of the use of instruction-following LLMs, with few-shot abilities, as mutation operators. 

We present a series of complementary results in the attached pdf.

### Results with different models 
To respond to Reviewer qqHU’s concerns of over-reliance on a single model, and to calls by Reviewers LkwK, qqHU to use bigger, state-of the art models, we performed additional experiments with the new Llama 405B model and Mistral large 2, models on par with GPT-4. Using those LLMs leads to a better Quality-Diversity score overall, up to 25.6% for Mistral Large and 12.3% for Llama 405B (using Llama 405B and Mistral large 2 both for the difficulty metric and skill labeling). This demonstrates how ACES scales with models of higher size. Evaluating Mistral Large on the dataset generated by Llama 405B, as well as the other way around, we find pass@1 scores of 56.7% and 58% respectively. This demonstrates the effectiveness of our method in generating a challenging benchmark, even for state-of-the-art models, as well as the fact that difficulty measures transfer across models of similar capabilities.

Examining the archive generated by Llama-3-70B with ACES-ELM, Mistral Large 2 achieved a 70% pass@k (74% for Llama-3-405B), while Llama-3-70B has a pass@1 of 36.8%. This demonstrates Mistral-Large and Llama-405B's superior performances as solvers. However, even with these state-of-the-art models, the benchmark generated by Llama-3-70B is not saturated, as there is still approximately 30% room for improvement to fully solve it.

### New finetuning results
To address concerns of Reviewers ESVE and NuHw about applications and model improvement, we performed experiments with finetuning. We finetuned the Llama-3-8b model using datasets generated by WizardCoder (variant of the state of the art method WizardLM for generating synthetic data [4]), StaticGen (established baselines), and our proposed ACES-ELM method.  We then evaluated the model's performance using the greedy pass@1 metric on a series of test sets. These test sets were equally composed of puzzles from our method and StaticGen with increasing difficulty levels (k value in the Figure 1.d), generated using a different seed than the training data. 

The results of this experiment, illustrated in Figure 1.d, reveal several findings that highlight the superiority of ACES-ELM. On the most challenging test set, the Llama-3-8b model finetuned with data generated by ACES-ELM achieved a remarkable pass@1 score of 53.3, significantly surpassing both baseline methods and also outperforming the Llama-3-70B model. This demonstrates the effectiveness of our ACES-ELM method in generating high-quality training data that enables models to tackle more complex coding tasks.
While the Llama-3-8b models fine-tuned with WizardCoder and StaticGen showed improvements over the baseline Llama-3-70B model (achieving pass@1 scores of 49.4 and 41.6, respectively), they consistently underperformed compared to the ACES-ELM-trained model. This underscores the superior quality of the training data generated by ACES-ELM. Moreover, as evident from Figure 1.d, the performance gap between ACES-ELM and the baseline methods becomes more pronounced as the difficulty level of the testset increases. This suggests that ACES-ELM is particularly effective in preparing models for more complex coding challenges.

---

We think we have clarified all the points the reviewers have raised and responded to concerns regarding the contribution, applications and generality of our method. We thus kindly ask reviewers to raise their grade if they feel their concerns have been addressed or otherwise provide detailed requirements that would convince them to do so.

[1] Evolution Through Large Models, Lehman et. al. 2023

[2] Quality-Diversity Through AI Feedback, Bradley et. al. 2023

[3] Rainbow Teaming: Open-Ended Generation of Diverse Adversarial Prompts, Samvelyan et. al. 2024

[4] WizardCoder: Empowering Code Large Language Models with Evol-Instruct, Luo et. al. 2023

Meta-review: This paper presents a new method for automatic generation of challenging and diverse coding puzzles, which could be an important step towards open-ended improvement of LLMs. After discussion, 3/4 reviewers have voted for acceptance, with one reviewer strongly opposing acceptance. The main arguments given in favor of acceptance are that the method is interesting and novel and has high potential for impact. Reviewers also noted the solid validation and clear presentation. The authors have engaged thoroughly with all reviewers and addressed most concerns.

One reviewer (NuHw) remains skeptical, since the work relies too much on LLMs (which are unreliable) and follows a questionable approach (since the generated test functions could be wrong). This reviewer is generally skeptical about work that builds on LLMs, and believes that evaluation of code based on testing is inherently flawed, and formal verification is required.

In my opinion, the most important criticism is the validity of the generated test functions. Here I think the authors have done a good job addressing this concern. Specifically, if we take the generated test function f to *define* the problem, there is no way in which it could be invalid. By definition, a function g solves the problem if f(g()) == True. The question of whether f corresponds to some text description is secondary, since the text does not formally define the problem, and need not be passed to the LLM that is being evaluated. Thus I do not agree that the method is dubious.

Given that the majority of reviewers agree the paper is worth accepting, and the rebuttal of all significant criticisms by the authors, I recommend for this paper to be accepted at NeurIPS.
Decision: Accept (spotlight)