acceptodds
Under review as a conference paper at ICLR 2027

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

Abstract

Designing effective heuristics for diverse combinatorial optimization problems requires substantial expertise and repeated search. Large language models (LLMs) automate heuristic generation and refinement, but heuristic search typically depends on evaluation feedback from the problem being optimized. Generalizing to new problem definitions using only source-task feedback therefore remains a central challenge. We introduce MECo, an LLM-driven multi-task evolutionary framework for zero-shot cross-problem generalization. MECo maintains task-conditioned heuristic populations and uses a transfer gap based on cross-task population performance to guide their interactions. These interactions enable the transfer and recombination of heuristics. A complementary selection criterion then constructs a compact heuristic set by rewarding each member's additional coverage of source combinations. The selected set is applied to target problems without further search or adaptation. Experiments on 32 problem variants across vehicle routing (VRP) and flexible job-shop scheduling (FJSP) show that MECo achieves the lowest mean costs compared with eight automated heuristic design (AHD) baselines under the same budgets. On out-of-domain problems, it outperforms the strongest baseline in each family, respectively. Moreover, integrating the framework of MECo with different AHD methods significantly improves their performance in both families, supporting its effectiveness across different methods.

Primary area:
optimization
Keywords:
Automated Algorithm Design, Multi-task Evolution, Zero-shot Generalization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_jP9POpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how to use large language models (LLMs) to develop heuristics for an unseen problem using only the evaluation feedback of the source problems. To this end, the paper proposes an LLM-driven multi-task evolutionary framework called MECo. Specifically, MECo constructs the heuristic population for different tasks and performs task interactions according to the transfer gap among different populations. Then, MECo leverages the performance complementarity between source tasks to select a compact heuristic set to apply to the target task without search or adaptation. Experiments on the vehicle routing problem (VRP) and flexible job-shop scheduling problem (FJSP) construct 32 problem variants and verify the effectiveness of the proposed method in ID and OOD settings. The experimental results report that MECo outperforms all baselines in terms of mean costs under the same budgets.

Critical strengths
  1. The paper studies a practical and valuable problem. In real-world scenarios, new constraint combinations are emerging continuously. However, it is expensive to perform a separate heuristic search for each new problem.
  2. The paper provides extensive experiments, which cover 32 problem variants across VRP and FJSP with eight automated heuristic design methods as baselines. The comparisons within these experiments are controlled due to shared source tasks and proposal budgets.
  3. The paper presents the performance of baselines (EoH, ReEvo, and HSEvo) equipped with the proposed method. It not only verifies the effectiveness of the proposed method in a new combination task, but also demonstrates the applicability of the proposed method across different heuristic search methods.
Critical weaknesses
  1. The generalization evidence in the paper is limited by the scope of the OOD setting. The OOD experiment investigates the performance of the proposed method on combined-constraint tasks derived from seen single-constraint tasks within the same problem family. This supports the generalization capability on limited changes of constraint combinations and cannot demonstrate the generalization capability under broader changes. The authors should evaluate the effectiveness of the proposed method on more complex constraint combination settings, such as narrower time windows.
  2. Further clarification of methodological contributions compared to existing methods is necessary. EoH-S [1] has already employed a complementary heuristic selection and selected parents according to performance differences. EMO-STA [2] has investigated the sharing and transfer of programs across tasks. The authors should further demonstrate the distinct methodological design of the proposed method compared to these two methods.
  3. It is unclear whether a smaller transfer gap indicates greater gains from cross-population recombination. Specifically, the paper fails to verify that Eq. 6 is an effective metric to predict gains after combining two single-constraint tasks. Eq. 6 measures the cross-task performance reduction of the current populations, but its ability to predict gains after cross-population recombination remains under-explored. Thus, the authors should provide empirical or theoretical evidence to verify the relationship between the transfer gap in Eq. 6 and gains from cross-population recombination.
  4. The advantage of the proposed method compared to the strongest baseline (MoH) needs more convincing validation. Specifically, the experimental results in Table 2 are averaged over three runs. Meanwhile, in Appendix E.5, the authors perform ten searches to report the final results. The paper should increase the number of independent runs for the key comparisons, such as the comparison between the proposed method and MoH. Meanwhile, it is also important to increase the number of independent runs for the ablation study.

