acceptodds
Under review as a conference paper at ICLR 2027

Guided Evolution and Automated Refinement for LLM-based Heuristic Design

Abstract

LLM-based Automated Heuristic Design (AHD) has shown great promise for combinatorial optimization (CO), discovering competitive heuristics for well-studied problems such as the Traveling Salesman Problem (TSP). However, the quality of LLM-generated heuristics degrades in less-studied CO domains such as airline crew pairing, where LLMs lack domain-specific priors. We hypothesize that the general heuristic-design knowledge of LLMs can still be effective in such domains, and that the bottleneck lies in how the surrounding search loop selects candidates and feeds back information. We study this in a joint multi-component setting, where constructive and refinement heuristics are evolved together; the enlarged space makes scalar-fitness-based selection and feedback particularly uninformative. We propose Guided heuristic Evolution and Automated Refinement (GEAR), which uses complementary-gain population management to retain candidates that excel on different instances, and an executable Analyst that writes feature functions over evaluated solutions to produce structured, distributional feedback. Across four less-studied and four classic CO domains, with all baselines adapted to the same joint space, \ours achieves the highest mean test fitness in all eight domains and consistent gains on scale-up generalization in the classic domains.

Primary area:
optimization
Keywords:
automated algorithm discovery, LLM agent, combinatorial 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_YrV6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

GEAR uses large language models to write heuristic programs for combinatorial optimization problems. These programs first construct an initial solution and then improve it. GEAR modifies the code for both steps together. It selects programs with different strengths and uses them as references for the language model to generate new programs. To find what still needs improvement in the programs, GEAR also uses an Analyst to write and run analysis code. GEAR feeds the results back to the language model to guide further changes. The experiments cover eight types of problems.

Critical strengths
  1. The method considers the different strengths of programs. The case study and ablation experiments suggest that selecting programs in this way is useful.
  2. The Analyst writes and runs analysis code to help the language model find what needs improvement in the programs.
  3. The experiments cover eight types of problems, and the paper reports how performance varies across three runs.
  4. The paper also examines the role of each component.
Critical weaknesses
  1. The final test results lack comparisons under equal time or token budgets.

GEAR uses more time and tokens per iteration than most of the baseline methods.

  1. Some tasks have few test samples.

For example, PVRP has only 4 test instances, Crew Pairing has only 7 test files, and PDPTW has only 14 test instances. Performance on these tasks still needs to be checked using more test samples.

Questions for authors
  1. If all methods use the same amount of time or the same number of tokens, do the final programs produced by GEAR still perform better on the test set?

  2. Tasks such as PVRP have few test samples. Are results on more test samples available to support the current conclusions?

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

This paper studies LLM-based automated heuristic design in less-studied combinatorial optimization domains. It proposes GEAR, which jointly evolves constructive and refinement heuristics. Complementary-gain population management retains candidates with different strengths across instances, while a code-writing Analyst extracts features from problem–solution pairs and provides structured feedback for further revisions. Experiments cover four less-studied and four well-studied domains.

Critical strengths
  1. GEAR achieves the highest mean test fitness among the evaluated methods across all eight domains. The results suggest that the framework is useful across several optimization problems.
  2. The Analyst provides measured feedback beyond aggregate fitness. The PDPTW case study offers a concrete example of how diagnostic features can inform algorithm revisions.
Critical weaknesses

The paper motivates GEAR through weaker domain-specific priors in less-studied domains. It argues that these conditions make joint optimization, instance-level complementarity, and richer feedback particularly important. My concern is that the experiments do not directly test the link between these limitations and the less-studied setting. The same selection and feedback limitations also arise in broader AHD settings, where related approaches have already been studied. Showing that these techniques work on less-studied tasks does not yet establish why weaker domain priors make them especially important, or what the results reveal about less-studied AHD specifically.

Questions for authors
  1. Dependence on the less-studied setting. Do the Analyst and complementary-gain mechanisms provide larger or qualitatively different benefits on less-studied tasks than on well-studied tasks? Table 3 reports component ablations only for the four less-studied domains. Please extend the same ablations to the well-studied tasks and discuss whether the results support the hypothesis about weaker domain priors. If the evidence instead supports a general improvement to AHD, the research objective and contribution statements should reflect that scope.

  2. Joint versus sequential optimization. Section 4.1 explains that the constructive and refinement components are generated and evaluated together. Appendix Table 7 shows that allowing both components to change is beneficial compared with fixing either one, but does not establish whether joint evolution is preferable to sequential optimization. Under the same total search budget, please compare joint evolution with first optimizing the constructive component while holding refinement fixed, then optimizing refinement while holding the resulting constructor fixed. This would clarify whether the benefit comes from joint search or from making both components editable.

  3. Relation to CPI. Appendix B.2 discusses EoH-S but leaves the mathematical distinction unclear. For a CPI defined as the mean best fitness across instances, complementary gain appears to be its marginal improvement multiplied by the number of instances. Please clarify this relationship and explain the differences in parent selection and population survival.

  4. Insights from Analyst features. I encourage the authors to extend the PDPTW feature analysis to other tasks. Representative features, the failure modes they describe, and the subsequent algorithm changes could provide useful insights for both AHD and the underlying CO domains.

  5. Limitations of the Analyst. Please also discuss the limitations of the Analyst and its feature-based feedback, such as cases where it fails to identify useful features or guide effective optimization. Understanding these limitations could inform the design of future AHD frameworks.

