acceptodds
Under review as a conference paper at ICLR 2027

Evolutionary-Potential-Aware Iterative Preference Learning for LLM-Based Automatic Heuristic Design

Abstract

Automatic Heuristic Design (AHD) uses large language models (LLMs) to construct heuristics for complex optimization problems. Existing LLM adaptation methods largely learn from the immediate performance of generated heuristics, overlooking the longer-term evolutionary potential revealed by their descendants. Search trees naturally preserve parent–descendant relationships and the outcomes of subsequent exploration, providing structural information that can serve as preference supervision. We propose an evolutionary-potential-aware iterative preference learning framework for LLM-based AHD that converts this information into search-feedback signals. After each MCTS expansion, newly observed descendants reassess the relative evolutionary potential of their ancestors; changes in local rankings then yield search-feedback preference pairs. These pairs complement on-policy performance preferences from newly generated candidates to fine-tune a local LLM through direct preference optimization. The updated LLM subsequently guides MCTS exploration, closing the iterative search–learning loop. Experiments across NP-hard combinatorial optimization tasks show that our method achieves the best overall result in six of nine ACO task–scale settings and the best LLM-based AHD result in eight. Despite using a locally deployed quantized 7B model, it outperforms GPT-4o-mini-based AHD baselines across all nine ACO settings.

Primary area:
optimization
Keywords:
Evolutionary computation, combinatorial optimization, automatic heuristic design

Reviews

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

This paper proposes MCTS-EPPL, an iterative preference-learning framework for LLM-based Automatic Heuristic Design (AHD). Experiments on OP, CVRP, and MKP under ACO, and TSP under GLS demonstrate the effectiveness of MCTS-EPPL.

Critical strengths

S1: The paper identifies a meaningful limitation of existing LLM-based AHD methods.

S2: The ablation study is reasonably extensive.

Critical weaknesses

W1: The novelty of this manuscript appears somewhat limited. The use of MCTS for LLM-based automatic heuristic design has already been explored in [1], while fine-tuning LLMs with DPO to improve heuristic generation has also been investigated in [2].

W2: The empirical validation of the proposed framework is still limited. The main experiments are mainly conducted within the ACO-based heuristic design setting, and the trainable LLM is restricted to Qwen2.5-7B-Instruct. This is insufficient to demonstrate that the proposed MCTS-EPPL generalizes across different heuristic-generation frameworks and LLM backbones. This concern is further amplified by the fact that the framework adopts problem-specific hyperparameter configurations, as shown in Table 2.

W3: The manuscript claims that EPS captures the future search value of a heuristic. However, this claim is not directly validated. The current experiments mainly show that incorporating EPS-based search-feedback preferences improves the quality of the discovered heuristics, but they do not explicitly evaluate whether EPS itself is predictive of a heuristic’s future search value.

W4: This manuscript has substantial room for improvement in terms of presentation quality. For example, EPS is used in the Introduction before its full name, Evolutionary Potential Score, is formally introduced later in the methodology. In addition, the citation style is inconsistent; in most cases, citations should be presented using the \citep{} command.

[1] Monte carlo tree search for comprehensive exploration in LLM-based automatic heuristic design. ICML 2025.

[2] Fine-tuning large language model for automated algorithm design. arXiv: 2507.10614, 2025.

Questions for authors

Q1: The authors state that MCTS-EPPL "modifies the expansion stage to produce multiple comparable candidates" and subsequently evaluates these candidates. Are all fitness evaluations incurred by these additionally generated candidates counted toward the total heuristic-evaluation budget? If not, the comparison may not be fully fair, since the proposed method could effectively consume more fitness evaluations than the baselines under the same nominal search budget.

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

This paper presents MCTS-EPPL, an iterative search-and-learning framework for LLM-based Automatic Heuristic Design (AHD). Unlike existing methods that adapt models solely using immediate heuristic performance, MCTS-EPPL leverages search trees to evaluate long-term "evolutionary potential". It constructs two complementary training signals: on-policy preference pairs comparing newly co-generated candidates, and search-feedback preference pairs derived from ancestor ranking reversals based on an Evolutionary Potential Score (EPS). Fine-tuning a local quantized 7B LLM via Direct Preference Optimization (DPO) within the MCTS loop achieves state-of-the-art results across NP-hard combinatorial optimization tasks and outperforms stronger commercial LLM baselines.

Critical strengths

MCTS-EPPL recognizes that an algorithm's immediate objective value does not fully reflect its capacity to produce superior descendants. It then formalizes this insight through the Evolutionary Potential Score (EPS) and pairwise ranking reversals. By converting tree-search dynamics into credit-assigned search-feedback preferences, it effectively bridges Monte Carlo Tree Search exploration with continual parameter-efficient fine-tuning (LoRA-DPO). The preference-oriented expansion strategy further guarantees that generated candidate comparisons are strictly controlled under shared prompt and operator contexts. Empirically, the framework demonstrates remarkable efficiency: deploying an INT4-quantized local 7B model (Qwen2.5-7B-Instruct), it outperforms competitive API-driven baselines utilizing GPT-4o-mini across all evaluated Ant Colony Optimization benchmarks and achieves the best overall LLM-based results in 10 of 12 experimental settings, all while maintaining tractable training runtimes and low GPU memory overhead.

