acceptodds
Under review as a conference paper at ICLR 2027

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search

Abstract

Automated Heuristic Design (AHD) with Large Language Models (LLMs) has shown remarkable progress in discovering high-quality heuristics. However, existing LLM-based AHD methods optimize heuristics on a fixed training instance set and may fail catastrophically when deployed under real-world distributional shifts. We propose Robust Adversary Instance Search (RAISE), a framework that integrates constrained worst-case instance search within a principled neighborhood of the training instance set into the LLM-based evolutionary search loop. RAISE consists of two loops: an LLM-free inner loop repeatedly discovers hard instances inside an -ball around the training instance set using a basis distribution parameterization with boundary projection, and an LLM-driven outer loop evolves heuristics to optimize aggregate performance over the dynamically accumulated hard-instance set. Experiments across four different combinatorial optimization tasks, covering five distribution families, twelve size configurations, and 95 test datasets demonstrate that existing LLM-based AHD methods degrade by up to under distribution shift, while RAISE consistently maintains strong performance across different tested distributions and problem scales.

Primary area:
optimization
Keywords:
Automated Heuristic Design, Large Language Model, Evolutionary Search, Algorithm Design, Optimization

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_hpDqOpenReview ↗
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
  1. How does RAISE compare with random augmentation using the same perturbation family, radius, number of added instances, and evaluation budget?
  2. Could the authors report performance on independent in-distribution test instances and clarify how the primary radius is selected without using OOD test performance?
  3. How was the evaluated EoH-S member selected? Could the authors provide additional independent search runs or confidence intervals for the principal comparisons?
  4. 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
AuthorsOpenReview ↗

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.

Q1 (random augmentation).

We compared RAISE with random augmentation that uses the same code, perturbation functions, radius (ε=0.1\varepsilon=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.)

Variant (3 seeds)OBP shifted waste (%) ↓Offline JSS makespan ratio ↓
No added instances5.563 ± 0.2211.2670 ± 0.0407
Random: 1 random instance2.381 ± 0.4421.2249 ± 0.0000
Random best-of-N (same evaluation budget)2.124 ± 0.0381.2252 ± 0.0004
RAISE2.048 ± 0.0561.2192 ± 0.0161

Values are mean ± std over 3 runs. "OBP shifted waste" is the average waste over all 60 shifted test sets (lower is better).

  • Adding in-ball instances gives most of the gain.
  • On OBP, active search is better than random augmentation with the same budget, by 0.076 points. The 95% confidence interval (CI) of this difference, computed over the 60 test sets, is [−0.120, −0.036]. It does not include 0, so the difference is significant.
  • On offline JSS, the difference is not significant (−0.006, 95% CI [−0.012, +0.000]).

The revision states where the gain comes from.

Q2a (independent in-distribution test).

We generated 60 new held-out Weibull instances with new seeds, on the same size grid as the OOD sets (n∈n \in {1k, 5k, 10k}, C∈C \in {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.)

MethodNominal, train (%)Nominal, held-out (%)Shifted waste (%)
BestFit1.5511.9082.095
EoH / ReEvo / PartEvo / MoH0.199 / 0.139 / 0.199 / 0.2782.078 / 1.384 / 3.223 / 2.3235.452 / 5.075 / 4.045 / 5.772
EoH-S (reported heuristic)1.1331.3552.116
RAISE (ε=0.1\varepsilon=0.1, 3 runs)1.670 ± 0.0602.325 ± 0.1412.048 ± 0.056
  • The nominal-optimized baselines do not overfit the five training instances. On new instances of the training size (n=5000n=5000, C=200C=200), their waste stays at 0.21–0.27%. Their higher held-out waste comes from the other sizes and capacities.
  • RAISE gives up nominal performance for robustness. With a fixed nominal weight β=0.5\beta=0.5 (new; see our reply to QX76), its held-out nominal waste drops to 1.78%, and its shifted waste is 2.13%.

Q2b (choice of the main radius).

We agree that ε=0.2\varepsilon=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\varepsilon=0.1, the default value that we use unchanged on all other tasks. The full sweep (ε∈\varepsilon \in {0.02, 0.05, 0.1, 0.2}) stays in the paper as a sensitivity analysis.

  • At ε=0.1\varepsilon=0.1, RAISE reaches 2.048% shifted waste over the 60 OOD sets. The reported EoH-S heuristic reaches 2.116%, and the rank-1 members of three EoH-S runs reach 2.071 ± 0.048%.
  • In Table 1 (n=5000n=5000, C=200C=200), the values are 1.858% (RAISE) and 1.828% (reported EoH-S heuristic).
  • The difference to EoH-S is not significant (vs. the rank-1 members: 95% CI [−0.10, +0.05], which includes 0).

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.

Q3a (EoH-S member selection).

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.)

