acceptodds
Under review as a conference paper at ICLR 2027

Empirical-Measure Search States for Quality-Diversity Optimization

Abstract

Quality-Diversity (QD) optimization seeks collections of solutions that are both high-performing and behaviorally diverse. Many QD methods use an archive both to retain solutions and to guide subsequent search through archive improvement. Useful search, however, does not always look like immediate improvement. When evaluated candidates fail to improve the archive, they may not be retained, so search may stop pursuing those directions, leaving valuable regions undiscovered. We therefore need to separate search-state representation from result retention, allowing past search effort to continue guiding where to search even without immediate archive improvement. We introduce Quality-Diversity Empirical Measure (QDEM), which separates search-state representation from result retention, target-relative valuation, and search control. Under a fixed reference projection, QDEM recursively maintains a fixed-dimensional state of cumulative target support from all valid evaluations, guiding search toward under-supported targets. Our experiments demonstrate that QDEM outperforms state-of-the-art methods on a broad range of standard QD benchmarks and high-dimensional visual reference tasks, while remaining competitive where quality improvement already guides search effectively. In robot morphology evolution, QDEM allows lower-fitness intermediate designs rejected by the archive to remain part of the search process, enabling controller adaptation on the new morphology to recover and exceed pre-change performance.

Primary area:
optimization
Keywords:
Quality-Diversity Optimization, Black-box optimization, Evolutionary Computation, Search-State Representation, Empirical Measures

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_HzauOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper addresses the problem that the search during optimisation may stop pursuing good search directions due to using the same archive for search and solution storage. I.e. there is a need for stepping stones and measures of intermediate search progress. The proposed solution is to use an empirical measure of past evaluations as a fixed-dimensional state to guide the search to undersupported targets. On several benchmarks, the proposed algorithm outperforms previous algorithms and robot morphology adaptation is also successful.

Critical strengths
  • Favourable results: the algorithm gives performance benefits on a wide variety of benchmarks.
  • Generalisable method: the principle is generalisable so it can be applied quite generally for QD optimisation.
  • Well-chosen baselines for comparison: the comparison includes standard QD algorithms and algorithms that include intermediate-progress based archive improvement evaluation. The authors demonstrate a good awareness of relevant algorithms and state-of-the-art concepts.
Critical weaknesses
  • There are no formal guarantees although this is common in the field.
  • The paper does not provide much insight into the reason for the success of the algorithm.
Questions for authors
  • The Gaussian weights on kk nearest references. How are these weights and references determined? What advice would there be for practitioners wishing to use your technique?
  • The MSG score weights the new behaviour and assigns it a score based on the share ratio (search state (support score) divided by the desired share). The marginal weights are set to decline exponentially with the support score, thereby encouraging the search over undersupported areas in the behaviour space. Are these choices mainly heuristic or is there a guarantee of some kind? A little bit more insight in the experiments comparing the different ways to measure archive process and how it affects the search may also be useful.
  • The related work section in the main paper is particularly short. While there is more in the appendix, perhaps this can be slightly expanded.
6 comments
AuthorsOpenReview ↗

Author Response (Part 1)

We sincerely thank you for your careful reading and your thoughtful, insightful review. We particularly appreciate your recognition of our favorable experimental results, the generalizability of our method, and the well-chosen baselines for comparison. We are also grateful for your detailed and constructive suggestions on how to provide deeper insights into why QDEM succeeds. We are pleased to address the points you raised.

W1. There are no formal guarantees although this is common in the field.

W2. The paper does not provide much insight into the reason for the success of the algorithm.

Q2. The MSG score weights the new behaviour and assigns it a score based on the share ratio (search state (support score) divided by the desired share). The marginal weights are set to decline exponentially with the support score, thereby encouraging the search over undersupported areas in the behaviour space. Are these choices mainly heuristic or is there a guarantee of some kind? A little bit more insight in the experiments comparing the different ways to measure archive process and how it affects the search may also be useful.

We read these three points as asking two things: whether the design choices behind MSG are principled or mainly heuristic, and why QDEM succeeds, particularly how its feedback guides search differently from archive-progress signals.

In brief, MSG has a principled structure: it is derived from a utility that, for fixed total support, is maximized exactly at the desired target allocation (Proposition 2). The exponential weighting is one choice within this structure. Although these theoretical properties do not guarantee global convergence of the CMA-ES-based search, our experiments show that the intended guidance translates into effective search behavior in practice. MSG can continue to distinguish contributions to under-supported targets even when the archive is not improving, whereas archive-progress signals may provide limited guidance for continuing exploration in this situation.

Following your suggestions, we added an evaluation-allocation analysis with heatmaps on Rastrigin 2D (Appendix C.12), comparing how QDEM, DMS, and CMA-MAE distribute evaluations throughout search. We have also expanded the explanation of this mechanism in the Discussion (Section 6, L510–518). We explain these points in five steps below, with evidence at each step.

1. References let QDEM track how much support each target has received. QDEM places a fixed set of reference points in the behavior space as targets. Every valid evaluation, whether or not the archive retains it, adds one unit of support to the references near its behavior. Accumulating these contributions gives the search state StS_t, where St,jS_{t,j} is the total support that target jj has received so far.

2. MSG identifies where support is lacking. For a candidate with behavior zz,

MSGt(z)=∑jψt′(St,j/πj)wj(z),\mathrm{MSG_t}(z)=\sum_j\psi_t'(S_{t,j}/\pi_j) w_j(z),

