acceptodds
Withdrawn from ICLR 2027

ParetoEvo: Pareto-Guided Evolutionary Tree Search for Automatic Heuristic Design with LLM Agents

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Combinatorial optimization (CO) generally relies on human-designed heuristics to obtain high-quality solutions when exact search is computationally prohibitive. Large language model (LLM)-based automatic heuristic design (AHD) reduces this reliance by iteratively generating, evaluating, and revising executable heuristics. However, evaluating heuristics primarily by average solution quality can overlook execution cost and difficult-instance performance. Moreover, attained objective values do not necessarily reveal a heuristic’s potential for further evolution. To address these limitations, we propose ParetoEvo, a Pareto-guided evolutionary tree-search framework that combines objective trade-offs with evidence of search potential. We develop Pareto-dominance Monte Carlo tree search (PD-MCTS) to allocate evaluations through vector-valued subtree returns over average quality, execution time, and worst-instance quality. To complement descendant-based evidence with earlier indications of search potential, we propose adaptive productivity control (APC) to grant additional expansions when productive creation empirically predicts productive subsequent search. To adapt revisions to search experience, reflection-conditioned Actor and Reflector LLM agents use evaluated transitions to update guidance for subsequent heuristic generation. Experiments across diverse CO tasks demonstrate improvements in solution quality, execution efficiency, and worst-instance performance over LLM-based AHD baselines, alongside faster convergence and higher final Pareto-front quality.

Primary area:
optimization
Keywords:
Automatic heuristic design, Large language model, optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Mp3XOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes ParetoEvo, an LLM-based automatic heuristic design framework that combines multi-objective tree search with adaptive expansion and reflection-based generation. It introduces Pareto-dominance MCTS (PD-MCTS) to guide search using average solution quality, execution time, and worst-instance performance. Adaptive productivity control (APC) allocates additional expansions based on evidence of future search potential, while Actor and Reflector agents use evolutionary feedback to guide heuristic generation. Experiments across multiple combinatorial optimization problems and heuristic paradigms report improvements in solution quality, execution efficiency, and Pareto-front convergence.

Critical strengths

The paper addresses a practically relevant limitation of existing AHD methods by considering solution quality, execution efficiency, and worst-instance performance jointly. The integration of multi-objective subtree selection with productivity-guided expansion provides a coherent approach to allocating search effort, and the ablation results suggest that the proposed components contribute to overall performance. Another strength is the extensive experimental evaluation across multiple optimization problems and heuristic paradigms, including comparisons with multi-objective AHD baselines, generalization tests, and sensitivity analyses. These results provide encouraging evidence of the framework's effectiveness.

Critical weaknesses

The main concern is that the proposed search mechanisms lack sufficient justification. PD-MCTS uses mean subtree objective vectors, which may obscure promising Pareto trade-offs, while the maximal crowding-distance rule in Eq. (7) may favor extreme solutions. The Scalar-UCT ablation does not establish its advantage over alternative Pareto-aware selection strategies. Although APC improves performance, the paper does not directly validate whether productivity at creation predicts subsequent expansion success or distinguish this effect from reallocating expansion opportunities.

Despite the broad evaluation, some conclusions require stronger evidence. Improvements over the strongest baselines in Table 1 are often marginal, while significance tests compare only against EoH. Pareto-front comparisons are limited to constructive TSP. Moreover, the reported heuristic runtimes exclude LLM generation, reflection, and other solver costs, leaving end-to-end efficiency unclear.

Questions for authors
  1. Why does PD-MCTS use mean subtree objective vectors rather than the non-dominated outcomes of each subtree? Could the maximal crowding-distance rule in Eq. (7) bias selection toward extreme solutions? How does this strategy compare with alternative Pareto-aware MCTS selection rules?

  2. What empirical evidence supports the assumption that productivity at creation predicts successful subsequent expansion? Can the authors report the conditional success rates and compare APC with random or fitness-based promotions under the same expansion budget?

  3. Given the small improvements over the strongest baselines in several settings, are these differences statistically significant?

  4. How much additional cost is introduced by the Actor–Reflector framework? Can the authors report overall search time and compare search performance under matched wall-clock budgets?

5 comments
AuthorsOpenReview ↗

Response (1/4)

Thank you for your time and effort in reviewing our work. Below, we justify the PD-MCTS selection design, report conditional success rates and matched controls for APC, add significance tests, extend the Pareto-front comparison to CVRP-ACO, and analyze end-to-end search cost.