EoH-S heuristic (OBP)Nominal, held-out (%)Shifted waste (%)
Reported best heuristic1.3552.116
Rank-1 member of each run (3 runs)1.574 ± 0.3432.071 ± 0.048
Mean over final populations (3 runs × 10)46.778.84
Mean over final populations, without 4 failed members2.756 ± 4.3493.107 ± 1.598
Best single member, chosen on the test sets–1.786
Best member for each test set (oracle)–1.446
  • Choosing the member by training score gives results on par with RAISE.
  • The quality of the final population varies a lot. The last two rows choose members using the test sets, which is not possible at deployment time.
  • EoH-S also trains on 128 instances from several distributions, while RAISE uses 5 nominal instances.
AuthorsOpenReview ↗

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 1Run 2Run 3Mean ± std
EoH-S2.1272.0472.0392.071 ± 0.048
RAISE (ε=0.1\varepsilon=0.1)2.1051.9932.0462.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_2D distances. 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.
AuthorsOpenReview ↗

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.

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

RAISE augments LLM-based automated heuristic design with an alternating search over heuristic programs and challenging instances. An LLM-free inner loop searches for instances on which the current best heuristic performs poorly, using basis-function perturbations and a radius constraint around fixed nominal encodings. The discovered instances expand the evaluation set, and the outer loop evolves and selects programs according to their mean performance on this set. The framework is evaluated on online bin packing, scheduling and vehicle routing, as well as offline scheduling and TSP local-search guidance. The experiments report improved performance under the tested shifts and explicitly examine the trade-off with performance on the nominal training instances.

Critical strengths

S1. Clear Motivation for Improving Generalization in Heuristic Design

The paper addresses a practical concern in LLM-based heuristic design: selecting programs on a small fixed instance set can encourage specialization that does not transfer well to new distributions. Dynamically improving the evaluation instances during search is a useful direction that complements work on program-generation and evolution operators. The motivation is clear, and the reported bin-packing results illustrate why this problem matters.

S2. A Coherent Framework Combining Heuristic Evolution and Instance Search

RAISE combines heuristic evolution with a compact search for challenging instances and uses the resulting instances to update population evaluation and selection. Fixed nominal anchors, a low-dimensional perturbation parameterization and an explicit radius constraint give the inner search a concrete and controllable scope. The inner loop requires no additional LLM calls, which is an attractive practical property. The paper also clearly distinguishes its motivating minimax formulation from the implemented mean-fitness objective and the empirical nature of its robustness results.

S3. Broad Evaluation Across Tasks and Heuristic Roles

The evaluation covers four problem families in five task settings, including online decision rules, offline schedule construction and guidance within a classical local-search solver. The bin-packing experiments provide the strongest evidence of improved performance under distribution shift, while the offline JSS and TSP experiments include useful controls that remove the inner loop from the same synthesis pipeline. The explicit reporting of the nominal-performance trade-off and the provision of synthesized functions with behavioral analyses also help readers interpret the results.

Critical weaknesses

W1. Unclear Added Benefit over Random Instance Augmentation

The existing ablations support the usefulness of the full inner-search module, but removing it also removes the additional instances and the diversity they introduce. The experiments therefore do not fully isolate the benefit of actively targeting the current heuristic's weaknesses from that of broader instance exposure. A random augmentation control using the same encoding, perturbation family, radius and number of added instances, with evaluation cost also controlled, would strengthen the evidence for the central mechanism.

W2. Limited Evidence for Transfer Across AHD Frameworks

The experiments demonstrate useful breadth across tasks and downstream solver interfaces, but the outer program search uses EoH-style evolutionary operators. Comparisons against other AHD methods do not establish whether adding the instance-search module to those methods would also improve them. Its potential as a broadly applicable enhancement is plausible, but direct evidence of transfer to a different outer search framework remains limited. This primarily limits the scope of the generality claim rather than the demonstrated results within the current framework.

Questions for authors

Q1. How Much Does Active Search Add Beyond Random Augmentation?

Do the authors have results or preliminary observations comparing active hard-instance search with random constrained augmentation under the same encoding, perturbation family, radius and number of added instances? A comparison that also controls heuristic-evaluation cost would help clarify how much of the improvement comes specifically from targeting the current heuristic's weaknesses.

3 comments

