acceptodds
Under review as a conference paper at ICLR 2027

Instance Clustering and Selection: Reducing Evaluation Cost for Automated Algorithm Design in LLM-Assisted Evolutionary Search

Abstract

Candidate evaluation is a computational bottleneck in LLM-assisted evolutionary search (LES) for automated algorithm design, as each generated algorithm must be evaluated on training instances to provide a search signal to guide the evolution. We identify instance redundancy as a key inefficiency and propose Behavior-based Dynamic Instance Clustering and Selection (B-DICS), a feature-free method that represents instances through their behavioral responses to candidate algorithms. B-DICS progressively uncovers latent instance structure during search by clustering instances in the behavior space and selecting representative core instances for efficient evaluation. We further integrate B-DICS into LES to form a co-evolving framework, B-DICS-LES, where emerging algorithms induce more discriminative behavioral signals that refine the instance structure over time. This closed feedback loop reduces evaluations while preserving the fidelity of search guidance and enabling structure-aware algorithm design. Experiments on three algorithm design tasks show that B-DICS-LES achieves state-of-the-art performance while reducing evaluation cost by an average of 29.8%, paving the way for the scalable deployment of the LES paradigm in real-world automated algorithm design.

Primary area:
optimization
Keywords:
Automated algorithm design, instance selection, evaluation cost reduction

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_mEmLOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes B-DICS-LES, a framework for reducing evaluation costs in LLM-assisted evolutionary search for automated algorithm design. The method uses behavioral responses to dynamically cluster problem instances and select representative subsets for candidate evaluation, while integrating instance selection with specialized evolutionary search. Experiments on three algorithm design tasks demonstrate competitive performance with an average reduction of 29.8% in instance evaluations.

Critical strengths
  1. The paper addresses an important computational bottleneck in automated algorithm design by introducing behavior-based dynamic instance clustering and selection. Rather than relying on predefined instance features, B-DICS exploits algorithm evaluation data naturally accumulated during evolution to identify representative instances. This approach is particularly valuable for black-box or unfamiliar problem domains where meaningful instance features are difficult to obtain.
  2. Experiments across three algorithm design tasks demonstrate an average reduction of 29.8% in instance evaluations while maintaining competitive performance against strong LES baselines. The additional analyses of clustering convergence, ranking fidelity, and computational overhead further support the effectiveness of the proposed approach. These results suggest that behavior-driven instance reduction is a promising direction for improving the scalability of LLM-assisted evolutionary search.
Critical weaknesses
  1. The innovativeness of this method is not yet clearly distinguished from existing research. DyCA has already explored behavior-based dynamic instance clustering and dedicated evolution, while complementary population structures and diverse search mechanisms originate from early LES frameworks such as EoH-S. The true novelty of this paper appears to lie primarily in the introduction of anchor-based instance reduction and the use of a smaller number of instances to evaluate candidate algorithms. Furthermore, the comparative and ablation experiments are insufficient. A direct comparison with DyCA would be more beneficial. It remains unclear whether the observed benefits of anchor selection, dynamic recalibration, and complementary pooling consistently hold for OBP and LLC. Extending these ablations to the other tasks would provide stronger evidence for the general effectiveness of the proposed components.
  2. Although the paper reports a 29.8% average reduction in instance evaluations, it does not directly demonstrate the corresponding savings in actual evaluation time. Appendix B.3.3 only provides a runtime breakdown for B-DICS-LES, without comparable evaluation-time or end-to-end runtime results for the original LES baselines. Such comparisons are needed to quantify the practical computational benefits of the proposed method. In addition, the computational cost is analyzed for only one dataset task. It is necessary to extend the runtime comparison to all three tasks.
Questions for authors
  1. The proposed instance selection criterion maximizes the number of distinguishable behavioral patterns, but this does not necessarily guarantee that the selected instances preserve the fitness values or relative rankings of candidate algorithms on the full training set. Although the appendix provides some evidence of ranking fidelity, it remains unclear whether this property holds consistently throughout evolution, particularly for newly generated algorithms. How do the authors ensure that the reduced instance set provides sufficiently reliable fitness estimates for guiding evolutionary selection?
  2. The evaluation protocol reports the performance of the best-performing algorithm from the final algorithm portfolio as an upper-bound measure. However, it is unclear how the appropriate algorithm is selected for an unseen test instance in practice. The authors should clarify this procedure and discuss whether additional evaluation costs are required for algorithm selection.
4 comments
AuthorsOpenReview ↗

Response to Reviewer mEmL (Part 1/3)

Dear Reviewer mEmL and AC,

We thank the Reviewer for carefully reading our submission and for the constructive comments. Below, we address the questions point by point. In response to the identified weaknesses, we have strengthened the experimental validation and added further analyses and clarifications. All corresponding revisions have been incorporated into the revised manuscript and highlighted in blue.

Question 1:Clarification and Evidence on Ranking Fidelity During Evolution

We agree that maximizing the number of distinguishable behavioral patterns does not mathematically guarantee the exact preservation of full-set fitness values or pairwise rankings for unseen algorithms. Indeed, no objective based solely on currently observed algorithms can guarantee accurate rankings for algorithms that have not yet emerged, even if ranking fidelity itself is directly optimized. We mitigate this limitation through two complementary mechanisms:

  1. Population-Based Selection Tolerance & Full-Set Supplementary Evaluation: Unlike single-point optimization, which is highly sensitive to ranking errors, population-based evolutionary search exhibits inherent resilience to minor ranking noise. A promising candidate algorithm does not need to be ranked first to survive; as long as it is not severely misranked, it may remain in the population and retain opportunities for further evolution. Crucially, at the end of each recalibration interval, surviving algorithms undergo supplementary evaluations on all omitted instances. This recovers their exact full-set fitness, correcting coreset-based estimation errors for subsequent search and recalibration.

  2. Dynamic Recalibration: Intuitively, removing instances that provide largely redundant behavioral and performance information across the currently observed algorithms should have limited impact on their relative rankings. Since automated algorithm design is an incremental process, our framework periodically incorporates newly emerging behavioral responses and refreshes the coreset. This allows the coreset to adapt to the evolving search frontier and maintain ranking fidelity throughout the search.