W1 & Q1: Subtree returns and Pareto-aware allocation in PD-MCTS selection.

W1: The main concern is that the proposed search mechanisms lack sufficient justification. PD-MCTS uses mean subtree objective vectors, which may obscure promising Pareto trade-offs, while the maximal crowding-distance rule in Eq. (7) may favor extreme solutions. The Scalar-UCT ablation does not establish its advantage over alternative Pareto-aware selection strategies.

Q1: Why does PD-MCTS use mean subtree objective vectors rather than the non-dominated outcomes of each subtree? Could the maximal crowding-distance rule in Eq. (7) bias selection toward extreme solutions? How does this strategy compare with alternative Pareto-aware MCTS selection rules?

Thank you for these insightful questions. In short, PD-MCTS uses subtree means to judge how reliably a lineage produces good heuristics, and crowding distance to keep exploring lineages with different objective strengths. We address each point below.

1. Why use mean subtree vectors rather than non-dominated outcomes?

A subtree's non-dominated set records only the best trade-offs it has attained; once these are found, later dominated outcomes leave the set unchanged. It therefore cannot distinguish a branch that repeatedly produces strong candidates from one that reaches the same frontier through a few exceptional outcomes among many low-quality candidates. Mean backup retains this distinction: every newly evaluated descendant updates its ancestors' means, so branch allocation reflects the overall observed returns of a lineage rather than only its best attained outcomes.

This choice does not obscure Pareto trade-offs. First, averaging is performed within each objective, so the branch statistic remains a three-dimensional vector compared through Pareto dominance, consistent with MO-MCTS [1] and Pareto MCTS [2]. Second, the global Pareto archive is updated with each candidate's own objective vector, so a strong candidate is never discarded because its branch has a lower mean.

2. Does maximal crowding distance favor extreme solutions?

Eq. (7) does favor boundary branches, and this is by design. Heuristic lineages often excel in different objectives, such as solution quality, execution time, or worst-instance performance. Prioritizing boundary directions keeps these complementary lineages under exploration.

This preference does not amount to a bias toward extreme programs, for two reasons. First, Eq. (7) operates on Pareto-UCT vectors that combine locally ranked subtree means with count-based exploration. A boundary position therefore reflects a branch's current exploration-adjusted score rather than the extreme raw performance of a single program, and it is recomputed as evidence accumulates. Second, Eq. (7) only decides where to spend the next evaluation. The reported program is selected separately from the final Pareto set by normalized distance to the ideal point, which favors a balanced compromise.

3. How does PD-MCTS compare with other Pareto-aware MCTS rules?

  • Uniform Pareto-UCB selection [2] samples uniformly among non-dominated children, so a region containing kk of mm such children receives probability k/mk/m regardless of how similar they are. Eq. (7) instead directs evaluations toward distinct objective directions.
  • Hypervolume-based MO-MCTS [1] scores branches with a scalar criterion that depends on the archive and a reference point. PD-MCTS compares locally ranked vectors through Pareto dominance and requires no reference point.
AuthorsOpenReview ↗

Response (2/4)

4. What does the Scalar-UCT ablation establish?

The Scalar-UCT ablation keeps all other components unchanged and replaces Pareto-based selection with an equal-weight aggregation of the objective-wise ranks. Gap and Worst are minimized, and Time measures heuristic execution.

Table R1. Scalar-UCT ablation on constructive TSP (N=100N=100) and CVRP-ACO (N=50N=50).

Selection ruleConstructive TSP, N=100N=100: Gap (%)Time (ms)WorstCVRP-ACO, N=50N=50: Gap (%)Time (ms)Worst
PD-MCTS (Full)12.863410.1144.665.410.471
Scalar-UCT (Q,E,WQ,E,W)15.553310.49310.337.911.106

Replacing Pareto selection increases the average gap by 2.69 percentage points on TSP and 5.67 percentage points on CVRP, and also worsens worst-instance quality on both tasks. This supports the benefit of Pareto-based allocation over a fixed scalarization. This ablation isolates the contribution of Pareto-based selection itself, while Point 3 explains how Eq. (7) differs from other Pareto-aware rules in what it prioritizes.

References

[1] Weijia Wang and Michèle Sebag. Multi-objective Monte-Carlo Tree Search. In Proceedings of the Asian Conference on Machine Learning, PMLR 25:507–522, 2012. Paper.

[2] Weizhe Chen and Lantao Liu. Pareto Monte Carlo Tree Search for Multi-Objective Informative Planning. In Proceedings of Robotics: Science and Systems, 2019. Paper.


