ACES: Generating a Diversity of Challenging Programming Puzzles with Autotelic Generative Models

Authors: julien  pourcel
gaia  molinaro
pierre-yves  oudeyer
laetitia  teodorescu inria
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 19:03:51

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.

Main paper: 
 introduction: 
 Humans are not only talented problem solvers, they are first of all remarkable problem generatorsgenerating endless streams of new problems for themselves and others Chu and Schulz [2020] , Molinaro and Collins [2023] . We set build problems for others to learn, set challenges to ourselves, [Burton and Hiron, 2008] , aggregate problems to train and test AI models [Hendrycks et al., 2020 , Chen et al., 2021] , and come up with new problems that drive innovation in art and science [Gromov, 2018 , Chu et al., 2024] . This intrinsic drive to generate problems for oneself -the autotelic propertyhas further been argued to 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 problem-generation 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 al. [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 et al., 2022] and may be a key component of automated scientific discovery [Grizou et al., 2020 , Etcheverry, 2023] .We propose to leverage machine learning -a set of tools usually targeted at solving problems -to automate the generation of a diverse set of interesting problems, here in the domain of Python programming puzzles. Programming puzzles indeed represent an open-ended space of problems to Figure 1 : 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 an LLM solver tries to solve 50 times (2). If never solved, the puzzle is 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 a puzzle for a particular solver: out of 50 attempts, the solver should solve the problem at 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 a 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. [Mouret and Clune, 2015] , an evolutionary quality-diversity (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 high-dimensional objects that we chose to represent by the set of programming skills required to solve them -a high-level semantic description space that better captures intuitive notions of puzzle diversity than pretrained embedding representations. We obtain these by asking a large language model (LLM) to label each problem a set of skills from a list of 20 possible ones. Just like Map-Elites, ACES maintains an archive of generated outcomes grouped by skill sets (descriptor niches) and optimizes quality (here difficulty) locally within each niche. While Map-Elites randomly mutates solutions sampled from the archive in hopes of discovering a new niche or finding higher-performing solutions, ACES performs an explicit goal-directed exploration [Colas et al., 2022] . At each iteration, ACES targets a goal descriptor, carefully selects relevant and challenging example problems from the archive and, conditioned on these, prompts an LLM to generate a more difficult 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 are harder to solve than those found in existing Python programming benchmarks, this for all the 11 state-of-the-art LLM-based problem solvers we tested. Whereas the HumanEval+ benchmark is starting to saturate (GPT-4-turbo achieves a pass@1 of 86.6%, CodeQwen1.5-7B-Chat 78.7%, [Liu et al., 2024] )1 , the best solver (Mixtral-8x22B-Instruct-v0.1) only achieves a pass@1 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. 
related work: 
 Open-ended exploration algorithms Our puzzle-generating method is at the intersection of two research lines: evolutionary computing [Lehman and Stanley, 2011a ,b, Mouret and Clune, 2015 , Pugh et al., 2016 , Cully and Demiris, 2018a , Lehman et al., 2022] and intrinsically-motivated learning [Baranes and Oudeyer, 2013 , Etcheverry et al., 2020 , Forestier et al., 2022 , Colas et al., 2022] . Beginning with novelty search [Lehman and Stanley, 2011a,c] , the evolutionary approach to exploration expanded with the invention of quality-diversity algorithms [QD: Lehman and Stanley, 2011b , Mouret and Clune, 2015 , Cully and Demiris, 2018a] , a set of methods striving to evolve a diverse population of locally-performant solutions via the undirected mutation of existing solutions. A parallel line of research introduced goal-directed exploration processes, also called autotelic learning, where agents learn to 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 to 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 et al., 2019 , Etcheverry et al., 2020] or physical [Grizou et al., 2020] .LLM-augmented exploration LLMs can be useful in various parts of quality-diversity and exploration 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 et 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 et 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 et 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-augmented goal generation, which echoes recent methods leveraging generative models for open-ended goal-based 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.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-targeting of ACES, Eldan and Li [2023] generates diverse training data by asking an LLM to write stories employing a combinations of words randomly sampled from a 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 def f(ls: List[str]):"""Divide the decimal representation of 8^88 up into strings of length eight.""" return "".join(ls)==str(8 ** 88) and all(len(s)==8 for s in ls) def g():return [str(8 ** 88)[i:i+8] for i in range(0,80,8)] assert f(g()) == True Figure 2: Puzzle example. A simple programming puzzle and its solution from the P3 dataset [Schuster et al., 2021] . A solution function g must return a valid solution such that f(g()) == True.any few-shot examples, do not optimize nor measure difficulty for an LLM while generating their problems. 
