acceptodds
Under review as a conference paper at ICLR 2027

Beyond Average Performance: Dynamic Instance Clustering and Specialized Algorithm Design in LLM-Assisted Evolutionary Search

Abstract

Large Language Model-assisted Evolutionary Search (LES) has emerged as a powerful paradigm for automated algorithm design. However, existing LES methods primarily optimize for average performance, inherently directing search effort toward instances that contribute most to this metric while leaving others poorly served, resulting in weak tail robustness and limited real-world reliability. To address this limitation, we propose Dynamic Instance Clustering and Specialized Algorithm Design (DyCA), an LES framework with a feature-free, structure-aware mechanism for constructing reliable algorithm portfolios under heterogeneous instance distributions. DyCA treats instance clustering as a co-evolving component within the search process, reusing accumulated evaluation data as feature-free signals to progressively partition instances with similar algorithmic response patterns. The uncovered clusters decompose the mixed objective into a set of structure-aware sub-objectives, thereby enabling finer-grained and more adaptive guidance for specialized algorithm design. Experimental results across four algorithm design tasks with heterogeneous instances demonstrate that DyCA outperforms state-of-the-art LES baselines, improving tail robustness by an average of 11.8% and overall performance by 7.1% while maintaining competitive head performance.

Primary area:
optimization
Keywords:
Automated algorithm design

Reviews

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

The paper presents DyCA, a LES method for automated algorithm design. Such methods iteratively refine an algorithm or a small pool of algorithms, and the goal is to optimize the average performance across a set of task instances, parameterized, for example, by some initial conditions. The main problem the paper studies is the heterogeneity of the task-instance distribution. If similar task instances dominate in the training set, the usual average performance optimization may focus on marginal improvements of simple tasks instead of tackling the tail of the distribution, i.e., the hardest samples. The authors propose to cluster the task instances to identify the modes, but instead of using domain-specific per-instance information, like in InstSpecHH, they employ task sensitivity to algorithmic updates. The feature vector per task instance is therefore a vector of per-algorithm performance on this instance. This gives a domain-independent way to compare task instances, and therefore cluster them and balance the distribution and the performance target. The paper compares to several baselines (e.g., InstSpecHH, EoH, FunSearch, ReEvo) and achieves around 7% average gain over the best one.

Critical strengths
  • Simple improvement. The method is quite simple. It removes additional assumptions and components and derives similarity between task instances elegantly through the algorithm's performance. The improvement is clear over the baselines.
  • Breadth of evaluation: The experiments cover three combinatorial optimization tasks and a control task, alongside transfer to established public benchmarks.
Critical weaknesses
  • Important baseline missing: It is unclear whether the gain of DyCA comes from clustering the instances by algorithm performance and rebalancing the target, or can be achieved by simply weighting the instances poorly served by the current portfolio. For example, if we take the worst-performing instances (10%) and upweight them in the Δ\Delta CPI, it may perform similarly.
  • Paper structure and clarity: To an inexperienced reader, it is not clear what the method actually does globally. Does it maintain a pool of algorithms and report the average performance of the pool? How many candidate algorithms are generated, and what goes into the prompt? At the same time, there is a bit of redundancy in the text; for example, 3.2 reiterates the motivation for DyCA, though it could be incorporated into the previous paragraph.
Questions for authors
  1. Comparison with hard-instance reweighting. Could the authors provide an EoH-S baseline that periodically identifies the 10% of training instances with the worst current portfolio performance and upweights their contributions to Δ\Delta CPI? It will establish whether DyCA’s clustering and specialist evolution provide additional benefits beyond directly prioritizing poorly served instances.
  2. Simplifying the instance representation. Could the discretization and greedy anchor-selection procedure be replaced with a standard method for reducing redundancy in the algorithm–instance performance matrix? For example, PCA/SVD could produce a compact instance representation, while column-pivoted QR could select representative algorithm columns. This could eliminate several additional hyperparameters (e.g., η\eta). Please report downstream mean and tail performance.
5 comments
AuthorsOpenReview ↗

Response to Reviewer VPFv (Part 1/3)

Dear Reviewer VPFv and AC,

Thank you for your dedication in reviewing our submission and for recognizing the merits of our work. In response to your comments, we have added the suggested hard-instance-reweighting EoH-S baseline, implemented and analyzed the proposed SVD/CPQR alternatives to our discretization and greedy anchor-selection procedure, and added an overall pseudocode to improve the clarity of the proposed framework. Our detailed responses are provided below.


Response to Weakness 1 and Question 1:

Short answer. Simply prioritizing the worst-performing 10% of instances on EoH-S does not reproduce DyCA's gains. On the three CO tasks, EoH-S-Hard10 is worse than standard EoH-S on both mean and tail. DyCA outperforms EoH-S-Hard10 on all eight metrics. This demonstrates that identifying difficult instances alone is insufficient; behavior-based clustering and specialist evolution provide additional benefits beyond directly prioritizing poorly served instances.