Q2: Evidence for APC and promotion controls. What empirical evidence supports the assumption that productivity at creation predicts successful subsequent expansion? Can the authors report the conditional success rates and compare APC with random or fitness-based promotions under the same expansion budget?

Thank you for this question. APC is motivated by the distinction between a heuristic’s current performance and what a further expansion of that heuristic is likely to yield. Fitness-based promotion selects which eligible nodes receive extra expansions based on their current objective values. APC uses productivity at creation as a signal for subsequent expansion and checks whether observed outcomes support acting on that signal.

1. Evidence for using creation productivity

Let YY indicate whether a node’s creation was productive, and let Y+Y^+ indicate whether its first expansion was productive. APC estimates ϑi=Pr⁡(Y+=1∣Y=i)\vartheta_i=\Pr(Y^+=1\mid Y=i) for i∈{0,1}i\in\{0,1\} from the first-expansion outcomes observed up to that point. These are exactly the conditional success rates of subsequent expansion given creation productivity. The score qtq_t is the posterior probability that ϑ1−ϑ0\vartheta_1-\vartheta_0 exceeds the required margin. The table summarizes certified nominations from five GPT-4o-mini runs per task.

Table R2. APC certified nominations and posterior estimates from five GPT-4o-mini runs per task.

ProblemCertified nominationsMean posterior estimates at nomination (ϑ1,ϑ0)(\vartheta_1,\vartheta_0)Mean qtq_t
Constructive TSP10848.52%, 19.50%0.8831
TSP-ACO7044.06%, 16.74%0.8651
CVRP-ACO12344.28%, 17.00%0.8702
Constructive KP2438.97%, 14.25%0.8446
MKP-ACO6141.47%, 16.32%0.8535
Online BPP6646.10%, 19.60%0.8642

The posterior means in Table R2 are smoothed estimates of these conditional success rates: across all six tasks, nodes with productive creation succeed in their first expansion about 2.4 to 2.7 times as often as other nodes (38.97%–48.52% versus 14.25%–19.60%). This explains the design of APC: productive creation identifies a candidate for promotion, while the gate determines whether the observed outcomes provide sufficient evidence to use that signal. The promotion decision thus depends on both the node’s creation label and evidence about what happens when nodes with that label are expanded.

AuthorsOpenReview ↗

Response (3/4)

2. Comparison under matched budget constraints

Random promotion provides a reference for allocating extra expansions without using creation productivity. Fitness-based promotion provides a reference for allocating them by attained performance. All three policies use the same total evaluation budget and the same rules limiting extra expansions. The table reports test gaps at N=50N=50; lower is better.

Table R3. APC versus random and fitness-based promotion under matched budget constraints.

ProblemAPCRandomFitness-based
Constructive TSP, N=50N=50: Gap (%)11.0513.5214.60
CVRP-ACO, N=50N=50: Gap (%)4.668.168.89

APC reduces the gap relative to random and fitness-based promotion by 2.47 and 3.55 percentage points on constructive TSP, and by 3.50 and 4.23 percentage points on CVRP-ACO. The comparison with random promotion shows that access to extra expansions alone does not account for the observed gains. The comparison with fitness-based promotion further supports using evidence about subsequent productivity to decide where to spend those expansions.


Q3: Statistical significance and joint performance gains. Given the small improvements over the strongest baselines in several settings, are these differences statistically significant?

Thank you for the question. We extended the solution-quality comparisons to six test settings and four baselines. All 24 reported pp-values are below 0.05.

1. Statistical significance

Table R4. pp-values for solution-quality comparisons between ParetoEvo and four baselines.

Test settingEoHReEvoHSEvoMCTS-AHD
Constructive TSP, N=50N=500.000040540.0000316390.0121740.013757
Constructive TSP, N=200N=2000.0000000113060.00997250.00894760.036327
KP, N=50N=500.00000311620.0000181770.000000660330.0000014339
KP, N=200N=2000.0000000632830.000000633750.000000239670.00000038086
TSP-ACO, N=100N=1000.00257110.000587830.000512160.015831
Offline BPP, N=1000N=10000.000726040.000583510.000460770.023266

ParetoEvo achieves the lowest or tied-lowest average gap among LLM-based methods on 13 of the 14 main constructive and ACO test sets. Across all 14 settings, no compared LLM baseline dominates ParetoEvo jointly in average solution quality, heuristic execution time, and worst-instance performance.

