We thank Reviewer XBPq for their detailed and helpful comments and questions.

“The observation that LLMs can generate tasks outside the P3 dataset (the training set that is used for prompting), is basically because the LLM has been pre-trained on many larger scale coding question datasets. For example, the combination of string and grid question on page 21 is a canonical programming task. Even if it's not in P3 dataset, it's highly likely that LLM has seen this during pretraining.”

This is true for any generative algorithm based on an LLM. Whether puzzles exist somewhere in the world or not, we’re asking whether we can build an algorithm able to generate a diversity of such puzzles along a predefined set of dimensions of interest, and whether this diversity is greater than the one produced by existing algorithms. This is what this paper shows. We make no claim about the historical novelty of the generated problems.

“The semantic descriptor is sort of defined arbitrarily. It's fine if only used to prompt the LLM, but not quite reasonable in measuring interesting-ness and diversity. For example, solely from the human labeled P3 dataset, what's the correlation coefficients between each pairs of labels? As far as the reviewer can see, many labels are highly related, e.g. sorting and searching -> stacks and queues or tree or recursion. Using Hamming distance over those highly correlated field is problematic. Similarly, in the diversity measurement, the grid of labels is reasonable only if categories are almost independent and orthogonal to each other.”

We agree with the concern about the selection of descriptor features for evaluation and, for this reason, include measures of diversity computed in three embedding spaces that were not used during training. This point is addressed in the general answer as it was raised by other reviewers as well.

We’re not sure to understand the concern about hamming distance and the diversity measurement (entropy over cells, cell count), could you be more specific?

“The process relies on LLM to label the generated tasks and add them into the prompt example pool. View from the Figure 3, this labelling accuracy is far from satisfactory, especially the generation process is iterative and accumulates the errors.”

This point is similar to the one above and is also answered in the general answer. The concern about the accumulation of errors is only valid for the evaluation using semantic descriptors but cannot possibly explain increased diversity in the three embedding spaces. Based on these three latter metrics alone, we can reasonably argue that our method generates a stronger diversity than existing ones. Furthermore, the bias introduced by the imperfect labeling is constant across algorithms (it should impact baselines in the same way).

“What does the first contribution bullet in the introduction section mean? We define the notion of semantic descriptors to leverage LLMs for the encoding of high-dimensional textual data into hard-to-compute, abstract and interpretable features of interest”

One contribution of our paper is to give experimenters the possibility to define abstract and interpretable features of interest that best capture the dimensions of the type of diversity they want to generate. Whereas before they could only define features they could hand-code a function for, leveraging LLM gives them more expression power.

“What does the first sentence in Figure 1 caption mean?”

“ACES maintains an archive of discovered puzzles grouped into cells indexed by their semantic representation (skill combination)” means that ACES stores and accumulates valid generated puzzles into an archive organized into different cells, where each cell corresponds to a particular semantic representation. Each representation is a binary vector describing whether skill i is required (1) or not (0) to solve the puzzle.

“The page limit of 9 suggests that the reproducibility and ethics should be put after the references.”

This has been updated.

We thank Reviewer ufAe for their detailed and helpful comments and questions.

Comparison to related works:

“Mutation for diversity. Unnatural Instructions [1] starts with 15 seed examples of (instruction, input, constraints) tuples and mutates a 3-example demonstration to generate new examples. Self-Instruct [2] also does similar things with (instruction, input, output) tuples and it randomly samples instructions from both the initial pool (like your P3 train set) and the generated pool (like your generated puzzle-solution pairs) to start their mutation. Evol-Instruct [3] uses an even more complicated evolutionary algorithm to mutate and generate complex instruction samples.

Goal specification for diversity. The authors claim that the semantic descriptor (binary vector that indicates which features to include) of ACES is novel and easy to interpret. I agree with the interpretability argument but not the novelty argument. TinyStories [4] also tries to create diverse stories to train language models by creating a list of story features and asking language models to include randomly sampled features from the list each time. Evol-Instruct [3] also involves rewriting and evolving the prompts towards different goals.

More importantly, even in the domain of generating coding tasks, these two approaches (mutation and goal specification) have been used to generate diverse coding tasks (though not programming puzzles). Gunasekar, Suriya, et al. [5], Code Llama [6], and WizardCoder [7] all use these approaches to instruction-tune language models.”