Critical weaknesses

MCTS-EPPL relies on delicate heuristic hyperparameters and problem-specific engineering. The operator weight ratios (we2:wm1:wm2:ws1w_{e2}:w_{m1}:w_{m2}:w_{s1}) and retained candidate counts (ksavek_{save}) are hand-tuned per problem domain (e.g., varying between 4:2:1:14:2:1:1 and 1:2:2:11:2:2:1), which compromises autonomous generalizability across unstudied combinatorial optimization problems. In addition, running frequent DPO optimization updates alongside MCTS node expansions introduces notable computational overhead, requiring more than double the search wall-clock time of competing methods like CALM (3.18 hours vs. 1.44 hours). The empirical validation is also confined to relatively standard synthetic benchmark distributions within ACO and GLS frameworks, leaving the method untested on large-scale industrial instances or alternative algorithmic metaheuristics (such as genetic algorithms or branch-and-bound). Finally, the tree-augmented completion mechanism incorporates heuristics with strictly worse immediate performance to enforce diversity, an ad hoc intervention whose theoretical justification remains underdeveloped.

Questions for authors
  1. The operator weighting vector and the pruning parameter ksavek_{save} vary considerably across the four evaluation tasks (e.g., ksave=4k_{save}=4 for MKP vs. ksave=2k_{save}=2 for CVRP/OP). How can an end-user configure or adapt these hyperparameters when applying MCTS-EPPL to a completely new combinatorial optimization domain without performing an expensive grid search?
  2. Fine-tuning the LoRA adapter after each parent-node expansion increases search wall-clock time to 3.18 hours (compared to 1.44 hours for CALM). Have you explored lazy, batched, or event-triggered DPO updates (e.g., updating only when a significant EPS reversal occurs or every KK tree expansions), and how would that affect both convergence rate and overall runtime?
  3. The ablation analysis reveals that 26.6% of the tree-augmented completion pairs actually choose a heuristic with worse immediate objective performance than the rejected candidate. Does injecting these inverted objective pairs risk destabilizing the policy, and have you measured whether they induce catastrophic forgetting of basic code syntax or validity?
  4. The experiments exclusively adapt an INT4-quantized Qwen2.5-7B model. Does the evolutionary potential preference signal scale effectively to larger base models (e.g., 14B/32B parameters) or non-quantized weights, or do larger models exhibit diminishing returns relative to the increased DPO fine-tuning latency?
  5. In continual, online DPO across 1,000 evaluations, is the reference model πref\pi_{\text{ref}} kept permanently frozen as the initial base model, or is it periodically updated to a historical checkpoint to prevent the implicit reward from drifting too far from the policy?
Reviewer_piWLOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MCTS-EPPL, an iterative search–learning framework for LLM-based automatic heuristic design built on MCTS-AHD and continual LoRA/DPO fine-tuning. At each expansion, a local LLM samples multiple candidates under one shared operator prompt. Shared-prompt candidates yield adjacent immediate-fitness preference pairs, while descendant-induced reversals in ancestor EPS rankings yield search-feedback pairs. Both kinds of pairs are used to fine-tune a 4-bit Qwen2.5-7B with LoRA-based DPO after every expansion. Experiments on multiple problems each with a 1,000-evaluation budget achieve the best LLM-based result in most scenarios.

Critical strengths
  1. The paper offers a useful paradigm for LLM-based AHD that uses the MCTS search tree both for exploration and as a source of supervision, combining MCTS with iterative DPO fine-tuning of a local model, which is practical and empirically effective.
  2. With a local 7B small model, the method outperforms the GPT-4o-mini-based AHD baselines in most of the problem settings.
Critical weaknesses
  1. Combining tree search with iterative DPO has already been studied before, and fine-tuning the LLM during AHD search has also been studied in CALM and EvoTune. Adding preference learning on top of a strong MCTS-AHD backbone is therefore a fairly natural extension, and the main new element is the EPS-reversal labeling rule.
  2. Compared with the best-known baseline MCTS-AHD on the model, several improvements in Table 1 seems to be small, and no variance and significance test are reported. Notably, the result of w/o DPO variant is worse than the search-only MCTS-AHD variant in Table 4, which means the modified expansion alone seems to degrade the performance.
  3. MCTS-EPPL takes 3.18h per run compared with only 1.44h for CALM as reported in Appendix, yet its margins over local CALM are small. The gain may come from the extra compute spent on per-expansion fine-tuning rather than from the proposed preference signals. If the total evaluation budget is the same, what is the reason for twice the wall-clock time cost?
Questions for authors
  1. The selection step still uses UCT, where Q(v)Q(v) already backpropagates the best descendant value. What extra information does EPS capture beyond Q(v)Q(v) when αEPS=1α_{EPS}= 1 ?
  2. Tables 1 and 3 report means over three runs without std, reporting the std or significance test would be better especially for settings where margins are small.
  3. The total evaluation budget is set to 1000 and DPO runs after every expansion, is DPO with so few pairs per update stable, compared with EvoTune’s original budget of 22,400 outputs?

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.