Thank you for the thoughtful review. All changes are marked in blue in the revised PDF, and the new experiments are in Appendix F. We provide point-to-point responses as follows:

W1/Q1 (active search vs. random augmentation).

We ran the control you suggested on OBP and offline JSS. All variants use the same code, encoding, nine perturbation functions, radius (ε=0.1\varepsilon=0.1), 20 refreshes, 20 added instances and LLM budget. Only the way each new instance is chosen differs. (Section 4 and Appendix F.1 of the revision.)

Variant (3 seeds)OBP shifted waste (%) ↓Offline JSS makespan ratio ↓
No added instances5.563 ± 0.2211.2670 ± 0.0407
Random: 1 random admissible encoding2.381 ± 0.4421.2249 ± 0.0000
Random best-of-N: as many candidates as RAISE evaluates, keep the hardest2.124 ± 0.0381.2252 ± 0.0004
RAISE2.048 ± 0.0561.2192 ± 0.0161

Values are mean ± std over 3 runs. "OBP shifted waste" is the average waste over all 60 shifted test sets (lower is better).

Evaluation cost.

  • All variants make the same LLM calls and the same outer-loop evaluations, because their instance sets have the same size at every refresh.
  • RAISE's only extra cost is the inner search: 630–637 heuristic evaluations per OBP run at ε=0.1\varepsilon=0.1 (from the logs), about 31 per refresh.
  • Random best-of-N spends the same number of evaluations per refresh on random candidates. So it matches RAISE in both added instances and evaluation cost, and the only difference is the inner evolutionary search.

How much active search adds.

  • Most of the gain comes from adding in-ball instances (OBP 5.56 → 2.38; JSS 1.267 → 1.225).
  • On OBP, searching for the current heuristic's weak points gives a further gain over random best-of-N of 0.076 points. The 95% confidence interval (CI) of this difference, computed over the 60 test sets, is [−0.120, −0.036]. It does not include 0, so the gain is significant. It is also much more stable than one random instance (std 0.056 vs. 0.442).
  • On offline JSS, the further gain is not significant (−0.006, 95% CI [−0.012, +0.000] over the 20 test sets). All random runs ended with almost the same dispatching rule.

We revise the paper to state where the gain comes from.

W2 (transfer to another outer framework).

We added the unchanged inner loop to a different framework ReEvo. The only changes are the instance set used to score candidates and a re-scoring step after each refresh. (Appendix F.6.)

OBP, 3 seedsNominal, held-out (%)Shifted waste (%)
ReEvo1.771 ± 0.8565.286 ± 0.512
ReEvo + RAISE inner loop1.649 ± 0.4682.619 ± 1.007
RAISE (EoH-style outer loop)2.325 ± 0.1412.048 ± 0.056
  • The inner loop halves ReEvo's shifted waste (−2.67 points, 95% CI [−3.31, −2.05], better on 50 of 60 sets). Held-out nominal waste does not get worse.
  • It is still worse than RAISE with the EoH-style outer loop and varies more across seeds (3.77 / 1.88 / 2.21). So the outer framework also matters.

The revision states that we have tested the inner loop with these two outer frameworks only.

Thank you for the explanation and additional experiments. I appreciate that the revision explains where active search helps and how far the transfer evidence extends. I’m keeping my original rating of 3.

Thank you for taking the time to read our response and the revised paper. We appreciate your acknowledgment of the additional experiments and clarifications, and are glad that they have addressed the concerns raised in your original review.

Thank you again for your constructive feedback, which has helped us strengthen the paper and better clarify the scope of our contributions.

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

This paper proposes RAISE, a bi-loop framework for LLM-based automated heuristic design. The outer loop evolves heuristics using LLMs, while the inner loop searches for adversarial instances, serving as a form of adaptive data augmentation. Extensive experiments across multiple optimization tasks demonstrate improved OOD robustness and evaluate the effectiveness of key components.

Critical strengths
  1. The paper addresses an important limitation of existing LLM-based AHD methods: their poor robustness under distribution shifts.

  2. RAISE introduces a bi-loop framework that combines LLM-based heuristic evolution with adversarial instance search, without requiring additional LLM calls.

  3. Extensive experiments across online and offline optimization tasks demonstrate improved OOD robustness. Additional analyses investigate nominal–OOD trade-offs, instance weighting strategies, sensitivity to nominal training distributions, and computational costs, providing a comprehensive evaluation of the framework.