Empirical Evidence of Ranking Fidelity Throughout Evolution:

To empirically examine whether ranking fidelity is consistently maintained throughout evolution, we retrieved the coresets logged at every accelerated interval across five CVRP runs, obtaining 19 coresets in total. We evaluated an independent pool of 567 fully evaluated reference algorithms on both each coreset and the complete set of 240 training instances, and measured the Spearman rank correlation between their resulting mean-score rankings.

  • Across all coresets, Spearman's (ρ\rho) averages 0.9873, with the lowest single-coreset correlation reaching 0.9791.
  • Notably, the initial transition in each run already achieves a mean Spearman's (ρ\rho) of 0.9881, while subsequent transitions maintain a consistently high average correlation of 0.9870.

These results demonstrate that high ranking fidelity is not merely achieved by the final coreset, but is consistently maintained across the observed evolutionary stages. We have incorporated these additional results into Appendix C.4.4 of the revised manuscript.

(Continued in Part 2/3...)

AuthorsOpenReview ↗

Response to Reviewer mEmL (Part 2/3)

(Continued from Part 1/3)

Question 2: Clarification on Algorithm Selection for Unseen Instances and Deployment Overhead

We thank the Reviewer for this insightful comment. We agree that practical deployment is an important consideration for real-world algorithm applications.

In the current framework, following the evaluation protocol established in EoH-S, we do not explicitly perform instance-level algorithm selection for unseen test instances. Instead, we recommend directly executing the complementary algorithm portfolio on the target instance and selecting the best solution among the resulting outputs. When sufficient computational resources are available, the portfolio algorithms can be executed in parallel. This avoids the need for a separate instance-selection model or an additional probing stage.

For tasks without well-established instance features, B-DICS offers a potential route toward instance-level algorithm selection. Specifically, one could first execute a set of anchor algorithms on an unseen instance to obtain its behavioral response vector, and then match the instance to the learned instance clusters to select the corresponding specialist, in a manner conceptually related to Exploratory Landscape Analysis (ELA). However, this approach requires additional evaluations of the anchor algorithms before selecting a solver. In our setting, we consider directly executing the compact complementary portfolio more practical than incurring this additional probing cost.

Alternatively, users can deploy a single algorithm selected according to its average performance across the training instances, following the standard EoH protocol. This incurs no additional online selection cost, although it may sacrifice some performance on instances that benefit from specialized algorithms.

Nevertheless, your comment highlights an essential direction for practical deployment. We are currently pursuing this line of research in our ongoing follow-up work: for novel tasks without effective prior instance features, we aim to leverage the behavioral structures uncovered by B-DICS to guide the automated construction of instance feature representations during the evolutionary search itself. This will allow unseen instances to be directly mapped to feature vectors for ultra-fast online matching and algorithm selection. However, this representation-learning mechanism is beyond the scope of the current submission, which focuses on evaluation-efficient automated algorithm design.

Response to Weakness 1: Direct Comparison with DyCA

We have added a direct empirical comparison with the concurrent work DyCA to the main experimental results in Table 1 and Appendix C.2.

We have also included a more detailed comparison in Appendix B to clarify the distinct research objectives and contributions of the two approaches:

AspectDycAOur B-DICS-LES
Primary research questionHow can LES improve robustness under heterogeneous instance distributions?How can LES substantially reduce evaluation cost while preserving search fidelity?
Targeted LES stageEvolutionary optimizationCandidate evaluation
Primary algorithmic contributionBias-aware evolutionary optimization (Weighted CPM, specialist evolution, adaptive resource allocation)Behavior-based instance reduction (core instance selection and evaluation replacement)
Primary optimization objectiveTail robustness and reliabilityComputational efficiency
Primary evaluation metricsAverage performance, tail performance, robustnessEvaluation cost, search fidelity, efficiency
Main scientific conclusionStructure-aware optimization substantially improves robustnessStructure-aware instance selection substantially reduces evaluation cost while preserving evolutionary guidance

In summary, while DyCA focuses on improving the robustness of evolutionary optimization, our contribution is an anchor-based coreset selection approach that substantially reduces candidate-evaluation costs while preserving informative feedback for LES.

Response to Weakness 2: Additional Ablation Studies on OBP and LLC

We have extended the ablation studies to OBP and LLC in Appendix C.7. The additional results consistently support the contributions of anchor selection, dynamic recalibration, and complementary pooling, demonstrating that their observed benefits are not limited to CVRP.

(Continued in Part 3/3...)

AuthorsOpenReview ↗

Response to Reviewer mEmL (Part 3/3)

(Continued from Part 2/3)

Response to Weakness 3: Wall-Clock Runtime Comparison

We have added wall-clock runtime comparisons with other algorithm design methods in Appendix C.3. The results show that the reduction in instance evaluations translates into practical savings in algorithm design and evaluation time, confirming that the efficiency gains are not limited to evaluation counts.

Response to Weakness 4: Computational Cost Analysis on Additional Tasks

We have further added computational-cost analyses of B-DICS-LES on OBP and LLC in Appendix C.4.3, providing additional evidence of its computational overhead across different problem domains.