The last two points are suggestions to improve the explanation and usefulness of the paper, rather than reasons to lower the recommendation.

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

GEAR jointly evolves constructive and refinement heuristics using complementary population management and an executable Analyst that provides diagnostic feedback. The results are promising, but the novelty beyond existing EoH-S method and the benefits over strong existing initialization methods and solvers remain insufficiently established.

Critical strengths

Executable diagnostic feedback is a promising design, and the component ablations show meaningful performance gains.

Critical weaknesses
  1. Substantial overlap with EoH-S and no direct comparison. EoH-S already uses instance-wise performance profiles, greedy marginal improvement of a complementary population objective for survival, and complementary behavior for parent selection. GEAR’s survival gain has the same marginal-improvement structure when expressed using a common score convention. See EoH-S’s complementary search and population management procedures. GEAR’s directional parent sampling and single-program output provide distinctions, but their additional value is untested. The experimental comparison omits this particularly relevant method. This substantially weakens the novelty claim.

  2. The necessity of evolving initialization is not established against strong existing methods. The motivation emphasizes the potential limitations of fixed initialization, but the presented comparisons do not establish an advantage over strong existing constructive heuristics or other initialization methods. The critical comparison is between full GEAR and a strong existing initializer paired with an evolved refinement component. The refinement component should be evolved separately for each initializer under comparable discovery budgets. Initial solution quality, feasibility, construction time, and final solution quality under equal total solving time should all be reported. Standalone initialization superiority is not essential, but the additional downstream value of evolving initialization needs to be demonstrated.

Questions for authors
  1. How GEAR perform compared with EoH-S and EoH-S with the same Analyst under matched search spaces and computational budgets?

  2. Would strong existing initializers, each paired with a separately evolved refinement component, match or exceed full GEAR under equal solving time?

  3. How do the generated heuristics compare with strong traditional and recent neural solvers on representative compatible tasks?

6 comments
AuthorsOpenReview ↗

Response Part I (comparison with EoH-S and necessity of evolving initialization)

We thank the reviewer for the thoughtful feedback. We have clarified GEAR’s relationship to EoH-S and added comparisons addressing its methodological differences, evolving initialization, and practical performance. We hope these results address your concerns and would be happy to discuss any remaining questions.

(Q1/W1) Comparison with EoH-S and EoH-S + analyst

We thank the reviewer for this suggestion. We added comparisons with EoH-S and EoH-S + Analyst, with matched search space and computation budget. EoH-S + Analyst uses our Analyst feedback while retaining EoH-S’s parent-selection and population-survival rules. The test AF results are:

DomainEoH-SEoH-S + AnalystGEAR
PDPTW0.5160.6180.667
Crew Pairing0.7520.8551.104
Technology Mapping0.5880.5940.626
Intra-op0.4620.4810.488
CVRP0.8710.8690.936
FSSP0.9170.9350.957
MDMKP0.7340.7520.789
PVRP0.7130.7460.726

GEAR achieves higher test AF than EoH-S on all eight domains and EoH-S + Analyst on seven of eight domains. Adding the Analyst improves EoH-S on most domains, but a performance gap remains. These comparisons support the effectiveness of GEAR’s complete design.

We agree with the reviewer that GEAR’s survival gain shares the marginal-improvement structure of EoH-S under a common score convention. Building on this shared principle, GEAR uses directional complementary gain for both parent selection and survival. In comparison, EoH-S favors crossover parents with larger Manhattan distance and starts greedy survival from the single heuristic with the highest average fitness. At the framework level, GEAR combines this strategy with executable Analyst feedback to jointly evolve construction and refinement. We have updated manuscript to clarify these differences and explicitly acknowledge the shared marginal-gain survival principle.


(Q2/W2) Necessity of evolving initialization

We thank the reviewer for suggesting this comparison. We added experiments with fixed initialization and separately evolved refinement across all eight domains. The initializer remains fixed throughout discovery, while refinement is evolved specifically for it, with the Analyst and population-management components enabled. Example initialization include nearest-neighbor construction for CVRP, greedy schedule and route construction for PVRP, and multi-start job orderings for flow shop.

We additionally measured initialization quality, feasibility, construction time, and final quality for saved full-GEAR programs. Both configurations use the same total solving limits, including construction and refinement.