2. Joint performance gains

In settings such as TSP-ACO and Offline BPP, ParetoEvo further improves solution quality over strong baselines while substantially reducing heuristic execution time. Table R5 reports main-table means as MCTS-AHD → ParetoEvo; lower is better for all three metrics.

Table R5. Main-table means of MCTS-AHD and ParetoEvo on three settings (MCTS-AHD → ParetoEvo).

ProblemGap (%)Time (ms)Worst
CVRP-ACO, N=100N=1005.94 → 4.5821 → 6.517.672 → 17.056
Offline BPP, N=1000N=10000.26 → 0.001,560 → 17417.667 → 415
TSP-ACO, N=100N=1000.53 → 0.0034,100 → 2868.818 → 8.787

Across these three settings, ParetoEvo improves both average and worst-instance solution quality while achieving approximately 3.2×3.2\times to 119×119\times speedups in heuristic execution. The Pareto-front results also support the joint gains: on constructive TSP at N=50N=50 and 100100, final HV improves by 34.7% and 46.5%, while IGD decreases by 50.2% and 48.3%, respectively, relative to the strongest corresponding baseline among MEoH and MPaGE.


W2: Scope of the Pareto-front comparison. Pareto-front comparisons are limited to constructive TSP.

Thank you for this suggestion. We extended the three-objective Pareto-front comparison to CVRP-ACO using the same two multi-objective baselines, MEoH and MPaGE.

Table R6. Pareto-front quality on CVRP-ACO.

MethodHV ↑IGD ↓
MEoH0.9492840.142229
MPaGE1.0139000.111096
ParetoEvo1.1224450.091746

Compared with MPaGE, the strongest baseline on both metrics, ParetoEvo achieves 10.7% higher HV and 17.4% lower IGD. Together with the constructive TSP results, this comparison shows that ParetoEvo improves the trade-offs among average solution quality, heuristic execution time, and worst-instance performance in both constructive and ACO settings.

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

This paper proposes ParetoEvo, which uses LLMs to generate and revise heuristic functions within a predefined solver framework. It jointly optimizes average solution quality, heuristic-call time, and worst-instance quality. The method has three components: PD-MCTS keeps the source–offspring relations among heuristics. It takes the mean objective vector of the evaluated heuristics in each subtree as the branch return. APC uses Beta posteriors to assess whether productive creation predicts productive first expansion. It grants promising nodes one additional expansion (a promotion). Reflection-conditioned Actor and Reflector agents use evaluated transitions to update operator-specific textual guidance for mutation and crossover.

Critical strengths
  1. The formulation matches practical requirements well. Candidate evaluation includes average quality, execution cost, and worst-instance performance, which gives a more complete assessment than optimizing average quality alone.

  2. The experiments cover TSP, KP, CVRP, MKP, and BPP under three solver frameworks (step-by-step construction, ACO, and GLS) and multiple instance sizes. They include ablations on the objectives, scalarized branch selection, APC, and reflection.

Critical weaknesses
  1. The paper does not specify how the reported program is selected from the final Pareto set. Algorithm 1 returns the final non-dominated set, yet the main tables report a single Gap, Time, and Worst per method.

  2. The PD-MCTS traversal appears biased toward depth-first search. In Section 3.3, the traversal stops at the first node with no viable child and at least one remaining opportunity. A newly created child receives b0b_0 expansion opportunities, so it is viable. A node that has just been expanded therefore cannot be the traversal endpoint as long as this child remains viable. Whenever ancestor-level selection re-enters this branch, the next endpoint lies deeper.

  3. Some related references are missing: [1] C. Chen, et al. HiFo-Prompt: Prompting with hindsight and foresight for LLM-based automatic heuristic design. In International Conference on Learning Representations, 2026. [2] O. Gungordu et al. PathWise: Planning through world model for automated heuristic design via self-evolving LLMs. In International Conference on Machine Learning, 2026. [3] Y. Wu et al. RefineEvo: Planning-guided heuristic evolution with bidirectional experience. In International Conference on Machine Learning, 2026.

Questions for authors
  1. Do the three metrics in each run come from the same program? Is this program selected only on the search set and then fixed for testing? Does cross-size testing reuse the same program, or is a different front member selected for each test size?

  2. Could the authors report the distributions of subtree size and depth at the end of each independent run? Could you also report, at termination, statistics on remaining expansion opportunities and viable status?

5 comments
AuthorsOpenReview ↗

Response (1/3)