We thank the reviewer for extensive pointers to relevant prior work and agree additional discussion of code data augmentation methods is needed. We updated the related work section of the manuscript to include this. A general comment here is that these methods, coming from the synthetic training data generation literature, do not aim to optimize for diversity as a goal; usually when they include diversity promoting mechanisms it is for the sake of downstream performance only. As another general note, in addition to the semantic descriptors we introduce, there are two important aspects of our method which are goal selection (which the reviewer points out) and the evolutionary search aspect (which is different from mutation only). All algorithms we evaluate in our experiments except the static-generation are non-stationary since they add their generated data back into the candidates one can sample from. The generative process evolves over time by reusing discoveries for further discoveries. Unnatural instructions simply generates novel instructions from few-shot examples and is neither autotelic, nor diversity-maximizing or non-stationary. Self-Instruct uses both seed examples and generated examples so does display non-stationarity. However it does not maximize diversity, and it is not autotelic. Evol Instruct (as is used both in WizardLM and WizardCoder) is not autotelic, even if it is non-stationary; in any case there is no explicit diversity-maintaining mechanism and additionally there are absolutely no evaluations of the diversity of the produced dataset which prevents any conclusion.

We thank the reviewer for pointing out TinyStories to us, a work we were unaware of that is quite relevant. The proposed goal-generating process is indeed autotelic but it is not evolutionary; the generated stories are never put back in the pool. It is probably totally satisfactory for their domain because they have many different nouns to combine and the requirements to produce a valid story with an LLM are pretty low. The goals they use are a mixture of concrete words (we explicitly want to foster diversity in a space of abstract), and story features such as good or bad endings, which is very much similar to what we do and we find very interesting; they only have one abstract feature per story however (and do not measure the diversity of generated stories with respect to these features, even if we can guess that GPT4 will do fine at capturing them in their generated data). Evol-Instruct, on the other hand, has different prompts with categories of mutations but as mentioned earlier they do not attempt to measure the diversity of the actually generated samples.

(the rest of the answer is in the part 2)

This contradicts what the authors proposed in the introduction regarding applications:

education (generating problems for students to solve), data augmentation (generating problems and solutions for AI model training), or automated scientific discoveries (e.g. discovering new scientific problems and their solutions)