We sincerely thank the Reviewer again for the insightful comments and constructive suggestions. They have helped us strengthen both the empirical validation and the presentation of our contributions. All corresponding changes have been incorporated into the revised manuscript and highlighted in blue.

We hope that these clarifications and additional results adequately address your concerns and lead to an improved rating for our submission. Please let us know if you have any remaining questions or if further discussion would be helpful—we are more than happy to engage further.

AuthorsOpenReview ↗

Follow-up on Rebuttal

Dear Reviewer mEmL,

We would like to kindly follow up on our rebuttal and the revised manuscript. In response to your concerns, we have added a direct comparison with DyCA, extended the ablation studies to OBP and LLC, and provided wall-clock runtime comparisons and computational-cost analyses across all three tasks. We have also added an analysis of ranking fidelity throughout evolution and clarified the algorithm selection procedure for unseen instances.

As the discussion period is approaching its end, we would greatly appreciate it if you could take another look at our responses and let us know whether they have addressed your concerns. We would be happy to provide any further clarification.

Thank you again for your thoughtful review and constructive suggestions.

Best regards, The Authors of Submission 17245

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

This paper proposes B-DICS to reduce candidate-evaluation costs in LLM-assisted evolutionary algorithm design. It represents instances through algorithm performance, selects anchor algorithms, dynamically clusters instances, and evaluates new candidates on representative subsets once the clustering stabilizes. The resulting B-DICS-LES framework combines specialist and complementary algorithm pools. Experiments on three tasks, with five independent search runs and additional public-benchmark evaluations, report competitive portfolio performance with an average 29.8% reduction in instance evaluations, including supplementary evaluations.

Critical strengths

1.The paper addresses a practical bottleneck in automated algorithm design. Updating instance representations from evolving algorithm behavior provides a useful way to reduce evaluation costs without requiring handcrafted instance features.

2.The empirical evidence extends beyond final performance comparisons. Independent search runs, component ablations, ranking-fidelity analysis, and additional public-benchmark evaluations provide meaningful support for the approach. Explicitly accounting for supplementary evaluations strengthens the reported evaluation-count savings.

Critical weaknesses

1.The core-instance selection rule is insufficiently specified. Equation (9) counts distinct anchor-performance profiles using the continuous response matrix. If all anchors have different scores on the initial representative instance, this count already reaches its maximum, potentially terminating augmentation immediately. Unlike anchor selection, the manuscript does not explicitly specify discretization or a numerical tolerance here. This ambiguity affects reproducibility and the interpretation of the central selection mechanism.

2.The incremental benefit over alternative instance-selection strategies needs clearer support. Tables 2 and 9 do not clearly specify whether subset sizes and evaluation budgets are matched across strategies. Moreover, existing online behavior-based down-sampling methods, such as informed down-sampled lexicase selection [1], provide relevant context beyond random selection. These gaps limit conclusions about the specific advantage of the proposed selection rule.

[1] Ryan Boldi et al. Informed Down-Sampled Lexicase Selection: Identifying Productive Training Cases for Efficient Problem Solving. Evolutionary Computation, 32(4):307–337, 2024. https://doi.org/10.1162/evco_a_00346

Questions for authors

1.Does Equation (9) operate on raw or discretized responses? Please specify the equality criterion, stopping rule, and cluster-specific selection budgets, and explain what prevents immediate saturation after selecting one instance.

2.Are the strategies in Tables 2 and 9 matched in subset size, refresh schedule, and total evaluation cost? Please also clarify the methodological distinction from online informed down-sampling approaches such as [1].

3.Were the algorithms in Table 9 excluded from constructing the anchors and core subsets? This distinction matters for interpreting whether the selected instances preserve rankings of newly generated candidates.

4 comments
AuthorsOpenReview ↗

Response to Reviewer HCJD (Part 1/2)

Dear Reviewer and AC,

We thank the Reviewer for carefully reading our submission and for the constructive comments. We appreciate the reviewer’s recognition of the practical significance of B-DICS and its empirical effectiveness. Below, we address the two weaknesses and the specific questions in detail.

Q1

1. Does Equation (9) operate on raw or discretized responses?

Equation (9) operates on discretized responses. Specifically, for each cluster CkC_k, let A(k)\mathcal A^{(k)} denote its current population of surviving candidate algorithms. Their responses on CkC_k are first processed using Natural Break Discretization (Appendix D.1.1), yielding the discrete response matrix L(k)\mathbf L^{(k)}. We have clarified the notation in Eq. (9) as follows:Ψ(W)=∣U((LW,A(k)(k))⊤)∣.\Psi(\mathcal W) = \left\vert{}\mathcal U\left( (\mathbf L^{(k)}_{\mathcal W,\mathcal A^{(k)}})^\top \right)\right\vert{}.

Since the responses are discretized into integer-valued behavioral tiers, two candidate algorithms are considered to have identical profiles if and only if their discretized responses are exactly equal across all selected instances. Thus, no floating-point tolerance is required. We have clarified this definition in Appendix D.3.

2. Clarification on the stopping rule and cluster-specific selection budgets

The greedy augmentation follows the following stopping criteria:

(i) No further discriminative gain: Augmentation stops when no remaining instance yields a positive marginal gain in Ψ\Psi, i.e.,max⁡Ii∈Ck∖W[Ψ(W∪{Ii})−Ψ(W)]=0.\max_{I_i\in C_k\setminus\mathcal W} \left[ \Psi(\mathcal W\cup\{I_i\})-\Psi(\mathcal W) \right]=0.This is equivalent to Ψ(W)=Ψ(Ck)\Psi(\mathcal W)=\Psi(C_k), following the same operational principle as anchor selection in Appendix D.1.2.