Minors

  1. In line 121, the last word in this line, “geberakuzatuin” may be “generalization”.
  2. In lines 236-239, c3c_3 and m1m_1 are referred to as exploratory crossover and single-parent mutation, while Table 4 uses w/o diversification and w/o transfer repair. The authors should use consistent terminology and clarify the correspondence.

References

[1] EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design.

[2] Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery.

Questions for authors

Refer to Critical Weaknesses for more details.

Reviewer_6LNuOpenReview ↗
Rating
4(+1)
Confidence
4(+1)
Informativeness
2
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper considers a limitation of existing AHD methods, which typically rely on evaluation feedback from the task being optimized. However, the resulting heuristics may not transfer effectively when the problem definition changes. To address this zero-shot cross-problem generalization challenge, the paper proposes MECo, which enables knowledge transfer by interacting and recombining heuristics across task-conditioned populations. A population-level transfer gap guides which tasks interact at each stage. Experiments on 32 problem variants across VRP and FJSP show that MECo outperforms the evaluated task-specific and multi-task AHD baselines in terms of average ID and OOD performance. The framework can also be integrated with different AHD search methods to improve their performance.

Critical strengths
  1. The paper is clearly written and well organized, with an accessible presentation of the proposed framework. It explores a practically relevant AHD setting in which heuristics generalize to new combinations of known constraints without evaluation feedback from the target problems.
  2. The experiments show improved average performance on ID and OOD across two problem families. Integration with existing AHD methods further supports the framework’s utility, with statistically significant improvements demonstrated for EoH and ReEvo on FJSP.
Critical weaknesses
  1. The contribution of transfer-gap guidance is not separately evaluated, as the current ablation also removes the preference for unexplored task combinations.
  2. The paper employs a complementary criterion to select the final set of heuristics. However, its additional benefit is not separately evaluated.
Questions for authors
  1. Could the authors add an ablation that keeps the preference for unexplored task combinations while replacing transfer gap guidance with random pairing?
  2. Could the authors add an ablation that uses the same candidate pool but selects the four heuristics with the lowest average normalized cost across the four source tasks? This would help clarify the benefit of the proposed selection mechanism.

Typo:

  • Minor writing issues include a missing “of” in “a set ... heuristics” at line 116, the typo “geberakuzatuin” at line 121, and a missing space in “Figure5” at line 421.
  • Please also check the statement at lines 434–435 against Table 4, where removing transfer repair, rather than transfer-gap guidance, gives the highest VRP OOD cost.
Reviewer_K11kOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes MECo, an LLM-based multi-task evolutionary framework for zero-shot generalization across combinatorial optimization problems. It uses transfer-guided interactions between heuristic populations and selects complementary heuristics using source-task feedback. Experiments on VRP and FJSP show improvements over several baselines.

Critical strengths

The paper addresses an interesting and important problem of transferring heuristics to unseen optimization tasks. The proposed combination of multi-task evolution and heuristic selection seems promising, although some aspects of the approach feel somewhat heuristic and hand-wavy. I also appreciate authors effort to compare the method with several baselines and the component ablations provided by the authors. This paper is fairly well written.

Critical weaknesses

One of the improvement areas I see is that the evaluation is limited to standard, well-studied optimization problems with, as I see, controlled synthetic constraints. Since LLMs may already be familiar with common VRP and FJSP heuristics, it is unclear how well the approach would work on less familiar messy real world problems (a main motivation for the work). More realistic settings involving non-metric travel costs, dynamic constraints, or stochastic conditions would provide stronger evidence of generalization. Furthermore, while I appreciate authors doing experiments with VRP and FSJP, the experiments still cover only two problem families, where unseen tasks are combinations of four known constraints. This is a narrow form of compositional generalization and given the heuristic nature of the work, the paper claims would be stronger if more problem families can be considered.

Another point is that the paper seems to lack a simpler baseline that evolves a single population of heuristics using feedback from all source tasks simultaneously, rather than progressively combining task-specific populations as MECo does. Comparing against such a baseline would help clarify whether the proposed task composition and transfer mechanisms actually provide additional benefits over straightforward joint optimization. It is possible that I may be overlooking something here and would appreciate authors thoughts.

Overall, I find the work to be useful and interesting but can be made stronger.

Questions for authors
  1. Can the authors compare methods under matched computational budgets rather than only matched proposal counts? MECo sometimes may require substantially more tokens and training time, so it would be useful to understand whether the performance gains justify the additional computational cost (specially given some performance improvement seems marginal).

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.