Thank you for your feedback. While we could have devoted more effort to evaluating the data quality, this does not necessarily conflict with the proposed applications, particularly in education. For more details, see 'Answer (part 4)' in our response to reviewer AUHG (https://openreview.net/forum?id=hqUznsPMLn&noteId=6FIypHHOgY).

But is there any concrete example that the authors can provide to convince me that this is indeed the case?

In our experiment, we utilized an LLM proficient in programming, though not the most advanced in recent coding model releases. Despite this, our goal-directed methodology enabled the LLM to create creative and novel coding puzzles not found in archives from other baselines. For instance, consider this example puzzle (docstring of the puzzle): "Given a grid of 0s and 1s, determine if there exists a path from the top-left corner to the bottom-right corner, where you can only move down, right, or diagonally down-right. Additionally, the sum of the numbers along the path must be a prime number."

While this combination might not be overly surprising to an expert, it is nonetheless non-trivial. It shows the potential of our approach. Furthermore, it's worth noting that employing a more advanced LLM could potentially lead to even more creative and surprising combinations. This suggests that as AI models continue to evolve, the scope for generating intricate and intellectually stimulating puzzles in educational settings may expand significantly, offering further evidence of the practical applications of our proposed methods.

“The 2**10 size grid of sets of semantic descriptors is (a) in my opinion quite small. P3 has 636 train puzzles spanning ~60-80 cells, but there are only 1024 cells in total to try to cover (using 45000 generated programs to do so). (b) I expect that many of these cells aren't meaningful, e.g. it doesn't seem that important to identify a programming puzzle that is simultaneously a Sorting and Searching, Counting and Combinators, Tree and Graph, Bit manipulation, string manipulation, recursion, and dynamic programming problem (7 semantic descriptors), and a full 38% of the cells represent the goal of having 6 or more semantic descriptors. Indeed Figure 7 confirms generating programming puzzles with 6+ semantic descriptors is quite rare, yet the algorithm spends significant time trying to do so.”

In the most interesting cases, it may be hard to imagine solutions that would end up in some of the cells our semantic descriptors define. This is fine. We invent many descriptors for movies, music or poetry, it doesn’t mean that we expect specific movies, songs or poems to have any arbitrary conjunction of these features. What’s important is to ‘spread out’ interesting objects by defining axes of variation we care about while ‘conflating’ irrelevant objects together. Assuming a perfect feature description function, if a cell cannot be reached it will never be, but maybe it will be, and then we will have learned something new. There exists a paper full of anecdotes from evolutionary search where the system found creative ways to reach points of a representation space that was thought to be impossible to reach (e.g. a robot found a way to walk without having either of its feet touch the floor by crawling on its back), see The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities (Lehman et al., 2018).

“The primary measure of diversity (number of cells covered in the archive) is both an imperfect measure (the labels used to determine which cell is covered are determined by ChatGPT) and also the same model producing the puzzles (where generation is conditioned on the desired label) is the one predicting the label. Since puzzle generation is conditioned on the goal label and the same model then predicts those labels, there is real risk of the model overestimating the amount of diversity produced. As a toy example of how this overestimation could occur, we could imagine the model adds a comment to each generated puzzle saying what labels that puzzle should have. Then during labeling, the model ignores the code and simply reports the labels indicated by the comment. If this were to occur, the semantic descriptor metric would report all cells get covered (despite not actually achieving the desired diversity). I trust that this precise mechanism is not taking place here, but something directionally similar could easily evade notice and I don't think is being checked or controlled for.”

This is a fair argument. The current evaluation metric based on semantic descriptors isn’t very reliable, and although this is fine for the purpose of guiding the diversity search, it poses problems when used for evaluation. This is precisely for this reason that we propose other diversity metrics computed from three different embedding spaces that were not used in the training procedure. On its own, the fact that our method outperforms others on these unbiased evaluation metrics should be sufficient to make the argument that our method allows to generate more diversity than existing ones. The semantic descriptor evaluation, in addition to the exploration of generated puzzles, brings additional elements to the study of the generated diversity, although it is not a definitive argument as such for the reason mentioned above. The reviewer is right to point that this evaluation could be in principle hijacked by the puzzle generator. Although we did not implement any mechanism to prevent this from happening, we can have a look at the difference of performance between ELM semantic and ELM in embedding space. These two do not aim for semantic goals, which means that the generator is unaware of the labeling procedure. Therefore, the noise in the semantic diversity metric is the same for both algorithms. Yet, ELM semantic still outperforms ELM in terms of semantic diversity.

We thank Reviewer AUHG for their detailed and helpful comments and questions.

There were several questions and comments about the choice of semantic descriptors and its impact on the generated diversity:

“ACES relies on a manually crafted set of semantic descriptors that is specific to the task of generating programming puzzles. The paper does not explore the role that the selection of these semantic descriptors plays on the resulting set of programming puzzles, and does not provide insight into how the approach works in non-programming puzzle domains where these pre-selected semantic descriptors would not be appropriate.”

“One weakness of this manually crafted set of semantic descriptors is that it places a kind of constraint on the diversity that the approach can produce, and it shifts the burden of identifying this diversity from the ACES algorithm itself to the human seeding the algorithm with semantic descriptors.”

We answer these in the general answer as these questions came up for other reviewers as well.

“The semantic descriptor based metric is tailored specifically for the semantic descriptors selected for the approach. If the set of semantic descriptors used in the approach were to change, it's not clear the current semantic descriptor approach (holding the set of semantic descriptors fixed to allow comparing across the change) to measuring diversity would remain meaningful.”

We are not sure to understand this comment, do you point at the fact that the metric we optimize for it is the same we use for evaluation? If so, note that we evaluate the competing methods with diversity metrics computed in three distinct embedding spaces as well (see General Answer).

“Why do you select the grid of 2^10 sets of semantic descriptors as your set of possible goals to induce diversity? I ask this question with the following thoughts in mind. First, it seems like many of the cells in this grid don't actually represent diversity of interest (e.g. 38% of cells have 6 or more semantic descriptors which seems an unwieldy amount). Second, it seems like there are more dimensions of diversity not being considered. I brainstorm a few here to make the point: complexity/difficulty, domain, number of inputs, reliance on data dependencies, libraries used, and wall clock runtime.”

As discussed in the general answer, we can always think of other representation features and their choice will influence the produced diversity. The definition of the representation function is necessarily subjective because it is precisely the means through which experimenters define what type of diversity they care about. The suggested representation features are all valid and adding them would result in the generation of a different type of diversity along these dimensions as well. We made the choice of not including them but could have. Complexity and difficulty are definitely good candidates, especially in educational contexts (see our comment about education below). Including it would require an extra measure of complexity, e.g. by asking GPT or another LLM to solve the problem several times and using the negative success rate as a measure of difficulty. Note that we use a binary measure of difficulty (valid vs invalid) for filtering puzzles that enter the archive. Including the number of inputs or wall clock time may not lead to the production of interesting diversity (e.g. adding time.sleep() instructions, or useless inputs). This point is interesting because it illustrates a contribution of our approach. The definition and use of semantic descriptors, by making explicit the space in which the diversity is produced, allows us to discuss the inclusion/exclusion and careful definition of the dimensions of interest. We can thus debate about whether sets A or B of semantic descriptors would allow us to generate the kind of diversity we care the most about for application X. This is not possible with embedding representation functions which, by making these choices implicit, restrict our ability to discuss and debate them. We answer the concern about parts of the representation space being hard or impossible to reach in the following answer.

“In Section 3.2 you introduce a notion of interestingness, saying that functions R will map all uninteresting samples to the same point. This R notation is then never used, and the notion of interestingness is not further explored. What is meant by interesting, and how do the two representation functions (cosine distance and semantic descriptors) send uninteresting examples to the same point?”

R is the ‘representation function’ mapping a generated object (here a programming puzzle) into a given representation space (here the embeddings, or the semantic descriptors). In the case of semantic descriptors, R “spreads out” programming puzzles we care about: the ones that are valid and that require various programming skills to get solved and “conflates” uninteresting ones: invalid puzzles are not even represented, and all puzzles that require no skill get mapped to the same unique cell (coordinates [0]^10). Conducting the diversity search in the semantic space is thus expected to be more efficient than conducting it in the original representation space (eg space of token sequences), or even in the embedding space which may not have such properties (ie all puzzles that require no skill to be solved may be mapped to different areas of the embedding space and thus be judged novel). As discussed in the general answer, the choice of the representation function directly influences the produced diversity precisely for this reason.

“In "What's new?" you claim ACES is the first algorithm to use an autotelic LLM to generate diverse artifacts via in-context learning. In seeking to evaluate this claim, I am reminded first of EvoPrompting: Language Models for Code-Level Neural Architecture Search (https://arxiv.org/abs/2302.14838) (which is not autotelic, instead optimizing an objective) and I subsequently find concurrent work LLMatic: Neural Architecture Search via Large Language Models and Quality-Diversity Optimization (https://arxiv.org/abs/2306.01102). This concurrent work is also not autotelic. Another such concurrent work is Quality-Diversity through AI Feedback (https://arxiv.org/abs/2310.13032). Finally, does not Colas 2023 Augmenting Autotelic Agents with Large Language Models (https://arxiv.org/abs/2305.12487) also have all of these properties?”

You are right to point out that other works have begun to consider LLMs as mutation operators in evolutionary and related algorithms. EvoPrompting is an example of this where the authors mutate the Python code for designing neural architectures and use the negative generalization error as fitness. However, that method does not perform any diversity optimization. LLMatic follows this path by applying a QD algorithm powered by LLM-based generation. Their approach is not autotelic as you have mentioned, but more importantly, the archive they use for their Map-Elites implementation is based on very simple surface-level descriptors (FLOPS, width-to-depth), and does not capture the human-relevant diversity we seek to achieve in this work. QDAIF is the work closest in spirit to ours, even if they perform their experiments in poem and movie review domains that are quite different from the coding domain, mainly because the solvability of programming puzzles can be done by a python interpreter. Note that both LLMatic and QDAIF are under review at this same conference and should not be considered prior work. And finally, the work of Colas et. al. does not maximize for any form of diversity and, let alone define its diversity through AI feedback.

We have updated the appendix to include an "Additional Related Work" section to include a discussion of these works and the crucial aspects in which they differ from ours to make the novelty of our contribution easier to evaluate.

“I have collected some typographic suggestions for you below. These issues did not meaningfully harm the readability of the paper.”

Thank you, these were all fixed.

“And of course there is the significant weakness, readily acknowledged and discussed by the paper, that the diversity of puzzles identified by ACES did not help in fine-tuning for the downstream task of puzzle solving on the test set compared with the static gen baseline. I applaud the frank discussion of this weakness in Section 4.4 and the discussion of the paper.”

This result should not be seen as a weakness per se. As discussed in the introduction and the discussion, data augmentation is only one of several possible motivations for diversity-producing algorithms. Other possible motivations include: the generation of diverse problems for training and evaluating human learners, scientific discovery (eg automatic theorem proving), but also artistic projects (eg generating an interesting diversity of visual artefacts, where the notion of interestingness can be highly subjective: eg beautiful from the point of view of the artist). Our paper only studies quality with respect to the data-augmentation application as it is the one that is easiest to automate. Studying quality for educational or artistic purposes would require extensive and careful human studies, which could be the subject of a stand-alone paper. In general, automating measures of quality or interestingness remain a central challenge in AI (e.g. see an attempt in OMNI: Open-endedness via Models of human Notions of Interestingness, Zhang et al., 2023)