(ii) User-specified core-set budget (optional): B-DICS also supports an optional budget for explicitly controlling the retained instance fraction. Given a target evaluation-saving fraction ρ∈[0,1]\rho\in[0,1], the retained fraction is 1−ρ1-\rho, and the cluster-specific budget is defined asBk=max⁡(1,⌊(1−ρ)∣Ck∣⌋).B_k=\max\left(1,\left\lfloor(1-\rho)\vert{}C_k\vert{}\right\rfloor\right). Augmentation terminates once ∣W∣=Bk\vert{}\mathcal W\vert{}=B_k. The minimum of one ensures that each cluster retains at least one representative instance. We clarify that this optional budget is not activated in our reported experiments, where the no-gain criterion is used as the stopping rule. We have added the explicit budget definition to Appendix D.3.

3. What prevents immediate saturation after selecting one instance?

The natural-break discretization prevents minor numerical differences from being treated as distinct behavioral tiers.Let mk=∣A(k)∣m_k=\vert{}\mathcal A^{(k)}\vert{}, with mk≥2m_k\geq 2, denote the number of surviving candidate algorithms in cluster CkC_k. Consider the initial representative instance Iinit(k)I_{\mathrm{init}}^{(k)}. Let its sorted candidate responses be v1≤⋯≤vmkv_1\leq\cdots\leq v_{m_k}, with adjacent gaps gu=vu+1−vug_u=v_{u+1}-v_u and mean gapgˉ=1mk−1∑u=1mk−1gu.\bar g=\frac{1}{m_k-1}\sum_{u=1}^{m_k-1}g_u.When gˉ=0\bar g=0, all responses are identical and only one behavioral tier is induced. Otherwise, since ηgap=2.0\eta_{\mathrm{gap}}=2.0, the discretization threshold satisfiesτi≥2gˉ.\tau_i\geq 2\bar g.Let ss denote the number of significant gaps. By definition, each significant gap satisfies gu>τig_u>\tau_i. Therefore,2sgˉ<∑significantgu≤∑u=1mk−1gu=(mk−1)gˉ.2s\bar g < \sum_{\text{significant}} g_u \leq \sum_{u=1}^{m_k-1} g_u = (m_k-1)\bar g.Consequently,s<mk−12,s<\frac{m_k-1}{2},and the initial instance induces at mosts+1≤⌊mk2⌋s+1\leq\left\lfloor\frac{m_k}{2}\right\rfloordistinct behavioral tiers. Hence, even if all raw candidate responses are numerically distinct, they cannot produce mkm_k distinct profiles after discretization. This rules out the degenerate saturation caused solely by numerical uniqueness in raw continuous responses. Importantly, legitimate early termination remains possible when the initial representative already captures all distinct behavioral profiles present in its cluster, in which case the stopping criterion is correctly satisfied. Empirically, under our 10-candidate pool configuration, a single instance induces at most 4 behavioral tiers, with an average of 2.3, consistent with the above bound.

(Continued in Part 2/2...)

AuthorsOpenReview ↗

Response to Reviewer HCJD (Part 2/2)

Q2:

1. Are the strategies in Tables 2 and 9 matched in subset size, refresh schedule, and total evaluation cost?

Yes. In both Tables 2 and 9, the subset size of every variant is set to the coreset size produced by No. 4 (B-DICS); all variants use the same recalibration interval (refresh schedule) and the same total LLM-query budget. The comparison therefore isolates the effect of which instances are selected, rather than the effect of a larger evaluation budget or a different refresh schedule. For Table 9, the ground-truth full-set evaluations are shared across all strategies, and the reduced subsets have the same size, so the ranking-fidelity comparison is matched as well.

2. Methodological distinction from informed down-sampled lexicase selection [1].

We thank the reviewer for pointing us to this relevant work. We have added [1] to the related-work discussion and clarified its relationship to B-DICS.

Informed Down-Sampled Lexicase Selection (IDLS) is an online down-sampling approach designed for lexicase-based parent selection. It leverages population-level behavioral information to identify informative training cases and construct down-sampled case sets for the selection operator.

B-DICS addresses a different stage and objective in evolutionary search. Specifically, it is a periodic, behavior-driven instance-reduction module for candidate-algorithm evaluation. It:

(i) constructs a compact anchor set to preserve the discriminative power of the behavioral representation;

(ii) clusters instances in the anchor-induced behavioral space to uncover latent instance structures; and

(iii) selects representative core instances by maximizing the discriminative power of their discretized performance profiles.

The resulting core set serves as the evaluation set for candidate algorithms throughout a recalibration interval, rather than being sampled within the parent-selection procedure. Moreover, the discovered clusters provide structural information for guiding specialist evolution.

Therefore, the two approaches differ in their optimization targets, operating granularity, and roles in evolutionary search. They are potentially complementary rather than direct substitutes. A direct application of IDLS as a baseline would require adapting it from lexicase-based parent selection to candidate-level fitness evaluation in LES. We have clarified these distinctions and cited [1] accordingly.

Q3:

Were the algorithms in Table 9 excluded from constructing the anchors and core subsets?

Yes. We clarify that the 567 reference algorithms in Table 9 were collected from a separate and independent B-DICS-LES run. They are completely disjoint from the algorithm pools used to construct the anchors and core instances for all compared strategies, including the B-DICS-LES variant evaluated in Table 9.

Neither their algorithm identities nor their instance-wise evaluation responses were used during anchor selection, instance clustering, or core-instance selection. They were exclusively used for the subsequent ranking-fidelity evaluation, where their rankings on the full 240-instance set serve as ground truth and their rankings on the selected subsets serve as proxies.

Therefore, Table 9 already provides an independent evaluation of ranking preservation on previously unseen candidate algorithms. We have clarified this experimental protocol in the revised manuscript.


