- Rating
- 3
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper introduces RAISE, a framework for improving the robustness of LLM-based automated heuristic design. It combines LLM-driven heuristic evolution with an LLM-free inner search that discovers difficult instances within a constrained neighborhood of fixed nominal encodings. The accumulated instances guide subsequent heuristic selection. Experiments across online and offline optimization tasks show promising performance under the evaluated distribution shifts. Overall, the framework offers a practical contribution supported by broad empirical evaluation, with several evaluation details requiring clarification.
Critical strengths
- Relevant motivation. Overfitting to small, fixed training sets is an important concern in automated heuristic design. The paper directly addresses its implications for deployment under distribution shift.
- Practical framework. The inner search requires only black-box heuristic evaluation and introduces no additional LLM calls, making the approach potentially straightforward to integrate into existing evolutionary pipelines.
- Broad evaluation. Experiments cover four problem families across five task settings. Component ablations, aggregation comparisons, and sensitivity analyses provide useful evidence about the framework’s behavior.
- Clear acknowledgment of limitations. The paper distinguishes its implemented mean-fitness objective from the motivating minimax formulation and explicitly discusses nominal-performance trade-offs and assumptions imposed by the encoding and perturbation family.
Critical weaknesses
- The current ablations do not fully isolate the benefit of adaptive adversarial search from that of expanding the training set. A matched random-augmentation baseline would strengthen the attribution of improvements to the proposed search mechanism.
- Several evaluation and reporting details need clarification: nominal performance is measured on training instances, TSP search and reference costs use different distance conventions, and the reported refresh counts and evaluation-cost estimates appear inconsistent.
Questions for authors
- How does RAISE compare with random augmentation using the same perturbation family, radius, number of added instances, and evaluation budget?
- Could the authors report performance on independent in-distribution test instances and clarify how the primary radius is selected without using OOD test performance?
- How was the evaluated EoH-S member selected? Could the authors provide additional independent search runs or confidence intervals for the principal comparisons?
- Could the authors reconcile the refresh counts and evaluation totals in Tables 7 and 30, and either use a consistent TSP distance convention or revise the interpretation of the reported gap?
4 comments
Response 2/2
Q3b (independent runs and confidence intervals).
Three independent EoH-S runs (rank-1 member of each) vs. three RAISE runs (Appendix F.4):
| OBP shifted waste (%) | Run 1 | Run 2 | Run 3 | Mean ± std |
|---|---|---|---|---|
| EoH-S | 2.127 | 2.047 | 2.039 | 2.071 ± 0.048 |
| RAISE () | 2.105 | 1.993 | 2.046 | 2.048 ± 0.056 |
The 95% CI of the difference over the 60 test sets is [−0.102, +0.054]. It includes 0, so the two methods are not significantly different. RAISE is better on 30 of the 60 sets. All new comparisons in our replies use 3 runs per method and the same type of CI (paired bootstrap over test sets).
We want to highlight that that EoH-S trains on 128 diverse instances that are prepared in advance to cover several distributions, while RAISE starts from 5 nominal instances and generates new instances automatically.
Q4a (Tables 7 vs. 30).
Thank you; Table 30 was wrong. Each run has about 100 generations with a refresh every 5 generations. This gives 20 refreshes and 20 added instances, as in Table 7.
- Each refresh evaluates at most 40 candidates (8 initial + 4 generations × 8). The logs record 630–726 inner evaluations per run.
- Table 30 (Table 39 in the revision) now uses the counts from the logs: about 18.3k–18.6k heuristic evaluations on instances per run.
- We corrected the ratio to EoH-S in Table 31 (Table 40 in the revision).
Q4b (TSP distance convention).
Thank you; we revise how we interpret the gap.
- All methods' tours are measured with the same unrounded Euclidean length. So the comparison between methods uses one convention.
- The reference values are the TSPLIB best-known costs, which use rounded
EUC_2Ddistances. So the reported number is a gap to the TSPLIB best-known cost, not an exact optimality gap. - We rename the metric accordingly and remove the phrase "against the known optimal tours" from Appendix E.3.
Follow-up on Rebuttal
Dear Reviewer hpDq,
We would like to kindly follow up on our rebuttal and the revised manuscript. We have conducted additional experiments and provided clarifications to address your questions regarding random augmentation, independent nominal evaluation, EoH-S comparisons, and evaluation and reporting details, and updated the manuscript accordingly.
As the discussion period nearing its end, we would appreciate knowing whether our responses have addressed your concerns, and would welcome any further feedback you may have. We would be happy to provide additional clarification while there is still time.
Thank you again for your detailed review and constructive suggestions.
Best regards,
The Authors
Thank you for the detailed rebuttal by the author. My concerns have all been addressed. I remain positive about this paper and have decided to maintain my original score.
Response 1/2
Thank you for the detailed review and valuable suggestions. All changes are marked in blue in the revised PDF, and the new experiments are in Appendix F.
We compared RAISE with random augmentation that uses the same code, perturbation functions, radius (ε=0.1), number of added instances (20) and LLM budget. Random best-of-N also matches the evaluation budget. At each refresh, it evaluates as many random candidates as RAISE's inner search (about 31) and keeps the hardest one. (Section 4 and Appendix F.1 of the revision.)
Values are mean ± std over 3 runs. "OBP shifted waste" is the average waste over all 60 shifted test sets (lower is better).
The revision states where the gain comes from.
We generated 60 new held-out Weibull instances with new seeds, on the same size grid as the OOD sets (n∈ {1k, 5k, 10k}, C∈ {100, 200, 300, 400}; 5 instances each). We evaluated every method on them. Table 3 now includes this column. (Full table in Appendix F.3.)
We agree that ε=0.2 was the best value in the OBP sweep, and that the sweep was evaluated on the OOD sets. The main result now uses ε=0.1, the default value that we use unchanged on all other tasks. The full sweep (ε∈ {0.02, 0.05, 0.1, 0.2}) stays in the paper as a sensitivity analysis.
We therefore revise the claim. RAISE is on par with EoH-S, the strongest robustness baseline, while it trains on 5 nominal instances instead of 128 instances from several distributions.
The paper reports the member that ranks 1 by EoH-S's own training score. We now state this and add other choices. (Appendix F.4.)