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

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.