DomainConfigurationInitial AFFeasibility rate: initial → finalConstruction (s/file)Final AF
PDPTWFixed init0.0000.0% → 57.1%0.140.532
GEAR0.12814.3% → 75.0%2.910.667
Crew pairingFixed init0.744100.0% → 100.0%0.060.744
GEAR0.79571.4% → 100.0%7.181.104
Technology mappingFixed init0.525100.0% → 100.0%0.490.601
GEAR0.23487.5% → 100.0%0.250.626
Intra-opFixed init0.26726.7% → 100.0%1.970.394
GEAR0.46466.7% → 100.0%7.970.488
CVRPFixed init0.795100.0% → 100.0%0.070.896
GEAR0.933100.0% → 100.0%2.920.936
Flow shopFixed init0.875100.0% → 100.0%0.010.957
GEAR0.975100.0% → 100.0%44.930.957
MDMKPFixed init0.62466.7% → 66.7%0.420.716
GEAR0.45433.3% → 100.0%0.930.789
PVRPFixed init0.17925.0% → 100.0%0.000.639
GEAR0.591100.0% → 100.0%0.010.726

Full GEAR achieves better final AF in this comparison. It also achieves better final quality in cases where the fixed initializer has higher initial feasibility. This suggests that the benefit of evolving initialization extends beyond producing feasible starting solutions and is consistent with better coordination between jointly evolved construction and refinement.

AuthorsOpenReview ↗

Response Part II (Comparison with Classical Solver and Neural Solver)

(Q3) How well does classical solver and neural solver work

We thank the reviewer for this suggestion. We added strong traditional baselines across six domains and pretrained neural baselines on compatible CVRP and flow-shop benchmarks. The new baseline evaluations use matched budget, and pretrained networks are used without retraining.

GEAR’s reference AF is close to URS on CVRP (0.936 vs. 0.931). On the five-machine flow-shop subset, our fresh evaluation achieves 0.994, compared with 0.980 for PFSS-IL. Specialized traditional solvers perform better in several settings; for example, NEH and Iterated Greedy achieve 0.979 and 0.999 on the full flow-shop test set, compared with GEAR’s reported 0.957.

These results complement our comparisons with AHD baselines. GEAR improves the effectiveness of automated heuristic discovery across domains, and the resulting programs achieve competitive quality in some settings. The specialized-solver comparisons establish the practical context for these improvements and identify where performance gaps remain.

DomainMethodTest AF ↑Reference GEAR AF ↑
PDPTWLKH-30.6430.667
Crew pairingRestricted set partitioning + HiGHS0.8871.104
Technology mappingMockturtle, area-oriented 6-LUT mapping1.0110.626
Intra-opASPLOS 2025 contest winner0.9740.488
DomainMethodTest AF ↑Reference GEAR AF ↑
CVRPHGS-CVRP0.9930.936
URS, pretrained neural0.9310.936
Flow shop, full test setIterated Greedy0.9990.957
NEH0.9790.957
Flow shop, five-machine subsetIterated Greedy1.0000.994
NEH0.9950.994
PFSS-IL, pretrained neural0.9800.994

GEAR jointly evolves construction and refinement heuristics within a shared solver skeleton. This provides a common search space for comparing AHD methods and allows us to evaluate discovery effectiveness under a finite budget. Given the skeleton and evaluator, GEAR automatically develops the problem-specific construction and refinement heuristics.

Strong specialized solvers remain valuable where suitable implementations are available. However, their availability and compatibility cannot be assumed for every problem or variant. GEAR provides a reusable discovery procedure across domains, offering a way to develop heuristics within the supplied solver structure. Our experiments show improvements over the evaluated AHD baselines, and the additional comparisons show that generated programs can achieve quality competitive with evaluated existing algorithms in some settings. GEAR’s practical value is in automating heuristic development across domains while producing competitive programs with limited human effort.

I thank the authors for their hard work. The new results and discussion improve the soundness of the paper. However, I have some further concerns about the new results of fixed initialization in the response:

  1. The compared fixed initializations on some problems may be too naive and ineffective to support the novelty and significance of the newly proposed method, for example, on PDPTW the initialization feasibility rate is 0%. As far as I know, advanced solution construction methods exist, like Clarke–Wright savings for CVRP, Lu–Dessouky insertion for PDPTW, and NEH for flow shop. Although the time is limited, which I understand, I believe involving stronger initialization in comparisons on CVRP, PDPTW, and flow shop is very helpful in supporting the significance of the proposed method. It will also provide insight about whether the proposed method can achieve further improvement based on those existing strong initialization methods.

  2. On flow shop, GEAR gets initial A 0.975 but final AF of 0.957. Is there a specific reason for the performance drop? Together with the previous concern, does it mean GEAR may damage the performance gained from existing strong construction methods?

I will raise my rating to 3 if the above points are addressed by empirical evidence or sound argumentation.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.