- 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 , heuristic merit , and evolutionary credit . 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 for parent selection, whereas Fig. 3, Algorithm 3, and §4.3 use .
- Fig. 3 (panel D.2) mixes indices ( and ).
Questions for authors
-
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?
-
How often does the credit-selected exemplar differ from the highest-fitness member of elite set, and does evolutionary credit predict later offspring improvement?
-
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?