- 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 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
- 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 CPI? It will establish whether DyCA’s clustering and specialist evolution provide additional benefits beyond directly prioritizing poorly served instances.
- 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., ). Please report downstream mean and tail performance.
5 comments
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:
- SVD-based representation: Directly applies SVD to the algorithm-instance performance matrix to obtain compact, low-dimensional instance representations.
- 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 mean | DyCA mean | SVD mean | CPQR mean | EoH-S tail | DyCA tail | SVD tail | CPQR tail |
|---|---|---|---|---|---|---|---|---|
| CVRP (↓) | 0.1489 | 0.1361 | 0.1455 | 0.1371 | 0.2907 | 0.2491 | 0.2818 | 0.2584 |
| TSP (↓) | 0.0815 | 0.0738 | 0.0758 | 0.0725 | 0.1271 | 0.1112 | 0.1132 | 0.1140 |
| OBP (↓) | 0.0233 | 0.0227 | 0.0228 | 0.0228 | 0.0407 | 0.0397 | 0.0403 | 0.0401 |
| LLC ( ↑) | 270.55 | 285.02 | 282.02 | 283.06 | 254.80 | 281.82 | 275.32 | 281.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.
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.
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.
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.