- 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
- 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.
- 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
- 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.
- 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
- 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?
- 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
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:
| Aspect | DycA | Our B-DICS-LES |
|---|---|---|
| Primary research question | How can LES improve robustness under heterogeneous instance distributions? | How can LES substantially reduce evaluation cost while preserving search fidelity? |
| Targeted LES stage | Evolutionary optimization | Candidate evaluation |
| Primary algorithmic contribution | Bias-aware evolutionary optimization (Weighted CPM, specialist evolution, adaptive resource allocation) | Behavior-based instance reduction (core instance selection and evaluation replacement) |
| Primary optimization objective | Tail robustness and reliability | Computational efficiency |
| Primary evaluation metrics | Average performance, tail performance, robustness | Evaluation cost, search fidelity, efficiency |
| Main scientific conclusion | Structure-aware optimization substantially improves robustness | Structure-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...)
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.
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
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:
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.
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.
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...)