acceptodds
Withdrawn from ICLR 2027

Dual-Process Tree Search with Heuristic Merit and Evolutionary Credit for Automatic Heuristic Design

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

Abstract

Large language model (LLM)-based automatic heuristic design (AHD) has recently emerged as a promising paradigm for automating heuristic discovery with reduced reliance on manual engineering. Tree-structured search has demonstrated advantages in organizing and exploring LLM-generated heuristics. However, parent-path credit propagation during search is structurally misaligned with exemplar-guided evolution, causing improvements induced by auxiliary exemplars to be attributed predominantly to the parent lineage. Meanwhile, fitness-based exemplar selection conflates standalone heuristic merit with evolutionary utility, potentially overlooking heuristics with modest standalone performance but stronger capacity to guide subsequent refinement. Moreover, evaluating heuristics on a finite set of instances yields potentially biased fitness estimates, steering the search toward overfitted local optima. To address these limitations, we propose Dual-Process Tree Search (DPTS), a framework that disentangles evolutionary credit from heuristic merit within a shared search tree. DPTS maintains distinct estimates of parent lineage merit and exemplar-induced evolutionary credit, selects exemplars according to downstream evolutionary utility, and aggregates evidence across structurally related nodes to improve the robustness of frontier evaluation under finite-sample noise. Experiments on representative combinatorial optimization benchmarks demonstrate that DPTS consistently outperforms state-of-the-art AHD baselines across constructive and ACO-based settings.

Primary area:
optimization
Keywords:
Automatic heuristic design, Large language models, Tree search, Evolutionary credit assignment, Combinatorial optimization.

Reviews

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

This paper proposes Dual-Process Tree Search (DPTS) for LLM-based AHD, building on the tree-structured search of MCTS-AHD. Each node of the shared heuristic evolution tree maintains three statistics: empirical fitness gvg_v, heuristic merit QvQ_v, and evolutionary credit BvB_v. For the exploitation action, exemplars are selected from the elite set by a UCB rule on evolutionary credit. The credit is the binary parent-relative signal propagated along the exemplar trajectory. Parents are selected from a randomly sampled subset of legal leaf nodes in the open set by maximizing the topology-aggregated merit, which is a weighted average of the leaf's own fitness and its ancestors' merit, with truncated linear weights. Each iteration adds exploitation offspring, attached to their parents, and one exploration offspring, attached to the root to initiate a new algorithm lineage. It further introduces DPTS-K, which extracts heuristic experts from root-level branches. Experiments on TSP, KP, BPP, CVRP, MKP, and DPP, under both step-by-step construction and ACO frameworks, report improvements over MCTS-AHD and other LLM-based AHD baselines.

Critical strengths

The motivation is genuine and under-explored. In exemplar-guided crossover, the auxiliary exemplar shapes the offspring, yet existing tree-based AHD methods propagate offspring gains only along the parent path and thus credit only the parent lineage. How good a heuristic is on its own and how useful it is as a reference are indeed different questions.

Heuristic merit and evolutionary credit are inexpensive to maintain. They require neither additional heuristic evaluations nor additional LLM calls, and they could be ported to other AHD frameworks. The benchmark coverage is broad, and the paper includes component ablations, a hyperparameter sensitivity analysis, and a train/test consistency check.

Critical weaknesses

Mismatch between motivation and method. The paper argues that fitness-based exemplar selection may overlook heuristics with modest standalone performance but a stronger capacity to guide subsequent refinement. However, the candidate set for exemplars is still the fitness-ranked elite set. DPTS merely re-ranks exemplars by evolutionary credit, so heuristics with modest fitness are excluded by construction.

Upper-confidence bonus in DPTS-K. Eq. 17 adds an upper-confidence bonus when extracting the final heuristic experts. This may favor under-explored branches, the opposite of what selection for reliability calls for. Since a new root child is added at every iteration, single-node branches that were never expanded may rank above well-refined lineages. Notably, expert h2 in Appendix I reduces to the Greedy baseline.

Some notation errors:

  • Throughout the paper, textual citations (\citet) are used where parenthetical citations (\citep) are intended.
  • Eq. 8 uses QvQ_v for parent selection, whereas Fig. 3, Algorithm 3, and §4.3 use Qv~\tilde{Q_v}.
  • Fig. 3 (panel D.2) mixes indices (WiBW_i^B and NvBN_v^B).
Questions for authors
  1. About Theorem 1. For two sibling frontier nodes, the shared ancestor terms in Eq. 14 cancel. The ranking probability is therefore unchanged, which contradicts the strict inequality in Eq. 16. Could the author provide an explanation for this?

  2. How often does the credit-selected exemplar differ from the highest-fitness member of elite set, and does evolutionary credit predict later offspring improvement?

  3. How many root children does the final tree have, how many remain single-node, and what are the visit counts of the branches selected by DPTS-K?

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

