- Rating
- 4
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper proposes CoEvoRL, a framework that jointly evolves LLM-generated heuristics and an RL-based heuristic selector. The selector identifies states where the current pool lacks promising actions, and this feedback guides the LLM toward complementary heuristics. A variable-pool selector and coverage-aware admission/pruning rules support this iterative process. Experiments cover JSSP, TSP, multidimensional knapsack, and online bin packing.
Critical strengths
-
Clear motivation and a meaningful methodological contribution. Using selector feedback to generate complementary heuristics is a sensible way to address this mismatch, and gives the LLM and RL components a clear reason to interact.
-
The components fit together well. Coverage diagnosis guides generation, the admission criterion controls pool growth, and the variable-pool selector accommodates new heuristics. The analysis provides a useful rationale for balancing action coverage against selection difficulty.
-
Broad and reasonable evaluation. Comparisons among heuristic-based methods control the initial pool, LLM budget, and selector training budget. The appendix includes results across ten runs with std, while the component ablations and exact decomposition on TSP-10 help explain the source of the gains.
Critical weaknesses
-
The practical dependence on reference feedback needs clarification. Section 4.2 combines critic-estimated coverage gaps with optional reference-action feedback. However, it is unclear which main experiments use reference actions and how much they contribute. Appendix B.1 describes offline reference solutions, but does not fully explain how these become reference actions at partial states visited by the selector. The current “w/o diagnosis” ablation removes the diagnosis as a whole, so it does not establish how well the method works using only the learned critic. This matters when high-quality reference solutions are expensive or unavailable. Which experiments use reference-action feedback, and how are those actions obtained at the visited partial states? Could the authors report a critic-only variant without reference-action feedback?
-
Evaluating four problem types is a strength. A compact heuristic pool reduces the selector’s action space, but coverage diagnosis still evaluates the full feasible primitive action set, so computational scalability also deserves empirical validation. Can an evolved pool and trained selector be reused on larger instances or a different distribution without repeating the full co-evolution process? A small transfer experiment, together with a runtime breakdown on larger instances, would help establish the practical scope.
-
The efficiency claims. Table 3 reports total runtime and LLM usage only for JSSP (10x10), and inference time per instance is not reported. The matched-episode comparisons are useful for the limited-training setting, but the quality-cost trade-off differs across tasks. E.g., on TSP-100, CoEvoRL achieves a 13.94% gap, compared with 0.77% for Construct. (Full). The strongest conclusion is therefore that CoEvoRL improves heuristic selection and performs well under limited training budgets, with task-dependent trade-offs against fully trained construction policies. What is the training/evolution cost and inference time per instance for the other tasks, and specify the actual Full training budgets? A quality vs. total-cost comparison would make the intended application setting clearer.
Questions for authors
Please refer to weaknesses.
5 comments
Response by Authors [2/3]
W2. Transfer to larger instances and runtime breakdown.
Thank you for this constructive feedback.
First, following your suggestion, we have evaluated the evolved heuristic pool and trained selector on larger-sized and out-of-distribution instances. We freeze both components of CoEvoRL trained on TSP-100 and JSSP 20 × 20, and evaluate them directly on 1) larger-sized instances up to TSP-1000 and JSSP 100 x 20 and 2) different instance distributions from the TSPLIB and Taillard JSSP benchmarks. The results are as follows (bold = best among methods under matched training budgets):
| Problem | JSSP 30×20 | JSSP 50×20 | JSSP 100×20 | TSP-200 | TSP-500 | TSP-1000 |
|---|---|---|---|---|---|---|
| Construct. (Full) | 27.83% | 17.99% | 7.28% | 4.50% | 34.12% | 52.84% |
| Construct. (Limit) | 33.70% | 21.92% | 10.21% | 85.99% | 130.35% | 172.35% |
| Best Heur. | 30.76% | 16.97% | 7.35% | 28.47% | 26.17% | 25.14% |
| EoH | 31.05% | 18.00% | 7.57% | 25.06% | 24.43% | 24.41% |
| Fixed Pool | 27.54% | 17.30% | 7.76% | 23.28% | 22.95% | 23.72% |
| HeurAgenix | 26.89% | 17.24% | 7.24% | 19.21% | 20.58% | 22.48% |
| CoEvoRL (Ours) | 26.62% | 16.71% | 7.02% | 17.10% | 18.27% | 20.48% |
| Taillard Bench. | 15 × 15 | 20 × 15 | 20 × 20 | 30 × 15 | 30 × 20 | 50 × 15 | 50 × 20 | 100 × 20 |
|---|---|---|---|---|---|---|---|---|
| Construct. (Full) | 22.16% | 27.99% | 24.55% | 29.11% | 33.78% | 20.84% | 23.49% | 15.15% |
| Construct. (Limit) | 28.82% | 30.83% | 34.22% | 34.28% | 37.47% | 23.07% | 25.86% | 16.16% |
| Best Heur. | 23.94% | 31.42% | 27.39% | 31.21% | 31.13% | 20.67% | 23.93% | 13.57% |
| EoH | 25.40% | 31.66% | 28.61% | 30.86% | 31.70% | 20.82% | 24.33% | 13.29% |
| Fixed Pool | 21.89% | 27.41% | 25.17% | 28.70% | 30.89% | 21.01% | 23.28% | 13.47% |
| HeurAgenix | 21.19% | 26.36% | 23.78% | 28.46% | 29.95% | 20.67% | 22.77% | 13.18% |
| CoEvoRL (Ours) | 21.01% | 26.49% | 23.57% | 28.26% | 29.45% | 21.20% | 22.33% | 13.17% |
| TSPLIB Bench. | 50-100 | 100-200 | 200-500 | 500-1000 | 1000-2000 |
|---|---|---|---|---|---|
| Construct. (Full) | 1.88% | 6.08% | 26.13% | 43.77% | 78.08% |
| Construct. (Limit) | 51.96% | 71.47% | 109.35% | 143.64% | 205.61% |
| Best Heur. | 25.25% | 23.38% | 23.88% | 27.84% | 25.94% |
| EoH | 21.92% | 21.29% | 22.78% | 26.31% | 24.81% |
| Fixed Pool | 19.49% | 18.49% | 22.69% | 25.12% | 23.59% |
| HeurAgenix | 15.57% | 16.06% | 19.92% | 22.42% | 23.00% |
| CoEvoRL (Ours) | 14.97% | 15.40% | 18.81% | 21.73% | 21.88% |
CoEvoRL shows strong generalization, achieving the best solution quality in nearly all settings. Notably, as the instance size grows, the advantage of learning heuristic selection approaches becomes more significant. The gaps of Construct. (Full) grow from 0.77% to 52.84% when generalizing from TSP-100 to TSP-1000, while CoEvoRL remains stably effective across a range of larger instance sizes (20.48% on TSP-1000) and on out-of-distribution benchmark instances.
Furthermore, in response to your concern about the runtime breakdown, we report the inference runtime on the original and larger-sized instances, and break the total time into three components: 1) generating proposals with the heuristics (), 2) selecting a proposal with the selector (), and 3) updating the environment (). The results are as follows (in seconds):
| JSSP | 10 × 10 | 15 × 15 | 20 × 20 | 30 × 20 | 50 × 20 | 100 × 20 |
|---|---|---|---|---|---|---|
| 0.018 (34.5%) | 0.058 (41.0%) | 0.141 (46.9%) | 0.295 (51.3%) | 0.768 (57.0%) | 2.903 (62.9%) | |
| 0.023 (44.4%) | 0.052 (37.1%) | 0.094 (31.3%) | 0.143 (24.8%) | 0.239 (17.8%) | 0.486 (10.5%) | |
| 0.010 (18.3%) | 0.028 (19.6%) | 0.060 (19.9%) | 0.129 (22.4%) | 0.326 (24.2%) | 1.200 (26.0%) | |
| 0.052 | 0.141 | 0.300 | 0.576 | 1.348 | 4.617 |
| TSP | 20 | 50 | 100 | 200 | 500 | 1000 |
|---|---|---|---|---|---|---|
| 0.004 (37.3%) | 0.020 (54.0%) | 0.083 (69.3%) | 0.321 (78.1%) | 1.964 (78.6%) | 7.847 (67.3%) | |
| 0.005 (44.5%) | 0.012 (31.9%) | 0.024 (20.2%) | 0.050 (12.1%) | 0.135 (5.4%) | 0.607 (5.2%) | |
| 0.002 (15.8%) | 0.005 (12.6%) | 0.012 (9.6%) | 0.038 (9.2%) | 0.395 (15.8%) | 3.187 (27.3%) | |
| 0.010 | 0.036 | 0.119 | 0.411 | 2.500 | 11.663 |
As instance size grows, generating proposals with the heuristics becomes the dominant runtime cost, reflecting the necessary computational requirements on larger instances, while the selector accounts for a smaller share of total runtime. Overall, even at the largest sizes tested (TSP-1000 and JSSP 100 × 20), we can reuse the frozen heuristic pool and selector directly, with a modest end-to-end inference time. The full transfer results and detailed runtime statistics are reported in Appendices C.5 and C.7 of our revised manuscript.
Response by Authors [3/3]
W3. Inference time and training efficiency.
Thank you for this insightful feedback. Your assessment, "The strongest conclusion is therefore that CoEvoRL improves heuristic selection and performs well under limited training budgets, with task-dependent trade-offs against fully trained construction policies", exactly highlights the central claim and main findings of our work.
Following your suggestions, we now provide 1) more comprehensive training / evolution cost statistics on all four problems (Appendix C.7), 2) the inference runtime on both the original and larger-sized instances (response W2), and 3) the full training budgets of Construct. (Full) baselines in our experiments (Appendix B.3). All the detailed statistics and results are also presented in the appendices of our revised manuscript.
Furthermore, to make our standpoint clearer, we provide a solution quality vs. training budget curve to compare the construction policies under different training budgets from 1× to 12× relative to CoEvoRL (Appendix C.4 of our revised manuscript). The table below summarizes the gaps at selected budgets:
| Problem | JSSP 10×10 | TSP-20 | MKP-100 | OBPP-100 |
|---|---|---|---|---|
| CoEvoRL (1×) | 14.09% | 7.12% | 1.32% | 5.09% |
| Construct. (1x) | 22.12% | 18.32% | 4.45% | 7.14% |
| Construct. (4x) | 16.43% | 9.39% | 4.15% | 6.95% |
| Construct. (8x) | 16.29% | 8.23% | 4.11% | 6.91% |
| Construct. (12x) | 17.58% | 7.58% | 4.10% | 6.85% |
The marginal gains from additional training vary across tasks, while the construction baseline approaches CoEvoRL on TSP-20 at 12× budgets, but its gains on MKP-100 and OBPP-100 are rather modest, possibly due to different problem structures. CoEvoRL achieves better solution quality than the construction baselines, with only a smaller training budget. The detailed curves are presented in Figure 5 of Appendix C.4.
Response by Authors [1/3]
Thank you for your careful review and constructive feedback. We address each point below, and have incorporated the related clarifications and additional results in our revised manuscript.
Thank you for raising this point.
First, we apologize for the ambiguity caused by our overly brief description in the original manuscript. We have revised Section 4.2 and Appendix B.2 to clarify under what condition reference actions can serve as meaningful diagnostic feedback and how we derive them from offline solutions. We use reference-action feedback only when the problem structure allows us to translate a given offline solution into a well-defined state-action MDP sequence. This feedback is used for TSP and JSSP in our main experiments. Specifically, for TSP, we follow the offline reference tour from the starting city, and take each subsequent city as the reference action for the corresponding decision step. For JSSP, we order the operations in the reference schedule by start time while respecting job precedence, then record their corresponding jobs to obtain a reference dispatch sequence. In both tasks, we use the reference action for diagnosis only if it is feasible in the current rollout state.
For the other two tasks, MKP and OBPP, the same translation does not produce a meaningful reference action at each decision step. In MKP, an offline solution specifies a subset of items but leaves their selection order undetermined, while in OBPP, the offline solution uses future arrivals, and thus a recovered decision may depend on hindsight unavailable to the selector in the current state. We therefore use only the critic-based coverage residual approximation for diagnosis in MKP and OBPP.
Second, to address your concern about the contributions of the critic-based residual and reference-action feedback in the diagnosis, we further evaluate two diagnosis-ablation variants: critic-only diagnosis and reference-only diagnosis:
Generally, both signals contribute to the performance, and combining them yields the best gap in nearly all settings, suggesting that the two signals provide complementary information in the diagnostic feedback. Notably, the gain of critic-based diagnosis is more significant on larger instances with longer decision sequences, and the critic-only variant still remains advantageous without reference-action feedback. This demonstrates the effectiveness of CoEvoRL in settings where reference solutions are expensive or unavailable. This additional ablation study is provided in Appendix C.6 (Table 12) of our revised manuscript.
Finally, CoEvoRL still remains effective when reference solutions are expensive or unavailable. In CoEvoRL, each evolution round uses only 12 reference solutions for diagnostic feedback, which can also be reused across rounds. This cost is very low compared to the millions of training samples in common NCO methods. Furthermore, according to the ablation results, CoEvoRL still remains advantageous without reference-action feedback. Therefore, the critic-only variant provides another practical option and remains advantageous in settings where reference solutions are expensive or unavailable.