programming puzzles and the p3 dataset: 
 The Python Programming Puzzles dataset (P3) contains 1715 puzzle-solution pairs where each puzzle is defined by a short test program f designed to verify the validity of solution programs g such that valid solutions satisfy f(g()) == True when run in an interpreter, see example in Figure 2 [Schuster et 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 LLMs.In this work, we aim to generate sets of puzzles that are collectively as 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.We measure the empirical difficulty of a puzzle with respect to a target LLM solver as the opposite of the solver's competence on that puzzle. We measure competence using the standard pass@k metric with k=1: the number of valid solutions generated after k=1 attempts (which is simply the success rate) [Chen et al., 2021] . We estimate the pass@1 competence over N = 50 solving attempts and report the empirical difficulty (puzzle fitness F) as its negative success rate rescaled to the 0-100 range:F(f) = (-pass@1(f, LLM) + 1) × 100 if pass@1 ̸ = 0 -∞ 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 to LLM-based methods of assessing the quality of a sample (typically, critic or LLM-as-judge methods), this difficulty-based metric measures a ground-truth objective: how hard a given puzzle is 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 LLM feedback [Zheng et al., 2024 , Sachdeva et al., 2024] . This said, an existing possibility for hacking the difficulty metric is to import a random number generator library and to make the f function return True with probability 1/50. We have not observed this phenomenon in our experiments.The diversity measure we choose to optimize will have an important impact on the distribution of generated puzzles. Ideally, the set of puzzles should be diverse in their structures and topics. We thus define a set of 20 tags corresponding to different programming skills and label each programming puzzle with the combination of skills needed to solve it (reminiscent of Skill-Mix [Yu et 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 a niche or a cell in the rest of the paper. We sample our 20 tags from a larger list generated by an LLM (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 us 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 a 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.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 deduplicated2 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 a combination of skills) using the 3 sampled puzzles as examples.To select examples from one cell, we normalize the range of fitness scores in this cell between 0 and 1 and then sample from a softmax distribution from these normalized fitnesses with a 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 a 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, we rely on 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, a 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 HumanEval). 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.Avoiding label hacking The reason we generate the puzzle description separately from the puzzle itself is that in preliminary experiments, we observed a form of label hacking where the generator LLM, when tasked with generating puzzles with a particular combination of skills, generated generic simple puzzles and listed the relevant skills in the description even if they were not required in solving the puzzle. These puzzles were then wrongly tagged with a 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.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, a 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 of 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-based descriptors to 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 a 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 code5p-embedding model.Our final baseline is 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, 3 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. 
experimental details: 
 Puzzle generation, solution generation, description generation, and puzzle labeling are all implemented with the state-of-the-art open source model Llama 3 70B, quantized in 4 bits, with a temperature parameter of 0.8. 3 . We repeat all experiments using 3 different random seeds and report the means and standard deviations of the results. Each experiment was performed on 1 node of 4 Nvidia Tesla V100 SXM2 32 GB, with 160 GB RAM, for about 20 hours using the vLLM library [Kwon et al., 2023] . Each experiment is run for 40 generations, where each generation corresponds to 160 puzzles generated by the puzzle generator -a total of 6400 puzzle generation attempts per run. 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 to capture with hand-written descriptor functions, and thus lets us optimize diversity in a 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 a puzzle with a totally irrelevant descriptor -although it did sometimes answer quite literally, calling a problem set problem when it 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.More diverse The ability of an algorithm to generate diversity can be measured as the number of descriptor niches it manages to fill -stronger algorithms can reach more niches. On this metric, ACES and its variant ACES-ELM vastly outperform other baselines, reaching up to 700 different niches by the end of the experiment (Figure 3a ). This shows that our approach can effectively generate a 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 as effectively as the goal-directed generation operator of 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 it to 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 StaticGen do not leverage the semantic representation 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 of other sentence embedding spaces not used at any point during training. This measure is obtained by embedding all generated puzzles with a given model, then computing the average cosine distance between all pairs of embeddings in the set. Figures 6a and 3c show these metrics for two standard embedding models: codet5p-embedding and deepseek-coder-1.3b: ACES and its variant significantly outperform others here too. ELM-CVT represents problems and optimizes for diversity in the codet5p embedding space, which explains its ability to generate higher diversity in that space than ELM (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 are 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 a 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 to 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@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, generated using a seed different from the training data.Results revealed that the Llama-3-8b model finetuned with ACES-ELM-generated 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@1 scores of 49.4 and 41.6, respectively), they consistently underperformed compared to the ACES-ELM-trained model. Notably, the performance gap between ACES-ELM and baseline methods widened as testset difficulty increased, demonstrating ACES-ELM's effectiveness in preparing models for complex coding challenges and generating high-quality training data.Diversity We found that ACES could generate more diverse and challenging problems, but what happened if we tried to use a 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 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 larger size.difficulty Evaluating Mistral Large and Llama 405B on each other's generated datasets reveals pass@1 scores of 56.7% and 58%, respectively (Figure 4a ). These results demonstrate the effectiveness of our method in creating challenging benchmarks, even for state-of-the-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 2 achieved a 70% pass@k score, while Llama-3-405B reached 74%. In contrast, Llama-3-70B itself attained a pass@1 score of 36.8%. These findings underscore the superior problem-solving 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.ACES variants generate problems that are more challenging than problems generated by other baselines. But how challenging are they really? Here, we measure the competence of 10 state-ofthe-art LLM problem solvers and compare it to the performance of these same models on existing human-curated benchmarks. Figure 4a reports the pass@1 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 set 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.CodeQwen1.5-7B-Chat, Llama3-70B-instruct and Mixtral-8x22B-Instruct-v0.1, one of the best open source models on HumanEval with 78.7, 72 and 72% pass@1 respectively, get a considerable drop in pass@1, falling to 15, 47 and 34% respectively on problems generated by ACES-ELM with Llama-3-70b (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 is 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@1 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-generated dataset using ACES-ELM achieved a correlation of 0.83 with LiveCodeBench.In contrast, HumanEval only reached a correlation 0.46 with Live Code Bench, underscoring the challenging nature and value of our generated benchmark for comparing LLMs. 
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 et al.[2021], we currently only test solutions with one set of arguments, there should be tests with a 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 a puzzle's quality than difficulty alone, which remains an open problem. Overall,we believe that open-ended algorithms will play an increasing role in automatically evaluating LLMs in the future [Samvelyan et al., 2024] .Other applications ACES is a general algorithm that can be easily translated to other application domains by letting the user define a new descriptor and quality function. Swapping the difficulty metric with a more subjective objective estimated by an 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 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] .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 openended exploration algorithms applied to problem generation range from educational technologies to automated scientific discovery, helping shoulder some of the rising needs of the future.Descriptor spaces for exploration methods In all open-ended exploration methods, one must define a Behavioral Characterization (BC) space to characterize novelty. The earliest works used predefined low-dimensional descriptors to represent generated artefacts [Lehman and Stanley, 2011a , Baranes and Oudeyer, 2013 , Mouret and Clune, 2015] , which constrains the search along a handful of features one can code a descriptor for. More recent works have relied on higher-dimensional learned or pretrained embedding functions [Nair et al., 2018 , Laversanne-Finot 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, 2018b, Etcheverry et al., 2020] . Diversity-search algorithms sometimes need to be adapted to work with such high-dimensional spaces whose discretization leads to an exponential number of cells [Vassiliades et al., 2017] . But the main issue is that they are hardly interpretable and might not always align with the dimensions of variation humans find meaningful.With ACES, we propose an autotelic diversity-producing algorithm that constrains the search along a set of abstract, interpretable and hard-to-compute features of interest evaluated by LLMs.Here are the various prompts we use for ACES and all baselines. To solve the problem, we need to understand the logic of the 'f' function and how it checks for the presence of 1000 'o's and no adjacent 'o's. We also need to understand the implementation of the 'g' 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 (to understand the string concatenation and searching) Therefore, the list of indices for the problem is: [1, 5] Prompt for the puzzle generator of ACES. This prompt is used for ACES and all autotelic variants.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 a function 'g' such that 'f(g())' evaluates to 'True'-Each puzzle includes two functions: 'def f(...)' and 'def g(...)'.-The first argument of 'f' is always the output from 'g()'.-Ensure 'f' and 'g' have matching argument signatures (e.g., 'def f(solution, arg1=value1, arg2=value2, ...)' and 'def g(arg1=value1, arg2=value2, ...)'). You also need to set the value of argument of f (arg1,arg2,...) and g when you define them.-Avoid using 'f' 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 sure the puzzle is self-contained within these two functions.-Make sure that each puzzle have just all required skills (see below)Puzzle description: A two to four sentence summary of the puzzle's content. To explain what is the problem 'f', and how you can solve it with 'g'. 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 a function 'g' such that 'f(g())' evaluates to 'True'-Each puzzle includes two functions: 'def f(...)' and 'def g(...)'.-The first argument of 'f' is always the output from 'g()'.-Ensure 'f' and 'g' have matching argument signatures (e.g., 'def f(solution, arg1=value1, arg2=value2, ...)' and 'def g(arg1=value1, arg2=value2, ...)'). You also need to set the value of argument of f (arg1,arg2,...) and g when you define them.-Avoid using 'f' 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 sure the puzzle is self-contained within these two functions.-Make sure that each puzzle have just all required skills (see below)Puzzle description: A two to four sentence summary of the puzzle's content. Prompt for the puzzle generator of 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 a SAT problem 'f' and a function 'g' such that 'f(g())' evaluates to 'True'-Each puzzle includes two functions: 'def f(...)' and 'def g(...)'.-The first argument of 'f' is always the output from 'g()'.-Ensure 'f' and 'g' have matching argument signatures (e.g., 'def f(solution, arg1=value1, arg2=value2, ...)' and 'def g(arg1=value1, arg2=value2, ...)'). You also need to set the value of argument of f (arg1,arg2,...) and g when you define them.-Avoid using 'f' 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 sure the puzzle is self-contained within these two functions.Puzzle description: A two to four sentence summary of the puzzle's content. Prompt for the puzzle generator of ELM and ELM semantic. This prompt is used for nonautotelic baselines.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 a function 'g' such that 'f(g())' evaluates to 'True'-Each puzzle includes two functions: 'def f(...)' and 'def g(...)'.-The first argument of 'f' is always the output from 'g()'.-Ensure 'f' and 'g' have matching argument signatures (e.g., 'def f(solution, arg1=value1, arg2=value2, ...)' and 'def g(arg1=value1, arg2=value2, ...)'). You also need to set the value of argument of f (arg1,arg2,...) and g when you define them.-Avoid using 'f' 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 sure the puzzle is self-contained within these two functions.Puzzle description: A two to four sentence summary of the puzzle's content. To explain what is the problem 'f', and how you can solve it with 'g'. User: A Python programming puzzle is defined by two functions, the problem f(solution, arg1=value1, arg2=value2, ..) and the solution. f defines an algorithmic puzzle, and the solution solves this puzzle. You should pay a particular attention that the puzzle is solved if and only if **f(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 all 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 'n' respectively, return the median of the two sorted arrays.'The puzzle is: ...User: You are a helpful assistant to a Professor teaching a programming course in Python.The Professor want to give Pyhton programming puzzles to his Computer Science student to teach them Python. A Python programming puzzle is defined by two functions, the puzzle f(. . . ) and the solution g(. . . ). f defines an algorithmic challenge, and g solves this challenge. g is a solution to f if 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 is: skills listThe puzzle is: ...Respond with two or three sentence explaining the topics used in the puzzle. Then summarize your response by giving a list from 1 to 5 index corresponding to topics that are actually used in the puzzle above in this format: 'The list of skill use is: [].' where [] is the list of index of the topics used in the puzzle for example [3, 5, 6] .User: You will be given a function. Respond only in code with a correct, efficient implementation of the function. You will need to generate the correct solutions (g), for the Problem 2 that satisfies the condition f(g()) == True.Problem 0: def f(... Problem 2: def f(...Example Generation labelfrom typing import * def f(n: int, lst=['apple', 'banana', 'orange', 'grape']) -> bool:"""Check if the given element n is a prefix of any element in the list lst""" for word in lst: if word.startswith(n): return True return False def g(lst=['apple', 'banana', 'orange', 'grape']):return lst[1] assert f(g())Assistant:from typing import * import math def f(n: int, lst=[1, 2, 3, 4, 5]) -> bool:"""Check if the given list contains any perfect square number and if it is divisible by n.""" for num in lst: if math.isqrt(num) ** 2 == num: return n % num == 0 return False def g(lst= [1, 2, 3, 4, 5] ):for num in lst: if math.isqrt(num) ** 2 == num: return num return None assert f(g()) Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: The code is available at https://github.com/Julien-pour/ OpenELM/tree/imgep-qdaif. Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, 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 of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Justification: We documented the specs of the machines on which we performed our experiments at 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 or 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 or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Justification: We have reviewed the code of Ethics and do not find we have violated any principle in our research.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 our discussion section.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or 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 out 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 are 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 a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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)? 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 a best faith effort. 12. Licenses for existing assets Question: 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? 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 use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are 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 are encouraged to reach out to the asset's creators. 
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 is released but not yet properly documented; we plan to add a cleaner version that is documented as 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 as 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 to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
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 as 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects.• 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.https://evalplus.github.io/leaderboard.htmlEvery P3 puzzle comes in several instances with different arguments. We randomly sample one instance per puzzle, which gives use 155 seed puzzle instances.Model available at: https://huggingface.co/TechxGenus/Meta-Llama-3-70B-Instruct-GPTQ 
 
 Appendix:  


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

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: ### The presentation could be improved:
- 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.
- 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?
- 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.
- There are some questions in the question section that I do not fully understand.
questions: questions: - How the target cell get selected?
- I don't fully understand the motivation behind the ablation using ELM with semantic categories. What does "ablation of goal-directedness" mean?
- 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?
- Which variant is the final proposed method? Is it ACES-ELM, ACES, or another variant?
- 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.
- 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: Limitations are addressed in the Discussion section
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
4. 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.
questions: 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.
2. Some typos: Tesla V100 SXM2 32 Go (GB?), Appendix Section! A.2.
3. Can the authors test the generated tasks on closed-source LLMs like GPT (it is okay to say no)?
limitations: limitations: The authors have discussed the limitations well.
paper_summary: paper_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. 

The 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.
strength_weakness: strength_weakness: - rely too much on LLMs
- follow a questionable approach
- overclaim

I 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.
This 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.  

As 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.
questions: questions: Line 2,
"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."


The proposed approach relies on LLMs for problem representation, skill label generation, diversity characterization, difficulty evaluation, and puzzle generation. 
The proposed approach does not provide a mechanism to improve the current imperfect LLMs, so that it does not close the loop.


Line 30,
"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]."

Similar to above, the feedback loop is not closed, so it is an over-claim. 


This can be estimated by computing the empirical difficulty of a puzzle for a particular
39 solver: out of 50 attempts, the solver should solve the problem at least once (solvability) but as rarely
40 as possible (difficulty).


Line 44
"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]."

Why is it the standard approach? There are some papers working this way does not make it the standard way.


Line 134,
"Both datasets are pre-filtered to examples shorter than 1024 tokens to accommodate for limited context windows in LLMs."
This is an unnecessary limitation due to relying on LLMs.

Line 147,
"Puzzles for which no solution is found are considered invalid and are discarded."
This is problematic, at least, not ideal.
Line 202,
"If the puzzle is not solved by the solver model in 50 attempts, it is considered unsolvable and discarded."
It is the limitation of current LLMs, and the authors do not propose a mechanism to overcome it.

Line 150,
"this difficulty-based metric measures a ground-truth objective: how hard a given puzzle is for a target LLM solver"
It is not ground-truth: LLM solvers are not perfect, so some measure wrt an LLM is not a ground-truth.


Line 151,
"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)." 

This may not say much about transferability, since most LLM models were built with similar methods.


Line 164,
"We sample our 20 tags from a larger list generated by an LLM (GPT-4-0125)"

Use an imperfect LLM, namely, GPT-4, as reference has inherent limitations. 


Line 194,
"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."
Again, limitations of current LLMs.


Line 335,
"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."
It 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".


Line 354,
"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]."
This is an overclaim and it is misleading.
It replies on imperfect LLMs and do not attempt to improve them.
limitations: limitations: The authors do not discuss enough the limitations of reliance on imperfect LLMs, and do not propose to improve imperfect LLMs.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.
questions: questions: - What are the practical applications of this framework? Why is generating diverse and challenging puzzles an important problem to address?

- 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?

- What does the shaded area represent on the graphs?

- I don't understand Figure 3(f). The x-axis represents fitness rescaled between 0-100, but what does the color signify?

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

[1] OMNI-EPIC: Open-endedness via Models of human Notions of Interestingness with Environments Programmed in Code

# Minor Corrections

L167: There is an inappropriate exclamation mark in "Appendix Section! A.2."
limitations: limitations: Yes, the authors adequately addressed the limitations.

Comments: comment: Many thanks for updating your score! 

On automated quality assessment one could use a model trained on human preference data over puzzles (in a similar way to reward models in RLHF), or use a classifier trained on sets of (good quality, bad quality) puzzles (in a similar way as classifiers used to filter pretraining data for large-scale LLM training).
1.
“We would like to point out that synthetic data is successfully used for supervised fine-tuning to enhance current LLM capabilities, even if LLMs can make mistakes.”

This means the method is dubious.

A top AI venue like NeurIPS should not accept a paper with a dubious method.

2.
"On HumanEval: You are right that, short of formal verification one cannot verify that a solution solves exactly the problem as it is formulated in the problem description."
"Would you similarly reject all papers using HumanEval to evaluate a code model on the grounds that the solutions generated by the models might be flawed?"

The right question you should ask is: Why have such papers been accepted?

A top AI venue like NeurIPS should not accept a paper with a flawed method.

3.

"AlphaGeometry does generate geometry problems, and uses a specialized geometry DSL to ensure correctness of solutions. This is the equivalent to the Python interpreter in our case."

AlphaGeometry can guarantee the correctness of the proof.
Your method can not guarantee the correctness of the code.

A top AI venue like NeurIPS should not accept a paper with a fundamental flaw.
Thanks for the response! I'm satisfied with the response except for the "Potential for automated quality assessment" part (how could we do that?). And the result that even weaker LLM can generate difficult tasks for better LLMs is impressive.

I updated my score to 6.
We thank the reviewer for their reply and we are happy they find “there are merits in the submission”. Their first concern is on building evaluations using LLMs to generate, label, and compute difficulty since LLMs can make mistakes. Their other concern seems to be on the computation of the pass@k. Reviewer qqHU shared part of the same concerns and we also refer to our response to them for additional discussion on the validity of using LLM-generated puzzles to evaluate LLMs themselves.

> All these components are based on an imperfect LLM, so all of them are not fully reliable.

We would like to point out that synthetic data is successfully used for supervised fine-tuning to enhance current LLM capabilities, even if LLMs can make mistakes. This is a common part of modern LLM post-training. For instance, in the Llama 3.1 paper [1] (Section 4.3.1) the authors use a previously trained version on llama 3 405B to generate coding exercises (based on random code snippets from “various sources”) and use execution feedback to ensure the generated solutions are correct according to the provided unit tests. They cannot fully guarantee the accuracy of generated solutions but they show this synthetic data is helpful for increasing model capabilities, illustrating the usefulness of the method. 
As explained in our reply to Reviewer qqHU, synthetic benchmarks and evaluations (beyond using GPT4 as a proxy for human evaluation) have also been useful to uncover surprising or harmful model behavior [2, 3, 4].

> rely on problematic method (evaluation of pass@k). HumanEval [...] is problematic [...] Formal verification is required. 

On HumanEval: You are right that, short of formal verification one cannot verify that a solution solves exactly the problem as it is formulated in the problem description. However this is the same situation as all coding competitions and evaluations directed at humans, where one relies on passing test cases to judge the validity of the solution (see LeetCode evaluations for instance), as well as most of the software written everyday in industrial applications (except some critical domains like aeronautics where software is verified). You seem to suggest that all coding competition grading is flawed, as well as all code model evaluations (for which HumanEval has been the main inspiration). While the evaluations are not perfect, this has consistently guided progress with coding LLMs. Would you similarly reject all papers using HumanEval to evaluate a code model on the grounds that the solutions generated by the models might be flawed?
Formally verifying solutions to general programming problems (using Coq, Lean, Isabelle, etc) is far from a standard in the field of code LLMs and turning arbitrary programming puzzles into a formal specification is out of reach for current autoformalization methods (and out of the scope of this paper, this is a research field in itself).

> Can authors ensure the correctness of the generated test program?

We are in a different setup from HumanEval. By definition of a P3 puzzle, if `f(g()) is True` (according to the Python interpreter, see also Section 3.1 and [5]), the solution is correct. If at least one solution is found, the puzzle is solvable (thus correct). This does not guarantee the puzzle is interesting but the P3 correctness criterion is straightforward to judge. We increase the chance the puzzles are interesting by optimizing how hard (for LLMs) and diverse they are.

> FunSearch and AlphaGeometry are different

Funsearch does not generate problems so is not directly comparable. AlphaGeometry does generate geometry problems, and uses a specialized geometry DSL to ensure correctness of solutions. This is the equivalent to the Python interpreter in our case.

We hope this discussion answers some of your concerns and we thank you for the opportunity to improve the paper.

[1] The Llama 3 Herd of Models, Llama team 2024

[2] Discovering Language Model Behaviors with Model-Written Evaluations, Perez et. al. 2022a

[3] Red Teaming Language Models with Language Models, Perez et. al. 2022b

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

[5] Programming Puzzles, Schuster et. al. 2021
We appreciate your thoughtful feedback and the opportunity to address this important question. We understand your concern about using puzzles generated by LLMs as benchmarks to evaluate LLMs themselves. We'd like to offer the following perspectives on this matter:

* **Objective solvability**: Since a P3 puzzle is defined by its test case only (and the language description is generated afterwards to provide help), puzzles with at least one solution are by definition correct (i.e. solvable). This ensures a baseline level of validity for the benchmarks.

* **Puzzle quality and interest**: Although all solvable puzzles are correct, this doesn’t mean they are interesting or worthwhile. We acknowledge that evaluating puzzles 'interestingness' or relevance is subjective and challenging to automate. Our approach with semantic labels provides users some control over the generation process, allowing them to orient puzzles towards abstract features they deem important. While we cannot fully automate the assessment of puzzle quality, our method generates problems that are more difficult and diverse in customizable ways, potentially increasing their overall quality and relevance. We could also add an interesting metric judge by an LLM [1, 2] and/or an educational value [3, 4] to filter the least interesting puzzles.

* **Preexisting automated benchmarks**: we would like to point out that synthetic benchmarks have already led to discovery of interesting features of LLMs [5, 6, 7]

* **Human-in-the-loop approach**: Our method significantly speeds up benchmark generation by producing a pool of potentially interesting puzzles from which humans can select, in a similar fashion as BigCodeBench or HumanEval Plus where the authors used a human in the loop method to guide or filter LLM generated data;

* **Potential for automated quality assessment**: In the future, we could explore using preference models or tournament-style competitions with the top k LLMs to automatically select top puzzles from the generated set. This approach has shown promise in other areas of AI evaluation.

* **Comparative evaluation**: To address the concern of using LLM-generated benchmarks to evaluate LLMs, we could compare LLM performance with human performance on these benchmarks. This approach has been used effectively in other studies comparing the reasoning capabilities of LLMs and humans [8]. Additionally, we note that model scores on our generated sets and on LiveCodeBench (composed of newly released coding puzzles to avoid contamination) are strongly correlated (See additional Figure 1c). We take this as evidence that the generated set measures underlying coding capabilities;

> Perhaps we can use benchmarks generated by stronger LLMs to evaluate weaker ones, but how do we evaluate the stronger LLMs?

In ACES, increasing the number of attempts leads to harder problems (since we can optimize for puzzles solved once out of N with N being large). Thus, even weaker LLM can generate difficult tasks for better LLMs, as shown in our additional experiment where Llama-3.1-405B only gets 74% pass@1 on a dataset generated with ACES-ELM with Llama-3-70B (Additional Figure 1a). This is directly due to the fact that ACES can optimize for empirical difficulty.

* Although we have shown that puzzle difficulties transfer between Llama and Mistral (additional Figure 1a, Mistral Large and Llama 3 405B have similar scores on ACES-ELM datasets generated by both models) we could also take the three or four best LLMs and generate multiple archives with our method, then merge them to get a test set; as each LLM has some strengths and weaknesses, the resulting archive should be balanced in terms of puzzle difficulties for other models.

We hope this addresses your concern and provides evidence for the usefulness of synthetically-generated evaluation sets. Given that many of your previous concerns have been addressed and you've acknowledged this work as a commendable attempt, we kindly request that you consider updating your score to reflect your opinion of the paper.

Thank you again for your valuable feedback and the opportunity to improve our work.

[1] Omni: Open-endedness via models of human notions of interestingness, Zhang et. al. 2023

[2] OMNI-EPIC: Open-endedness via Models of human Notions of Interestingness with Environments Programmed in Code, Faldor et. al. 2024

[3] Cosmopedia: how to create large-scale synthetic data for pre-training, Ben Allal et. al. 2024

[4] Textbooks Are All You Need, Gunasekar et. al. 2023

[5] Discovering Language Model Behaviors with Model-Written Evaluations, Perez et. al. 2022a

[6] Red Teaming Language Models with Language Models, Perez et. al. 2022b

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

[8] Beyond the imitation game: Quantifying and extrapolating the capabilities of language models, Srivastava et. al. 2022
Thanks for the response! Many of my concerns have been addressed and for other ones, although the authors did not provide a clear solution and acknowledged this as a limitation of their work, I believe that overall, this work represents a commendable attempt.

Now, I think there is only one question that remains unanswered:

As I mentioned earlier, and as reviewer NuHw also noted, how can puzzles generated by LLMs, which cannot guarantee correctness, serve as benchmarks to evaluate LLMs themselves (or other LLMs)? 

I know the following information, but I don't think this answers the question.

1. I know that some benchmarks use LLMs (mostly GPT-4) as the evaluation metric because these benchmarks require human evaluation, which cannot be automated. GPT-4 here serves as an approximate automated evaluation method.
2. I know that LLMs can automatically generate training datasets for training purposes because we have golden benchmarks to evaluate the final training outcomes. However, if we use LLM-generated benchmarks for the final evaluation, there will be nothing to ensure their performance.
3. Perhaps we can use benchmarks generated by stronger LLMs to evaluate weaker ones, but how do we evaluate the stronger LLMs? If we use human-designed benchmarks to evaluate stronger LLMs, then why not use them directly to evaluate weaker ones?

This is quite important and I hope the authors can discuss this question further.
Thanks the authors for the detail rebuttal.
I admit there are merits in the submission, and I am aware there are many papers similar wrt (unreliable) LLM-based methods.
However, I am not convinced.


There are two fundamental issues with the submission:
1) fully rely on an imperfect LLM;
2) rely on problematic method (evaluation of pass@k).


1) 

As in my original review:
I 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.
This approach has a fundamental issue and is misleading: no current LLM is perfect, so LLMs may make mistakes, and usually there is no mechanism to improve current LLMs in such framework.  


Line 247
"Puzzle generation, solution generation, description generation, and puzzle labeling are all implemented with the state-of-the-art open source model Llama 3 70B, quantized in 4 bits, with a temperature parameter of 0.8."

All these components are based on an imperfect LLM, so all of them are not fully reliable.

2)