This paper studies credit assignment for auxiliary exemplars, exemplar selection, and finite-sample evaluation noise in tree-structured LLM-based automatic heuristic design. Building on MCTS-AHD, the authors propose Dual-Process Tree Search, which adds UCB-based evolutionary credit or exemplar selection and path-based, topology-aware merit aggregation for leaf evaluation, as well as a multi-heuristic portfolio variant. The method is evaluated on constructive and ACO-based benchmarks, as well as the Decap Placement Problem, under a 1,000-evaluation budget.

Critical strengths

1.The paper is well written and easy to follow. The research motivation and the overall search procedure are explained clearly.

2.The authors provide a thoughtful analysis of tree search for heuristic design. They clearly explain why standard credit assignment has trouble when combining ideas from multiple parent heuristics.

Critical weaknesses

1.The tested problems are too few to clearly demonstrate the advantage of the proposed method. In addition, all experiments are run only three times without reporting standard deviations, making it hard to tell whether the improvements come from the method or simply from randomness.

2.The novelty of this work is somewhat limited. The whole framework appears to be a modification of MCTS-AHD, and the issues it targets, such as credit assignment and noisy evaluations, are very common in heuristic search. Furthermore, the authors’ own ablation study shows that removing evolutionary credit changes the gap by only about 0.2%, meaning the core proposed mechanism provides limited practical benefit.

I suggest that the authors address these weaknesses, and I will actively participate in the review process.

Questions for authors

1.All experiments are based on only three runs without any standard deviations. Could the authors report mean values and the standard deviations or run more trials to prove that the small performance gains are statistically meaningful rather than random noise?

2.In Table 6, removing evolutionary credit only changes the gap by about 0.2%. Could the authors explain why this credit mechanism is truly necessary, and whether it brings any noticeable difference in practice?

3.DPTS-K evaluates five heuristics on each test instance and reports the best result. How does DPTS-K compare with other baselines if they also select their top five heuristics and test them under the exact same setup?

4.The paper mentions finding exemplars that are not necessarily top performers on their own. However, the algorithm only picks exemplars from the top ten elite set. How can any heuristic outside this top ten list ever get a chance to be chosen as an exemplar?

5.The figures in this paper is too-big for human to read. Please consider shrink them.

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

This paper proposes Dual-Process Tree Search (DPTS), an LLM-based automatic heuristic design framework that addresses three key limitations of existing tree-search methods: inaccurate attribution of evolutionary credit, overreliance on heuristic fitness for exemplar selection, and search overfitting caused by finite-sample evaluation. DPTS introduces two coordinated search processes within a shared tree to separately estimate parent-lineage merit and exemplar-induced evolutionary contributions. It further selects exemplars based on their downstream evolutionary utility rather than standalone fitness. Additionally, a topology-aware aggregation mechanism is developed to improve the robustness of fitness estimation and the reliability of search decisions under finite-sample noise. Experimental results demonstrate that DPTS outperforms existing LLM-based AHD methods across various combinatorial optimization benchmarks.

Critical strengths
  1. Well-motivated problem formulation. The paper identifies important limitations of existing tree-based AHD methods, particularly the mismatch between parent-path credit propagation and exemplar-guided evolution. The distinction between standalone heuristic merit and evolutionary utility is meaningful and provides a clear motivation for the proposed approach.
  2. Novel dual-process search framework. DPTS introduces a dual-process formulation that separately models parent-lineage merit and exemplar-induced evolutionary contributions within a shared search tree. This provides a more principled way to assign evolutionary credit and guide the search process.
  3. Well-written and clearly organized. The paper is well-written and easy to follow.
Critical weaknesses
  1. The experimental results demonstrate the effectiveness of the proposed method. However, the paper lacks deeper, more insightful analysis explaining why the proposed method works.
  2. DPTS introduces additional search and feedback mechanisms, which may increase computational overhead compared with conventional tree-based AHD methods. A more comprehensive analysis of computational efficiency, including LLM calls, runtime, and performance under matched computational budgets, would help clarify the practical benefits of the proposed framework.
Questions for authors

N/A

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

This paper proposes Dual-Process Tree Search, or DPTS, to improve large language model-based automatic heuristic design. Existing tree-search methods propagate rewards along parent paths and select exemplars based on their standalone performance, making it difficult to accurately measure how auxiliary exemplars contribute to offspring improvement. Furthermore, evaluation on finite instance sets may lead to overfitting. DPTS separates heuristic merit from evolutionary credit within a shared search tree and propagates them through distinct feedback paths. It selects exemplars according to their demonstrated ability to support downstream improvements. In addition, a topology-aware aggregation mechanism combines evaluation evidence from structurally related nodes to reduce estimation variance. Experiments show that DPTS outperforms existing automatic heuristic design methods on problems including TSP, knapsack, bin packing, and vehicle routing under both constructive and ant colony optimization settings, demonstrating improved robustness and generalization.

Critical strengths