Thank you for your time and effort in reviewing our work. Below, we clarify the final program selection protocol, explain the traversal behavior with final-tree and expansion-opportunity statistics, and add the suggested references.

W1 & Q1: Final program selection, metric reporting, and cross-size testing.

W1: The paper does not specify how the reported program is selected from the final Pareto set. Algorithm 1 returns the final non-dominated set, yet the main tables report a single Gap, Time, and Worst per method.

Q1: Do the three metrics in each run come from the same program? Is this program selected only on the search set and then fixed for testing? Does cross-size testing reuse the same program, or is a different front member selected for each test size?

Thank you for raising these related points. We acknowledge that the selection step between the final Pareto set returned by Algorithm 1 and the single program reported in the result tables was not explained clearly enough. We clarify the selection and evaluation protocol below.

1. Select one balanced program using only the search set

For each run, we select one heuristic from the final Pareto set by normalizing its three objective values and choosing the candidate with the smallest distance to the ideal point. The ideal point represents the best value of each objective considered separately. This criterion seeks a compromise among average solution quality, execution time, and worst-instance performance. Normalization allows the three objectives to contribute on a comparable scale, while proximity to the ideal point favors their joint performance.

Objective normalization, calculation of the ideal point, and candidate selection all use only search-set evaluations. The test sets do not participate in this procedure.

2. Report all three metrics from the same fixed program

Within each run, Gap, Time, and Worst all come from the same selected program. Once selected using the search set, the program is fixed and evaluated on the held-out test sets. We do not select different Pareto-set members for different metrics. The main tables average these per-run test results across independent evolution runs.

3. Reuse the same program across all test sizes

Within each run, the same selected program is used for every test size. We do not select a different Pareto-set member for each size. The cross-size results therefore assess the generalization of the same fixed program to different instance sizes.

AuthorsOpenReview ↗

Response (2/3)

W2 & Q2: Traversal motivation and final-tree statistics.

W2: The PD-MCTS traversal appears biased toward depth-first search. In Section 3.3, the traversal stops at the first node with no viable child and at least one remaining opportunity. A newly created child receives b0b_0 expansion opportunities, so it is viable. A node that has just been expanded therefore cannot be the traversal endpoint as long as this child remains viable. Whenever ancestor-level selection re-enters this branch, the next endpoint lies deeper.

Q2: Could the authors report the distributions of subtree size and depth at the end of each independent run? Could you also report, at termination, statistics on remaining expansion opportunities and viable status?

Thank you for this careful analysis and for requesting these statistics. We clarify the motivation for the traversal rule, explain the resulting behavior, and report the per-run structural and budget statistics below.

1. Motivation and traversal behavior

Our motivation is to allocate evaluations among evolving heuristic lineages according to their potential for further improvement. PD-MCTS therefore assesses each branch using the evaluated heuristics throughout its subtree. Continuing through viable descendants enables successive revisions of a selected lineage and provides further evidence for this subtree-level assessment.

The reviewer correctly observes that a newly created viable child prevents its parent from being the ordinary traversal endpoint. This creates a preference for continued descent within the selected lineage. However, each ordinary traversal starts again from the root. Wherever multiple viable child subtrees exist, Pareto-UCT makes a new allocation decision using subtree returns and exploration bonuses. Continued refinement within one lineage therefore does not require subsequent iterations to revisit that same lineage.

Ordinary traversal can also terminate at internal nodes. When a child exhausts its opportunities on invalid or duplicate candidates, its parent becomes the endpoint if it retains an opportunity of its own. The rule thus supports continued refinement while allowing internal-node expansion, as the statistics below confirm.

2. Final-tree and expansion-opportunity statistics

The following tables provide per-run summaries at 1,000 FE using GPT-4o-mini across five problem types. Tree size counts heuristic nodes and excludes the virtual root. Depth is measured from the virtual root at depth zero, and mean depth includes all heuristic nodes. Branching nodes have at least two direct children. Ordinary internal terminations count ordinary traversal endpoints at nodes that already have a child.

Table R1. Final-tree structure statistics at 1,000 FE using GPT-4o-mini.

ProblemTree sizeMaximum / mean depthBranching nodesOrdinary internal terminations
Online BPP771129 / 45.03315
CVRP-ACO631114 / 33.001426
MKP-ACO75795 / 31.88612
TSP-ACO757100 / 33.90738
Constructive TSP817121 / 32.43315

