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.

What are the practical applications of this framework?

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

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

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

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

[...] I believe this is a limitation because the primary goal of generating new data is likely to enhance training.

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

Questions

I don't understand Figure 3(f).

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

I am uncertain if the difficulty measure is appropriate. [...] Can you provide more details on this aspect?

We 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). The 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.

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

What does the shaded area represent on the graphs?

They represent standard deviation, each experiment is repeated 3 times with different seeds.

OMNI-EPIC [1] utilizes a task archive [...]

Of course! Thanks for pointing this out. We have added the reference.

[1] Automatic Goal Generation for Reinforcement Learning Agents, Florensa et. al. 2017

[2] Learning with AMIGo: Adversarially Motivated Intrinsic Goals, Campero et. al. 2020

[3] Intrinsic Motivation and Automatic Curricula via Asymmetric Self-Play, Sukhbaatar et. al. 2017

[4] Evaluating Large Language Models Trained on Code, Chen et. al. 2021

[5] Language Models Can Teach Themselves to Program Better, Haluptzok et. al. 2022

[6] Mathematical discoveries from program search with large language models, Romera-Paredes et. al. 2023

[7] Large Language Monkeys: Scaling Inference Compute with Repeated Sampling, Brown et. al. 2024

We thank the reviewer for their comments and hope to be able to convince them that our assumptions are sound.

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

For each of the components we use LLMs for, they clearly outperform other available options:

• For puzzle generation, other program synthesis methods would hardly give interesting, human-relevant programming puzzles;
• 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.
• 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);

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

overclaim

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

Questions

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

The proposed approach does not provide a mechanism to improve the current imperfect LLMs, so that it does not close the loop.

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

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

This is part of the motivation of the paper (beginning of the introduction), not its contributions.

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

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

[on discarding unsolvable puzzles] This is problematic, at least, not ideal.

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

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

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

[on generating the initial list of skills] Use an imperfect LLM, namely, GPT-4, as reference has inherent limitations.

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

"to drive discovery of puzzles with novel skill combinations, we rely on the LLM recombining [...]" Again, limitations of current LLMs.

Could you be more specific?

It is not reasonable to postpone the development [...]

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

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

This is one of our last paragraphs and is future work/discussion! We do not claim to instantiate a self-play loop in this paper.

[1] Using Centroidal Voronoi Tessellations to Scale Up the Multi-dimensional Archive of Phenotypic Elites Algorithm, Vassiliades et. al. 2016

[2] Mathematical discoveries from program search with large language models, Romera-Paredes et. al. 2023

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

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

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.

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.

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

How do the results differ when using different models as solvers? [...]

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

How does the author ensure the correctness of the generated test program [...]

We agree that it is not feasible to manually ensure consistency of the generated puzzles. For 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).

Some parts are not clear. (1) I'm confused about which one is your final method, ACES or ACES-ELM?

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

In section 4.2, what do these numbers (F1 scores) represent [...]?

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

[difficulty] which is actually the passing rate of the LLM, rather than an objective difficulty

Unfortunately 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!

However, I believe that difficulty is just one of the criteria for evaluating a benchmark, and this approach is somewhat one-sided.

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

Questions

Why there are 21700 niches in total?

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

Can the authors test the generated tasks on closed-source LLMs like GPT (it is okay to say no)?

See our results with large open models.

[1] LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code, Jain et. al. 2024

[2] BigCodeBench: Benchmarking Code Generation with Diverse Function Calls and Complex Instructions, Zhuo et. al 2024

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.

The presentation could be improved.

We thank you for this feedback. We have modified section 3.4 by being more precise when introducing Map-Elites.

My current understanding is that the difficulty metric is used as fitness, and two diversity metrics are two dimensions in the Map-Elites archive.

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

Regarding embedding diversity, [...] does it make sense to use it as one dimension in the Map-Elites archive?

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

The authors might consider introducing the motivation behind their design choices before explaining them.

Thank you for your suggestion! The reason for using P3 is twofold:

• 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;
• 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]).

As for the metrics introduced in section 3,2:

• 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.
• 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).
• Embedding diversity: see previous response.

Questions:

How is the target cell selected?

In 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);

I don't fully understand the motivation behind the ablation using ELM with semantic categories. What does "ablation of goal-directedness" mean?

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

[...] Do the authors consider using more powerful LLMs like GPT-4 or Claude-3.5?

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

Which variant is the final proposed method?

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

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?

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

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