where St,j/πjS_{t,j}/\pi_j is the support that target jj has received relative to its desired share, and ψt′\psi_t' is a decreasing marginal weight. A candidate scores highly when its evaluation would contribute to targets that are behind their intended share. Both ingredients of this credit matter empirically. Shuffling MSG among candidates while keeping the same history sharply reduces coverage on every task (Appendix C.3), and restricting support to recent or top-quality evaluations also reduces coverage on every task (Appendix C.2).

3. Proposition 2 specifies what this signal aims at. MSG is not an ad hoc score. It is the directional derivative of the utility

Ut(S;T)=∑jπjψt(Sj/πj)U_t(S;T)=\sum_j\pi_j\psi_t(S_j/\pi_j)

along the candidate’s support contribution. Proposition 2 shows that, for any fixed total support NN, Ut(S;T)≤ψt(N)U_t(S;T)\leq\psi_t(N), with equality if and only if S=NπS=N\pi under strict concavity. Intuitively, the evaluation budget is a resource shared among targets, and with diminishing returns it is best spent when every target has received its intended share. MSG therefore points toward the prescribed allocation, and once that allocation is reached it is identical for all candidates, so no region is favored further. The exponential decay is one smooth choice satisfying this diminishing-return principle, similar to concave saturation functions used in probabilistic coverage (Lv et al., 2026). Appendix C.7 shows that reciprocal weights perform similarly on most tasks, while linear-hinge weights are more task-dependent.

AuthorsOpenReview ↗

Author Response (Part 2)

4. CMA-ES turns the signal into search. CMA-ES is rank-based: it adapts the mean, step size, and covariance of its sampling distribution from the ordering of candidates alone (Hansen, 2016). It therefore requires only a reliable ordering in each batch, and QDEM provides one even when no candidate improves the archive. With soft assignment, a batch of 540 candidates receives 539–540 distinct credit values; with hard assignment this number drops, in some cases to one, and performance falls on all eleven tasks (Appendix C.10). CMA-ME, CMA-MAE, and DMS also use CMA-ES emitters (Fontaine et al., 2020; Fontaine & Nikolaidis, 2023; Tjanaka et al., 2026), allowing us to compare different search-feedback designs within the same optimizer family. As with these methods, we do not prove global convergence of the resulting search, and we state this explicitly in the revised Discussion (Section 6, L530–531). The evidence in the next step indicates that this does not limit QDEM in practice.

5. The resulting search behaves as the analysis predicts. Steps 1–4 yield a testable prediction: if the generator follows MSG, realized evaluation effort should track the prescribed target shares. Our unequal-target experiment (Appendix C.8) tests exactly this. Changing only the target shares to 25%, 50%, and 75% yields evaluation allocations of approximately 24%, 50%, and 76%.

To examine how different search signals shape search, we additionally analyzed the evaluation allocation of QDEM, DMS, and CMA-MAE on Rastrigin 2D over five seeds (Appendix C.12).

MetricCMA-MAEDMSQDEM
Final QD Score ↑5,276.41 ± 14.385,723.88 ± 85.965,916.63 ± 36.07
Coverage (%) ↑80.13 ± 0.3891.53 ± 2.6493.34 ± 0.55
Late top-10 cell evaluation share (%) ↓21.83 ± 1.5040.30 ± 5.287.84 ± 1.49
Late effective cells ↑139.93 ± 23.2744.32 ± 8.97676.51 ± 195.62

Mean ± sample SD over five seeds. “Late” refers to the final 540,000 evaluations. Effective cells are calculated as 1/∑jpj21/\sum_j p_j^2, where pjp_j is the evaluation share of cell jj within this window.

QDEM allocates substantially less of its budget to the most-visited cells, maintains a broader visitation distribution, and achieves the highest mean final QD Score and Coverage. The heatmaps in Appendix C.12 show the same pattern over time: DMS increasingly concentrates evaluations near the boundaries, CMA-MAE shows less severe but still localized concentration, and QDEM remains broadly distributed. We interpret this as follows. Archive-relative signals evaluate candidates against archive-derived quality thresholds or estimates, which can concentrate search where such feedback continues to reward progress. QDEM can instead credit contributions to under-supported targets even without immediate archive improvement, consistent with the broader exploration observed here.

The same behavior appears on Hiker, where QDEM allocates 26% of its budget to the ten most-visited regions compared with 62% for DMS (Appendix C.1). Finally, replacing MSG with a kNN novelty score, with all other settings fixed, lowers QD Score and Coverage on all eleven tasks (Appendix C.11). Taken together, these results are consistent with the mechanism identified by the analysis and support it as a main source of the empirical gains.

We appreciate the reviewer's insightful comments, which helped us better articulate the mechanisms underlying QDEM's empirical success in the revised Discussion and strengthen the overall argument of our paper.

AuthorsOpenReview ↗

Author Response (Part 3)

Q1. The Gaussian weights on kk nearest references. How are these weights and references determined? What advice would there be for practitioners wishing to use your technique?

We appreciate the reviewer's questions about the implementation details and practical use of QDEM. Following your questions, we have also added explicit references in Section 4.1 (L183–188) to the detailed formulas and settings in the appendix, making them easier for readers to locate.