Critical weaknesses
  1. Although RAISE improves OOD performance through adversarial instance augmentation, it remains unclear whether the generated heuristics discover generalizable decision rules or simply adapt to an increasingly diverse set of training instances. Appendix B.4 requires the LLM to provide a natural-language description of each heuristic, but such descriptions may not necessarily reflect the actual decision logic implemented in the code.

  2. RAISE achieves strong OOD performance at the cost of degraded nominal performance. Under uniform weighting, the total weight assigned to the original training instances decreases as adversarial instances accumulate, which may contribute to this degradation. Although the authors explore Hedge and Age Decay weighting strategies, they do not explicitly consider the relative importance of nominal and adversarial instances.

  3. The authors have acknowledged the limitation that RAISE relies on task-specific instance encodings and nine manually designed perturbation functions. I consider this design reasonable and acceptable within a clearly defined task scope. The paper also discusses replacing the hand-designed perturbation functions with learnable generative models as a potential direction for future work.

Questions for authors
  1. Please further analyze the consistency between the descriptions and the generated algorithms, and investigate whether the learned decision rules remain generalizable across different distributions.

  2. Could a weighting strategy that assigns greater importance to nominal instances preserve their performance while maintaining better OOD performance than existing baselines? An analysis of different nominal–adversarial weighting ratios would help clarify whether the observed trade-off can be further improved.

  3. Could the authors provide further justification for the selection of the nine hand-designed perturbation functions and conduct individual function ablations to assess whether each function is necessary and how much it contributes to RAISE's OOD performance?

  4. A simple comparison between RAISE and random or other instance augmentation methods would help clarify the necessity and effectiveness of the proposed adversarial search mechanism.

3 comments
AuthorsOpenReview ↗

Response 1/2

Thank you for your valuable review and the concrete suggestions. All changes are marked in blue in the revised PDF, and the new experiments are in Appendix F. We provide point-to-point responses as follows:

W1/Q1 (general rules; descriptions vs. code).

Generalization gap. If RAISE heuristics only fitted their growing training set, they would do much better on their own accumulated instances than on new instances from the same ε\varepsilon-ball. We evaluated the final OBP heuristics (3 runs each) on their training instances, on new in-ball instances, and on the 60 OOD sets. The new in-ball instances are 20 random admissible encodings, plus the hardest instance found by a new inner search (new seed) against the final heuristic. (Appendix F.7.)

Waste (%)Training: nominalTraining: accumulated adversarialNew in-ball: randomNew in-ball: hardestOOD (60 sets)
EoH0.232 ± 0.057–3.808 ± 1.43120.325 ± 3.2294.054 ± 1.478
RAISE1.670 ± 0.0608.462 ± 0.8422.572 ± 0.2125.442 ± 0.6542.048 ± 0.056
  • EoH gets much worse just outside its training instances: from 0.23% to 3.81% on random in-ball instances, and to 20.3% on the hardest one.
  • RAISE gets only mildly worse (1.67% → 2.57% and 5.44%).
  • RAISE does not do better on its own accumulated adversarial instances (8.46%) than on new hard instances it has never seen (5.44%). So we see no sign that it memorizes its training instances.

Descriptions. We agree that the one-sentence descriptions may not match the code. As in EoH, they are only given to the LLM as context for the next step. No selection, evaluation or claim uses them. The analysis in Appendix F.1.2 (G.1.2 in the revision) is based on the code itself, e.g., the feasibility mask, the reciprocal tight-fit term and the multiplicative combination of terms in the OBP heuristic. The revision states this explicitly.

W2/Q2 (nominal vs. adversarial weighting).

We added a two-level weighting. The nominal instances get a fixed total weight β\beta, and the adversarial instances share 1−β1-\beta. Under uniform weighting, the nominal share drops to 5/25 = 0.2 by the end of a run. We measure nominal performance on 60 new held-out Weibull instances. (Appendix F.2.)

OBP, 3 seedsNominal, held-out (%)Shifted waste (%)
uniform (current)2.325 ± 0.1412.048 ± 0.056
β=0.25\beta=0.252.142 ± 0.4212.120 ± 0.052
β=0.5\beta=0.51.781 ± 0.0262.133 ± 0.111
β=0.75\beta=0.751.800 ± 0.1332.525 ± 0.256
EoH-S (rank-1 member, 3 runs)1.574 ± 0.3432.071 ± 0.048
EoH (3 runs)1.811 ± 0.5364.054 ± 1.478

