- 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
-
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?
-
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?
-
Given the small improvements over the strongest baselines in several settings, are these differences statistically significant?
-
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
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 () and CVRP-ACO ().
| Selection rule | Constructive TSP, : Gap (%) | Time (ms) | Worst | CVRP-ACO, : Gap (%) | Time (ms) | Worst |
|---|---|---|---|---|---|---|
| PD-MCTS (Full) | 12.86 | 34 | 10.114 | 4.66 | 5.4 | 10.471 |
| Scalar-UCT () | 15.55 | 33 | 10.493 | 10.33 | 7.9 | 11.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 indicate whether a node’s creation was productive, and let indicate whether its first expansion was productive. APC estimates for 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 is the posterior probability that 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.
| Problem | Certified nominations | Mean posterior estimates at nomination | Mean |
|---|---|---|---|
| Constructive TSP | 108 | 48.52%, 19.50% | 0.8831 |
| TSP-ACO | 70 | 44.06%, 16.74% | 0.8651 |
| CVRP-ACO | 123 | 44.28%, 17.00% | 0.8702 |
| Constructive KP | 24 | 38.97%, 14.25% | 0.8446 |
| MKP-ACO | 61 | 41.47%, 16.32% | 0.8535 |
| Online BPP | 66 | 46.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.
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 ; lower is better.
Table R3. APC versus random and fitness-based promotion under matched budget constraints.
| Problem | APC | Random | Fitness-based |
|---|---|---|---|
| Constructive TSP, : Gap (%) | 11.05 | 13.52 | 14.60 |
| CVRP-ACO, : Gap (%) | 4.66 | 8.16 | 8.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 -values are below 0.05.
1. Statistical significance
Table R4. -values for solution-quality comparisons between ParetoEvo and four baselines.
| Test setting | EoH | ReEvo | HSEvo | MCTS-AHD |
|---|---|---|---|---|
| Constructive TSP, | 0.00004054 | 0.000031639 | 0.012174 | 0.013757 |
| Constructive TSP, | 0.000000011306 | 0.0099725 | 0.0089476 | 0.036327 |
| KP, | 0.0000031162 | 0.000018177 | 0.00000066033 | 0.0000014339 |
| KP, | 0.000000063283 | 0.00000063375 | 0.00000023967 | 0.00000038086 |
| TSP-ACO, | 0.0025711 | 0.00058783 | 0.00051216 | 0.015831 |
| Offline BPP, | 0.00072604 | 0.00058351 | 0.00046077 | 0.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).
| Problem | Gap (%) | Time (ms) | Worst |
|---|---|---|---|
| CVRP-ACO, | 5.94 → 4.58 | 21 → 6.5 | 17.672 → 17.056 |
| Offline BPP, | 0.26 → 0.00 | 1,560 → 17 | 417.667 → 415 |
| TSP-ACO, | 0.53 → 0.00 | 34,100 → 286 | 8.818 → 8.787 |
Across these three settings, ParetoEvo improves both average and worst-instance solution quality while achieving approximately to speedups in heuristic execution. The Pareto-front results also support the joint gains: on constructive TSP at and , 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.
| Method | HV ↑ | IGD ↓ |
|---|---|---|
| MEoH | 0.949284 | 0.142229 |
| MPaGE | 1.013900 | 0.111096 |
| ParetoEvo | 1.122445 | 0.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.
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.
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?