How to evaluate "pass" (in pass@k)?
How to guarantee the correctness of the evaluation?

In the current popular approach, like HumanEval, if a solution passes several test cases, then it is a pass. 
This is problematic: Testing only can not guarantee the correctness of a piece of code. Formal verification is required. 

This is not a reliable evaluation.

As a result: no guarantee of the quality of generated puzzles, some of them may be wrong.

A question from reviewer qqHU:
"How does the author ensure the correctness of the generated test program $f$"?

Can authors ensure the correctness of the generated test program?
The binary answer should be NO.
With LLMs, it is best effort.


From authors' general rebuttal:
"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."
This is both true and false. In a top AI venue like NeurIPS, we want to see papers with reliable method / results, without fundamental issues. The current submission has a fundamental issue: reliance on an imperfect LLM. 

FunSearch and AlphaGeometry are different: they have reliable verifier in the loop.

This is a problem for the community, in particular, those working on LLM-based method.
Top AI venues like NeurIPS should not publish more such papers without fully reliable methods. This is misleading.
Thank you for thoroughly addressing my comments and providing the additional results. After carefully reviewing your response, I find that my primary concerns and points of confusion have been addressed. I support the publication of this paper in NeurIPS and will maintain my current score.
Thank you for your detailed rebuttal. I found your answer and the main rebuttal PDF helpful.

Overall, I think that the paper is making a modest, yet interesting contribution. Most importantly, the paper is technically solid and the claims are appropriately matched to the paper's contribution. In the end, the community would probably benefit and learn from this paper.

Given these considerations, I am happy to increase my score.