We sincerely thank the reviewer again for the insightful comments. These suggestions have helped us improve the precision of the methodological description and strengthen the experimental validation. We have updated the manuscript accordingly, with all revisions highlighted in blue.

We hope that these clarifications and additional results adequately address your concerns. Please let us know if you have any remaining questions or if further discussion would be helpful—we are more than happy to engage further.

Thank you for explaining how discretization prevents small numerical differences from causing early saturation in Eq. (9), and for confirming that the 567 algorithms in Table 9 were held out during core-set construction. These clarifications address my concerns in Q1 and Q3.

For Table 2, I understand that all variants used the same LLM-query budget. Did they also perform the same total number of instance evaluations, including full-set and supplementary evaluations? If the totals differ, please report the count for each variant.

Overall, the response addresses my main concerns, and I maintain my recommendation of weak acceptance.

Dear Reviewer HCJD,

Thank you very much for your thoughtful and constructive feedback, and for taking the time to review our rebuttal in detail. We appreciate your continued engagement and are glad that our responses have addressed your main concerns.


Below, we report the total number of instance evaluations and their breakdown into full-set evaluations, accelerated (coreset-based) evaluations, and supplementary evaluations for the four variants in Table 2. The counts are averaged over five independent runs.

VariantPerformance ↓Total evaluationsFull-setAcceleratedSupplementary
Global0.1632282,324149,712108,10924,503
Random0.1644216,66454,240129,78032,645
Oracle0.1447267,47954,560158,71154,208
B-DICS (Ours)0.1420270,651130,704107,98631,961

The total evaluation counts differ across the four variants because the point at which each variant enters the accelerated evaluation phase depends on its evolving algorithm-design process.

Importantly, the performance advantage of B-DICS is not simply a result of conducting more instance evaluations. Global Selection incurs the highest evaluation cost but still achieves substantially worse performance than Oracle and B-DICS. More importantly, B-DICS and Oracle have comparable evaluation costs, yet B-DICS achieves better performance. These results suggest that the improvement comes from the quality of the selected instances and the resulting search guidance, rather than simply from a larger evaluation budget.


We hope this additional information clarifies the evaluation cost-performance comparison in Table 2.

Thank you again for your time and valuable contribution to the review process. We wish you a pleasant day!

Reviewer_BhyaOpenReview ↗
Rating
3
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper addresses the evaluation bottleneck in LLM-assisted Evolutionary Search (LES) for automated algorithm design. It proposes Behavior-based Dynamic Instance Clustering and Selection (B-DICS), a feature-free method that represents training instances via their behavioral responses to generated algorithms, clusters them in this space, and selects representative core instances. B-DICS is integrated into a co-evolving framework (B-DICS-LES) that also uses the discovered structure for specialized algorithm design. Experiments on three tasks (CVRP, Online Bin Packing, and Lunar Lander Control) show state-of-the-art portfolio performance with an average 29.8% reduction in instance evaluations.

Critical strengths

The problem is well-motivated. Candidate evaluation dominates cost in LES (O(X⋅M)O(X \cdot M)), and the observation that many instances induce redundant algorithmic response patterns is practically relevant, especially for novel or black-box domains where handcrafted features are unavailable. B-DICS is conceptually clean: it builds an online behavior matrix from evaluations that LES already performs, reduces dimensionality via a discriminative anchor set (greedy selection + pruning), clusters with k-means (elbow method), and performs cluster-aware core-instance selection. The continuous recalibration as new algorithms appear is a natural fit for the evolutionary process. The co-evolving loop and structure-aware specialization are interesting. The OBP heatmap (Figure 2) provides clear qualitative evidence that specialist pools spontaneously align with latent instance groups without access to ground-truth distribution labels. Empirical support is reasonably strong. Table 1 shows competitive or better performance than EoH, ReEvo, PartEvo, InstSpecHH, and EoH-S, while cutting evaluations by 43.5% (CVRP), 33.1% (OBP), and 12.9% (LLC). Ablations (Table 3) isolate the contributions of instance selection, anchor selection, dynamic recalibration, and the complementary pool; the large drops from removing anchors or the complementary pool are informative. Overhead is claimed to be negligible (<0.01%).

Critical weaknesses

Differentiation from concurrent work needs tightening. The paper notes DvCA (Hu et al., 2026), which also uses behavior-based dynamic clustering for specialized algorithm design and tail robustness. B-DICS’s distinctive contribution is the use of the same structure for representative instance selection to reduce evaluation cost. This distinction should be made more explicit in the related-work section and experimentally (e.g., a direct comparison or an ablation that isolates the selection benefit beyond specialization). Evaluation protocol and statistical robustness could be stronger. Performance is reported via the best algorithm in a complementary pool (or union of specialists), following EoH-S. While the paper attempts to equalize this across methods, portfolio-style reporting can favor methods that maintain diversity. With only five independent runs and high stochasticity from LLM sampling (GPT-4o-mini), confidence intervals or more runs would help. The heterogeneous instance sets are carefully constructed; it remains unclear how much the observed redundancy and savings generalize to other, less structured training distributions. Several design choices are under-analyzed in the main text. The discretization of continuous performance into behavioral tiers, the precise definition of discriminative power Φ(S)\Phi(S), the elbow-method reliability for determining cluster count, and the stability criterion for freezing core instances are deferred to the appendix. Sensitivity to these choices (especially discretization granularity and the number of anchors) is not discussed. The claim that core instances preserve search-signal fidelity is supported by one ablation (0.56% degradation), but more quantitative measures of ranking correlation or fitness approximation error would strengthen it. The relative importance of efficiency versus specialization is not fully disentangled. The strongest results combine both. It would be useful to see a pure efficiency variant (B-DICS selection without specialist pools) versus a pure specialization variant (structure-aware search on the full instance set) to quantify each benefit separately under identical budgets.

