- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
TRACE-EA is an LLM-driven automatic heuristic design framework for multi-objective combinatorial optimization. It queries NSGA-II/SEMO search trajectories through 11 diagnostic tools to guide operator variation; a second loop adjusts the observation window, query rounds, and tool priors. Experiments on bi-/tri-objective TSP, CVRP, and FJSP across scales and evaluation budgets show substantial gains on several TSP/CVRP tasks, with mixed FJSP results.
Critical strengths
-
The paper asks what execution evidence beyond aggregate HV should drive heuristic revision in multi-objective search. Using the additive ε-indicator in both directions to separate coverage gained from coverage lost is a nice touch. The tool interface keeps prompts compact, and the tool-usage analysis in Fig. 3 is informative.
-
The paper has good protocol choices. Comparisons are made within a shared inner solver. HV reference points are fixed and independent of any method’s output, and HV is computed per run. Cross-scale transfer is evaluated.
Critical weaknesses
-
Limited methodological novelty. DASH (Wang et al., 2026) and AutoEP (Xu et al., 2026) already leverage search dynamics for LLM-guided algorithm design/adaptation; MoH (Shi et al., 2026) and MeLA (Qiu et al., 2025) explore feedback-based adaptation of heuristic generation. TRACE-EA mainly exposes established Pareto indicators via 11 tools and adjusts a small observation policy using fixed thresholds and multipliers (Appendix C.3). Its distinct information-selection or policy-learning advance over these precedents is insufficiently established.
-
Experimental evidence does not adequately isolate the proposed mechanisms. The main ablations are confined to Bi-TSP50/NSGA-II (Table 2), without comparison against a tuned fixed-observation strategy or validation on another problem/solver. Moreover, the NSGA-II baselines and TRACE-EA evolve different operator interfaces (mutation operator, operator chain, and batch operator), while TRACE-EA–SEMO uses a 360 s candidate limit versus 120 s for MPaGE/MEoH (Table 7). These design differences complicate attribution of the reported gains specifically to trajectory observation and policy adaptation.
-
The paper argues that aggregate HV masks search dynamics, yet the second feedback loop assigns credit using only a difference in mean HV and citations self-reported by the LLM. As a result, an edit that fixes the diagnosed problem but does not raise HV may be counted as a failure, while an HV gain unrelated to the diagnosis may reward the cited tools. Whether this feedback actually improves observation remains unsupported.
-
The observation process in TRACE-EA is very expensive. The paper reports 78,074 tool calls over 6,813 observed search steps across the 36 TRACE-EA searches.
Questions for authors
-
What new diagnostic or information-selection principle does TRACE-EA offer beyond the dynamics-aware feedback in DASH/AutoEP and querying established Pareto indicators? Can the authors illustrate a distinctive decision?
-
How does the second loop differ methodologically from MoH/MeLA? What motivates its thresholds, 1.2/0.9 tool-prior multipliers, and short accept/revert horizon? Why should cited evidence predict causal utility?
-
Can TRACE-EA and the strongest NSGA-II baseline be compared using the same editable operator interface and candidate-evaluation rules?
-
On Bi-CVRP50/NSGA-II, can the authors compare the adaptive observation policy with a tuned fixed-observation policy under the same observation budget, to establish the added value of online adaptation?
7 comments
Response to Reviewer 2MMa
| Seen Setting (HV at 30 s) | TRACE-EA (SEMO, 120 s) | Previous 360 s | MPaGE (120 s) | MEoH (120 s) |
|---|---|---|---|---|
| Bi-TSP50 | 0.6377 ± 0.0034 | 0.6371 | 0.6059 | 0.6150 |
| Tri-TSP50 | 0.4359 ± 0.0035 | 0.4431 | 0.3658 | 0.3729 |
| Bi-CVRP50 | 0.5400 ± 0.0013 | 0.5413 | 0.5361 | 0.5355 |
| Tri-CVRP50 | 0.5249 ± 0.0005 | 0.5256 | 0.5105 | 0.4996 |
| Bi-FJSP10j5m | 0.3668 ± 0.0077 | 0.3658 | 0.3619 | 0.3725 |
| Tri-FJSP10j5m | 0.1363 ± 0.0006 | 0.1359 | 0.1320 | 0.1323 |
- Additional problem and solver ablations (Q4, Appendix G.2): Across 3 search seeds (100-candidate budget) on unseen medium-scale instances, we added: (i) Bi-CVRP50 with NSGA-II, comparing online policy adaptation against a pre-tuned fixed policy (0.5096 ± 0.0167 vs. 0.4839 ± 0.0043 HV at 30 s; Q4), and (ii) Bi-TSP50 with SEMO (120 s cap), comparing selective tool observation against fixed trajectory summaries (0.6420 ± 0.0045 vs. 0.6374 ± 0.0034 HV at 30 s; 0.6425 ± 0.0049 vs. 0.6376 ± 0.0038 at 60 s).
W3 (Credit assignment in Loop 2: relationship between fixing the diagnosed behavior and HV gain)
Single-step mismatches indeed occur in stochastic heuristic search. Using the same-parent Structural Mutation (M1) protocol (Appendix E.4), we measured this directly on Bi-TSP50 across 14 parents from early, middle, and late search stages (4 independent children per parent, 56 edits total) against each parent's diagnosed runtime metric (stalled-direction R2 progress, occupied front cells, or target-operator late improvement rate):
| Same-parent M1 edits on Bi-TSP50 (56 edits across 14 parents) | Mean HV increased () | Mean HV did not increase () | Conditional HV-gain rate |
|---|---|---|---|
| Targeted runtime metric improved () | 18 (agreement) | 7 (12.5% mismatch) | 72.0% (18/25) |
| Targeted runtime metric did not improve () | 6 (10.7% mismatch) | 25 (agreement) | 19.4% (6/31) |
Repairing the targeted behavior raises HV-gain probability by 3.7× (72.0% vs. 19.4%; 76.8% overall agreement vs. 23.2% step-level mismatches). Averaging action-adjusted residuals over 4 steps with automatic rollback (Q2) smooths out these step-level mismatches, enabling online adaptation to outperform a task-tuned fixed policy on unseen Bi-CVRP50 (Q4; documented in Appendix E.4).
W4 (Tool-querying overhead and future directions)
Note that the 76,763 tool calls across the 36 main searches (~11.3 per observed step; 78,074 in the initial submission before the 120 s SEMO rerun) are local, read-only Python slices over already-recorded trajectory arrays at 0 extra solver evaluations, batched into 2–4 Observer LLM turns per step rather than separate LLM calls per tool. Even so, multi-round LLM querying adds outer-search interaction cost. Once what set-valued trajectory evidence matters is established, a natural next step is distilling recorded TRACE-EA trajectories and diagnoses into a lightweight specialized tool-selection module for MOCOPs to predict informative windows and indicators directly from compact solver states—cutting querying latency and token cost in future work, which we will note in the final version.
Response to Reviewer 2MMa
Q1 (Information-selection principle beyond DASH/AutoEP, and a distinctive decision)
- Principle (3D fault localization across time window × trade-off region × operator): TRACE-EA narrows down where and why front expansion stalls in three steps: (1) cross-run consistency (
scan_findings,compare_repeats) filters single-run noise; (2) window and region slicing (region_progress,front_shape) separates benign trade-off shifts () from stalled directions or coverage loss (); and (3) time-alignedoperator_statscompares sibling operators on the same population to isolate the failing function (Appendix E.2–E.3). - Distinctive decision on Bi-TSP50: On parent
958bf3350013(defining 2-opt, 3-opt, and Or-opt), overall HV rises smoothly to 0.5482 ± 0.0088 with and high diversity (0.96), so scalar curves look healthy. Zooming into generations 20–30 reveals that progress is skewed toward Objective 1 (+0.055 utility at vs. +0.011–0.016 on central/Objective-2 weights across 5 cells) and that 2-opt and 3-opt still gain HV (1.54 and 2.90) whereas Or-opt is nearly dead (2.1% late improvement rate, 0.03 HV gain). Guided by this diagnosis, the LLM leaves 2-opt and 3-opt intact and rewrites only Or-opt from random relocation to weighted high-cost edge relocation biased toward central/Objective-2 trade-offs—lifting Or-opt's late improvement rate up to 19.8% and improving HV in 3/4 children, whereas all 4 no-feedback children mutate the already-strong 3-opt and regress (Appendix E.4).
Q2 (Loop 2 vs. MoH/MeLA, parameter motivation, and why cited evidence is used)
- Difference from MoH / MeLA: MoH and MeLA adapt how heuristics are generated from endpoint black-box scores; Loop 2 leaves the generator untouched and adapts how trajectories are observed () online at zero extra solver runs (W1).
- Parameter motivation: With only ~25–50 steps over 100–200 candidates, rules must be deconfounded, reversible, and bounded: (1) action-adjusted residuals () remove baseline gain differences across variation actions (e.g., E1 vs. M2); (2) the 4-step window spans one 4-action outer generation and hard-reverts any update whose mean residual drops; and (3) 0.5 / 0.9 citation gates (over rounds) and 1.2 / 0.9 prior multipliers (in ) trim unused rounds without disabling () or locking in () any tool.
- Why cited evidence: The code generator never sees the Observer's raw tool transcript—only cited slices enter the variation prompt (Appendix E.1). Uncited exploratory calls (
overview,scan_findings, 37% of calls) orient where to zoom, whereas cited calls (zoom98%,region_progress80%) are the sole trajectory inputs conditioning code edits. A citation rate thus directly signals over-querying (e.g., trimming from 4 to 2 on Bi-TSP50), and prior updates apply only to tools that actually conditioned the edit.
Q3 (Comparison with the strongest NSGA-II baseline under identical interface and evaluation)
We adapted official EoH—the strongest NSGA-II baseline on most Table 1 settings, and E2OC's inner evolver—to evolve the exact same multi-operator batch module under the exact same candidate evaluator, instances, and 200-candidate budget (Appendix G.1):
| Setting (HV at 30 s, mean ± SD) | EoH (single-operator) | EoH (batch interface) | TRACE-EA (batch interface) |
|---|---|---|---|
| Bi-TSP50 (Seen instances) | 0.5215 ± 0.0043 | 0.6265 ± 0.0031 | 0.6366 ± 0.0015 |
| Bi-TSP50 (Unseen instances) | 0.5253 ± 0.0199 | 0.6340 ± 0.0038 | 0.6403 ± 0.0022 |
| Bi-CVRP50 (Seen instances) | 0.3068 ± 0.0050 | 0.4632 ± 0.0645 | 0.5094 ± 0.0028 |
| Bi-CVRP50 (Unseen instances) | 0.3406 ± 0.0012 | 0.4633 ± 0.0438 | 0.5263 ± 0.0087 |
Upgrading EoH to the batch interface indeed accounts for a substantial part of Table 1's raw NSGA-II gap (+0.11 to +0.16 HV; Appendix G.1). At the same time, under identical interface and evaluation, TRACE-EA still outperforms batch-EoH on every setting with zero seed overlap on Bi-TSP50 and 5×–23× smaller across-seed SD on Bi-CVRP50 (±0.0028 / ±0.0087 vs. ±0.0645 / ±0.0438)—because without per-operator trajectory attribution, EoH mutates multi-function bundles blindly, whereas TRACE-EA localizes edits to the bottleneck operator (complementing SEMO, where all methods already share a single-function interface; W2).
Response to Reviewer 2MMa
We greatly appreciate your insightful comments and rigorous assessment of our experimental design. Your feedback directly guided the additional controlled experiments presented below and in the revised manuscript (highlighted in blue).
W1 (Methodological distinction from AutoEP, DASH, MoH, and MeLA)
We agree that individual Pareto indicators and bounded update rules are not new standalone algorithms. What none of these four works addresses is the core bottleneck in multi-objective multi-operator code design: when a multi-function program stalls on a set-valued Pareto front, how to localize which time window, which trade-off region, and which operator function caused the stall, and adjust observation online without extra solver runs.
We will incorporate a concise comparison with these four works into Section 2 (Related Work) in the final version.
W2 (Isolating mechanisms: NSGA-II interfaces, SEMO 360 s vs. 120 s cap, and ablation scope)
We thank the reviewer for catching these protocol differences and ran dedicated controls to isolate each factor:
select_neighborinterface of MPaGE and MEoH. We re-ran all 18 TRACE-EA (SEMO) searches (6 tasks × 3 seeds) from scratch under their exact 120 s per-candidate cap, updating the equal-wall-time data in Tables 1, 3, and 7 and Appendix D.1 of the revised PDF. At 30 s, TRACE-EA (SEMO) ranks 1st by mean HV in 18/24 settings within the SEMO group, including 5/6 seen settings (table below; all 24 settings in Appendix G.3) and all 16/16 settings on Bi-TSP, Tri-TSP, Tri-CVRP, and Tri-FJSP. The corresponding fixed-evaluation-budget runs (3,600 s per-run safety cap, Appendix D.2) for these 120 s SEMO operators are currently running, and we will immediately update both the PDF and this rebuttal as soon as they finish.