How references and weights are determined:

  1. References: References are fixed before search, and their resolution can be chosen independently of the reporting archive. When a representative target dataset is available, we use its behavior representations, following the reference-defined target setting of QDDM (Tjanaka et al., 2026): the 10,000 test images for TA and the CLIP embeddings of 10,000 LHQ landscape images for Hiker. Otherwise, we cover the prescribed behavior range directly: 100,000 uniformly sampled points for each numerical descriptor dimensionality, shared across tasks of the same dimensionality and across seeds, and a regular 20 × 20 grid for discrete robot descriptors (Appendices B.3–B.5).

  2. Gaussian weights: Each valid evaluation contributes one unit of support across its kk nearest references, with weights proportional to exp⁡(−∥z−rj∥2/(2h2))\exp(-\lVert z-r_j\rVert^2/(2h^2)) and normalized to sum to one (Eq. A.1). We use k=256k=256 on numerical tasks, 64 on TA, and 160 on Hiker.

  3. Bandwidth: The bandwidth is computed once from the reference set itself using a typical inter-reference distance (Eq. B.1), which sets the scale of Gaussian weight decay within each local neighborhood. It remains fixed throughout search.

Practical recommendations:

  1. Reference resolution and neighborhood size. We recommend choosing references that cover the behavioral regions of interest relatively uniformly and densely enough to distinguish meaningful behaviors, while avoiding unnecessary computational cost. A useful starting point is to scale kk proportionally with the reference count MM. Our sensitivity results (Appendix C.6) show that larger reference configurations generally benefit higher-dimensional numerical tasks. We also recommend soft assignment for continuous behavior spaces.

  2. Independence from the reporting archive. An important advantage of QDEM is that search-reference resolution can be chosen independently of the reporting archive. Fine-grained references can provide detailed search guidance while a coarser archive retains and reports results, making search more flexible without being constrained by archive resolution. Moreover, if evaluated solutions are logged, the reporting archive can be reconstructed at different resolutions after optimization through simple post-processing, without rerunning the search. We strongly encourage practitioners to take full advantage of this flexibility.

  3. Quality–support balance. We recommend starting with a moderate λ\lambda, chosen according to the quality loss practitioners are willing to accept for additional exploration. Since the support term is normalized to [0,1][0,1], λ\lambda bounds the quality disadvantage that additional support can compensate. On our normalized numerical benchmarks, values around 0.35–0.5 generally perform well (Appendix C.5). An excessively large value may sacrifice the quality aspect of QD, while a value that is too small may compromise its diversity aspect.

We have also incorporated some of these practical considerations into Section 6 (Discussion, L524–530) to make QDEM easier to understand and apply.

Reviewer_qoNbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Quality-Diversity (QD) optimization aims to find diverse, high-performing solutions. Most QD methods use an archive to retain solutions and guide search, but candidates that fail to improve the archive may still provide valuable search directions. We introduce Quality-Diversity Empirical Measure (QDEM), which separates search guidance from solution retention. Using a fixed reference projection, QDEM tracks cumulative support across all valid evaluations and directs search toward underexplored targets. Experiments show that QDEM outperforms state-of-the-art methods on standard QD benchmarks and high-dimensional visual reference tasks, while remaining competitive when archive improvement effectively guides search. In robot morphology evolution, QDEM allows rejected intermediate designs to guide further exploration, helping controllers recover and exceed previous performance.

Critical strengths

The paper's motivation are clear, and the topic of high interest and actual, since qulaity diversity algorithms emerged only recently in a strong fashion. I am also fine with its structure: Introducing all the necessary notation, then give some mathematical propositions, to finally provide some empirical results which are the core of the paper. I really like those, because they provide several interesting insights about how quality diversity works for controlled continuation, even if I found 5 runs a little bit few. I am also convinced regarding the remaining empirical results, which show exactly the purpose of this work.

Critical weaknesses

The core weakness of the paper is the introduction of the problem description and the mathematical concepts. Here, I recommend to introduce all sybmols carefully, and to write the proposition (including proof sketches) in a comprehensible way into the main paper, such that reader will be able to understand them. I also miss algorithms in pseudocodes you are using in your empirical studies! This is a thing you should definitely do in a revision or during the rebuttal!

Some points to address remain:

-> L47: Very interesting aspect! But you could introduce more cells to store individuals with low fitness there! Why is this a good approach then anyway? -> L56: How can this be done? -> L61: Explain the four subcases of QD in more detail! -> Section 2.3: You could add more precise mathematical descriptions of the underlying concepts. How does the map look like? Which type of cells are newly created? -> Chapter 4: Many symbols for the four different components are introduced without precise explanations. -> Proposition 1 and 2 are very hard to grasp since no intuition behind those is given. Further, symbols are hardly explained. What is the formal definition of C_t? In general, I recommend to be much more detailed and transparent with the maths to catch the reader. -> Sphere 2D/10D/20D/50D, Rastrigin 2D/10D, and Flat 2D/10D (Tjanaka et al., 2026: Explain those!

Questions for authors

See above!

3 comments
AuthorsOpenReview ↗

Author Response (Part 1)

We sincerely thank you for your careful reading, encouraging assessment, and constructive suggestions. We are pleased that you found our motivation clear and the topic timely, and especially glad that you found the robot morphology experiments insightful. We are also grateful for your valuable suggestions on making the mathematical presentation more transparent and accessible to readers. We are happy to address each of your points below.

W1. The core weakness of the paper is the introduction of the problem description and the mathematical concepts. Here, I recommend to introduce all sybmols carefully, and to write the proposition (including proof sketches) in a comprehensible way into the main paper, such that reader will be able to understand them.

We fully agree that a clear problem description and well-defined mathematical concepts are essential for understanding our work. We have clarified the motivation in the Introduction (L40–82), refined the problem formulation, notation, and archive update rules in Section 2 (L97–132) and Section 4 (L168–267) to improve clarity and readability, while preserving the core claims and method of the original submission.

In Section 4, we now introduce the mathematical concepts and notation progressively, from behavioral targets and cumulative support to target-relative valuation and MSG. We have also added intuitive explanations and brief proof sketches for Proposition 1 (L200–208) and Proposition 2 (L223–230), with full proofs in Appendix A. To keep the main exposition focused, the former Proposition 2 (exact target-support representation), which is less central to understanding the main method, has been moved to Appendix A.2 as Proposition A.1, and the former Proposition 3 (target calibration) is now Proposition 2. We believe these revisions make our method clearer and easier to follow.

W2. I also miss algorithms in pseudocodes you are using in your empirical studies! This is a thing you should definitely do in a revision or during the rebuttal!

We fully agree that including the pseudocode in the main text would help present our method more clearly. The QDEM pseudocode was originally placed in Appendix A.7. Following your suggestion, we have moved it into the main text as Algorithm 1 (L270–284), so readers can follow the procedure directly alongside the methodology.

AuthorsOpenReview ↗

Author Response (Part 2)

Q1. L47: Very interesting aspect! But you could introduce more cells to store individuals with low fitness there! Why is this a good approach then anyway?

Thank you for raising this thoughtful question. Increasing the number of archive cells or retaining multiple individuals per cell, as in MAP-Elites with Passive Genetic Diversity (MEPGD; Pugh et al., 2016), can indeed help preserve useful stepping stones. However, finer partitioning cannot distinguish candidates with identical behavior descriptors. Appendix C.4 illustrates this with a lower-fitness morphological intermediate that shares its parent's descriptor yet later produces a higher-fitness descendant. Retaining multiple individuals can alleviate this limitation, but expanding storage alone does not change the search feedback in archive-improvement-based methods. Directions requiring prolonged exploration without filling new cells or improving existing elites may therefore still receive insufficient positive feedback.

We particularly appreciate the insight behind your question. It helped us recognize an important missing logical connection in our original Introduction: although we had discussed the limitations of archive-based search, we had not clearly explained why these limitations motivate directly using behavioral targets to guide search. We apologize for not explaining this motivation more clearly.

Your question prompted us to clarify this motivation in the revised Introduction. We now begin from the goal of QD itself (L40–42):

QD optimization is built around a clearly defined goal of finding high-quality solutions that broadly cover a prescribed behavior space. This raises a natural question: Why not explicitly specify targets within this space and use them to guide search directly?

We further clarify why existing search feedback does not directly account for the desired allocation of evaluation effort (L42–44):

Existing QD search methods, however, often rely on indirect proxies such as archive improvement to guide search based on previously observed results rather than the desired allocation of evaluation effort across targets.

Reliance on archive improvement can lead to the stepping-stone problem discussed in both the original and revised Introduction (L52–57). This motivates QDEM, which explicitly specifies behavioral targets and uses cumulative evaluation support to guide search toward under-supported targets. By tracking how much evaluation effort each target has received, QDEM provides search credit to candidates contributing to under-supported targets, independently of which solutions are retained in the result archive.

Q2. L56: How can this be done?

Q3. L61: Explain the four subcases of QD in more detail!

Your questions helped us recognize that the actual search procedure needed a more concrete explanation. We have revised the Introduction and reorganized Section 4 accordingly.

Regarding Q2, we wish to allow evaluations rejected by the result archive to continue influencing subsequent search. This motivates maintaining an independent search state that accumulates support from all valid evaluations, including those not retained as elites. By recording how much evaluation effort each behavioral target has received, QDEM can identify targets that remain under-supported relative to their desired shares. It then uses MSG to give greater search credit to candidates contributing to these targets, guiding subsequent generator updates independently of archive retention. We now explain this motivation in the Introduction (L65–82) and present the corresponding mathematical formulation in Sections 4.1–4.3.

Regarding Q3, we have reorganized the original four-component description into a step-by-step explanation of how QDEM works. As we now explain in the Introduction (L78–82):

The search state then records the support that every valid evaluation, including those rejected by the archive, contributes to these targets. From this state, QDEM derives Marginal Support Gain (MSG) and combines it with task quality, so that the generator receives credit for contributions to under-supported targets, while the archive separately retains the resulting repertoire for presentation and evaluation.

Section 4 now follows this progression, introducing behavioral targets and the search state (Section 4.1), target-relative valuation (Section 4.2), and search control and result retention (Section 4.3).

We appreciate these suggestions, which helped us make the operation of QDEM easier to follow.

AuthorsOpenReview ↗

Author Response (Part 3)

Q4. Section 2.3: You could add more precise mathematical descriptions of the underlying concepts. How does the map look like? Which type of cells are newly created?

We have expanded Section 2.3 (L110–132) to explicitly define the fixed partition of the behavior space (e.g., a regular grid or CVT), the mapping from behaviors to cells, and the elite retained in each cell. We have also added the corresponding archive update rule (L115–118).

We further explain that the cells are predefined rather than dynamically created. A “new cell” refers to a previously empty cell becoming occupied, while improvement of an occupied cell requires replacing its elite with a higher-quality solution (L119–121). This makes the distinction between cell creation and archive improvement explicit.

Q5. Chapter 4: Many symbols for the four different components are introduced without precise explanations.

Q6. Proposition 1 and 2 are very hard to grasp since no intuition behind those is given. Further, symbols are hardly explained. What is the formal definition of C_t? In general, I recommend to be much more detailed and transparent with the maths to catch the reader.

We sincerely appreciate your suggestions.

Regarding Q5, we have reorganized Section 4 (L168–267) to improve readability. Rather than introducing a large number of symbols upfront, we now present the method step by step, introducing and defining notation as needed. This makes it easier for readers to understand the purpose of each component without being overwhelmed by notation. Section 4.1 defines the behavioral targets, support assignment, and cumulative search state. Section 4.2 explains how target-relative valuation leads to MSG, and Section 4.3 describes how MSG guides search while the result archive independently retains solutions.

Regarding Q6, we have added intuitive explanations and brief proof sketches to the main text. Proposition 1 (L200–208) now explains why cumulative support can be updated exactly without revisiting past evaluations. We have moved the former Proposition 2 (exact target-support representation) to Appendix A.2 as Proposition A.1 to keep the main exposition focused. The current Proposition 2 (L223–230) establishes why the desired support allocation maximizes the proposed utility, with a proof sketch based on Jensen's inequality.

We have also explicitly defined CtC_t as the candidate comparison set in Section 4.3 (L252–262). For CMA-ES emitters, Ct=BtC_t=B_t contains the full synchronous batch, while for survivor selection, Ct=Unique⁡(Pt∪Bt)C_t=\operatorname{Unique}(P_t\cup B_t) includes the current survivors and new offspring. The complete procedure is now presented in Algorithm 1 (L270–284), with detailed mathematical proofs retained in Appendix A.

Q7. Sphere 2D/10D/20D/50D, Rastrigin 2D/10D, and Flat 2D/10D (Tjanaka et al., 2026: Explain those!

We agree that simply listing the benchmark names and citing the original paper was insufficient for readers unfamiliar with these tasks. We have expanded Section 5.1 (L300–306) to explain their definitions and differences.

Specifically, all eight benchmarks use a 100-dimensional decision space, while the suffixes 2D/10D/20D/50D indicate the dimensionality of the behavior descriptors. The descriptors are obtained by transforming the decision variables and summing them in contiguous groups. Sphere has a unimodal quadratic quality landscape, Rastrigin has a multimodal landscape with many local optima, and Flat assigns constant quality to all candidates. These tasks allow us to examine QDEM across different behavioral dimensionalities and quality landscapes. The exact objective functions and behavior mappings are provided in Appendix B.3.

We hope that these explanations and revisions sufficiently address your concerns. Please let us know if any further clarification or modification is required to satisfy your remaining concerns.

References

Reviewer_XTyGOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a framework for Quality-Diversity methods that separates result retention from search state, so that evaluations that are rejected by the archive can still contribute to the search process. The method, QDEM, tracks how evaluation effort is distributed over the set of fixed reference targets in behavior space. Each candidate behavior is assigned a Marginal Support Gain (MSG) score, so that less explored targets are given a bonus (Eq.8) and the sampling distribution is then updated based on a trade-off between the candidate quality and its MSG ranking (Eq.9). The experiments are conducted on standard numerical benchmarks and high-dimensional visual targets. QDEM is compared to baselines such as CMA-MAE, CMA-ME, MAP-Elites, DDS and DMS, and mostly outperforms them, except on higher-dimensional Sphere, where DMS performs better. Lastly, the approach is evaluated on EvoGym morphology–controller coevolution, where it outperforms MAP-Elites in QD Score at full coverage.

Critical strengths

Framing. The paper examines a limitation of archive-based QD methods, where evaluations that do not improve the archive and thus are not added to the archive no longer influence the subsequent search process. It addresses this in a clear and straightforward way by computing the cumulative support for each target from all valid evaluations, which allows the candidate sampling distribution to be updated based on a combination of quality and the MSG score that mainly favors under-supported targets.

Experiments. The experiments validate that QDEM generally outperforms archive-improvement methods (MAP-Elites, CMA-ME, CMA-MAE, DMS) as well as a method that keeps a bounded buffer of past evaluations (DDS). It performs particularly well in exploration tasks where quality alone is not sufficient. In addition, the ablations are informative in determining what matters for performance, for example, shuffling MSG across candidates (Appendix C.3), while keeping the same cumulative history, causes coverage to collapse, showing that the history alone does not explain the improvement.

Critical weaknesses

Missing novelty-based baselines. While the method is compared against, and generally outperforms, archive-improvement methods (MAP-Elites, CMA-ME, CMA-MAE, DMS), it is not compared against methods such as Novelty Search, Novelty Search with Local Competition (NSLC) and Dominated Novelty Search (DNS). These are discussed in the related work but are not included as baselines, despite being among the closest existing alternatives as they try to address a similar core problem, where solutions that are useful for the search process may not necessarily correspond to high quality solutions, and therefore they should be included in the search process and not be discarded. Novelty search essentially allows past behaviors to still influence the search process through a novelty archive without an explicit quality metric, DNS rewards solutions that are either high-quality or far from fitter solutions and NSLC combines novelty with local quality through Pareto ranking. QDEM differs by using the cumulative support instead of a novelty archive and tries to balance novelty and quality by an explicit weighting between quality and support. DDS, which uses a low density oriented search of the behavior space, is used as a baseline in the numerical tasks but by design ignores quality. Given the MSG ablation (Appendix C.3, Table C2), removing MSG leaves a purely quality-driven search and thus performance collapses, showing that a diversity signal that is candidate-specific is necessary but not that MSG outperforms alternatives such as novelty. A comparison against these methods, especially NSLC, would therefore be important to assess whether the gains in performance come from the cumulative support representation.

Overall, the method is clear and the results are promising. The ablations show that cumulative support history indeed contributes substantially to the performance of QDEM framework (Appendix C.2), but without a comparison to novelty-based methods that also use quality (e.g. NSLC, DNS or MSG replaced by kNN novelty under the same setup), it remains unclear whether this cumulative support representation outperforms other standard exploration signals.

Questions for authors
  1. How does QDEM compare to an NSLC run with the same CMA-ES emitters and evaluation budget? Alternatively, what happens if MSG is replaced by a kNN novelty score with everything else fixed?
  2. QDEM restarts from a recent and top-quality memory (Table B2) and, on TA, uses a different restart schedule than CMA-MAE and DMS (Appendix B.4). How does QDEM perform with the same restart rule and schedule as DMS?
  3. How does QDEM perform with hard instead of soft assignment on the same numerical tasks?
  4. What is the runtime of QDEM compared to the baselines?
8 comments
AuthorsOpenReview ↗

Author Response (Part 1)

We sincerely thank you for your careful reading and for your insightful and constructive feedback. We are glad that you found our method clear and straightforward, our results promising, and our ablations informative. We would like to address each of your concerns below.

W1. Missing novelty-based baselines. While the method is compared against, and generally outperforms, archive-improvement methods (MAP-Elites, CMA-ME, CMA-MAE, DMS), it is not compared against methods such as Novelty Search, Novelty Search with Local Competition (NSLC) and Dominated Novelty Search (DNS).

Q1. How does QDEM compare to an NSLC run with the same CMA-ES emitters and evaluation budget? Alternatively, what happens if MSG is replaced by a kNN novelty score with everything else fixed?

We further compared QDEM with NSLC-CMA and DNS. Following Lehman and Stanley (2011), NSLC-CMA uses k = 15 and incorporates Pareto ranking based on novelty and local quality competition into CMA-ES. NSLC-CMA uses the same CMA-ES emitter configuration as QDEM and follows the restart schedule of DMS and CMA-MAE. For DNS, we use the official implementation and publicly available configuration of Bahlous-Boldi et al. (2025), with a population size of 1,024, k = 3 nearest neighbors, and Iso+Line mutation scales of 0.005 and 0.05, respectively. All methods share the evaluator, evaluation budget, and reporting archive. Consistent with the baseline evaluation protocol in the main paper, we use 20 seeds (42–61) for numerical tasks and five seeds (42–46) for image tasks. Each numerical run uses 5.4 million evaluations.

Table 1a. Comparison with novelty-based methods. Each cell reports QD Score / Coverage (%), mean ± sample SD. Numerical tasks use 20 seeds (42–61), and image tasks use five seeds (42–46), consistent with the main-paper baseline protocol.

TaskQDEMNSLC-CMADNS
(a) Numerical benchmarks
Flat 2D8,218.55 ± 73.05 / 82.19 ± 0.732,636.80 ± 206.57 / 26.37 ± 2.072,334.90 ± 201.07 / 23.35 ± 2.01
Flat 10D8,433.30 ± 92.78 / 84.33 ± 0.931,696.05 ± 43.82 / 16.96 ± 0.44444.20 ± 35.12 / 4.44 ± 0.35
Rastrigin 2D5,867.86 ± 73.28 / 92.34 ± 1.691,613.65 ± 630.18 / 22.36 ± 10.041,716.97 ± 102.32 / 21.91 ± 1.41
Rastrigin 10D5,328.62 ± 58.86 / 88.02 ± 0.71318.08 ± 21.34 / 4.08 ± 0.29197.68 ± 13.12 / 2.91 ± 0.21
Sphere 2D7,123.92 ± 21.15 / 94.83 ± 0.784,568.96 ± 191.46 / 54.78 ± 2.423,348.37 ± 133.10 / 39.40 ± 1.62
Sphere 10D7,005.63 ± 44.88 / 92.25 ± 0.43139.35 ± 13.49 / 1.43 ± 0.14219.03 ± 24.21 / 2.95 ± 0.34
Sphere 20D6,879.16 ± 37.09 / 90.08 ± 0.34485.30 ± 44.28 / 5.07 ± 0.471,574.43 ± 140.77 / 21.24 ± 2.52
Sphere 50D6,676.60 ± 26.18 / 82.42 ± 0.251,668.05 ± 50.22 / 17.55 ± 0.542,261.83 ± 227.36 / 29.79 ± 3.82
(b) Image benchmarks
TA-MNIST961.98 ± 0.48 / 99.98 ± 0.04947.18 ± 3.97 / 99.06 ± 0.34878.02 ± 39.18 / 94.02 ± 4.05
TA-FMNIST827.49 ± 5.94 / 85.02 ± 0.62554.15 ± 22.86 / 57.06 ± 2.37181.63 ± 21.58 / 18.92 ± 2.27
Hiker428.34 ± 75.37 / 8.30 ± 0.36-113.36 ± 145.32 / 0.80 ± 0.32-33,693.45 ± 16,068.44 / 1.96 ± 0.78

QDEM achieves higher mean QD Score and Coverage than both NSLC-CMA and DNS across all eleven tasks. The Flat results show that QDEM maintains an advantage even when quality provides no search signal. Figure D4 in Appendix D.4 visualizes evaluation allocation on Flat 2D (seed 42): NSLC-CMA and DNS concentrate evaluations in smaller regions, while QDEM maintains broader exploration across the displayed budget windows. These results support the effectiveness of target-guided exploration relative to the evaluated novelty-based methods.

Due to computational and time constraints during the rebuttal period, some runs were executed in parallel. We report the performance results for NSLC-CMA and DNS in Appendix D.4, but do not yet have comparable wall-clock measurements under matched conditions for these two baselines. We will remeasure their runtime under matched conditions, include both methods in the main-paper baseline comparisons, and report their runtime in the appendix in the final version of the paper.

AuthorsOpenReview ↗

Author Response (Part 2)

Following your suggestion, we further examined the role of MSG relative to a conventional novelty signal. We constructed a kNN-CMA control that replaces only MSG with the mean Euclidean distance from each candidate behavior to its nearest neighbors in the behavior history. We use k = 100, following the setting in the DDS paper by Lee et al. (2024). All other settings, including the quality term, rank normalization, CMA-ES configuration, restart policy, and evaluation budget, remain unchanged. kNN uses the full valid-evaluation history, updated after scoring each batch.

Table 1b. MSG versus kNN novelty scoring. Each cell reports QD Score / Coverage (%), mean ± SD over five seeds.

TaskQDEMkNN-CMA
(a) Numerical benchmarks
Flat 2D8,212.80 ± 72.91 / 82.13 ± 0.737,892.40 ± 56.66 / 78.92 ± 0.57
Flat 10D8,444.20 ± 110.60 / 84.44 ± 1.114,730.00 ± 36.81 / 47.30 ± 0.37
Rastrigin 2D5,916.63 ± 36.07 / 93.34 ± 0.554,827.87 ± 97.11 / 72.37 ± 1.78
Rastrigin 10D5,333.78 ± 93.78 / 88.03 ± 1.082,664.86 ± 27.89 / 41.32 ± 0.48
Sphere 2D7,124.99 ± 17.44 / 94.65 ± 0.555,781.90 ± 81.18 / 70.95 ± 1.27
Sphere 10D7,033.44 ± 65.71 / 92.52 ± 0.643,324.00 ± 31.84 / 41.46 ± 0.45
Sphere 20D6,898.82 ± 41.72 / 90.19 ± 0.395,703.45 ± 55.44 / 71.03 ± 0.75
Sphere 50D6,685.84 ± 30.95 / 82.48 ± 0.246,196.56 ± 18.11 / 74.21 ± 0.15
(b) Image benchmarks
TA-MNIST961.98 ± 0.48 / 99.98 ± 0.04530.42 ± 63.91 / 56.16 ± 6.81
TA-FMNIST827.49 ± 5.94 / 85.02 ± 0.62228.18 ± 28.28 / 23.82 ± 2.95
Hiker428.34 ± 75.37 / 8.30 ± 0.3695.04 ± 58.80 / 2.82 ± 0.21

QDEM achieves higher mean QD Score and Coverage across all eight numerical tasks and all three image tasks. The Flat 2D heatmaps (Figure C3, Appendix C.11) show that QDEM maintains broader exploration, while kNN-CMA explores a smaller region in later stages. These results suggest that QDEM's gains arise not only from retaining history or introducing a diversity reward, but also from evaluating each candidate's value for search using cumulative support at the targets (MSG), rather than relying solely on distances between the candidate and historical samples.

AuthorsOpenReview ↗

Author Response (Part 3)

Q2. QDEM restarts from a recent and top-quality memory (Table B2) and, on TA, uses a different restart schedule than CMA-MAE and DMS (Appendix B.4). How does QDEM perform with the same restart rule and schedule as DMS?

Thank you for pointing out the potential influence of restart strategies on the algorithm comparisons. To address this concern, we conducted additional experiments controlling the restart source and schedule, including comparisons in both directions between QDEM and the baselines.

1. Effect of the Restart Source

To test archive-based restarts, as used by DMS and CMA-MAE, QDEM-Archive samples restart solutions uniformly from the result archive.

Table 2. QDEM with archive-based restarts, as used by DMS and CMA-MAE. Cells report QD Score / Coverage (%), both as mean ± SD.

TaskQDEMQDEM-ArchiveDMSCMA-MAEDDSMAP-Elites
(a) Numerical benchmarks
Flat 2D8,212.80 ± 72.91 / 82.13 ± 0.738,500.20 ± 45.31 / 85.00 ± 0.458,025.60 ± 210.94 / 80.26 ± 2.115,670.60 ± 451.46 / 56.71 ± 4.517,232.60 ± 250.99 / 72.33 ± 2.514,299.80 ± 58.93 / 43.00 ± 0.59
Flat 10D8,444.20 ± 110.60 / 84.44 ± 1.118,551.60 ± 108.51 / 85.52 ± 1.097,858.40 ± 148.87 / 78.58 ± 1.491,527.00 ± 101.99 / 15.27 ± 1.024,834.20 ± 190.46 / 48.34 ± 1.90102.60 ± 48.18 / 1.03 ± 0.48
Rastrigin 2D5,916.63 ± 36.07 / 93.34 ± 0.555,916.63 ± 36.07 / 93.34 ± 0.555,723.88 ± 85.96 / 91.53 ± 2.645,276.41 ± 14.38 / 80.13 ± 0.382,376.65 ± 274.24 / 72.41 ± 5.433,155.96 ± 14.15 / 48.04 ± 0.15
Rastrigin 10D5,333.78 ± 93.78 / 88.03 ± 1.085,187.63 ± 33.55 / 88.21 ± 0.415,078.08 ± 45.68 / 87.62 ± 0.30146.20 ± 12.98 / 1.66 ± 0.152,788.50 ± 106.28 / 55.29 ± 1.61570.27 ± 26.75 / 8.16 ± 0.38
Sphere 2D7,124.99 ± 17.44 / 94.65 ± 0.557,124.99 ± 17.44 / 94.65 ± 0.557,039.26 ± 68.74 / 96.43 ± 1.276,333.10 ± 23.84 / 81.01 ± 0.353,517.20 ± 144.98 / 72.05 ± 2.684,158.23 ± 26.56 / 50.67 ± 0.31
Sphere 10D7,033.44 ± 65.71 / 92.52 ± 0.646,854.77 ± 46.64 / 91.44 ± 0.566,403.56 ± 59.51 / 89.04 ± 0.68744.49 ± 129.89 / 7.77 ± 1.403,719.66 ± 114.96 / 56.39 ± 1.67168.34 ± 65.05 / 1.73 ± 0.67
Sphere 20D6,898.82 ± 41.72 / 90.19 ± 0.396,910.27 ± 24.85 / 90.14 ± 0.367,359.32 ± 122.66 / 95.93 ± 0.22836.38 ± 90.88 / 8.61 ± 0.976,996.82 ± 17.30 / 84.37 ± 0.193,297.89 ± 144.30 / 35.75 ± 1.65
Sphere 50D6,685.84 ± 30.95 / 82.48 ± 0.246,887.80 ± 23.25 / 83.88 ± 0.176,980.11 ± 20.91 / 86.81 ± 0.222,343.14 ± 58.89 / 24.38 ± 0.646,371.65 ± 7.29 / 74.29 ± 0.093,864.19 ± 66.67 / 40.81 ± 0.73
(b) Image benchmarks
TA-MNIST961.98 ± 0.48 / 99.98 ± 0.04962.02 ± 0.60 / 99.98 ± 0.04953.13 ± 2.13 / 100.00 ± 0.00954.24 ± 1.87 / 99.44 ± 0.26—940.71 ± 3.01 / 98.26 ± 0.34
TA-FMNIST827.49 ± 5.94 / 85.02 ± 0.62820.99 ± 7.47 / 84.26 ± 0.77710.43 ± 8.11 / 73.20 ± 0.85617.44 ± 12.87 / 63.06 ± 1.33—535.92 ± 20.72 / 55.02 ± 2.16
Hiker428.34 ± 75.37 / 8.30 ± 0.36428.34 ± 75.37 / 8.30 ± 0.36121.98 ± 122.08 / 3.00 ± 0.77-25.36 ± 128.32 / 1.41 ± 0.23—-19,295.61 ± 6,793.34 / 5.90 ± 1.48

As shown in Table 2, QDEM with archive-based restarts still outperforms DMS on six of the eight numerical tasks and all three high-dimensional image tasks, consistent with the original QDEM results. Switching the restart source has little effect on QDEM, with relative changes in QD Score within 3.5% across all tasks. These results indicate that QDEM's performance advantage does not depend on its particular memory-based restart source.

Furthermore, the comparable performance highlights a design advantage of QDEM: it can restart entirely from memory without querying the result archive during search, allowing the archive to serve solely for result retention.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response to Reviewers:Summary of Revisions

We sincerely thank all reviewers for their careful reading and thoughtful, constructive feedback. We greatly appreciate your recognition of our motivation, method, and experimental results. Your suggestions have been invaluable in helping us improve the clarity of our presentation and strengthen the empirical evidence.

We have highlighted the revisions in blue in the manuscript. Our core claims, methodology, and original experimental results remain unchanged. The main revisions are summarized below.

1. Clarified motivation and presentation

We revised the Introduction to convey our central motivation more clearly. Since QD already has a prescribed behavior space to cover, why not explicitly specify behavioral targets and use them to guide search directly? Existing methods often rely on indirect proxies such as archive improvement, which may overlook useful stepping stones and prematurely abandon promising search directions. This motivates QDEM.

We also reorganized Section 4 to introduce QDEM step by step, added proof sketches, and moved Algorithm 1 into the main text. We further expanded the Related Work and Discussion sections to clarify QDEM’s mechanism and implications.

2. Additional experiments

Following the baseline evaluation protocol in the main paper, our comparisons with NSLC-CMA and DNS use 20 seeds for numerical tasks and five seeds for image tasks. The other additional comparisons and ablations use five seeds:

  • Novelty baselines (Appendix D.4): QDEM achieves higher mean QD Score and Coverage than NSLC-CMA and DNS on all eleven tasks.
  • MSG vs. kNN novelty (Appendix C.11): Replacing only MSG with kNN novelty reduces QD Score and Coverage on all eleven tasks.
  • Soft vs. hard assignment (Appendix C.10): Soft assignment achieves higher QD Score and Coverage on all eleven tasks.
  • Restart (Appendix C.9): Switching to archive-based restarts changes QDEM's QD Score by less than 3.5% on each task.
  • Runtime (Appendix D.5): We additionally report wall-clock runtime across numerical and visual tasks.

Together with our original ablations (Appendices C.2–C.3), these experiments help clarify the distinct roles of QDEM's components and provide further evidence for their contributions.

3. Understanding why QDEM works

We have also strengthened the explanation of QDEM's underlying mechanism in the Discussion (Section 6, L510–518). Proposition 2 characterizes the desired support allocation, MSG provides candidate-specific feedback toward under-supported targets, and CMA-ES translates this feedback into adaptive search.

Our unequal-target experiment (Appendix C.8) demonstrates how prescribed target shares influence actual evaluation allocation. We further added evaluation-budget heatmaps on Rastrigin 2D (Appendix C.12), illustrating how QDEM sustains broader exploration than archive-relative search signals, consistent with our Hiker findings (Appendix C.1).

We hope we have addressed your concerns and questions in our individual responses. Please let us know if you have any other questions. We would like to discuss with the reviewers to make the paper even better.

Dear Reviewers,

As the discussion phase draws to a close, please acknowledge the author's response and let them know whether it has addressed some or all of your concerns.

Thank you for the time and effort you and the other reviewers have put into this discussion.

Best,

Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.