We implemented and ran exactly the suggested baseline, EoH-S-Hard10. At every population refresh, EoH-S re-identifies the ceil(0.1*N) training instances on which the current complementary pool performs worst (ranked by max over the pool of its score on instance m, i.e. the pool's coverage of that instance). We then assign these hard instances a weight of 10 and all remaining instances a weight of 1 when computing the CPI gain of each candidate. Nothing else changes: same prompt, operators, LLM, 2000-sample budget, training/test sets and seed pool. We evaluate the whole final complementary pool on the full test sets; values are mean / tail mean.

Task (metric)EoH-SEoH-S-Hard10DyCA
TSP (↓)0.0815 / 0.12710.0867 / 0.13600.0738 / 0.1112
CVRP (↓)0.1489 / 0.29070.1869 / 0.31870.1361 / 0.2491
OBP (↓)0.0233 / 0.04070.0253 / 0.04190.0227 / 0.0397
LLC (↑)270.55 / 254.80274.64 / 266.29285.02 / 281.82

Key findings:

  • Directly prioritizing the hardest instances is insufficient. Compared with standard EoH-S, EoH-S-Hard10 degrades both mean and tail on TSP, CVRP and OBP (CVRP: 0.1489 → 0.1869 mean, 0.2907 → 0.3187 tail).

  • DyCA consistently outperforms hard-instance reweighting. DyCA achieves better mean and common-tail performance on all four tasks. Compared with EoH-S-Hard10, DyCA improves the tail by 18.2%, 21.8% and 5.1% on TSP, CVRP and OBP, and the tail reward by 5.8% on LLC, while also achieving the best mean on every task.

These results demonstrate that simply identifying and prioritizing currently poorly served instances does not adequately address instance heterogeneity. Difficulty alone does not reveal whether different instances can benefit from similar algorithmic strategies. By contrast, B-DISA identifies behaviorally compatible instance groups based on their responses to diverse algorithms, enabling DyCA to construct coherent cluster-specific objectives and evolve dedicated specialists. The resulting gains therefore go beyond merely assigning higher selection weights to hard instances, highlighting the complementary benefits of behavior-grounded instance discovery and specialized algorithm evolution.

We sincerely thank the reviewer for this valuable suggestion. This additional baseline strengthens our empirical evidence and reinforces our confidence that specialist evolution provides additional benefits beyond directly prioritizing poorly served instances.

AuthorsOpenReview ↗

Response to Reviewer VPFv (Part 2/3)

Response to Question 2: Replacing anchor selection strategy with SVD/PCA or QR

Short answer. The suggested simplifications are indeed viable and preserve DyCA's improvements over EoH-S. However, our original B-DISA design achieves the strongest overall performance, particularly in terms of Tail robustness, outperforming both alternatives on all four tasks. Notably, CPQR is a promising alternative, achieving even better mean performance on TSP.

We implemented two alternative representation strategies within the DyCA framework:

  1. SVD-based representation: Directly applies SVD to the algorithm-instance performance matrix to obtain compact, low-dimensional instance representations.
  2. CPQR-based anchor selection: Uses column-pivoted QR to select representative algorithm columns as anchors, which are then used in the original anchor-induced representation and clustering pipeline.

We replace only the representation/anchor-selection component while keeping the downstream clustering and DyCA evolutionary mechanisms unchanged. The results are summarized below.

Task (metric)EoH-S meanDyCA meanSVD meanCPQR meanEoH-S tailDyCA tailSVD tailCPQR tail
CVRP (↓)0.14890.13610.14550.13710.29070.24910.28180.2584
TSP (↓)0.08150.07380.07580.07250.12710.11120.11320.1140
OBP (↓)0.02330.02270.02280.02280.04070.03970.04030.0401
LLC ( ↑)270.55285.02282.02283.06254.80281.82275.32281.52

Key findings:

  • Both alternatives preserve DyCA's improvements over EoH-S.
  • The original B-DISA design achieves the strongest Tail robustness.
  • SVD and CPQR offer different advantages. SVD provides a compact latent representation of instances, but its components are linear combinations of algorithm-response dimensions rather than actual algorithms. Consequently, obtaining the same representation for a new instance requires its responses over the algorithm basis used in the decomposition, rather than evaluations on a small set of directly identifiable anchor algorithms. In contrast, CPQR selects actual algorithms as anchors, making it a particularly promising and interpretable alternative for constructing behavioral representations.

These results highlight the flexibility and modularity of DyCA. The effectiveness of the framework does not hinge on a particular representation or dimensionality-reduction technique. Rather, its central idea is to exploit routinely accumulated algorithm-instance evaluation data to uncover latent instance structures and feed the resulting structural knowledge back into algorithm design. Different representation and anchor-selection strategies can be seamlessly incorporated into this process, offering practical trade-offs between simplicity, computational efficiency, and performance.

We believe this flexibility makes DyCA a promising and extensible paradigm for automated algorithm design and black-box instance-space understanding.

AuthorsOpenReview ↗

Response to Reviewer VPFv (Part 3/3)

Response to Weakness 2: Improving Paper Clarity

We thank the reviewer for pointing out these presentation issues. We have revised the manuscript to provide a clearer overview of DyCA and its implementation.

  • Overall pseudocode and pool organization. We have added an overall pseudocode of DyCA at the beginning of Section 3 (around Line 216). Algorithm 1 summarizes the complete workflow, including initialization, B-DISA-based instance structure learning, and structure-aware co-evolution. In particular, it explicitly shows that DyCA maintains one complementary algorithm pool and multiple specialist pools, each associated with an instance cluster identified by B-DISA. The number of specialist pools is determined by the resulting instance partition.

  • Search budget and algorithm generation. We have clarified that the total budget is 2,000 LLM samples per task, with each sample corresponding to the generation of one candidate algorithm, which is subsequently evaluated on the training instances. Thus, the sample budget directly specifies the number of candidate algorithms generated during evolution.

  • LLM prompt construction. We have made the prompt construction process explicit in Appendix I, providing the complete task-specific prompts and operator-specific templates used for algorithm generation. These prompts specify the task description, code template, parent algorithm information, and operator-specific instructions, clarifying what information is provided to the LLM during evolution.


We sincerely appreciate the time and effort you have devoted to reviewing our work, as well as your constructive suggestions.

We hope that these clarifications and additional experimental results adequately address your concerns and further support your positive assessment of our submission.

We would be happy to continue the discussion should you have any further questions.

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

This paper targets the tail robustness issue of existing Large Language Model-assisted Evolutionary Search (LES), which optimizes only average performance and neglects hard problem instances under heterogeneous distributions. This paper presents DyCA, a novel LES framework using a feature-free instance clustering module named B-DISA to partition instances by their algorithmic behavioral patterns and generate tailored sub-objectives for specialized algorithm evolution. This paper validates DyCA on four algorithm design tasks, showing the efficacy of B-DISA and the specialized design mechanism.

Critical strengths
  • The method proposed by the authors does not rely on any predefined instance features. It directly uses algorithm-instance evaluation results as signals and dynamically mines the latent structure of instances through the performance response patterns of instances to different algorithms. With the accompanying weighted complementary population management W-CPM and bias-aware resource allocation, search computing power is tilted toward a small number of difficult instance clusters.
  • The methodology paper is easy to read and understand, and the method is described in great detail.
  • The paper conducts an ablation study to analyze the effectiveness of each module.
Critical weaknesses
  • The novelty is somewhat insufficient. The method proposed in the paper uses a clustering algorithm to identify instance clusters and a weighting approach to address the majority-dominance bias problem.
  • The clustering input feature is the anchor-induced response vector. Would this make the algorithm complexity relatively high, since performance needs to be validated?
  • How should "online" in the algorithm be understood?
  • More comparison algorithms need to be added, for example, RefineEvo: Planning-Guided Heuristic Evolution with Bidirectional Experience, ICML 2026.
  • More LLMs should be used to test the generalizability of the method.
  • Experiments analyzing the time complexity compared with other comparison algorithms should be added.
  • The performance changes under different LLM call budgets need to be analyzed.
Questions for authors

See Weaknesses.

9 comments
AuthorsOpenReview ↗

Response to Reviewer Reviewer Ath4 (Part 1/4)

Dear Reviewer Ath4 and AC,

Thank you for your time in reviewing our submission and for your constructive comments. We have carefully addressed each of your concerns point-by-point through detailed clarifications and additional experimental evidence. We hope these responses adequately resolve your concerns and warrant a more favorable evaluation of our submission.


Response to Weakness 1: Methodological Novelty

We respectfully disagree that DyCA can be characterized simply as combining clustering with a weighting strategy, as it underestimates the contribution of DyCA.

The novelty of DyCA lies in how instance structures are discovered throughout the algorithm design process and how the discovered structures, in turn, reshape the entire evolutionary search process. In other words, algorithm discovery and instance-structure discovery mutually reinforce each other: evolving algorithms reveal the behavioral differences among instances, while the discovered instance structures guide the subsequent evolution of better algorithms. We clarify three key aspects:

  • Behavior-grounded instance discovery rather than conventional feature-based clustering. Unlike conventional clustering approaches that rely on predefined instance features or domain-specific representations, B-DISA constructs instance representations directly from their performance response patterns to selected anchor algorithms. These representations are derived from the accumulated algorithm-instance evaluation data routinely generated as part of the evolutionary process. Consequently, the instance characteristics relevant to algorithm design are discovered from algorithmic behaviors themselves, without requiring any prior instance features, distribution labels, or ground-truth partitions. The key innovation is not applying a clustering algorithm to instance data, but enabling the evolutionary process to autonomously construct its own instance-space representations from the behaviors of evolving algorithms.

  • Online structural discovery rather than static instance partitioning. B-DISA does not perform a one-time clustering before evolution, as in approaches such as InstSpecHH that rely on predefined instance partitions. Instead, it progressively accumulates behavioral evaluation data and updates instance characterization as the evolutionary process proceeds. Thus, the discovered instance structures are neither predefined nor fixed; they emerge and evolve alongside the algorithm population and its accumulated behavioral knowledge. In DyCA, algorithm discovery and instance-structure discovery are not two separate sequential stages, but two mutually reinforcing processes that co-evolve within the same evolutionary framework.

  • Structure-aware evolutionary adaptation rather than simple weighted selection. More importantly, the discovered structures directly influence subsequent search through W-CPM, specialized algorithm evolution, and bias-aware resource allocation. In particular, W-CPM incorporates the discovered instance clusters into complementary population management, balancing their contributions to selection pressure and mitigating the majority-dominance bias that can cause evolutionary search to overlook underrepresented instance groups. The resulting specialized algorithms generate new algorithm-instance performance observations, which in turn provide feedback for subsequent instance discovery. This establishes a closed-loop mechanism connecting behavioral instance discovery and adaptive algorithm evolution.

Therefore, DyCA does not simply add a clustering module and a weighting strategy to an existing LES framework. It fundamentally changes how an LES method acquires instance-space knowledge and exploits that knowledge throughout evolution. Its central contribution is to make instance-space structures autonomously discoverable and continuously actionable within evolutionary search, without relying on predefined instance information.

AuthorsOpenReview ↗

Response to Reviewer Reviewer Ath4 (Part 2/4)

Response to W2:

The clustering input feature is the anchor-induced response vector. Would this make the algorithm complexity relatively high, since performance needs to be validated?

No. B-DISA introduces negligible computational overhead and requires no additional algorithm evaluations.

First, constructing anchor-induced response vectors requires no additional performance evaluations or performance validation. During evolutionary search, each generated algorithm is already evaluated on the training instances, with its instance-wise performance recorded in the algorithm-instance performance matrix. B-DISA selects informative anchor algorithms from these records and constructs response vectors by retrieving their existing performance values. Thus, no additional LLM calls or objective evaluations are introduced.

Second, B-DISA's computational overhead mainly comes from lightweight matrix computations and array operations on the existing performance records. We profiled the wall-clock time of each DyCA component across four benchmark tasks. As shown in Table 1, B-DISA accounts for only 0.020%–0.027% of the total wall-clock time. Table 2 further breaks down its internal operations, confirming the negligible cost of anchor selection, instance re-clustering, and other processing steps.

Table 1: Wall-clock cost of a full DyCA design run on four tasks. Sampling/evaluation columns are summed over the parallel worker threads, so they exceed the wall-clock total.

TaskTraining instancesSamplesB-DISA roundsTotal wall-clock (s)LLM sampling, summed (s)Evaluation, summed (s)B-DISA total (s)B-DISA share
CVRP2402007208990.0 (2.50 h)18888.944544.41.760.020%
TSP2402007206477.7 (1.80 h)14995.328721.01.460.023%
OBP24020042011930.0 (3.31 h)13917.641017.13.180.027%
MoonLander352007204793.2 (1.33 h)20112.315522.91.050.022%

Table 2: Internal breakdown of B-DISA.

TaskAnchor selectionInstance re-clusteringARI convergence checkPool reorganisationB-DISA total
CVRP0.740.780.020.231.76
TSP0.420.870.020.161.46
OBP0.582.200.020.393.18
MoonLander0.070.820.020.151.05

These profiling results and detailed analysis have been incorporated into the Appendix D.3.

Response to W3: How should "online" in the algorithm be understood?

Here, "online" refers to when instance analysis is performed, rather than a setting where instances arrive sequentially. Specifically, B-DISA is integrated into the LES evolutionary loop. As new algorithms are generated and evaluated on the training instances, B-DISA reuses the accumulated evaluation data to incrementally update the anchor set and periodically recalibrate the instance clusters. The updated clusters then guide subsequent evolutionary processes, including population management and specialized algorithm evolution.

Thus, unlike conventional offline ISA, which fixes the instance partition before search begins, B-DISA progressively discovers and refines instance structures alongside algorithm evolution, enabling the search process to adapt to newly acquired behavioral evidence.

AuthorsOpenReview ↗

Response to Reviewer Reviewer Ath4 (Part 3/4)

Response to W4: Add RefineEvo as an Additional Baseline

We have added RefineEvo as an additional baseline, adapted its official implementation to the four task interfaces, and updated both Table 1 and the stability table (Table 5 of the paper) accordingly; the new row is highlighted in blue in the revised manuscript.

Experimental protocol. To ensure a fair comparison, RefineEvo uses exactly the same training/test sets, the same LLM (GPT-4o-mini, temperature 0.7, timeout 120 s), and the same budget of 2,000 evaluated candidate algorithms as DyCA and the other baselines. We use pop_size = 10 and init_pop_size = 30, and report the mean over three independent runs. Because RefineEvo natively terminates after a fixed number of generations, we imposed the same 2,000-candidate cap used for every other method.

MethodCVRP AvgTSP AvgOBP AvgLLC AvgCVRP TailTSP TailOBP TailLLC Tail
EoH0.21060.13460.0278200.680.38720.19360.0518171.98
FunSearch0.22730.13730.0277216.140.41410.19240.0516193.30
ReEvo0.22410.13310.0281242.090.40270.18970.0519214.02
RefineEvo (new)0.22480.12310.0275213.230.40240.18010.0519182.73
EoH-S0.14890.08150.0233270.550.29070.12710.0407254.80
InstSpecHH0.16170.07780.0236268.220.32170.12260.0439249.46
DyCA0.13610.07380.0227285.020.24910.11120.0397281.82

How does RefineEvo perform? RefineEvo is a strong baseline, and adding it strengthens the comparison:

  • It is the strongest among the standard LES baselines on TSP, reducing the average gap from 0.1331 (ReEvo) to 0.1231 (−7.5%) and the Tail gap from 0.1897 to 0.1801 (−5.1%). It also achieves the best OBP average among these baselines (0.0275).
  • Its advantage, however, is concentrated on average performance and does not carry over to robustness. On CVRP it is slightly worse than EoH on both Avg (0.2248 vs. 0.2106) and Tail (0.4024 vs. 0.3872); on OBP its Tail (0.0519) is comparable to those of the other baselines; and on LLC its average reward (213.23) is accompanied by a much lower Tail reward (182.73) and a success rate of only 53.7%.
  • DyCA still outperforms RefineEvo on all eight metrics. Specifically, DyCA reduces the gap by 39.5%/40.0%/17.5% on CVRP/TSP/OBP average and by 38.1%/38.3%/23.5% on their Tail, while on LLC it achieves 33.7% higher average reward and 54.2% higher Tail reward (285.02/281.82 vs. 213.23/182.73).
  • This conclusion is not an artefact of a single run: RefineEvo's 95% confidence intervals over three runs are narrow (±0.0046, ±0.0084, ±0.0008, and ±3.39 for CVRP/TSP/OBP/LLC, respectively, as reported in Table 5 of the paper).

Why does RefineEvo fall short on heterogeneous instances? RefineEvo's planner and bidirectional experience pool are very effective at improving a single global heuristic, and its gains are consistent with optimizing one aggregate objective over the training set. Under a heterogeneous instance mixture, however, this objective is dominated by the majority/typical instances, so the search improves the mean while spending little effort on the minority of hard subpopulations. In other words, as an average-performance-driven LES method, RefineEvo is also affected by the majority-dominance bias on heterogeneous instances.

A promising complementary direction. These results also suggest a natural way to combine the two frameworks. B-DISA already groups instances with consistent algorithmic responses into clusters and decides how much search budget each cluster receives; within such a cluster, the sub-objective is much more homogeneous, which is precisely the regime in which RefineEvo's planning-guided operator selection and bidirectional experience are most valuable for strong exploitation. We therefore see RefineEvo-style planning as a promising specialist designer inside DyCA's cluster-wise search, rather than as a replacement for bias-aware instance modeling.

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

This paper focuses on LLM assisted evolutionary search for automate heuristic design when instance distribution is heterogeneous and proposes DyCA, which co-evolves a complementary heuristic portfolio and specialist pools. Its core component B-DISA represents each instnace by its performance under anchor algorithms, and the clustered instances are re-clustered dynamically during search. DyCA reports gains over EoH-S and InstSpecHH of 7.1% in average performance and 11.8% in tail performance on multiple COP settings.

Critical strengths
  1. The paper identifies a limitation of prior work and addresses it by constructing instance clusters from the algorithm–instance performance data that the search already produces, and dynamically re-clustering during training.
  2. Fig. 3 show clearly that the discovered clusters on OBP and CVRP largely match the ground-truth generative distributions, which makes the results interpretable.
  3. The designed experiments cover multiple problem settings and public benchmarks and results consistently achieve strong performance.
Critical weaknesses
  1. The contribution of this paper is limited, some of the main components come from prior work: the complementary pool and CPI based selection are taken from EoH-S and the idea of specialist pool and partitioning instances comes from InstSpecHH. The effectiveness of the main new component B-DISA is also questionable (see Q2 for details).
  2. With only three runs each method, some of the results are close and may not be statistically significant. For example, the results of TSP for DyCA and InstSpecHH in Table 1,.
  3. In section 4.1, baselines EoH, ReEvo and FunSearch only use one best heuristic for evaluation, while other methods are evaluated with their full complimentary pool, which seems unfair.
Questions for authors
  1. How is a new heuristic scored across heuristics during searching? Within each cluster, is the score evaluated per-instance, or there is a overall score? How does the metrics in Table 1 and 2 obtained, just a simple average of all tested instances?
  2. In Table 3, the Oracle Feature clustering only 0.35% worse than DyCA. Is this result statistically significant? The import of B-DISA aims at dealing with settings where instance distribution is unknown, but all the training settings in paper are known in advance, so I wonder if the B-DISA component is necessary.
  3. Are the “ground-truth cluster labels” used for InstSpecHH the same as the “distribution labels” used in the Oracle ablation?
  4. Are all evaluation tests performed on the same scale as training? What is the performance when testing on larger instances, for example, TSPlib for sizes between 200 and 1000?
  5. Is there a risk of overfitting?Does the portfolio have a train-test gap even though they are drawn from the same distribution?
9 comments
AuthorsOpenReview ↗

Response to Reviewer 3zXb (Part 1/4)

Dear Reviewer 3zXb and AC,

Thank you for taking the time to review our submission and for providing your comments.

We believe that the current review underestimates the methodological contribution of DyCA by conflating its inherited evolutionary building blocks with its central innovation. We first clarify this distinction, followed by detailed responses to the other concerns and questions.


Response to Weakness 1: Clarification of the methodological contribution

We clarify several important points:

  1. The integration of EoH-S and InstSpecHH is not our claimed contribution. Our contribution is to enable these existing paradigms to operate effectively without predefined instance features or distributional knowledge. DyCA allows the evolutionary process to progressively discover instance structures from algorithmic behaviors and use the discovered structures to adaptively allocate search resources, thereby mitigating the majority-dominance bias arising from heterogeneous instance distributions.

  2. The statement that "all the training settings in the paper are known in advance" is a misunderstanding of the information available to DyCA. Although the instance distributions are specified by us when constructing controlled experimental settings, neither DyCA nor B-DISA is provided with any prior instance features, distribution labels, or ground-truth partitions. The structural information that drives specialized algorithm design and adaptive resource allocation is discovered autonomously from algorithm–instance performance data accumulated during the evolutionary process. Knowing how instances are generated at the experimenter level is fundamentally different from providing such knowledge to the algorithm.

  3. B-DISA removes a fundamental prerequisite of InstSpecHH. Under its original formulation, InstSpecHH relies on predefined instance features to partition instances and establish specialist pools. Without such prior features, it lacks the mechanism to obtain these partitions and consequently cannot initiate feature-based specialization. B-DISA fills precisely this gap by enabling online, behavior-driven instance partitioning without requiring any predefined instance knowledge, thereby extending the applicability of specialist-based algorithm design to feature-scarce or previously unexplored domains.

  4. DyCA also fundamentally adapts the complementary selection mechanism of EoH-S. Rather than directly reusing the original CPI, we introduce Weighted CPM (W-CPM), which incorporates the instance structures discovered by B-DISA into complementary population management. By balancing the contributions of different instance clusters, W-CPM prevents large or high-gradient instance groups from dominating selection pressure, explicitly addressing a key source of majority-dominance bias that the original CPI does not account for.

In essence, DyCA addresses a fundamental research question:

Can the evolutionary process itself discover the latent structure of the instance space, without predefined instance features or distributional knowledge, and continuously exploit this knowledge to reshape subsequent search?

DyCA provides an affirmative answer through a new feedback mechanism connecting behavioral instance discovery, structure-aware complementary selection, and specialized algorithm evolution. Existing methods provide useful evolutionary building blocks, but B-DISA fundamentally changes how instance structures are obtained, when they are discovered, and how they influence the entire evolutionary search trajectory.

Our experimental results further substantiate this contribution. Removing instance clustering leads to a 12.46% performance degradation, while replacing B-DISA with random clustering causes a 9.89% degradation. Meanwhile, B-DISA achieves performance comparable to the oracle feature-based setting without accessing any privileged instance information. These results demonstrate both the effectiveness of behavior-based structural discovery and its critical role in enabling DyCA's bias-aware algorithm design.

AuthorsOpenReview ↗

Response to Reviewer 3zXb (Part 2/4)

Response to Weakness 2: Statistical Reliability and Expanded Independent Runs

Thank you for your comment. We want to clarify the rationale for our initial setup and describe our updated results:

  1. Standard Practice & Computational Overhead: Reporting 3 independent runs is standard practice in recent LES literature (e.g., EoH, ReEvo, EoH-S) due to the substantial computational and API cost.
  2. Cross-Task Consistency: The consistent empirical trends observed across four distinct tasks significantly strengthened our confidence in the original findings. Across the four benchmark tasks, each method was effectively subjected to 4×3=124 \times 3 = 12 independent evaluation runs in total. DyCA's uniform lead across all tasks demonstrates that its performance gains stem from systematic architectural advantages rather than random seed artifacts.

To further address your concern, we have expanded the number of independent runs to 6 for all methods across all four benchmarks (+3 additional independent runs per task/baseline).

Updated Table 1: Comparison of average and tail performance (shared tail set) on testing instances.

MethodAvg CVRP(↓)Avg TSP(↓)Avg OBP(↓)Avg LLC(↑)Tail CVRP(↓)Tail TSP(↓)Tail OBP(↓)Tail LLC(↑)
EoH0.20980.13520.0277201.850.38620.19420.0516172.85
FunSearch0.22650.13680.0277214.300.41320.19180.0515191.60
ReEvo0.22480.13250.0280243.500.40380.18910.0517215.12
EoH-S0.14820.08180.0233270.920.28980.12760.0406255.15
InstSpecHH0.16230.07710.0235269.450.32280.12190.0437250.60
DyCA (Ours)0.13540.07340.0226286.150.24820.11100.0395282.90

As shown in the updated table, DyCA's performance advantages across both average and tail metrics remain consistent across 6 independent runs. These expanded runs further confirm the exceptional stability of DyCA, proving that its superiority is robust and not susceptible to random outlier runs.

Existing statistical evidence.

Beyond the newly added six-run experiments, our original submission already reported two complementary forms of statistical analysis (In Appendix C.2). Table 5 summarizes the performance variability across the three independent runs, providing an initial assessment of run-to-run consistency. In addition, Table 6 reports paired Wilcoxon signed-rank tests over held-out instances, where each instance's performance is averaged across the three runs before statistical testing.

The reported p-values for DyCA against InstSpecHH are:

  • CVRP: (9.6\times10^{-9})
  • TSP: (0.0147)
  • OBP: (0.0001)
  • LLC: (0.0122)

Against EoH-S, all four comparisons are also statistically significant, with p-values ranging from (4.8$\times10^{-6}$) to (0.0006).

In particular, the TSP improvement highlighted by the reviewer is not merely a numerical difference in Table 1; the existing instance-level paired test also supports a statistically significant improvement over InstSpecHH.

Response to Weakness 3: Fairness of the evaluation protocol

We report additional results in which EoH/Funsearch/ReEvo are evaluated with their entire final population, exactly as EoH-S/DyCA's complementary pool is evaluated.

Baselines evaluated with their full final population.

MethodAvg CVRP(↓)Avg TSP(↓)Avg OBP(↓)Avg LLC(↑)Tail CVRP(↓)Tail TSP(↓)Tail OBP(↓)Tail LLC(↑)
EoH (full population)0.18110.09060.0274257.230.34170.13930.0514231.67
FunSearch (full pool)0.19500.10880.0267250.180.36840.16710.0506226.90
ReEvo (full population)0.21220.10320.0276252.620.38970.15550.0512220.20
EoH-S0.14890.08150.0232270.550.29380.13090.0407243.97
InstSpecHH0.16170.07780.0236268.220.32520.12430.0439247.67
DyCA (Ours)0.13610.07380.0227285.020.25040.11260.0397276.50

The results show that:

  1. Pooled evaluation strengthens all three baselines, confirming that the single-algorithm protocol is indeed conservative for them.
  2. DyCA nevertheless remains the best on all eight metrics.
  3. The comparison with EoH-S/InstSpecHH and DyCA is unaffected.

In summary, the reviewer's concern does not change the conclusions: even after equipping the baselines with the full-population evaluation protocol, DyCA maintains a consistent advantage in both average and tail performance. We will report this additional analysis in the appendix of the revised version.

AuthorsOpenReview ↗

Response to Reviewer 3zXb (Part 3/4)

Response to Question 1:

How is a new heuristic scored across heuristics during searching? Within each cluster, is the score evaluated per-instance, or there is a overall score?

Each heuristic records its scores on a per-instance basis, providing flexibility for subsequent operations. Within each cluster, when scores are used for operations such as selection and elimination during specialized evolution, they are aggregated over the relevant instances.

How does the metrics in Table 1 and 2 obtained, just a simple average of all tested instances?

The metrics in Tables 1 and 2 are averages over all tested instances.

Response to Question 2:

The Oracle Feature clustering only 0.35% worse than DyCA. Is this result statistically significant? The import of B-DISA aims at dealing with settings where instance distribution is unknown, but all the training settings in paper are known in advance, so I wonder if the B-DISA component is necessary.

There is a fundamental misunderstanding here. We would like to reiterate that oracle feature clustering is not available to the actual DyCA algorithm. As experimenters, we need a transparent and controlled instance set whose underlying structure is known to us in order to evaluate DyCA and its ability to discover instance structures through B-DISA. The Oracle-DyCA variant is designed to examine whether DyCA's self-discovered structures can achieve algorithm-discovery performance comparable to that obtained when the instance partitions are known in advance. The small 0.35% performance gap suggests that algorithm design guided by DyCA's self-discovered instance structures achieves nearly the same effectiveness as oracle-guided algorithm design within the same framework, thereby directly demonstrating the effectiveness of B-DISA.

Our ablation studies against No Clustering and Random Clustering further demonstrate the necessity of B-DISA when prior instance features are unavailable.

Response to Question 3:

Are the “ground-truth cluster labels” used for InstSpecHH the same as the “distribution labels” used in the Oracle ablation?

Yes. The "ground-truth cluster labels" used for InstSpecHH are exactly the same as the "distribution labels" used in the Oracle ablation.

Response to Question 4:

Are all evaluation tests performed on the same scale as training? What is the performance when testing on larger instances, for example, TSPlib for sizes between 200 and 1000?

The test instances reported in Table 1 are evaluated at the same scale as the training instances.

For TSP, CVRP, and OBP, the training and test instances are independently generated from the same underlying distributions, with disjoint instance sets. The training instances are used for evolutionary search, whereas all reported primary results are obtained on held-out test instances.

Importantly, we also evaluate the learned algorithms on independent public benchmarks, including TSPLib (52–1,000 cities), CVRPLib (A, B, E, F, M, P, and X), and BPPLib (with very long item sequences). These benchmarks are not used during evolutionary search and are evaluated without fine-tuning or adaptation. DyCA consistently achieves the best reported performance across these benchmark collections.

We also clarify the scope of our claim: the primary synthetic test evaluates generalization to unseen instances within the considered heterogeneous distributions, while the public benchmarks provide additional evidence of transfer to independently collected instance families and larger problem scales.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Final Rebuttal Summary

Dear Area Chair and Reviewers,

We sincerely thank you and all reviewers for the time and effort devoted to evaluating and managing 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 DyCA's methodological novelty, the necessity of B-DISA, and its feature-free, online instance discovery mechanism. (Reviewers 3zXb, Ath4)
  • Strengthening statistical reliability and evaluation fairness by expanding from 3 to 6 independent runs and conducting full-population evaluations for EoH, FunSearch, and ReEvo. (Reviewer 3zXb)
  • Reporting train–test comparisons and conducting evaluations on independent public benchmarks, including larger-scale instances, to examine potential overfitting and demonstrate the generalization of DyCA's performance gains. (Reviewer 3zXb)
  • Incorporating RefineEvo as an additional baseline and evaluating DyCA across multiple LLMs to examine its generalizability across different LLM backbones. (Reviewer Ath4)
  • Providing comprehensive computational-cost and search-budget analyses, including detailed B-DISA overhead profiling, end-to-end runtime comparisons, and experiments with different LLM-call budgets, demonstrating DyCA's negligible instance-analysis overhead and improved search efficiency. (Reviewer Ath4)
  • Adding targeted baselines and ablation studies, including hard-instance reweighting (EoH-S-Hard10) and alternative SVD/CPQR-based instance representations and anchor selection, to further validate the benefits and design choices of DyCA. (Reviewer VPFv)
  • Improving manuscript clarity by adding an overall pseudocode and clarifying the algorithm-pool organization. (Reviewer VPFv)
  • Providing further explanations to clarify potential misunderstandings regarding the information available to DyCA, the role of distribution labels and oracle features, per-instance scoring, within-cluster aggregation, and the interpretation of online instance discovery. (Reviewers 3zXb, Ath4)

Regarding the reviewer discussion, Reviewers 3zXb and VPFv explicitly noted that we successfully resolved their concerns.

  • Reviewer VPFv confirmed that the additional baseline, experiments, and implementation details resolved their concerns, and retained their positive rating (3: Weak acceptance).
  • Reviewer 3zXb acknowledged that our additional experiments addressed concerns regarding evaluation fairness, generalization, and overfitting, considered the evaluation fairly comprehensive, and raised their score to 3: Weak acceptance.
  • Reviewer Ath4 did not provide further feedback before the rebuttal deadline. Nevertheless, we provided comprehensive point-by-point responses and additional empirical evidence addressing every concern raised in the review. We are confident that these responses adequately address their concerns as well. (We respectfully hope that the AC could seek the reviewer's further assessment during the AC–reviewer discussion. We also kindly ask the AC to take our detailed responses and additional evidence into account in reaching a fair and informed assessment.)

Importantly, all three reviewers recognized the research value and technical soundness of our work. Following the rebuttal, Reviewers VPFv and 3zXb further acknowledged the comprehensiveness and effectiveness of our experimental validation.


We firmly believe that DyCA contributes to the automated algorithm design community by going beyond aggregate performance optimization toward behavior-grounded instance understanding and specialized algorithm discovery. DyCA provides a general mechanism for jointly uncovering latent instance heterogeneity and developing algorithms tailored to different instance groups. This direction is particularly important for building more reliable automated algorithm design systems in real-world scenarios, where instances/cases are heterogeneous and predefined instance features or distributional knowledge may be 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.