Values are mean ± std over 3 runs. "OBP shifted waste" is the average waste over all 60 shifted test sets (lower is better).

  • β=0.5\beta=0.5 lowers held-out nominal waste from 2.33% to 1.78%, about the same as EoH (1.81%). Shifted waste rises a little (2.133% vs. 2.048%; the 95% confidence interval (CI) of this difference, computed over the 60 test sets, is [+0.03, +0.14]) but stays far below EoH.
  • A larger β\beta does not improve nominal waste further and costs more robustness.
  • Even at β=0.75\beta=0.75, RAISE's waste on the training instances (1.41%) is much higher than EoH's (0.23%). So the lower nominal weight is not the main cause of the nominal gap. The main cause is that RAISE selects heuristics that work on the whole instance set, not only on the nominal instances.

We add β\beta and this sweep to the paper and keep uniform weighting as the default.

AuthorsOpenReview ↗

Response 2/2

W3 (task-specific encodings).

Thank you for finding this design reasonable within a clear task scope. We agree that it is a real limitation and keep it stated in the paper. Replacing the hand-designed perturbation functions with a learned generator, as you mention, is the direction we plan to explore next.

Q3 (the nine perturbation functions).

Why these functions. They cover common shape changes of an encoded profile: shifts in location (Uniform, Small, Large, Center), several modes or local peaks (Bimodal, Gaussian, Peak), and periodic or heavy-tailed patterns (Periodic, Poisson-like). They act on the encoding. The test distributions were chosen independently of them.

Which functions are used. We recovered the exact weights of all 11,200 inner-search candidates in 14 runs. Within each search, we computed the correlation between each signed weight and instance hardness. We then applied a sign test across searches. Significant functions (p<0.05p<0.05):

  • OBP: Small, Large, Bimodal (at every ε\varepsilon), Center and Periodic (at most ε\varepsilon).
  • Offline JSS: Gaussian, Periodic, Poisson-like, Large, Center, Bimodal, Uniform.
  • Online JSP: Large, Center, Periodic, Poisson-like (negative correlation).

Necessity. Each task uses a different subset of functions. Only Large is significant on all three tasks. This is why we use them as a mixture. Every function except Peak is significant on at least one task. Peak has no significant effect on the tested tasks. We state this in the paper and keep Peak for generality.

End-to-end ablation. We ran RAISE on OBP without Gaussian, the function that OBP does not use. Shifted waste is 2.091 ± 0.015% vs. 2.048 ± 0.056% with all nine (95% CI of the difference [+0.002, +0.084]). So removing it gives a small but significant loss. We ran this full ablation only for Gaussian. (Appendix F.5.)

Q4 (random augmentation).

We compared RAISE with random augmentation. All variants use the same code, encoding, nine perturbation functions, radius (ε=0.1\varepsilon=0.1), 20 refreshes, 20 added instances and LLM budget. Only the way each new instance is chosen differs. Random best-of-N evaluates as many random candidates per refresh as RAISE's inner search and keeps the hardest one. (Section 4 and Appendix F.1 of the revision.)

Variant (3 seeds)OBP shifted waste (%) ↓Offline JSS makespan ratio ↓
No added instances5.563 ± 0.2211.2670 ± 0.0407
Random: 1 random instance2.381 ± 0.4421.2249 ± 0.0000
Random best-of-N2.124 ± 0.0381.2252 ± 0.0004
RAISE2.048 ± 0.0561.2192 ± 0.0161
  • Adding instances from the ε\varepsilon-ball gives most of the gain on both tasks.
  • On OBP, active search is better than random best-of-N with the same number of evaluations, by 0.076 points. The 95% confidence interval (CI) of this difference, computed over the 60 test sets, is [−0.120, −0.036]. It does not include 0, so the difference is significant. Active search is also much more stable than one random instance (std 0.056 vs. 0.442).
  • On offline JSS, the extra gain over random augmentation is not significant (−0.006, 95% CI [−0.012, +0.000]).

The revision states that the benefit of active search depends on the task.

AuthorsOpenReview ↗

Follow-up on Rebuttal

Dear Reviewer QX76,

We would like to kindly follow up on our rebuttal and the revised manuscript. We have conducted additional experiments to address your questions regarding nominal–adversarial weighting, perturbation functions, and random augmentation, and updated the manuscript accordingly.

As the discussion period is approaching 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 thoughtful review and constructive suggestions.

Best regards, The Authors

Comments on the paper

1 comment

Dear reviewers,

We have now received the author responses to your raised questions and concerns. Please go through them. Also, have they answered your questions appropriately? Please also look other reviewers' strengths / concerns. Have they changed your perception of the paper? In all cases, please communicate with the authors. It is important that we let them know what relevant issues still exist or have been answered. Please remember we have limited time to get any further responses from them.

Regards,

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.