Questions for authors

How does B-DICS-LES compare head-to-head with DvCA on the same tasks when both are allowed to use specialization? What is the incremental gain specifically attributable to core-instance selection? Can you report the distribution (or variance) of evaluation reductions across the five runs, and the correlation between performance rankings on the core set versus the full training set during search? How sensitive are the results to the discretization scheme and the target number of clusters? Does the elbow method ever produce unstable or degenerate clusterings on these tasks? In the LLC task the reduction is only 12.9%. Is this because the 35 training instances already have low redundancy, or does the method struggle when the behavior matrix is small?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Bhya (Part 1/3)

Dear Reviewer Bhya and AC,

We thank the Reviewer for carefully reading our submission and for the constructive comments. We appreciate the Reviewer’s recognition of the motivation and potential of behavior-based instance characterization. Below, we first answer the questions point by point, followed by clarifications and additional evidence regarding the broader concerns.


Part I. Response to the Questions

Q1: Head-to-head comparison with DyCA and gain of core-instance selection

We have added a direct head-to-head comparison between DyCA and B-DICS-LES on CVRP, OBP, and LLC. The detailed results are reported in Table 1 and Appendix C.2.

The direct comparison reveals a favorable performance-efficiency trade-off for B-DICS-LES. Among the three tasks, B-DICS-LES achieves the best performance on CVRP (0.1420 vs. 0.1461 for DyCA), while remaining highly competitive on OBP (0.0229 vs. 0.0227) and LLC (279.9 vs. 281.1), where DyCA has only marginal numerical advantages. Instance-level paired Wilcoxon tests further show no statistically significant difference between the two methods on CVRP (p=0.822p=0.822) and LLC (p=0.752p=0.752), while identifying a marginal advantage for DyCA on OBP (p=0.040p=0.040). Importantly, B-DICS-LES achieves this competitive performance with substantially fewer instance evaluations: 271k vs. 480k on CVRP (43.5% reduction), 321k vs. 480k on OBP (33.1% reduction), and 61k vs. 70k on LLC (12.9% reduction). These results demonstrate that B-DICS-LES preserves performance close to the state of the art established by DyCA, while substantially reducing the evaluation cost, particularly on CVRP and OBP.

To isolate the gain of core-instance selection, we compare B-DICS-LES with its variant without instance selection, which retains the specialist populations but evaluates candidates on the full training set. On CVRP, the two variants achieve comparable performance (0.1420 vs. 0.1428, a difference of approximately 0.56%), while B-DICS-LES reduces instance evaluations by approximately 43.7%. This comparison isolates the marginal benefit of core-instance selection under the same specialization-based search framework: it substantially reduces evaluation cost while largely preserving search performance.

These results clarify the complementary roles of the two approaches. DyCA primarily advances behavior-based specialization and resource allocation, whereas B-DICS-LES additionally exploits the discovered behavior structure to reduce the instance-evaluation cost.

Q2 (Part 1): Distribution of evaluation reductions across five runs

Below are the run-wise evaluation reductions and final test performances across the five independent runs:

TaskEvaluation reduction across five runs (%)Mean ± sample SDFinal performance across five runs
CVRP53.41, 40.63, 48.31, 34.90, 41.3943.73 ± 7.21%0.1479, 0.1401, 0.1365, 0.1373, 0.1479
OBP46.01, 23.41, 17.34, 50.20, 28.3433.06 ± 14.35%0.0234, 0.0227, 0.0226, 0.0227, 0.0233
LLC24.73, 3.94, 26.31, 4.79, 3.2012.59 ± 11.83%285.42, 266.17, 282.96, 277.51, 287.30

The results show that evaluation savings vary across runs, particularly on LLC. As detailed in our response to Q4, this variability is primarily associated with the stability-gated activation and fallback mechanism, rather than unconditional application of core-set evaluation.

Q2 (Part 2): Ranking fidelity between core-set and full-set evaluations during search

We retrieved the coresets logged at every accelerated interval across five CVRP runs, obtaining 19 coresets in total. We evaluated an independent pool of 567 fully evaluated reference algorithms on both each coreset and the complete set of 240 training instances, and measured the Spearman rank correlation between their resulting mean-score rankings.

  • Across all coresets, Spearman's (ρ\rho) averages 0.9873, with the lowest single-coreset correlation reaching 0.9791.
  • Notably, the initial Normal-to-Accelerated transition in each run already achieves a mean Spearman's (ρ\rho) of 0.9881, while subsequent transitions maintain a consistently high average correlation of 0.9870.

These results demonstrate that high ranking fidelity is consistently maintained across the observed evolutionary stages.

(Continued in Part 2/3...)

AuthorsOpenReview ↗

Response to Reviewer Bhya (Part 2/3)

(Continued from Part 1/3)

Q4: Why is the evaluation reduction lower on LLC?

The lower evaluation reduction on LLC should not be interpreted simply as evidence of low instance redundancy or an inability to perform core-instance selection with a small behavior matrix. Our run-wise results and clustering logs indicate that it is primarily associated with the conservative stability-gated acceleration mechanism.

LLC has only 35 training instances and approximately 6–9 anchor algorithms, resulting in a relatively small behavior matrix. Meanwhile, the observed reward values span a wide range (approximately −1600 to 280). As new and behaviorally distinct algorithms emerge during search, their anchor responses can alter the induced instance-space structure, making the clustering results more difficult to stabilize. The relatively small behavior matrix can further increase the sensitivity of the estimated clustering structure to these changes.