For the budget statistics, a node has remaining own opportunities when its ordinary expansion allowance is positive. A node is viable when either it or a descendant retains an opportunity; consequently, exhausting its own allowance does not necessarily make a node non-viable.

Table R2. Expansion-opportunity and viability statistics at termination.

ProblemRemaining ordinary opportunitiesNodes with own opportunities remaining / exhaustedViable nodesNon-viable nodes
Online BPP3,608766 / 5767 (99.48%)4
CVRP-ACO2,809608 / 23616 (97.62%)15
MKP-ACO3,550748 / 9751 (99.21%)6
TSP-ACO3,575742 / 15743 (98.15%)14
Constructive TSP3,888812 / 5813 (99.51%)4

These records show deep, sparsely branching trees, together with observed ordinary internal terminations. The remaining local opportunities are consistent with a globally budgeted search: b0b_0 specifies an allowance for future attempts at each node, rather than evaluations that must all be completed. Search stops at the global FE limit without requiring every local allowance to be exhausted. In this sense, b0b_0 acts as a per-node cap that prevents any single heuristic from absorbing a disproportionate share of the budget, similar to the expansion limit in progressive widening, rather than a quota that must be used up. Remaining local opportunities should therefore not be interpreted as unused evaluations from the global budget.

AuthorsOpenReview ↗

Response (3/3)

3. Practical implications of the observed behavior

A depth preference within selected lineages does not establish a design weakness. The relevant practical question is whether the resulting allocation discovers effective heuristics within the prescribed evaluation budget.

The Scalar-UCT ablation retains the stopping rule and evaluation budget while replacing Pareto-based branch selection. This increases the average gap from 12.86% to 15.55% on constructive TSP at N=100N=100, and from 4.66% to 10.33% on CVRP-ACO at N=50N=50. Because this ablation keeps the traversal rule, it produces the same kind of deep, lineage-focused search. The gains therefore show that, under this tree structure, the choice of which lineage to refine matters substantially, and Pareto-based allocation makes this choice effectively.

The intended behavior is therefore successive refinement within selected lineages, combined with evidence-guided allocation across competing subtrees. The recorded internal-node expansions and the performance gains above confirm that this behavior supports effective search.


W3: Related-work references. Some related references are missing: [1] C. Chen, et al. HiFo-Prompt: Prompting with hindsight and foresight for LLM-based automatic heuristic design. In International Conference on Learning Representations, 2026. [2] O. Gungordu et al. PathWise: Planning through world model for automated heuristic design via self-evolving LLMs. In International Conference on Machine Learning, 2026. [3] Y. Wu et al. RefineEvo: Planning-guided heuristic evolution with bidirectional experience. In International Conference on Machine Learning, 2026.

Thank you for pointing out these relevant works. We will add citations to HiFo-Prompt, PathWise, and RefineEvo in the revised manuscript.


We sincerely thank the reviewer for your careful evaluation and constructive feedback. Your comments have helped us clarify important aspects of our methodology and strengthen the empirical evidence through additional experiments and analyses.

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

The paper proposes ParetoEvo for LLM-based automatic heuristic design. It jointly optimizes solution quality, runtime, and worst-instance performance using Pareto-guided MCTS, adaptive expansion, and reflection-based LLM agents. The experiments show that the proposed method improves average solution quality and Pareto-front quality. It also improves runtime and worst-instance performance on some tasks.

Critical strengths
  1. The paper introduces a useful multi-objective formulation of LLM-based heuristic design. It explicitly considers solution quality, runtime, and worst-instance performance.

  2. The empirical evaluation is broad. The experiments cover multiple optimization problems, solver frameworks, and base models.

Critical weaknesses
  1. The specified PD-MCTS traversal appears to extend most nodes as chains, which makes ordinary branching. The expansion budget becomes ineffective. The central search mechanism does not operate as claimed.
  2. The empirical study is insufficient. The improvements over baselines are small. The reported numbers of runs are inconsistent. It is difficult to judge whether the proposed method is reliable.
Questions for authors
  1. With the claimed viability rule, the ordinary PD-MCTS traversal seems not to terminate at an internal node. Please clarify the expansion rule and report tree depth and branching statistics.
  2. Which heuristic from the final Pareto set is reported in the result tables? Is it selected using only the search set?
  3. How do the five-run main results relate to the seven runs in Table 9? Please report variance against the baselines.
  4. Does APC outperform ungated expansion of productive nodes and random extra expansion under the same condition (e.g., budget and expansion cap)?
  5. Please provide the code and data for review.
5 comments
AuthorsOpenReview ↗