The paper identifies an important structural mismatch in multi-source heuristic generation: offspring are jointly conditioned on a selected parent and an auxiliary exemplar, whereas conventional tree-based credit propagation attributes their performance primarily to the parent lineage. To address this issue, the paper introduces a dual-process tree-search framework that maintains separate statistics for parent-lineage heuristic merit and exemplar-induced evolutionary credit. In particular, distinguishing a heuristic’s standalone performance from its downstream utility as an auxiliary exemplar constitutes a clear and identifiable contribution beyond MCTS-AHD. The proposed framework is fully specified and empirically evaluated across multiple combinatorial optimization tasks and both constructive and ACO-based settings. That said, the evolutionary-credit mechanism itself is largely instantiated through established components, including a binary parent-relative improvement signal, an empirical success-rate estimate, UCB-style exemplar selection, and path-based backpropagation. The topology-aware merit aggregation mechanism adds a further methodological component, although it is also constructed from weighted aggregation of merit estimates propagated along the tree topology.

Critical weaknesses

1. The theoretical analysis of topology-based aggregation relies on questionable assumptions

Theorem 1 assumes that the estimates from different nodes along the same path are independent. However, these nodes often share the same descendant evaluation results. When a new node is evaluated, its fitness is propagated to both the node and its ancestors. Therefore, the estimates along the path are likely to be strongly correlated.

Because the proof ignores these correlations, it does not fully support the claim that topology-based aggregation always reduces variance. If the estimates are highly correlated, averaging them may provide only a small benefit.

The analysis also assumes that aggregation preserves the correct ranking of frontier nodes. This may not hold in practice because high-quality and low-quality descendants can appear under the same ancestor. An ancestor's average score may therefore lower the estimated quality of an excellent leaf node.

The authors should either revise the theoretical claim or provide an analysis that considers both correlation and bias. Empirical measurements of the correlations among ancestor estimates would also strengthen the argument.

2. The evolutionary credit does not reliably measure an exemplar's contribution

The paper assigns credit to an exemplar whenever an offspring performs better than its parent. However, this improvement may be caused by several factors other than the exemplar itself, including:

  • the quality and improvability of the parent;
  • the interaction between the parent and the exemplar;
  • randomness in LLM sampling;
  • prompt sensitivity;
  • noise from code execution and evaluation.

For example, an exemplar may receive credit more easily when paired with a weak parent than when paired with a strong parent. As a result, the final credit score may reflect the assigned parents rather than the exemplar's actual usefulness.

The paper also models the outcome as depending on the parent-exemplar pair, but later represents each exemplar using a single global score. This simplification is not fully consistent with the interaction described in the model.

The authors should control for parent quality and evaluate the same exemplar across multiple matched parents and repeated samples. They should also report whether the exemplar rankings remain stable after accounting for parent difficulty and sampling randomness.

3. The code provided in the appendix contains substantive issues that undermine experimental credibility and reproducibility

The paper claims that the appendix provides executable and representative heuristics. However, several code fragments contain unused variables, degenerate logic, or potential runtime errors.

Specifically:

  1. The purported return-aware nearest-neighbor heuristic degenerates into an ordinary nearest-neighbor heuristic.
    In h2h_2, return_distance is defined as the distance from the current node to the destination and remains constant across all candidate nodes. Therefore, minimizing current_distance + return_distance is exactly equivalent to minimizing current_distance alone. The expression does not capture the cost of returning from each candidate node to the starting point or destination.

  2. The MST term appears to be identically zero.
    In the TSP example, the nearest-neighbor rollout for each candidate repeatedly removes nodes from remaining_nodes until the set becomes empty. The code then calls calculate_mst_cost(remaining_nodes, ...). As a result, the MST cost is computed on an empty set and returns 0. This behavior is inconsistent with the description of an “MST-enhanced residual estimation.”

  3. The clustering result is not used by the scoring function.
    The code computes clusters = cluster_unvisited_nodes(...), but clusters is not subsequently used in candidate scoring. Therefore, the claimed cluster-aware or graph-structured information does not actually influence the decision through this variable.

  4. The random tie-breaking procedure in h4h_4 may produce all-zero weights.
    For every candidate whose score equals min_score, the corresponding weight is computed as min_score - combined_scores[i]. All tied minimum-score candidates therefore receive a weight of zero. Calling random.choices with all weights equal to zero may raise an exception.

These are not merely presentation-level defects. The paper uses the generated code examples and evolutionary trajectories to support the claim that the LLM progressively develops more sophisticated and structured algorithms. If the experimental implementation is identical to the appendix code, some of the reported interpretations may not be valid. If the experimental implementation differs from the appendix code, the current manuscript does not provide sufficient information to reproduce the results.

Questions for authors
  1. How does the theoretical analysis account for correlations and potential bias among ancestor and descendant estimates?

  2. How does the credit mechanism isolate an exemplar’s contribution from parent quality, parent-exemplar interactions, and sampling randomness?

  3. Is the appendix code identical to the experimental implementation, and how do the identified code issues affect the reported results and conclusions?

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

Related papers

Discussion (0)

Sign in to comment.