Specifically, our logs show that, in low-saving runs, the clustering stability criterion often fails to satisfy the requirement of consecutive ARI values above 0.9. In a representative run, the first five recalibration checkpoints do not meet this requirement. Although a later checkpoint briefly reaches an ARI of 0.90–0.92, the following checkpoint drops to 0.73, triggering the fallback condition (ARI < 0.8). Consequently, acceleration is maintained for only one 200-candidate block in such runs, limiting the total evaluation savings.

Importantly, this fallback is an intentional safeguard rather than a mechanism failure. B-DICS-LES does not pursue evaluation savings unconditionally: it accelerates only when the observed clustering structure is sufficiently stable and returns to full-instance evaluation when that stability is lost. This design prioritizes reliable search feedback over blindly reducing evaluation cost.

More broadly, this conservative stability-gated mechanism makes B-DICS-LES readily applicable to different tasks without requiring users to assess beforehand whether a given instance set is suitable for acceleration or decide when acceleration should be activated. Instead, B-DICS-LES continuously monitors the stability of the emerging behavior structure and autonomously identifies opportunities for acceleration during search. It activates core-set evaluation only when the stability criterion is met and falls back to full-instance evaluation otherwise. This allows the method to adapt to different instance characteristics without prior task-specific assessment, offering a practical balance between evaluation efficiency and reliable search guidance.

Q3 (Part 1) Sensitivity to discretization scheme

We conducted a joint sensitivity analysis over 36 hyperparameter configurations (ηrange∈[0.05,0.40]\eta_{\text{range}} \in [0.05, 0.40], ηgap∈[1.0,4.0]\eta_{\text{gap}} \in [1.0, 4.0]) of the natural-break discretization on historical trajectories from five CVRP runs (Appendix C.5.3, Fig. 5):

  • Output Stability: Although varying these parameters smoothly changes the mean anchor count from 13.6 to 3.8, downstream-critical metrics remain highly stable. The Top-10 ranking overlap between the core set and the full training set stays within 0.86–0.90 across the entire grid (0.90±0.060.90 \pm 0.06 at default).
  • Operating Plateau: A broad, stable operating plateau is observed around our default configuration ((ηrange,ηgap)=(0.15,2.0)(\eta_{\text{range}}, \eta_{\text{gap}}) = (0.15, 2.0)).
  • Cross-Task Robustness: The exact same default configuration was applied across CVRP, OBP, and LLC without any per-task hyperparameter tuning.

(Continued in Part 3/3...)

AuthorsOpenReview ↗

Response to Reviewer Bhya (Part 3/3)

(Continued from Part 2/3)

Q3 (Part 2) Cluster-number selection and clustering stability

B-DICS does not prescribe a fixed target number of clusters. Instead, the number of clusters (K) is automatically determined by the elbow method at each recalibration, based on the within-cluster sum of squares. Therefore, the relevant concern is whether the resulting clustering structure remains sufficiently stable as the observed algorithm behaviors evolve, rather than sensitivity to a manually specified K.

Our clustering-stability analysis shows that the structures gradually stabilize on CVRP and OBP, reaching ARI values above 0.9 after approximately six and five recalibration steps, respectively. LLC exhibits more noticeable temporal fluctuations, consistent with the analysis in our response to Q4. As new and behaviorally distinct algorithms emerge, their anchor responses can alter the behavior-space structure, leading to changes in the elbow-selected clustering solution across recalibration steps.

Regarding clustering degeneracy: Across all benchmark runs, the elbow-selected KK dynamically ranges between 2–4 for CVRP and OBP, and 3–6 for LLC. Minimum cluster sizes remain well above singletons (>5>5 instances per cluster), and no empty or singleton clusters were ever produced.

Importantly, B-DICS explicitly accounts for temporal instability through its stability-gated acceleration mechanism. It requires consecutive ARI values above 0.9 before activating core-set evaluation and reverts to full-instance evaluation if the ARI subsequently drops below 0.8. Thus, clustering fluctuations may limit evaluation savings, particularly on LLC, but do not lead the method to blindly continue using an unstable core set.

We also clarify that the number of anchors is not a manually specified hyperparameter. It is determined adaptively by the greedy selection and pruning procedure according to the marginal discriminative gain.


Part II. Clarifications on the Broader Concerns

Separate contributions of selection versus specialization

  • Conceptual Separation: Instance selection reduces candidate evaluation cost, whereas specialization improves algorithm design quality.
  • Empirical Proof: Ablation No. 2 (w/o Instance Selection) isolates selection under the same specialized search framework: removing instance selection changes performance by only 0.56% (0.1420 vs. 0.1428 on CVRP), while core-instance selection delivers a 43.7% reduction in instance evaluations. Specialization benefits have been independently established by InstSpecHH, EoH-S, and DyCA.

Evaluation protocol and statistical robustness

  • Set-Based Evaluation Protocol: Reporting portfolio-level performance (best algorithm in the output set) follows standard protocols from EoH-S, InstSpecHH, and DyCA. For fair comparison, we also report pool-level performance (size 10) for standard LES baselines (EoH, ReEvo, PartEvo). Single-algorithm evaluation is ill-suited for heterogeneous instance distributions.
  • Statistical Rigor: Table 6 in Appendix C.2 reports 95% confidence intervals (Mean ± 1.96 × SEM) across five independent runs, characterizing run-to-run variability. Table 7 further reports instance-level paired Wilcoxon tests, comparing per-instance performance averaged across the five runs over 120 test instances. B-DICS-LES achieves the best mean performance on CVRP and shows no significant difference from DyCA on CVRP and LLC (p=0.822p=0.822 and p=0.752p=0.752), although DyCA has a slight advantage on OBP (p=0.040p=0.040). B-DICS-LES also significantly outperforms InstSpecHH on CVRP and LLC, and EoH-S on LLC (p<0.001p<0.001). Together, these results support the run-to-run stability and competitive search quality of B-DICS-LES, alongside its substantial reductions in instance evaluations.