Response (1/4)

Thank you for your time and effort in reviewing our work. Below, we clarify the expansion rule with tree statistics, clarify the run counts, compare APC with matched controls, and provide the code and data.

W1 & Q1: Expansion rule and tree structure.

W1: The specified PD-MCTS traversal appears to extend most nodes as chains, which makes ordinary branching. The expansion budget becomes ineffective. The central search mechanism does not operate as claimed.

Q1: With the claimed viability rule, the ordinary PD-MCTS traversal seems not to terminate at an internal node. Please clarify the expansion rule and report tree depth and branching statistics.

Thank you for raising these related concerns. We acknowledge that the main text did not state clearly enough that invalid or duplicate candidates consume an expansion opportunity without being inserted into the tree. We clarify the expansion rule and provide tree statistics below.

1. Expansion rule and termination at internal nodes

The budget b0b_0 counts the expansion opportunities assigned to a new node. Each attempt consumes one opportunity. Only a valid, nonduplicate candidate is inserted as a child and receives its own budget. Thus, the budget limits attempts rather than prescribing the number of children a node must produce.

Here, tt denotes the search iteration, pp the current traversal node, C(p)\mathcal C(p) its children, and Ct+(p)\mathcal C_t^+(p) its viable children. A child is viable if it or a descendant retains an expansion opportunity. Ordinary traversal descends while Ct+(p)≠∅\mathcal C_t^+(p)\neq\varnothing. It terminates at pp when Ct+(p)=∅\mathcal C_t^+(p)=\varnothing and pp retains an opportunity of its own. Consequently, having children does not prevent termination at an internal node.

For example, with b0=6b_0=6, a node vv retains five opportunities after creating its sole child uu. If uu exhausts its six opportunities on invalid or duplicate candidates without producing descendants, then C(v)={u}\mathcal C(v)=\{u\} but Ct+(v)=∅\mathcal C_t^+(v)=\varnothing. Ordinary traversal can therefore terminate at vv and attempt to create another child. This mechanism does not require APC.

2. Tree statistics and implications for the search mechanism

The table reports tree statistics at 1,000 FE using GPT-4o-mini of five different problems. Depth is measured from the virtual root at depth zero, and mean depth measures all non-root nodes. Branching nodes are non-root nodes with at least two direct children. Ordinary internal terminations count ordinary PD-MCTS traversals stopping at a node that already has a child, irrespective of whether the subsequent attempt inserts another child.

Table R1. Tree statistics at 1,000 FE using GPT-4o-mini.

ProblemMaximum / mean depthBranching nodesOrdinary internal terminations
Online BPP129 / 45.03315
CVRP-ACO114 / 33.001426
MKP-ACO95 / 31.88612
TSP-ACO100 / 33.90738
Constructive TSP121 / 32.43315

We agree that these trees are deep and sparsely branching. This structure reflects the intended search behavior rather than a failure of the mechanism:

  • Deep chains reflect successive refinement. Each LLM revision builds on its parent, so continued descent within a promising lineage is the intended use of the evaluation budget.
  • Branching is adaptive. A node becomes an expansion source again when its descendants exhaust their opportunities on invalid or duplicate candidates, so new branches arise where refinement of the current lineage stalls. The ordinary internal terminations recorded on every problem confirm that this mechanism is active.
  • The MCTS component decides which lineage to continue, rather than how wide the tree becomes. Every evaluation starts a new traversal from the root, and Pareto-UCT makes an allocation decision at each node with multiple viable subtrees along the path.

The search mechanism therefore operates as designed: deep refinement within lineages, with branching where refinement stalls.

AuthorsOpenReview ↗

Response (2/4)

W2 & Q2–Q3: Empirical evidence, candidate selection, and run counts.

W2: The empirical study is insufficient. The improvements over baselines are small. The reported numbers of runs are inconsistent. It is difficult to judge whether the proposed method is reliable.

Q2: Which heuristic from the final Pareto set is reported in the result tables? Is it selected using only the search set?

Q3: How do the five-run main results relate to the seven runs in Table 9? Please report variance against the baselines.

Thank you for raising these related concerns. We acknowledge that the final candidate selection procedure and the relationship between the two sets of runs were not explained clearly enough. We summarize the empirical evidence and clarify the selection and evaluation protocols below.

1. Empirical coverage and component validation