Several design choices are analyzed in the Appendix

Due to main-text page limits, detailed sensitivity analyses for discretization parameters, recalibration interval, and stability threshold θstable\theta_{\text{stable}} are presented in Appendix C.5 with explicit hyperlinks in the main text.

Quantitative measures of ranking correlation

Full quantitative evaluations of search guidance fidelity (Spearman's ρ=0.9879\rho = 0.9879, Top-1 overlap =1.00= 1.00, Top-10 overlap =0.90= 0.90) are detailed in Appendix C.4.4 (Table 13).


We sincerely thank the Reviewer again for the insightful comments and constructive suggestions. All corresponding changes have been incorporated into the revised manuscript and highlighted in blue.

We hope that these clarifications and additional results adequately address your concerns. Please let us know if you have any remaining questions or if further discussion would be helpful—we are more than happy to engage further.

AuthorsOpenReview ↗

Follow-up on Rebuttal

Dear Reviewer Bhya,

We would like to kindly follow up on our rebuttal and the revised manuscript.

As the discussion period is approaching its end, we would greatly appreciate it if you could take another look at our responses and let us know whether they have addressed your concerns. We would be happy to provide any further clarification.

Thank you again for your careful review and constructive suggestions.

Best regards, The Authors of Submission 17245

Comments on the paper

2 comments

Dear Reviewers, the authors have submitted their response. Kindly review it and update your review where appropriate.

AuthorsOpenReview ↗

Final Rebuttal Summary

Dear Area Chair and Reviewers,

We sincerely thank you and all reviewers for the time and effort devoted to evaluating our submission. We would like to provide the following concise summary to assist your final assessment.


During the rebuttal period, we made substantial efforts to address all reviewer comments through detailed explanations and additional experimental evidence. We are confident that no reviewer concern or question has been overlooked. Our main efforts included:

  • Clarifying the methodological distinction between B-DICS-LES and DyCA, with a direct comparison isolating the contribution of core-instance selection to evaluation efficiency and search performance. (Reviewers Bhya, mEmL)
  • Reporting and analyzing ranking fidelity during evolution, with consistently high ranking correlations between core-set and full-set evaluations demonstrating the reliability of coreset-based search guidance. (Reviewers Bhya, mEmL)
  • Reporting run-wise evaluation savings and analyzing the sensitivity of discretization parameters, adaptive anchor selection, cluster-number determination, and clustering stability, including the stability-gated fallback mechanism explaining the lower savings on LLC. (Reviewer Bhya)
  • Extending component ablations to OBP and LLC to validate their effectiveness across tasks. (Reviewer mEmL)
  • Providing wall-clock runtime comparisons against existing LES baselines and extending computational-overhead analyses to all three benchmark tasks, demonstrating that evaluation-count reductions translate into practical time savings. (Reviewer mEmL)
  • Clarifying portfolio deployment and the costs and limitations of instance-level algorithm selection on unseen instances. (Reviewer mEmL)
  • Clarifying the core-instance selection mechanism, including the use of discretized behavioral responses, the equality criterion, stopping conditions, and optional cluster-specific selection budgets, to improve reproducibility. (Reviewer HCJD)
  • Clarifying the fairness of comparisons by matching subset sizes, recalibration schedules, and total LLM-query budgets across instance-selection strategies. (Reviewer HCJD)

Regarding the reviewer discussion:

  • Reviewer HCJD explicitly confirmed that our responses addressed their main concerns and maintained their recommendation of Weak Accept.
  • Reviewer Bhya did not provide further feedback before the deadline. Nevertheless, we provided comprehensive point-by-point responses, including a direct comparison with DyCA, additional ranking-fidelity analyses, extended ablations, and detailed sensitivity and stability analyses. We are confident that these additional explanations and experimental evidence adequately address the concerns raised in the review.
  • Reviewer mEmL did not provide further feedback before the deadline. We substantially expanded the empirical validation by adding a direct comparison with DyCA, extending ablations to OBP and LLC, and providing comprehensive runtime and computational-cost analyses. We also clarified the ranking-fidelity mechanism and practical algorithm-selection procedure. We are confident that these responses adequately address the concerns raised in the review.

Importantly, all three reviewers initially assigned our submission a Weak Accept rating and recognized the practical importance of reducing evaluation costs in LES and the potential of behavior-based instance selection. In particular, Reviewer mEmL explicitly acknowledged that the proposed approach offers a promising direction for improving the scalability of LLM-assisted evolutionary search, while Reviewer HCJD recognized the practical significance and empirical effectiveness of B-DICS.


We firmly believe that B-DICS-LES contributes to the automated algorithm design community by addressing a fundamental scalability bottleneck in LLM-assisted evolutionary search: the substantial cost of evaluating every generated candidate algorithm across all training instances. By exploiting behavioral redundancy and dynamically identifying representative core instances based on the behavioral signals of newly emerging algorithms, B-DICS-LES substantially reduces evaluation costs while preserving the fidelity of evolutionary search guidance, without relying on predefined instance features or distributional knowledge. Across three heterogeneous algorithm design tasks, it achieves state-of-the-art performance with an average reduction of 29.8% in instance evaluations.

We believe this work provides a practical, general mechanism to make LES more computationally efficient and scalable, particularly in settings involving costly instance evaluations and black-box problem domains where predefined instance features are unavailable.


We sincerely thank the Area Chair and Reviewers for their dedication. The constructive feedback has helped us strengthen the comprehensiveness of experimental validation and improve the clarity of our submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.