Our experiments cover six problem classes across constructive, ACO, and GLS settings, compare against hand-designed, neural, single-objective LLM-based (EoH, ReEvo, HSEvo, MCTS-AHD), and multi-objective LLM-based (MEoH, MPaGE) methods, and evaluate quality, execution time, worst-instance performance, cross-size generalization, TSPLIB, and a second LLM (GPT-5-NANO). Component ablations and hyperparameter analyses further validate each proposed component.

2. Improvements across the three objectives

We would like to clarify that the reported benefits extend beyond differences in average gap. They include substantial reductions in heuristic execution time with maintained or improved average and worst-instance quality, together with improvements in Pareto-front quality. These complementary benefits provide a fuller assessment of the method’s contribution.

ParetoEvo achieves the lowest or tied-lowest LLM-based average gap on 13 of the 14 main constructive and ACO test sets. Across all 14 settings, no compared LLM baseline dominates ParetoEvo jointly in average quality, execution time, and worst-instance performance.

The following original main-table means are shown as MCTS-AHD [1] → ParetoEvo. Time measures heuristic execution. Lower is better for all three metrics in these comparisons.

Table R2. Main-table means of MCTS-AHD and ParetoEvo on three settings (MCTS-AHD → ParetoEvo).

ProblemGap (%)Time (ms)Worst
CVRP-ACO, N=100N=1005.94 → 4.5821 → 6.517.672 → 17.056
Offline BPP, N=1000N=10000.26 → 0.001,560 → 17417.667 → 415
TSP-ACO, N=100N=1000.53 → 0.0034,100 → 2868.818 → 8.787

These comparisons show approximately 3.2×3.2\times to 119×119\times speedups in heuristic execution while improving average and worst-instance solution quality.

Against the strongest corresponding baseline among MEoH and MPaGE, final HV improves by 34.7% and 46.5%, while IGD decreases by 50.2% and 48.3%, on constructive TSP at N=50N=50 and 100100, respectively. These results further support the benefits of ParetoEvo in optimizing the joint objectives.

AuthorsOpenReview ↗

Response (3/4)

3. Final candidate selection and test isolation

For each run, we select one heuristic from the final Pareto set by normalizing its three objective values and choosing the candidate with the smallest distance to the ideal point. The ideal point represents the best value of each objective considered separately. This criterion seeks a compromise among average solution quality, execution time, and worst-instance performance. Normalization allows the three objectives to contribute on a comparable scale, while proximity to the ideal point favors their joint performance.

The selected heuristic is determined using only the search set. The entire selection procedure, including objective normalization and calculation of the ideal point, uses only search-set evaluations. The test sets do not participate in candidate selection. Once the heuristic is selected, it is fixed and evaluated on the held-out test sets. The result tables therefore report the test performance of the heuristic selected using the search set, with the three metrics corresponding to the same selected heuristic in each run. The same program is also reused across all test sizes.

4. Relationship between the five-run main results and Table 9

The main tables report averages over five independent runs per method and task. Table 9 presents a separate statistical comparison between ParetoEvo and EoH on constructive TSP at N=100N=100 and ACO-based offline BPP at N=500N=500, using seven additional independent runs per method and task. These seven runs are separate from the five used in the main tables. The means, standard deviations, and p-values in Table 9 are computed from its own seven-run samples. This experiment supplements the main performance comparisons by assessing between-run variability and statistical evidence for solution-quality differences on these two tasks.

Using different numbers of runs for the main benchmarks and supplementary statistical experiments has clear precedents in LLM-based AHD. MCTS-AHD [1] uses three independent runs in its main experiments and five or ten runs in its supplementary significance analysis, depending on the task (Section 4 and Table 9). PathWise [2] likewise reports three-run main results and six-run significance analyses (Section 4 and Tables 12–13). These examples support using different replication counts for experiments with different reporting purposes.

Accordingly, five and seven are the intended sample sizes of two distinct experiments. They do not represent conflicting run counts for the same experiment. Table 9 provides supplementary statistical evidence for its specified comparisons, with its p-values derived from the seven-run samples.

5. Run-to-run variability against the baselines

We will report the mean and sample standard deviation of Gap (%) for ParetoEvo and all four main baselines on all 14 main test sets in the revised manuscript.

References

[1] Zhi Zheng, Zhuoliang Xie, Zhenkun Wang, and Bryan Hooi. Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design. In Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:78338–78373, 2025. Paper.

[2] Oguzhan Gungordu, Siheng Xiong, and Faramarz Fekri. PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs. In Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:37779–37816, 2026. Paper.

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

Related papers

Discussion (0)

Sign in to comment.