Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Authors: Zhi Zheng
Zhuoliang Xie
Zhenkun Wang
Bryan Hooi
Venue: ICML 2025 poster (2025)
Keywords: Automatic Heuristic Design
Combinatorial Optimization
Large Language Model
Neural Combinatorial Optimization
Monte Carlo Tree Search
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: Handcrafting heuristics for solving complex optimization tasks (e.g., route planning and task allocation) is a common practice but requires extensive domain knowledge. Recently, Large Language Model (LLM)-based automatic heuristic design (AHD) methods have shown promise in generating high-quality heuristics without manual interventions. Existing LLM-based AHD methods employ a population to maintain a fixed number of top-performing LLM-generated heuristics and introduce evolutionary computation (EC) to iteratively enhance the population. However, these population-based procedures cannot fully develop the potential of each heuristic and are prone to converge into local optima. To more comprehensively explore the space of heuristics, this paper proposes to use Monte Carlo Tree Search (MCTS) for LLM-based heuristic evolution. The proposed MCTS-AHD method organizes all LLM-generated heuristics in a tree structure and can better develop the potential of temporarily underperforming heuristics. In experiments, MCTS-AHD delivers significantly higher-quality heuristics on various complex tasks. Our code is available.

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Zhi Zheng' Zhuoliang Xie
Zhenkun Wang²
Bryan Hooi
Abstract
60
Hoans
Handerafting heuristics for solving complex op- timization tasks (e.g., route planning and task al- location) is common practice but requires ex- tensive domain knowledge. Recently, Large Lan- guage Model (LLM)-based automatic heuristic design (AHD) methods have shown promise in generating high-quality heuristics without manual interventions. Existing LLM-basee AHD meth- ods employ a population maintain fixed num- ber of top-performing LLM-generated heuristics and introduce evolutionary computation (EC) it- eratively enhance the population. However, these population-hase -hased procedures cannot fully develop the potential of each heuristic and are prone to converge into local optima. To more comprehen- sively explore the space heuristics, this paper proposes to use Monte Carlo Tree Search (MCTS) for LLM-based heuristic evolution. The pro- posed MCTS-AHD method organizes all LLM- generated heuristics in tree structure and can bet- ter develop the potential of temporarily underper- forming heuristics. experiments, MCTS-AHD delivers significantly higher-quality heuristics on various complex tasks. Our code is available
Performance
Performance
Popubriim upp Uppiace
Feature of heuristic funetions
Feature beuristic functions
(a) Populations in LLM-based AHD
MUTS
MCT
Performance
Performance
Denalions of Tro Search
Feature heuristic funetions
Feature of heuristic functions
(b) MCTS for higher-quality LLM-based AHD (Ours)
Figure I. The generally adopted population (a) in existing LLM- based AHD methods (Liu et al., 2024b; Ye et al., 2024a) directly discards low-performance heuristics (under the red dashed line in (a)), thus falling into local optima. MCTS provides chances to de- velop low-performance heuristics, can more comprehcnsively explore the space of heuristic functions with different features.
1. Introduction
et al., 2011), job scheduling (Rajendran, 1993), and robotics (Tan al., 2021). However, manually crafted heuristics of- contain intricate workflows and parameter settings, mak- ing their design labor-intensive and reliant on task-specific expert knowledge. To achieve casier heuristic design across various tasks, the concept of Automatic Heuristic Design (AHD) (Burke et al., 2013) (also known as Heyeer-Hurisstics (Ye et al., 2024a)) has attracted extensive attention. It seeks the best-performing heuristic algorithm among valid options. Genetic Programming (GP) (Langdon & Poli, 2013) com- monly employed for AHD, with GP-based AHD methods introducing a series of mutation operators to gradually refine heuristic algorithms (Duflo et al., 2019). Nevertheless, the effectiveness of GP-based methods still relies on human def- initions of permissible operators (Liu et al., 2024b), which poses additional implementation difficulties.
Manually designed heuristics are promising in addressing complex optimization tasks (e.g., combinatorial optimiza- tion (CO) problems) (Desale et al., 2015). They are widely used real-world applications, such as traffic control (He
School of Computing, National University of Singapore, Sin- gapore GGanggoog Provincial Key Laboratory of Fully Actuated System Control Theory and Technology. School of Automation and Intelligent Manufacturing, Southern University Science and Technology, Shenzhen, China. Correspondence to: Bryan Hooi <bhooi @ wwwp.oou.....e.eeoooooooooo
Proceedings of the 4rnd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
'Our code is available https://gi com/ 22.1 3..335m//mmtt MCTS- mamter....

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
In recent years, large language models (LLMs) have shown exceptional effectiveness in various domains (Hadi al., 2023; 2024; Naveed et al., 2023). Leveraging LLMs to au- tomatically enhance heuristics, LLM-based AHD methods (Liu et al., 2024e; Yu & Liu, 2024) can design high-quality heuristics for various complex tasks without manual inter- ventions. EoH (Liu et al., 2023a; 2024b) and Funsearch (Radera-Pareeess et al., 2024) innovatively apply LLMs to AHD by designing a iipulation-based evolutionary compu- tation (EC) procedure. For a given task, several established general frameworks may exist for implementing heuristics, e.g., greedy solving frameworks or frameworks with search- based ideas for CO problems. LLM- AHD methods focus on designing key heuristic functions within one of these predefined general frameworks, rather than developing heuristics from scratch. These methods maintain a popula- tion of outstanding heuristic functions based on their per- formances on an evaluation dataset and iteratively prompt LLMs to generate new heuristic functions taking the existing ones as starting points. Building on this population nopulation-based EC framework, studies also introduce effective components. EoH develops several prompt strategies that guide L.LMS in generating effective heuristics. ReEvo (Ye al., 2024a) incorporates the reflection mechanism (Shinn et al., 2024) to enhance the reasoning of LLMs among heuristic function samples. HSEvo (Dat et al., 2024) presents diversity metries and harmony search (Shi et al., 2013) to increase the diver- sity of the population without compromising effectiveness.
novel tree-special prompt strategy to inspire LLMs with the organized function samples in the MCTS tree paths. More- over, as components, MCTS-AHD proposes an exploration- decay technique, which linearly decreases the rate at which we perform branching in MCTS as the algorithm progresses. We also present a novel thought-alignment procedure to generate precise linguistic descriptions of functions. In ex- periments, we implement MCTS-AHH to design heuristics with several general frameworks for wide range of NP- hard (Ausiello et al., 2012) CO problems and a Bayesian Optimization (BO)-related optimization task. MCTS-AHD achieves significantly higher-quality heuristics than hand- crafted heuristics and existing LLM-based AHD methods.
2. Preliminary
2.1. Definition: AHD & LLM-basse AHD
AHD: For given task P (e.g., a CO problem), AHD meth- ods search for the best-performing heuristic h" within a heuristic space H as follows:
h" = arg max g(h). REH
(1)
The heuristic space H contains all feasible heuristics for tasks P. Given a task P, heuristic h E H is an algorithm mapping the set of task inputs (also called instances) Ip into the corresponding set of solutions Sp, i.e., h Tp + Sp. For example, heuristics for an NP-hard CO task, Traveling Salesman Problem (TSP), map city coordinates (TSP in- stances) to travel tours (solutions). The function g(-) is per- formance measure function for heuristics, H + R. For CO task / minimizing an objective function f Sp - IR, AHD methods estimate the performance function g by eval- uating the heuristic h on a task specifce dataset D). Formally, we enumerate instances ins E D C Lp. obtain their so- lutions h(ins) by h, and calculate the expectation of the objective function values for the solutions as follows:
These population- based methods eliminate inferior heuristic functions in order to focus more on top-performance ones. However, lower-performance heuristic functions still have the potential to be outstanding after steps of LLM-based refinement. Thus, as shown in Figure 1, the population structure may guide the evolution of heuristics getting stuck in suboptimal local optima. Funsearch and HSEvo employ multiple-popuuieee
structures (Cantú-Pat) diversity metrics, respectively, to improve the diversity of populations. Populations with these components can reduce the probability of premature convergence but still fail to explore the complex space of heuristics.
al., 1998) and
g(h) = Ef
(2)
The heuristics in H belong wide range of general frame- works, and the optimal heuristic could be implemented with multiple frameworks. To focus more critical heuristic designs within each framework, AHD methods typically pre- define a general framework and design only a key heuristic function with specified inputs and outputs within this frame- work. For example, heuristies for TSP within step-by-step construction framework sequentially build TSP tours one city after another. AHD methods within this framework for TSP will design key heuristic function to select the next city based on the partial tour of previously visited cities. For simplicity, we still denote the function to be designed as h.
To address these drawbacks, this paper proposes MCTS- AHD, the first tree search method for LLM-based AHD, which employs a tree structure over all the heuristic func- tions generated so far and uses the Monte Carlo Tree Search (MCTS) algorithm with progressive widening technique (Coulom, 2007) to guide the evolution of further heuristics. Its advantages are: 1) Instead of directly discarding inferior heuristic functions, MCTS-AHD enables steps of LLM- based evolution on temporarily underperforming hcuristic functions while keeping focus on better- perterrierfooinngggg ones, achieving a more comprehensive exploration of the heuristic space. 2) The tree structure in MCTS can benefit the LLM- based heuristic refinement, where MCTS-AHD presents
LLM-based AHD: LLM-based AHD introduces LLMs into the search process for the optimal heuristic function
2

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Action: il
Action: ml
Action: m2
Inifialization: Generate heuristic function
Mutation: Modify the given heuristic function with its deseription (O), egg. add new mechanisms code segments.
Mutation: Modiff the given heuristic function its description (O). egg. change parameter settings
Task P & general framework
Prompt-
Prompe
Prompe
Function
Description
Fanction
Description
Function
Deseription
E!
<1>
New MCTS node
New MCTS node
New MCTS mode
Action: el
Action: e2
Action:
Given several funetions with their descriptions and perfortraecss R. generate tulally diffierntt onc.
Crossover:
Crossover:
Based a function with its description and performance (O). learn from another one (Q) and generate a new finction.
Given several related functions with their deseriptions and performaces, reason and generate a new function with better performance
Reasening:
Prompt
Function
Description
Sumple
Primpt
Function
Description
Prompx
Function
Deseription
</>
</>
Bile
New MCTS node
F
New MCTS mode
New MCTS node
Figure 2. LLL-- actions in MCTS- for heuristic evolution. Actions include initializing new heuristic (il); two mutation actions (ml and m2) to mutate an existing heuristic function into a new one with diverse mechanism or detail settings; two crossover actions (el and e2) to generate new heuristic from multiple existing ones; and novel tree-path reasoning action (s1) get better heuristic function from organized function samples on an MCTS tree path from the root node nz to a leaf node 744.
h" (within predefined framework). Existing LLM-based AHD methods (Liu et al., 2024b; Ye et al., 2024a) main- tain a population of M heuristic functions (AI...., har) and employ EC to update the population iteratively. Imi- tating mutation or crossover operators in EC, LLMebased AHD methods prompt LLMs to generate heuristics given existing heuristics from the population. In these methods, heuristic h will only be retained for the next iteration if its performance g(h) estimated in the evaluation dataset D exceeds the worst-performing heuristic in the original population, i.., ghh) > min;g (I.....MM) gh;)). This property makes it difficult for population-based methods to adopt a worse-before-better strategy for the optimal heuristic h²..
root node ny, the selection stage iteratively selects the child node with the largest UCT value until it reaches a leaf node. Given a current node ne. the UCT values for its child nodes c E Children(n.) (n.)) are calculated as follows:
[n(N(n,)) + + (C))
UCT(c) = (Q(c) + A
(3)
The expansion stage obtains multiple child nodes from the current (Ieaf) node n. by sampling several actions from the state of ne among all possible options.
Expansion:
Simulation: The simulation stage evaluates all newly ex- panded leaf nodes for their quality value Q(-).
2.2. Monte Carlo Tree Search
Backpropagation: The backpropagation process uses the results of simulations to update the values of (()),(()) for nodes on the tree path from ni to the root 7t..
MCTS Algorithm. MCTS (Swiechowski et al., 2023) is cibisiionmaking algorithm widely used in games (Silver et al., 2016) and complex decision-making tasks (Fu al., 2021). Recent studies also verify the power of MCTS in assisting LLMs to conduct multi-hop reasoning (Feng et al., 2023). In the MCTS tree, each node ne represents a state, and the MCTS will repeatedly select and expand the node with the highest potential judged by UCT algorithm (Koc- sis & Szepesvári. 2006). Each MCTS tree node ne records quality value Q(n.)) and a visit count N (nn.) represent- ing the number of times the node has been selected. From an initial root node n,, MCTS gradually builds the MCTS tree to explore the entire state space. Each round of MCTS consists of four stages as follows:
After several iterations of MCTS, the MCTS tree can contain nodes with high-quality states for games or tasks.
Progressive Widdnnng. Conventional MCTS is not suitable for tasks with extensive action options or dynamically chang- ing environments (Lee et al., 2020b). Progressive widening (Coulom, 2007) is a technique designed for MCTS to fit such tasks. gradually adds new child nodes to noa-leaf nodes as their visit counts N-(-) increases. Formally, for node ne with child nodes children(ne), new child node will be added every time the following condition is satisfied:
[N(m) |children(ne)ls
(4)
Selection: The selection stage identifies the most potential MCTS tree node for subsequent node expansions. From the
where (children(n.) | is the number of child nodes of ne-
3

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Repeated until evaluating g <
for T times
Selection
Expansion
Simulation
Backpropagation
MCT Root
MCT Root
MCT Root
MCT Root
streal rock
Initial modes
Initial
Initial modes
Initial modes
Progressive Widtaing
Tox usde with lagos UCT!)
011
The MCTS process in MCTS-AHI contains four stages, i..., selection, expansion, simulation, and backpropagation. MCTS- AHD simulates the quality value of each node the performance function values of their heuristics and the MCTS will terminate after total T performance evaluations. MCTS-AHD introduces the progressive widening technique to better crossover original heuristic functions with continuously generated new ones. It conducts the crossover actions el for the root node and action c2 for other nodes.
Figure 3.
3. MCTS-AHD
action, LLMs are supposed to output the Python code of a heuristic function and its linguistic description.
To address the challenges faced by population- LLM- based AHD methods in overcoming local optima and explor- ing complex heuristic spaces, this paper proposes a novel method called MCTS-AHD. It preserves all heuristic func- tions LLMs generated so far in an MCTS tree and employs MCTS with progressive widening for heuristic evolution. The MCTS root node n,- is a virtual node without represent- ing any heuristics, and each of the other nodes represents an executable Python implementation of a heuristic function E Hl along with its linguistic description.
Iniiill Action il: As action for initialization, the action il aims to directly generate heuristic function and its corresponding description from scratch by LLMs.
Mutation Action ml & m2: MCTS-AHD incorporates two mutation actions, m1 & m2, to attempt more detailed de- signs within the original function workflow. Based on the inputted heuristic function, action ml prompts LLMs to introduce new mechanisms and formulas, and action m2 prompts LLMs to modify the parameter settings.
As LLM-based actions for MCTS node expansion, MCTS- AHD prompts LLMs in existing strategies (e.g., mutation, crossover) and a novel tree-path reasoning strategy. More- over, to encourage the exploration of the heuristic space H in the early stages of MCTS and ensure convergence in the later stages, MCTS-AHD presents an exploration- decay technique that linearly reduces the exploration factor in UCT.
Crossover Action el: To explore heuristic functions with new workflows, we employ a crossover action el to generate a new heuristic function that diverges from multiple existing ones. These existing heuristic functions are inputted to LLMs with their performances g(-) and descriptions.
Crossover Action e2: The crossover action e2 prompts LLMs with parent heuristic function, a reference heuris- tic function, and their respective performances. L.MSs are supposed to identify the beneficial traits and settings in the reference one and craft an improved heuristic function based on the parent one. The reference is sampled from a dynami- cally maintained elite heuristic function set E consisting of heuristic functions with top 10 performances g(-).
3.1. LLM--bsee actions in MCTS-AHD
To simulate the mutation or crossover operators in EC, LLM- based AHD methods prompt LLMs with several prompt strategies generate new heuristic functions from existing ones (Liu et al., 2024b). Utilizing the advantage that the MCTS tree can record the relationships of all the generated heuristics, as shown in Figure 2, MCTS-AHI presents a novel MCTS-specific set of actions for LLM-based heuristic evolution, including action il, el, e2, ml, m2, and sl. The detailed prompts for these actions are in Appendix E. As commonality, all prompts contain descriptions of the task P, the predefined general framework, and the inputs and out- puts of the key heuristic function along with their meanings. For actions except il, prompts also contain implementations and descriptions of existing heuristic functions. For each
Tree-path Reasoning Action sl: The MCTS tree paths from the root n, to leaf nodes record the evolution history of heuristic functions. So, utilizing this feature, MCTS-AHII presents a novel action s1 to analyze all unique heuristic functions from the leaf node be developed nu up to the root n,, identify advantageous designs in these heuristics, and generate an enhanced heuristic function.
The Thought-Alignmee Pro- cess. Linguistic descriptions of heuristic functions can as- sist the reasoning of L.LMs (Liu et al., 2024b), where EoH
Generating Descriptions:
4

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
prompts LLMs for a description before outputting the func- tion code. However, due to LLM hallucination (Huang et al., 2023), such a procedure could lead to uncorrelated codes and descriptions. For correlated and detailed descrip- tions, MCTS-AHD proposes a thought-alignment process that summarizes descriptions after the code generation.
quality values and the visit counts in MCTS follows:
((ne) f
max cEChillren(ne))
Q(c).
((ne) +
Σ
N(c).
(6)
cEChildren((e))
Progressive Widening. Since the elite heuristic function set E for the action e2 updates gradually the search pro- gresses. MCTS-AHD introduces the progressive widening technique to enable the re-exploration of non-leaf nodes, especially nodes with higher visit counts. The progressive widening process will occur when the condition in Eq.(4) is satisfied and we have a = 0.5 for MCTS-AHD. We call the action el for new child node when the root node ny qualifies the condition in Eq,(4), and we call action when other nodes qualify. Heuristic funetions inputted to the ac- tion el are uniformly selected from 2 to 5 different subtrees of MCTS. We implement the progressive widening process during the selection stage, then these nodes will also be processed in the simulation and backpropagation stages.
Therefore, performing all the MCTS-AHD actions calls LLMs twice. In the first call, we adopt the LLM-generated Python implementation of a heuristic function with action prompts. Then, we conduct a thought-alignment process, prompting LLMs to generate linguistic code descriptions in up to three sentences (refer to Appendix E.2 for prompts). The second LLM call is significantly shorter than the first one, so it will not cause a severe increase in execution time and token cost.
3.2. MCTS settings
Figure 3 displays the MCTS process MCTS-AHD. first generates N2 initial nodes representing and links them to virtual root node n, that does not represent any heuris- tics. Subsequently, similar to the regular MCTS introduced in Section2.2, MCTS-AHD repeatedly performs the selec- tion, expansion, simulation, and backpropagation stages as follows until the number of evaluations of heuristics ap- proaches limit? 7:
Eventually, MCTS-AII will output a heuristic function with the highest performance value throughout the MCTS.
3.3. Exploration-Decat
The setting of the exploration factor in Eq,(5) determines the preferences of MCTS on exploration or exploitation (Browne et al., 2012). A larger À promotes the exploration of temporarily inferior nodes, while a smaller À stimulates concentration on nodes with higher quality values Q(-). To facilitate a more comprehensive exploration in the early it- erations of MCTS and ensure convergence in the later ones, MCTS-AHD presents an exploration-dess decay technique, lin- early decaying the exploration factor À in Eq.(5) follows:
Selection: In the selection process of MCTS-AHD, MCTS- AHD normalizes the quality value Q(-) to enhance the ho- mogeneity of different tasks in calculating UCT value for child nodes E Children(n.,) of node ne as follows:
UCT(c) ((c) Umin + X
In(N (nn(N(m)) +1)
Imax
qmin
(())
== Ao * T-t
(5)
where qmar and Amin are the upper and lower limits of qual- ity values (-)) that ever encountered in MCTS, respectively. From the root ny, MCTS iteratively selects a child node with the largest UCT value until reaching a leaf node.
T
Although having a task-specific setting A is helpful for high-quality heuristics, MCTS-AHD strives to keep the generalization ability, so we set Xo = 0.1 for all tasks.
Expansion: For the leaf node selected in the selection stage, the expansion stage prompts LLMs with actions e2, ml, m2, and s1 to build its child nodes. To attempt various detailed designs, in single expansion stage, MCTS-AHD generates child nodes with the actions ml and m2, one with e2 and sl, respectively (2k: + child nodes in total).
4. Experiments
This section evaluates the proposed MCTS on designing outstanding heuristics for complex optimization tasks, in- cluding NP-hard CO problems and a Cost-aware Acquisi- tion Function (CAF) design task for BO (Yao et al., 2024c). The definitions of these tasks are in Appendix B. We im- plement MCTS-AHD to design key functions of wide range of general frameworks (detailed in Appendix C) for these tasks, including step-by-step construction, Ant Colony Optimization (ACO), Guided Local Search (GLS), and BO.
Then, -CDS-AHD evaluates these newly gen- erated heuristic functions h on the evaluation dataset D for their performances yhh) and directly sets their quality value as their performances, i.e., Q(m)) < gh)). We also record their visit count N (m1)= + 1. Simultancously, the clite set E for the action e2, amaz. and Imin will be updated.
Simulation:
Settings. For experiments in this section, we set the number of initial tree nodes N₁ = 4, X = 0.1, a = 0.5. The
Backpropagation: The backpropagation process updates the
5

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Table 1. Designing hcuristies with the step-hy-step construction framework for TSP and KP. We evaluate methods 6 test sets with 1,000 instances each. Test sets with in in-domain scales (i.idd to the evaluation dataset D) are underlined. Since AHD methods have no guarantees for generalization ability, the effect on in-domain datasets more important. Optimal for TSP obtained by LKH (Lin Kernighan, 1973), and Optimal for KP is the result of OR-Tools. Each LLM-based AHD method is run three times and we report the average performances. The best-performing method with each LLM is shaded, and each test set's overall best result is in bold.
Task
TSP
KP
N=
N=50
N=100
N=200
N=50,
W=12.5
N=100.
W=25
N=200,
W=25
Methods
Obj-
Gap
Obj.
Gap
Obj-J
Gap
Obj.1
Gap
Obj-t
Gap
Obj.T
Gap
Optimal
5.675
7.768
10.659
20.037
40.271
57,448
Greedy Construct
6,959
22.62%
9.706
24.94%
13.461
26.29%
19.985
0.26%
40.225
0.12%
$7.395
0.09%
POMO
5.697
0.39%
8.001
3.01%
12.897
20.45%
19.612
2.12%
39.676
1.48%
57.271
0.09%
L.M based AHD:
GPT-3.5 nurbo
Funsearch
6.683
17.75%
9.240
18.95%
12,808
19.61%
19,985
0.26%
40.225
0.12%
57.395
0.09%
6.390
12.59%
8,930
14.96%
12.538
17.63%
19,994
0.21%
40.231
0.10%
57.400
0.08%
ACTS-AHD(Ours)
6.346
11.82%
8.861
14.08%
12.418
16.51
19.997
0.20%
40.233
0.09%
57.393
0.10%
L.LM-based AHD: GPT-4o-mini
Funsearch
6,357
12.00%
8.850
13.93%
12.372
15.54%
19,988
0.24%
40.227
0.11%
57.398
0.09%
EoH
6,394
12.67%
8.894
14.49%
12.437
16.68%
19,993
0.22%
40.231
0.10%
$7.399
0.09%
MCTS-AHD(OUrS)
6,225
9.69%
8.684
11.79%
12.120
13.71%
20.015
0.11%
40.252
0.05%
$7.423
0.04%
running time of each heuristic on the evaluation dataset D limited to 60 seconds. The composition of evaluation datasets D for each task is detailed in Appendix D as well as the settings of general frameworks. Valuable LLM-based AHD methods should be flexible for various pre-trained LLMs, so we include both GPT-3.5-turbo and GPT-4o-mini.
the 0-1 Knapsack Problem (KP), executing MCTS-AHD with 7=1,000 takes approximately three hours, 1M input tokens, 0.2M output tokens, about 0.3$ with GPT-4o-mini. Compared to LLM-based AHD baselines, there is signif- icant efficiency degradation or cost improvement.
4.1. MCTS-AHD for NP-hard CO Problems
Baselines. To verify the ability of heuristics designed by MCTS-AHD, we introduce four types of heuristics as base- lines: (a) Manually designed heuristics, e.g.. Nearest-greede (Rosenkrantz et al., 1977), ACO (Dorigo al., 2006), El (Mockus, 1974). (b) Traditional AHD method: GHPP (Duflo et al., 2019) (c) Neural Combinatorial Optimiza- tion (NCO) methods under the same general frameworks, e.g. POMO (Kwon et al., 2020) and DeepACO (Ye et al., 2024b). (d) Existing LLM-based AHD methods: Funsearch Coomera-Paredes et al., 2024), EoH (Liu et al., 2024b), ReEvo (Ye al., 2024a), and the most recent work HSEvo (Dat et al., 2024). Funsearch, ReEvo, and HSEvo design heuristics from a handcrafted low-quality seed function, and we provide the same seed function for each design scenario without providing external knowledge. Instead, running EoH and MCTS-AHD does not require manually setting a seed function to initiate the heuristic evolution, so both methods demonstrate better applicability.
As commonly recognized complex tasks (Korte al., 2011) 1), this subsection evaluates MCTS-AHD on NP-hard CO prob- lems, including TSP, KP, Capacitated Vehicle Routing Prob- lem (CVRP). Multiple Knapsack Problem (MKP), Bin- Packing Problem (BPP) with both online and offiine settings (online BPP & offline BPP), and Admissible Set Problem (ASP). For these NP-hard CO problems, we apply MCTS- AHD automatically design heuristics with several general frameworks, including step-by-step construction, ACO, and GLS (GLS results are shown in Appendix F.2).
The step-by-step construction framework (also known as the constructive heuristic framework) simple but flexible for task solving, which constructs nodes in feasible CO solutions one by one (Asani et al., 2023). Besides being a general framework for LLM-based AHD methods, it is also the most common framework adopted in NCO methods (Vinyals et al., 2015; Bello et al., 2016). We use MCTS-AHD to design heuristics with the step-by-step construction framework for TSP, KP, online BPP, and ASP (with ASP results in Appendix F.1).
Step-by-Step Construction Framework.
We design heuristics with the proposed MCTS-AHD and LLM-based AHD baselines on single Intel(R) i7-12700 CPU. Following similar settings of Liu et al. (2024b), for almost all tasks, we set the evaluation budget of based AHD methods on the evaluation dataset D as T = 1, 000. In designing heuristics for each application scenario, we conduct three independent runs for each LbMebased AHD method to reduce statistical biases. To verify the significant advantages of MCTS-AHD, we perform more runs on some tasks in Appendix F.4 to obtain the p-value. In designing heuristics with the step-by-step construction framework for
TSP & KP. We first evaluate MCTS-AHD by designing TSP and KP heuristics within step-by-step construction frame- works. The key heuristic function to be designed should se- lect the next TSP node or the next KP item to join taking the temporary solving state (e.g.. selected and remaining TSP nodes or KP items) as inputs. This function will be executed recursively until a complete feasible solution is constructed.
6

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Table 2. Designing heuristics with the ACO general framework for solving TSP, CVRP, MKP, and offline BPP. Each test set contains 64
instances and LLM LLM-based AHD methods' performances are averaged over three runs,
TSP
CVRP
MKP
Offline BPP
Test sets
N=
N=100
50
100
C=50
N=100,
m=5
NN m=
N=500, C= 150
N=1,000,
C=150
Methods
Obj..
Gap
0bj-
Gap
Obj.4
Gap
Obj--
Gap
Obj.t
Gap
Obj-t
Gap
Obj.J
Gap
Obj.
Gap
ACO
5,992
3.28%
8.948
9,40%
11.355
27.77%
18,778
25.76%
22.738
2.31%
40.672
4.30%
208.828
2.81%
417,938
3.15%
DeepACO
5.842
0.71%
8.282
1.26%
8,888
0.00%
14.932
0.00%
23.093
0.79%
41.988 1.20%
203.125
0.00%
405.172
0.00%
L.LM-based AHD:
GPT-4o-mini
EoH
5,828 0.45%
8.263
1.03%
9.359
5.31%
15.681
5.02%
23.139
0.59%
41.994
1.19%
204.646
0.75%
408.599
0.85%
ReEvo
5.856
0.94%
8.340
1.98%
9.327
4.94%
16.092
7.77%
23.245
0.13%
42.416
0.19%
206.693
1.76%
413.510
2.06%
HSEvo
5,810
0.14%
8.219
0.50%
9.349
5.19%
16.282
9.04%
23,276
0.00%
42.494
0.01%
205.563
1.20%
410.745
1.38%
MCTS-AHD(Ours)
5,801 0.00% % 8.179
0.00%
9,286
4.48%
15,782
5.70%
23,269
0.03%
42,498
0.00%
204.094
0.48%
407.323
0,53%
For all LLM-based AHD methods, the evaluation dataset D contains 64 50-node (N=50) TSP instances for TSP and 64 100-item (N=100) KP instances with capacity W = 25 for KP. Table shows the performance of baseline heuris- ties and LLM-based AHD methods. The Greedy Construct baseline is the Nearest-greedy -gredy heuristic algorithm for TSP and it constructs KP solutions by the item with the largest MCTS-AHD exhibits significant advan- tages on almost all test sets, surpassing manually designed heuristics and LLM-based AHD methods EoH and Fun- search. Moreover, compared to an advanced NCO method POMO which requires task-specific training, MCTS- -HD can design better heuristics in 200-node TSP and KP test sets, exhibiting its power to solve NP-hard CO problems.
Ant Colony Optimization Framework. The ACO is an optimization algorithm inspired by the foraging behavior of ants, which contains a heuristic matrix and implements a path selection mechanism to solve combinatorial optimiza- tion problems by simulating the transfer of pheromones between ants (Dorigo et al., 2006; Kim et al., 2024). LLM- based AHD can design a generation function of the heuristic matrix, thereby transforming ACO into framework and applying it to variety of tasks. Following Ye et al. (2024a), MCTS-AFH designs heuristics within the ACO framework for four NP-hard CO problems: TSP. CVRP, MKP, and of- fline BPP. The design results using GPT-4o-mini as LLMs are shown in Table 2, where MCTS-AHD exhibits signifi- cant leads to EoH and ReEvo in three in-domain test sets across four CO problems and three out-of-domain test sets. Moreover, the proposed MCTS-AHD can consistently out- perform manually designed ACO heuristics in all eight test sets and surpass an outstanding NCO method DeepACO (Ye et al., 2024b) in TSP and MKP test sets.
value-weight-we
Online BPP. As another widely considered NP-hard CO problem, online BPP is the online variant of BPP. It allows only immediate bin packing decisions once a new item is received. It is generally adopted as a common evaluation sce- nario for LLM-based AHD methods. We follow (Liu et al., 2024b) to generate WeiBull BPP instances (Castiñeiras et al., 2012) and use four WeiBull instances with diverse scales as the evaluation dataset D. As shown in Table 3, online BPP heuristics designed by MCTS-AHD demonstrate superior average performance of six test sets.
4.2. MCTS-AHD for Other Complex Tasks
To assess whether MCTS-AHD can still perform well in optimization tasks beyond CO problems, we follow Yao et al. (2024c) to evaluate MCTS-AHI by designing heuris- tic CAFs for BO. The CAF a crucial component for Cost-aware BO, helping to reach the global optimum in cost-efficient manner. There are several advanced hand- crafted heuristic CAFs, including EI (Mockus, 1974), Elpu (Snock et al., 2012), and El-cools (Lee et al., 2020a). We employ two synthetic instances with different landscapes and input dimensions (Ackley and Rastrigin in Table 4) as the evaluation dataset D for LLM- AHD and also test the manually and automatically designed heuristics on ten other synthetic instances. During heuristic evolutions, we set the sampling budget to 12 and run 5 independent trials for average performances. As shown in Table 4. heuristic CAFs designed by the proposed MCTS-AHD demonstrate superior BO results that outperform both manually designed heuristics and EoH in six out of twelve synthetic instances. It verifies that MCTS-AR AHD not only performs well in NP-
Table Design step-by-step construction heuristies for solving online BPP. The table exhibits the performance gaps of heuristics to the lower bound. Each LLM-based AHD method is run three times for the average gaps. Each test set contains five WeiBull BPP instances and we underline the four (in-domain) scales contained in D.. The scale notations of test sets are abbreviated, e.g., 1k_100 represents 1,000 items and capacity W- 100.
Online BPP
Test sets
1k_000
1k_500
5k_100
5k_500
10k_100
10k_500
Avg.
Best Fit
4.77%
0.25%
4.31%
0.55%
4.05%
0.47%
2.40%
First Fit
5.02%
0.25%
4.65%
0.55%
4.36%
0.50%
2.56%
LLM-based AHD:
GPT-4o-mini
Funscarch
2.45%
0.60%
1.30%
0.25%
1.05%
0.21%
0.99%
FaH
2.69%
0.25%
1.63%
0.53%
1.47%
0.45%
1.17%
ReEvv
3.94%:
0.50%
2.72%
0.40%
2.39%
0.31%
1.71%
HSEvo
2.64%
1.07%
1.43%
0.32%
1.13%
0.21%
1.13%
MCTS AHD
2.45%
0.50%
1.06%
0.32%
0.74%
0.26%
0.89%
7

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Table Designing CAFs for BO. The table shows the gaps optimal when running BO on instances with manually designed CAPs and CAFs designed by LLMe AHD methods. LLM-based AHD methods are run three times for the average gaps, In testing, the
evaluation budgets for BO are and we run trials for average gaps. The results EL, Elpu, and El-cool are from Yao et al. (2024c).
Instances
Ackley
Rastrigin
Griewank
Rosenbrock
Levy
ThreeHumpCamel StyblinskiTang Hartmann
Powell
Shekel
Hartmann
Cosine8
EI
2.66%
4.74%
0.49%
1.26%
0.01 %
0.05%
0.03%
0.00%
18.89%
7.91%
0.03%
0.47%
Elpu
2.33%
5.62%
0,34%
2.36%
0.01%
0.12%
0.02%
0.00%
19.83%
7.92%
0.03%
0.47%
El-cool
2.74%
5.78%
0.34%
2.29%
0.01%
0.07%
0.03%
0.00%
14.95%
8.21%
0.03%
0.54%
LLM based AHD: GPT-4o-miui
EoH 2,45%
0.90%
0.54%
56.78%
0.20%
0.26%
0.79%
0.04%
70.89%
4.56%
0.33%
0.36%
MCTS-AHD
2.40%
0.77% %
0.36%
1.68%
0.01%
0.02%
0.20%
0.01%
1.27 %
3.94%
0.38%
0.34%
hard CO problems but can also show great power in other complex optimization tasks.
actions. The importance of action sl also demonstrates that MCTS-AHD benefits from its organized tree structure.
Meanwhile, we measure the sensitivity of the main param- eter Ag. Results in the last two lines of Table 5 show that although the TSP and KP tasks may have respective prefer- ences in the Ao setting, the default setting (i.e., Ao 0.1) exhibits generally good quality.
5. Discussion
Experiments have demonstrated the effectiveness of the proposed MCTS-AHD in designing high-quality heuristics for wide range of application scenarios. This section first conducts essential ablation studies. Then, we will also analyze the advantages of utilizing MCTS in LLM-based AHD compared to the original population-basee FC.
5.2. MCTS versus Population EC
Ability of MCTS-AHD in Escaping from Local Optima. As the main contribution of this paper, instead of population- based EC, MCTS-AIB AHD can manage inferior but potential heuristic functions, achieving a more comprehensive explo- ration of the heuristic space H thus avoiding falling into lo- cal optima. To verify this, we plot the performance curves of MCTS-AHD and LLM-based AHD baselines in designing step-by-step construction heuristics for TSP and designing CAFs for BOs. Each curve is averaged over least five runs. As illustrated in Figure 4, all baseline methods with populations exhibit early convergences on performances, but MCTS-AHD can converge to significantly better perfor- mance via quick and continuous performance updates.
5.1. Ablation on Parameters and Components
To validate the necessity of its components, as shown in Table 5, we first remove three proposed components of MCTS-AHD (Progressive Widening,
and Exploration-decay) and use these variants to design step- by-step heuristics for TSP and KP. Line 3 to Line in Table 5 reports their average optimality gaps over three runs, and all these variants exhibit clear performance degradation in at least one task compared to the original MCTS-AII AHD.
The actions for node expansion in MCTS-AHD are also essential. Actions el and e2 are associated with the pro- gressive widening, so they cannot be ablated individually. According to Table 5, MCTS-AHD variants without actions s1, ml, and m2 could only design worse heuristics in at least one task, proving the significance of these -based
Evclatio LLL. Methols
Evolaioo Curva of L. A-be Mehoda
Fusuull
13
Rubio
MCTSAID (Oun)
Table Ablations on the components, actions, and parameter set- tings of MCTS-AHD, We use MCTS-AHD variants to design heuristics with the step-by-step construction framework for their
Narbe: Bwwkaeeee m.
1000
100
(a) Design Step-by-step Con- struction heuristics for TSP
(b) Design CAFs for BO
optimality gaps on 1,000-instance test sets averaged over five runs.
Methods
7SP50
KP100
Figure 4. Evolution curves on two diverse application scenarios.
MCTS- AHD (Original, 10 runs)
10.661%
0.059%
w/o Progressive Widening
12.132%
0.064%
w/o Thouugh-atiggmmen
11.640%
0.061%
Advantage scopes of MCTS-AHD. Compared to population-based baselines, we claim that MCTS-AHD demonstrates greater advantages in application scenarios with more complex heuristic spaces H and application sce- narios with more descriptions as knowledge. We analyze these two claims with experiments in Appendix F. 10
who Exploration-decay
11.606%
0.064%
w/o Action sl
11.919%
0.062%
w/o Action ml
10.921%
0.083%
w/o Action m2
11.679%
0.061%
MCTS-AHD variunt 0.05
11.080%
0.056%
MCTS-AHD variunt 0.2
12.124%
0.034%
8

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
6. Conclusion
Asani, E. O., Okeyinka, A. E., and Adebiyi, A. A. compu- tation investigation of the impact of convex hull subtour on the nearest neighbour heuristic. In 2023 International Conference on Science, Engineering and Business for Sustainable Development Goals (SEB-SDG), volume 1, pp. 1-7. IEEE, 2023.
In conclusion, this paper first applies MCTS to LLM-based AHD. The proposed MCTS-AHD achieves a comprehen- sive exploration of the heuristic space and can finally design higher-quality heuristics for NP-hard complex tasks. For LLM-based AHD, MCTS can be more promising evolu- tion method compared to population-base based EC.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Marchetti-Spaccannet Spaccamela, A., and Protasi, M. Complexity and approximation: Combinatorial optimization prob- lems and their approximability properties. Springer Sci- ence & Business Media, 2012.
As a limitation MCTS- AHD, the convergence speed of MCTS-AHD can still be improved. In the future, we will consider designing MCTS- population hybrid methods for better evolution efficiency.
Limitation and Future Work:
Bäck, T., Fogel, D. B., and Michalewicz, Z. Handbook of evolutionary computation. Release, 97(1):B1, 1997.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Bello. I,, Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning, arXiv preprint
2016.
Berto, F., Hua, C.,, Zepeda, N. G., Hottung, A., Wouda, N.,
Lan, L., Park. J., Tiemney, K., and Park. J. Routefinder: Towards foundation models for vehicle routing problems. arXiv preprint arXiv:2406. 2024.
Acknowledge
This work was partially supported by the National Natural Science Foundation of China (Grant No. 624761 18), the Natural Science Foundation of Guangdong Province (Grant No. 2024A151501 1759), the Natural Science Foundation of Shenzhen (Grant No.JCY1202205001 13013331) and the Guangdong Science and Technology Program (Grant No. 102411212000002
Biggs, N. The traveling salesman problem a guided tour of combinatorial optimization, 1986.
Blot, A., Hoos, H. H., Jourdan, L.,, Kessaci- Marmmin,, M.-É., and Trautmann, H. Mo-paramils: multi-objeccivve auto- matic algorithm configuration framework. In Learning and Intelligent Optimization: 10th International Con- ference, LION 10, Ischia, Italy, May 29-June 1, 2016, Revised Selected Papers 10, pp. 32-42 22-47.2 Springer, 2016.
Moreover, we would like to express our esteemed gratitude to Professor Wee Sun Lee for his valuable suggestions on this work.
Brandfonbrener, D., Henniger, S., Raja, S., Prasad, T., Loughridge, C. R., Cassano, F., Hu, S. R., Yang. J., Byrd, W. E.,, Zinkov, R., et al. Vermots: Synthesizing multi- step programs using verifier, a large language model, and tree search. In The 4th Workshop on Mathematical Reasoning and Al at NewrlPS 24, 2024.
References
Abgaryan, H., Harutyunyan, A., and Cazenave, T. Llms can schedule. arXiv preprint arXiv:2408.0699 2024.
Alhindi, A., Alhindi, A., Alhejali, A., Alsheddy, A., Tairan, N., and Alhakami, H. Moea/d-gls: a multiobjective memetic algorithm using decomposition and guided local search. Soft Computing, 23:9605-995 99119, 2019.
Brecklinghaus, and Hougardy, S. The approximation ratio of the greedy algorithm for the metric traveling salesman problem. Operations Research Letters, (3(3):259-22 261, 2015.
Ansari, 7. N. and Daxini, S. D. A state-of-the-art review mneta-heuristics application in remanufacturing, Archives of Computational Methods in Engineering, 29(1):427- 470, 2022.
Browne, C. B., Powley, E.,, Whitehouse, D., I Lucas, S. M., Cowling, P. L., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., and Colton, S. survey of monte carlo search methods. IEEE Transactions on Computa- tional Intelligence and Al in games, 4(1):1-43, 2012.
Amold, F. and Sörensen, K. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32 46, 2019.
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., and Qu, R. Hyper-heuristics: survey of the state of the art. Journal of the Operational Research Society, 64(12))1695- 2013.
Amold, F., Gendreau, M., and Sörensen, K. Efficiently solving very large-scale routing problems. Computers & operations research, 107:32 42, 2019.

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Özcan, E., and Woodward, J. R. A classification of hyper- heuristic approaches: revisited. Handbbok of metaheuris- tics, pp. 453-477, 2019.
Feng, X., Wan, Z., Wen, M., McAleer, S. M., Wen, Y., Zhang, W., and Wang, J. Alphazero-like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.17177 2023.
Cantú-Paz, E. et al. A survey of parallel genetic algorithms. Calculateurs paralletes, reseaux et systems repartis, 10 (2):141-171, 1998.
Fischetti, M., Lodi, A., and Toth, P. Exact methods for the asymmetric traveling salesman problem. The traveling salesman problem and its variations, pp. 169-205, 2007.
Castiñeiras, Cauwer, M., and O' S'ulllian,, B. Weibull- based benchmarks for bin packing. In International Con- ference on Principles and Practice of Constraint Pro- gramming, pp. 207-222. Springer, 2012.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI conference on artificial intelli- gence, volume 35, pp. 7474-7482, 2021.
Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. In Operations Research Forum, volume 3, pp. 20. Springer, 2022.
Gao, C., Shang, H., Xue, K., Li, D., and Qian, C. Towards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy, 2024.
Coulom, R. Computing "elo ratings" of move patterns in the game of go. ICGA journal, 30(4): 198-2088..2.1110 2007.
Guo, P.-F., Chen, Y.-H., Tsai, Y.-D,, and Lin, S.-D. Towards optimizing with large language models. arXiv preprint arXiv:2310.05204, 2023.
Dainese, N., Merler, M., Alakuijala, M., and Marttinen, P. Generating code world models with large language models guided by monte carlo tree search. arXiv preprint arXiv:2405. 15383, 2024.
Hadi, M. U.. Qureshi, R., Shah, A.. Irfan, M., Zafar, A., Shaikh, M. B., Akhtar, N., Wu, J., Mirjalili, S.. et al. A survey large language models: Applications, challenges, limitations, and practical usage. Authorea Preprints, 2023.
Dat, P. V. T., Doan, L., and Binh, H. T. Hsevo: Elevating automatic heuristic design with diversity-driven harmony search and genetic algorithm using Iims. arXiv preprint arXiv:2412. 14995, 149955 2024.
Hadi, M. U., AI Tashi, Q., Shah, A., Qureshi, R., Muneer, A., Irfan, M., Zafar, A., Shaikh, M. B., Akhtar, N., Wu, J., et al. Large language models: a comprehensive survey its applications, challenges, limitations, and future prospects. Authorea Preprints, 2024.
DeLorenzo, M.. Chowdhury, A. B., Gohil, V., Thakur, S., Karri, R., Garg, S., and Rajendran, J. Make every move count: Llm-based high-quality rtl code generation using mcts. arXiv preprint 240.:22000,0328,, 2024.
He, K., Zhang, X., Ren, S., and Sun, J. Deep residual lear- ing for image recognition. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Desale, S., Rasool, A., Andhale, S., and Rane, P. Heuristic and mnta-heuristtc algorithms and their relevance to the real world: a survey, Int. J. Comput. Eng. Res. Trends, 351(5):2349-708) 2015.
He, Q., Head, L., and Ding, Heuristic algorithm for priority traffic signal control. Transportation research record, 2259()):1-7, 2011.
Dorigo, M., Birattari, M., and Stutzle, T. Ant colony opti- mization. IEEE computational intelligence magazine, (4):28-39, 2006.
Helsgaun, K.
An extension of the lin-kernighan-heleee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12: 966-980, 2017.
Drakulic, D., Michel. S., and Andreoli, J.-M. Goal: A gen- eralist combinatorial optimization agent learning. arXiv preprint 2xXiv:2406.15075 2024.
Duflo, G., Kieffer, E., Brust, M. R., Danoy, G., and Bou- vry, P. A gp hyper-heuristic approach for generating tsp heuristics. In 2019 IEEE International Parallel and Dis- tributed Processing Symposium Workshops (IPDPSW), pp. 921-529, IEEE, 2019.
Hemberg, E., Moskal, S., and O'Reilly, U.-M. Evolving code with a large language model. Genetic Programming and Evolvable Machines, 25(2):21, 2024.
Hendrycks, D., Basart, S., Kadavath, S., Mazeika, M., Arora, A., Guo, E.,, Burns, C., Puranik, S., He, H., Song, D., et al. Mcasuring coding challenge competence with apps. arXiv preprint arXiv:2 00999998,,,,0 2021.
Eiben, A. E. and Smith, J. E. Introduction to evolutionary computing. Springer, 2015.
10

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Huang, L.,, Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., al. A survey hallucination in large language models: Principles, taxon- omy, challenges, and open questions. ACM Transactions on Information Systems, 2023.
Lange, R., Tian, Y., and Tang. Y. Large language models as evolution strategies. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 579-582, 2024.
Lee, E. H., Perrone, V., Archambeau, C., and Seeger, M. Cost-aware bayesian optimization. arXiv preprint arXiv:2003. 10870, 2020a.
Huang, X., Liu, W., Chen, X., Wang, X., Wang, H., Lian, D., Wang, Y., Tang, R., and Chen, E. Understanding the planning of Ilm agents: A survey. arXiv preprint arXiv:2402.02716 2024.
Lee, J., Jeon, W., Kim, G.-H., and Kim, K.-F. Monte- carlo tree search continuous action spaces with value gradients. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 4561-4568, 2020b.
Hudson, B., Li, Q.. Malencia, M., and Prorok, A. Graph neural network guided local search for the traveling sales- person problem. arXiv preprint arXiv:21 10. 0,0259 2021.
Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C., and Stanley, K. O. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331- 366. Springer. 2023.
Jiang. X., Wu, Y., Wang, Y., and Zhang, Y. Unco: Towards unifying neural combinatorial optimization through large language model. arXiv preprint arXiv:2408. 12214, 2024.
Lin, S. and Kernighan, B. W. An effective heuristic algo- rithm for the maveling-salesman problem. Operations research, 21(2):498-516, 1973.
Kambhampati, S., Valmeekam, K., Guan, L., Verma, M., Stechly, K., Bhambri, S., Saldyt, L., and Murthy, A. Lims can't plan, but can help planning in Ilm-modull frame- works. arXiv preprint arXiv:240..08817 2024.
Liu, F., Tong, X., Yuan, M., and Zhang, Q- Algorithm evolution using large language model. arXiv preprint 1:Xiv:3311115244 2023a.
Kim, M., Choi, S., Kim, H., Son, J., Park, J., and Bengio, Y. Ant colony sampling with gflownets for combinatorial optimization. arXiv preprint arXiv:2403.0704/ 2024.
Liu, F., Lin. X., Wang, Z., Zhang, Q., Xialiang, T., and Yuan, M. Multi-task learning for routing problem with cross-problem zero-shot generalization. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 1898-1908, 2024a.
Kocsis, L. and Szepesvári, C. Bandit based monte-carlo planning. In European conference machine learning, pp. 282-293. Springer, 2006.
Liu, F., Xialiang, T., Yuan, M., Lin, X., Luo. F., Wang, Z., Lu, 7.,, and Zhang, Q. Evolution of heuristics: To- wards efficient automatic algorithm design using large language model. In Forty-first International Conference on Machine Learning, 2024b.
Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv: 0903.08475. 2018
Korte, B. H., Vygen, J., Korte, B., and Vygen, J. Combina- torial optimization, volume 1. Springer, 2011.
Liu, F., Yao, Y., Guo, P., Yang, Z., Lin, X., Tong, X., Yuan, M., Lu, Z., Wang, Z., and Zhang, Q. A systematic survey on large language models for algorithm design. arXiv preprint arXiv:2410.14716, 2024c.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- tion Processing Systems, 33:21 188-21198, 2020.
Liu, F., Zhang, R., Xie, Z. Sun, R., Li, K., Lin, X., Wang, Z., Lu, Z., and Zhang, Q. Llm4ad: A platform for algo- rithm design with large language model. arXiv preprint arXiv:2412 17287, 2024d.
Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D.,. and Gwon, Y. Matrix encoding networks for neural combi- natorial optimization. Advances in Neural Information Processing Systems, 34:5138-5149 2021.
Liu, S., Chen, C., Qu, X., Tang, K., and Ong, Y.-S. Large language models as evolutionary optimizers. In 2024 IEEE Congress on Evolutionary Computation (CEC), pp. 1-8. IEEE, 2024e.
Lam, R., Willcox, K., and Wolpert, D. H. Bayesian opti- mization with a finite budget: An approximate dynamic programming approach. Advances Neural Information Processing Systems, 29, 2016.
Liu, W., Wang, H., Wang. J., Li, R., Yue, C., and Zhang, Y. Fr. Folded rationalization with a unified encoder. Advances in Neural Information Processing Systems, 35: 6954-6966, 2022.
Langdon, W. B. and Poli, R. Foundations of genetic pro- gramming. Springer Science & Business Media, 2013.

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Liu, W., Wang, J., Wang, H., Li, R., Deng, Z., Zhang, Y., and Qiu, Y. D-separation for causal self-explanation. Advances in Neural Information Processing Systems, 36: 38620-43633 2023b.
Ma, Y., Cao, Z., and Chee, Y. M. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Process- ing Systems, volume 36, 2023.
Liu, W., Wang, J., Wang, Li, R., Qiu, Y., Zhang, Y., Han, J., and Zou, Decoupled rationalization with asymmetric learning rates: A flexible lipschitz restraint. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1535-1547, 2023c.
Mei, Y., Chen, Q., Lensen, A., Xue, B., and Zhang, M. Ex- plainable artificial intelligence by genetic programming: A survey. IEEE Transactions on Evolutionary Computa- tion, 27 2022.
Merz, P. and Freisleben, B. Genetic local search for the tsp: New results. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC'97), pp. 159-164. IEEE, 1997.
Liu, W., Deng, Z., Niu, Z., Wang, J., Wang. H., Zhang, Y., and Li, R. Is the mmi criterion necessary for interpretabil- ity? degenerating non-causal features to plain noise for self-rationalization. Advances in Neural Information Pro- cessing Systems, 37:1 17666-1166666 2024f.
Meyerson, E., Nelson, M. J., Bradley, H.,, Gaier, A., Moradi, A., Hoover, A. K., and Lehman, Language model crossover: Variation through few-shot prompting. arXiv preprint arXiv:2302.121700 2023.
Liu, W., Wang, H., Wang. J., Deng, Z., Zhang, Y., Wang, C., and Li, R. Enhancing the rationale-input alignment for self-explaining rationalization. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2218-223.. IEEE, 2024g.
Mockus, On bayesian methods for seeking the extremum. In Proceedings of the IFIP Technical Conference, pp. 400-404, 1974.
Liu, W., Deng, Z., Niu, Z., Wang. J., Wang, H., and Li, R. Exploring practical gaps in using cross entropy to implement maximum mutual information criterion for rationalization. Transactions of the Association for Com- putational Linguistics, 13:577-594, 2025.
Naveed, H., Khan, A. U., Qiu, S., Saqib, M., Anwar, S., Usman, M., Akhtar, N., Barnes, N., and Mian, A. A comprehensive overview of large language models, arXiv preprint arXiv:2307.0643: 2023.
López-lbáñez, M., Dubois-Lacoste, J., Cáceres, L. P., Bi- rattari, M., and Stützle, T. The irace package: Iterated racing for automatic algorithm configuration. Operations Research Perspectives, 3:43-58, 2016.
Qi, Z., Ma, M., Xu, J., Zhang, L. L.,, Yang, F., and Yang, M. Mutual reasoning makes smaller llms stronger problem- solvers. arXiv preprint arXiv:2448.06/955 2024.
Luo, F., Lin, X., Zhong, M., Liu, F., Wang, Z., Sun, J., and Zhang, Q. Learning to insert for constructive neural vehicle routing solver. arXiv preprint arXiv:2505. 133044 2025a.
Rajendran, C. Heuristic algorithm for scheduling in a flow- shop to minimize total flowtime. International Journal of Production Economics, 29(1):65-73, 1993.
Reinelt, G. Tsplib a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
Luo, F., Wu, Y., Zheng. Z., and Wang, Z. Rethinking neural combinatorial optimization for vehicle routing problems with different constraint tightness degrees, 2025b. URL https: / arxiv. org/ abs///b//// 2205. 25...246222 24627.
B., Barckatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, J., Ellenberg. S., Wang, P., Fawzi, O., al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468-475, 2024.
Luong, P., Nguyen, D., Gupta, S., Rana, S., and
Venkatesh, S. Adaptive cost-aware bayesian optimization. Knowledge-Basee Systems, 332:107481, 2021.
Lusby, R. M., Larsen, J., Ehrgott, M., and Ryan, An exact method for the double tsp with multiple stacks. International Transactions in Operational Research, 17 (5):637-652, 2010.
Rosenkrantz, D. J., Stearns, R. E., and Lewis, II, P. M. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563-581, 1977.
Ma, Y., L., Cao, 7., Song, W., Zhang. I.,, Chen, Z., and Tang, J. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:11096- 11 1070, 2021.
Sánchez-Díaz, X., Ortiz-Bayliss, J. C., Amaya, I., Cruz- Duarte, J. M., Conamt-Pablos, S. E., and Terashima-Marín H. A caauure-independen hyper-heuristic approach for solving the knapsack problem. Applied Sciences, 11(21): 10209, 2021.
12

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Sengupta, L., Mariescu-Istodor, R., and Fränti, Which local search operator works best for the open-loop tsp? Applied Sciences, 9(1)):3885, 2019.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks.
Advances in neural information processing systems, 28, 2015.
Shahriari, B., Swersky, K., Wang, Z., Adams, R. P., and De Freitas, N. Taking the human out of the loop: A review of bayesian optimization, Proceedings of the IEEE, 104 (1):148-175, 2015.
Voudouris, C. and Tsang. E. Guided local search and its application to the traveling salesman problem. European journal of operational research, 1 13(2):4694999 1999.
Wang, Z., Yu, J., Ma, D., Chen, Z., Wang, Y., Li, Z., Xiong, F., Wang, Y., Tang, L., Zhang, W., et al. Rare: Retrieval-augmenned reasoning modeling. arXiv preprint arXiv:2503.23511 2025.
Shi, W. W. Han, W., and Si, W. C. A hybrid genetic al- gorithm based on harmony search and its improving. In Informatics and Management Science 1, pp. 101-109. Springer, 2013.
Wei, J., Wang. X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of- of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S. Reflexion: Language agents with verbal rein- forcement learning. Advances Neural Information Processing Systems, 36, 2024.
Weston, J. and Sukhbaatar, S. System 2 attention (is something you might need too). arXiv preprint 1xXiv:2311111822 2023.
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.., Van Den Driessche, G., Schritwwieser, J., Antonoglou, I., Panneershelvam,, V., Lanetot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484 489, 2016.
Williams, C. K. and Rasmussen, C. E. Gaussian processes for muchine learning, volume 2. MIT press Cambridge, MA, 2006.
Snoek, J., Larochelle, H., and Adams, R. P. Practical bayesian optimization of machine learning algorithms. Advances in neural information processing systems, 25, 2012.
Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A. Learning improvement heuristics for solving routing problems.. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Stützle, T. and López-lbáñez, M. Automated design of metaheuristic algorithms. Handbook of metaheuristics, pp. 541-579, 2019.
Wu, Z., Qi Q. Zhuang, Z., Sun, H., and Wang, Pre- tokenization of numbers for large language models. In The Second Tiny Papers Track at ICLR 2024, 2024.
Sui, J., Ding, S., Xia, B., Liu, R., and Bu, D. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Com- puling and Applications, 36(17):9687-970 2024.
Xin, L., Song, W., Cao, Z., and Zhang. J. Neurolkh: Com- bining deep learning model with mee--emiggan-hhesgaaee heuristic for solving the traveling salesman problem. Ad- vances in Neural Information Processing Systems, 34: 7472-7483, 2021.
Swiechowski, M., Godlewski, K., Sawicki, B., and Mañdziuk, J. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 5693)22477-256,, 2023.
Yang, C., Wang, X., Lu, Y.. Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers, 2024. URL https:tp:s.. httpaaxiivvvoo org/ /bs///b//22// 22099 03409
Yao, S., Liu, F., Lin, X., Lu, Z., Wang. Z., and Zhang, Q. Multi Multi-objective evolution of heuristic using large lan- guage model. arXiv preprint arXiv:2409. 16867, 2024a.
Tan, C. S., Mohd-Mokhtar, R., and Arshad, M. R. A com- prehensive review of coverage path planning in robotics using classical and heuristic algorithms. IEEE Access, 9: 119310-119342, 2021.
Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024b.
Tuononen, J. Analysis of rebuild local search operator for tsp. Master's thesis, Itä-Suomen yliopisto, 2022.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, E., and Polosukhin, I. At- tention is all you need. Advances in neural information processing systems, 30, 2017.
Yao, Y., Liu, F, Cheng, J., and Zhang, Q. Evolve cost-aware acquisition functions using large language models. In International Conference on Parallel Problem Solving from Nature, pp. 374-390. Springer, 2024c.
13

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Ye, H., Wang, Cao, Z.,, Berto, F,, Hua, C., Kim, H., Park, J., and Song, G. Reevo: Large language models hyper-heuristics with reflective evolution. arXiv preprint arXiv:2402.01145 2024a.
Zhou, A., Yan, K., Shlapentokh-Rottman M., Wang, H., and Wang, Y.-X. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint arXiv:3310.04405 2023.
Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deepaco: neural-enhanced ant systems for combinatorial optimiza- tion. Advances in Neural Information Processing Systems, 36, 2024b.
Ye. H., Wang, J., Liang, H., Cao. Z., Li, Y., and Li, F. Glop: Learning global partition and local construction for solving large-scale routing problems in real-time. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2024c.
Yin. H.. Kononova, A. V., Bäck, T., and van Stein, N. Controlling the mutation in large language models for the efficient evolution of algorithms. arXiv preprint arXiv:2412.03250 2024.
Yu, H. and Liu, J. Deep insights into automated optimization with large language models and evolutionary algorithms. arXiv preprint arXiv:2400.20853 2024.
Zhang, D., Huang, X., Zhou, D., Li, Y., and Ouyang, W. Accessing gpt-4 level mathematical olympiad solutions via monte carlo tree self-refine with Ilama-3 8b. arXiv preprint arXiv:2406.07394 2024a.
Zhang, D.. Zhoubian, S., Hu, Z., Yue, Y., Dong, Y., and Tang, Rest-mets*: Llm self-training via process reward guided tree search. arXiv preprint arXiv:2406.03816 2024b.
Zhang, Y., Pan, Y., Wang, Y., and Cai, J. Pybench: Evaluat- ing Ilm agent on various real-world coding tasks. arXiv preprint 11X1v:2407.16732, 2024c.
Zheng, Z. and Lee, W. Reasoning-ov: Fine-tuning power- ful reasoning lims for soowledge-assisteee claim verifica- tion. arXiv preprint arXiv:2505. /2348, 2025.
Zheng, Z., Yao, S., Li, G., Han, L., and Wang. Z. Pareto improver: Learning improvement heuristics for multi- objective route planning. IEEE Transactions on Intelli- gent Transportation Systems, 2023.
Zheng, Z., Yao, S., Wang, Z.,, Tong, X., Yuan, M., and Tang, K. Dpn: Decoupling partition and navigation for neu- ral solvers of min-mat vehicle routing problems. arXiv preprint ar arXiv:2405.17277 2024a.
Zheng, Z., Zhou, C., Xialiang. T., Yuan, M., and Wang, Z. Ude: A unified neural divide-and-cone and-cquu framework for lcrge-scale combinatorial optimization problems. arXiv preprint ArXiv:2407.000 02 2024b.
14

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
A. Related Work
This section presents a detailed literature review of various research areas related to LLM, AHD, MCTS, and CO problems.
AHD
Automatic Heuristic Design, also known as Hyper-Heuristies, (Burke et al., 2013) aims to find the hest-performing heuristic among an extensive set of valid heuristics, i.c., the heuristic space. As the search strategy, AHD generally adopts the evolutionary algorithm to update heuristic algorithms automatically (Stützle & López-Ibáñez, 2019) using various effective methodologies and frameworks (Blot et al., 2016; lópez-Ibáñezz al., 2016; Burke et al., 2019). GP (Mei et al., 2022) is a prevailing and effective approach for AHD. However, it requires hand-crafted operators for heuristic mutation and crossover (Dutlo et al., 2019; Sánchez-Díaz et al., 2021).
A.2. Neural Combinatorial Optimization (NCO)
Traditional methods for NP-hard CO problems contain exact algorithms (Fischetti al., 2007: Lusby et al., 2010) and approximation algorithms (including handcrafted heuristics) (Merz& & Freisleben, 1997; Helsgaun, 2017). Integrating the deep learning technique (He et al., 2016; Vaswani et al., 2017), Neural Combinatorial Optimization (NCO) methods can obtain near-optimal results with less time consumption compared to traditional methods (Bello et al., 2016; Kool et al., 2018). These methods train neural networks for Decision-mmaing with diverse solving process (c.g., the LKH algorithm (Xin et al., 2021), the GLS algorithm (Sui et al., 2024; Hudson et al., 2021), improvement-bant based framework (Wu et al., 2021; Zheng et al., 2023), or step-by-step construction (Vinyals et al.. 2015; Zheng et al.. 2024a; Luo al., 2025a)). NCO methods can be regarded as special kind of Hyper-Heuristies (AHD) (Ye et al., 2024a), where the solving process is the general framework of AHD and training NCO methods searches for the optimal parameter settings within a parameterized heuristic space. In contrast to traditional heuristies, NCO does not require expert knowledge so some NCO methods can be applicd to multiple CO problems (Ye et al., 2024c; Zheng et al., 2024b; Luo et al., 2025b; Liu et al., 2024a; Drakulic et al., 2024; Berto et al., 2024).
Compared to NCO methods, designing heuristics with L.L.- AHD methods for NP-hard CO problems demonstrates better efficiency, better applicability, and lower implementation difficulty. Training an NCO model on a given framework would take several days even several weeks advanced GPU (Kwon et al., 2020), whereas high- sigh--uality heuristic can be generated in few hours using the LLM-based AHD methods without GPU requirements. Considering applicability, NCO methods require special framework and network designs to solve special CO problems (Kwon et al., 2021), but LLM-based AHD methods can be applied to new CO problems without task-specific adaptations. NCO methods also bring implementation difficulties when creating complicated task environments for model training (Zheng et al., 2024b). Instead, I.LM-based AHD methods only need some linguistic descriptions as the task environment. Moreover, L.L.-based AHD) methods can even demonstrate better results than NCO methods some application scenarios, shown in Table 1, Table 2, and Table 8, heuristies designed by the proposed MCTS-AHD can outperform advanced NCO methods under the same solving framework (c.g. POMO (Kwon et al., 2020). DeepACO (Ye et al., 2024b)) in 10 out of 16 test sets.
A.3. LLM for EC
EC is generic optimization principle inspired by natural evolution (Bäck et al., 1997; Eiben & Smith, 2015). The core idea of EC is generate set of candidate solutions (called populations) by simulating genetic variation and natural selection in the process of biological evolution and to gradually optimize these solutions through an iterative process over multiple generations. Some recent work focuses on stimulating the crossover or mutation operators in the original evolutionary computation framework by prompting LLMs (Lehman et al., 2023; Meyerson et al., 2023; Lange et al., 2024) or introducing L.MSS to generate auxiliary information (Ye et al., 2024a). L.LM-based EC approaches can be specified to plenty of application scenarios, including planning (Kambhampati et al., 2024), code generation (Hemberg et al., 2024), and LLM-based AHD discussed in this article (Romera-Paredes al., 2024).
A.4. LLM for AHD
LLM-based AHD methods with populations can be summarized as a four-part process (Liu et al., 2023a; Romera-Parede al., 2024; Liu et al., 2024b; Ye al., 2024a; Dat et al., 2024: Liu al., 2024d), 1): Heuristics Initialization: LLM-based AHD methods employ LLMs to generate multiple initial heuristic functions or directly handcraft seed functions as initial
15

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
heuristic functions. 2): Operator selection: Existing methods design variety of prompts corresponding to mutation or erossover operators parent heuristics. In this step, population-based methods will randomly select operator to be executed. Afterward, these methods also select the parent heuristic(s) to be operated from the current population (Yin et al., 2024). 3): New heuristic generation: Next, LLM-based AHD methods will prompt LLMs for the Python code implementation of a new heuristic function based on the description of the task P, general framework, the prompt of selected operators, and the selected parent heuristics. 4): Population update: As the final step in each iteration, each newly generated heuristic/ h will run on the evaluation dataset D to obtain g(h). The invalid heuristics will be discarded. The population will update according to performances g(-) of heuristics. The last three processes will run loop until the number of heuristic evaluations reaches a given budget T.
Yao et al. (2024a) considers multiple objectives (for example, heuristic performance and execution efficiency) in LLM-based AHD. This article focuses only on heuristic performances, so we do not involve it as baseline.
A.5. LLM for CO
Besides LLM-based AHD, there are also two ways to utilize LLMs for CO problems, including LLM-as-optimizer methods and (fine-tuned) LLM-as-solver methods. Yang et al. (2024) first develop LLMs as the optimizer for TSP tours. LLM-as- optimizer methods (Guo et al., 2023; Liu et al., 2024e) initially generate several feasible solutions for a single CO instance. Then, the LLM iteratively prompted for better solutions by taking the existing top-performing solutions and their objective values as in-context information. Then, the newly generated solution in each iteration is evaluated for its objective value and inserted back into the in-context. LLM-as-solver methods directly treat LLMs as end-to-end CO instance solvers (Abgaryan et al., 2024; Jiang et al., 2024). These methods consider LLMs as pre-trained NCO models and establish environments to fine-tune LLMs for better performances on CO instances.
LLM-based AHD methods, especially MCTS-AHD, are still the most promising directions for solving complex NP-hard CO problems. LLM--as-ptimmizer methods pose high demand for LLM's reasoning ability and knowledge storage, and current LLMs (Huang et al., 2024) can only offer extremely limited results on infamous and large-scale CO instances (refer to comparisons in Table 14). It should be noted that Kambhampati et al. (2024) also recommends using L.MSs for module design instead of instance solving for planning tasks, where the module design process corresponds to the idea of LLM-based AHD. (Fine-tuned) LLM-as solver methods (Abgaryan al., 2024; Jiang et al., 2024) require additional training and face difficulties in configuring training environments. Moreover, unlike NCO models that represent each coordinate value as piece of embeddings, LLMs face challenges in tokenizing high-precision coordinate numbers in linguistic way (Wu et al., 2024).
A.6. LLM Inference with MCTS
With the great success of CoT (Wei et al., 2022) and ToT (Yao et al., 2024b) in enhancing the ability of LLM reasoning, a series of System 2 techniques (Weston & Sukhbaatar, 2023) have been proposed in various applications (Wang et al., 2025; Zheng & Lee, 2025). Among them, MCTS has recently emerged as a powerful technique to enhance the reasoning capabilities of LLMS (Zhang et al., 2024b). These methods mainly construct MCTS in two ways (Feng et al., 2023), representing each node with a complete answer refined from the parents (Zhang et al., 2024a; Zhou et al., 2023) or a reasoning step following its parents (Qi et al., 2024). The MCTS-AHD in this paper belongs to the former, where each node represents a complete piece of executable function and its description. When dealing with commonsense QA or mathematical problems, System 2 techniques often use self-evaluation for MCTS simulation (Zhang et al., 2024a), but MCTS-AHD does not involve the self-evaluation or rollout (Silver et al., 2016) since AHD methods can easily obtain performances ((-) for tasks.
A.7. LLM for Code Generation
Recent LLMs have strong coding capabilities (Zhang et al., 2024c), and some recent papers have designed a series of structures based on reflection and MCTS (Dainese et al., 2024; DeLorenzo et al., 2024) to promote this ability. The LLM for code generation is similar domain to L.Le- AHD. Compared to code generation tasks aiming at passing algorithm tests, LLM-based AHD faces significantly more challenges in finding the optimal heuristic (Liu et al., 2024c). LLM-based AHD needs consider more on exploring the entire heuristic space and optimizing code performance by modifying parameter settings and detail designs.
16

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
As similar method to this paper, Brandfonbrener al. (2024) uses MCTS with the progressive widening technique for code generation, but its specific MCTS and progressive widening procedure are totally different from the proposed MCTS-AHD.
A.8. Connection to General LLM Applications
Nowadays, language models are dominant in wide range of Al applications, and there are increasing concerns about their interpretability (Liu et al., 2025; 2024g), causal reasoning (Liu et al., 2023b; 2024f), and robustness (Liu et al., 2023c; 2022). We acknowledge its growing importance and will consider it in the future of our research.
B. Definition of Tasks
B.1. NP-hard CO Problems
This paper conducts experiments on six NP-hard representative CO problems, including TSP, CVRP, KP, MKP, ASP, and BPP. For BPP, we consider both its online setting (online BPP) and offline setting (offline BPP). In this section, we will introduce the mathematical definitions of these CO problems in detail.
Traveling Salesman Problem TSP is one of the most representative COPs (Biggs, 1986), which aims at finding the shortest path to visit each city once and returns to the starting point. An N-node TSP instance ins contains distance matrix (D = J = l..... N, = 1...,N? N) E RNN,, where dj.x denotes the cost between nodes k and j. the goal is to minimize the following objective function (Zheng et al., 2024b):
N-1 decoess + day
minimize f(8)
Σ 1=1
(8)
where the solution ($1, ,....., .N) is permutation of all node indexes. All the feasible solutions satisfy the constraint of the degree of each node being two and containing no loop with lengths less than N.
Capacitated Vehicle Routing Problem CVRP aims to plan several to depot, meeting the demands of multiple customers, and minimizing the total travel distance. Each CVRP instance contains a depot (the 0-th node) and several customers. With a distance matrix (D = dj.k.J = 0,..., N, k = 0..., N), the CVRP can be expressed as follows:
vehicles starting at and returning
W11
minimize
f(8) = Σ C(P),, C(P)= = Σ d Meieeee + d Phyinb"
1=1 s.t. 0 0 $ Σ sC fl. fl..... icp
(9)
where s is a solution representing the complete route of vehicles and consists of sub-routes & = ppt.pp,..... pi....,,,p". sub-route p (p) , Phy): j {I,...,4} starts from the depot 89 and goes back to 8g. n, represents the number of customer nodes in it. n Σj=1 my is the total number of customer nodes; & denotes the demand of node i; C' denotes the capacity of the vehicle. This paper follows the settings of ReEvo (Ye et al., 2024a) when generating CVRP data sets, fixing the depot coordinates to (0.5, 0.5).
p²}. Each
0-1 Knapsack Problem KP is a typical CO problem, consider loading items of a maximum total value to a W -caapacity knapsack, Each item can only be picked once. KP solution S 21,2,..., N) records the selection item indexes. A KP instance ins records the value i Uniform(O, 1) and weight w; Uniform (0, 1) of each candidate item. We follow the settings in Kool et al. (2018) in generating instances and have W 25 for 100-item and 200-item KP instances and W- 12.5 for 50-item ones.
We adopt a traditional greedy heuristic algorithm for the Greedy Construct in Table 1 (Kwon et al., 2020). This algorithm starts with an empty knapsack (as solution s) and recursively adds the item that meets the capacity limit and has the maximum malue-weight-ratte (%)) from the remaining items into the current knapsack (add this item to solution s as well). The algorithm will stop when the knapsack can no longer load more items.
17

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Multiple Knapsack Problem We follow the ReEvo (Ye et al., 2024a) settings for MKP instances, uniformly sampling the value H4 Uniform(O, 1) and weight for the knapsack Waj Uniform(0, 1), {1, ( m),j (l,...,, We also uniformly sample the capacity of the m knapsacks C, E (I,..., m from (maxy Wijs Σ; way)
Admissible Set Problem ASP constructs set of n-dimennional vectors A (called admissible set) where vectors E AA C {0, 2, and the number of non-zero items is constrained to be ASP aims to maximize the size of the admissible set A under a certain constraint that for any three distinct vectors there is a coordinate in which their three respective values are {0, O, 1}. {0, 0, 2}, or {0, 2,). We formulate the objective function and constraints as follows:
maximize
[A]
(10)
s.t.
Σ
Ia. + 0] w, Bi (L....,n)). fa. c. E (1000.),,
A,
where Ma; # 0] represents the number of non-zero items vector ( an.)
Bin Packing Problem BPP a classic NP-hard CO problem that aims to place set of items with different sizes into as few W-capacity bins as possible. Online BPP requires making an immediate decision on which bin to place once new item is received, while offline BPP does not require this. We follow Romera-Parede et al. (2024) and Liu et al. (2024b) to generate WeiBull instances for online BPP and follow Ye al. (2024a) to generate offline BPP instances with W 150 and the size of items uniformly sampled from 20 to 100.
B.2. Cost-Aware Acquisition Function Design in Bayesian Optimization
Please refer to Appendix C.4 for relevant introductions.
18

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
C. Definition of General Frameworks
For NP-hard combinatorial optimization (CO) problems, we employ MCTS-AHD to design key functions within given of MCTS-AHD, we include three general frameworks for CO
general frameworks. To verify the in experiments, e.g., step-by-step construction, GLS, and ACO, as well as the CAF design task using BO as the outer framework. Next, in this section, will introduce these involved general frameworks in detail.
C.I. Step-by-Step Construction
Step-by-step construction is an intuitive framework capable of handling almost all CO problems. It considers gradually extending a solution (s) of an NP-hard CO problem from seratch until a complete and feasible solution is constructed. In each step of the construction (i.e., solution extension), the step-by-step construction framework assigns priority to each candidate (decision variable), and the candidate with the highest priority will be added to the solution.
In the step-by-step construction framework, MCTS-AHD and LLM-based AHD baselines design the same key heuristic function that will be repeatedly executed to calculate the priority of candidates. This paper adopts the step-by-step construction framework for solving four CO problems, including TSP, KP, ASP, and online BPP. Built on this framework, Nearest-greedy is prevailing manually designed heuristic for TSP that scores candidate nodes based sorely on their distance from the current node. Similarly, a greedy process that evaluates KP items based their value-weight ratio is also commonly used. We consider these two handcrafted heuristics as the Greedy Construct baseline in Table 1. Additionally, in both TSP and KP, there is a series of NCO methods that train deep neural networks based on the step-by-step construction framework. Their neural networks can be considered as more efficient and sophisticated key functions for evaluating all candidate nodes or items. For involved CO problems, the detailed settings of the key heuristic function in the construction frameworks are as follows:
For TSP, MCTS-AHD is responsible for designing a function to select the next node to visit based on node coordinates, starting point, distance matrix, and all unvisited nodes.
For KP, MCTS-AHD is responsible for selecting the next item to add to the knapsack based on the value and weight of all items to be chosen and the remaining capacity of the knapsack.
For ASP, the key function provides a score for the current vector to determine to what extent it is suitable to added to the admissible set (A).
In MCTS-AHD, the function required for online BPP gives a preference score for adding the current newly input item to each bin based on the item's 's size and the remaining capacity of all bins.
C.2. Ant Colony Optimization
ACO is meta-heuristic and evolutionary algorithm (EA) inspired by the behavior of ants find the shortest route between their colony and food sources (Dorigo al., 2006; Ansari & Daxini, 2022).
ACO records pheromone matrix 7 and heuristic matrix 77. Each item in the matrix Tij indicates the priority of including that edge (i. in solution. The pheromone trails are iteratively updated based on the quality of the solutions found, encouraging future ants to follow better paths. The heuristic information on each edge (i.e., Tk5) is a problem-specific measure that indicates the immediate benefit of choosing a particular path. For solving TSP with ACO and a manually designed heuristic matrix, 7h is often set to the inverse of the distance between cities and j. that is, Mi d., LLM-based AHD methods are employed to design a more effective heuristic matrix v) based on the necessary ppoecec- inputs.
1
Ants construct solutions by moving from node to node, probabilistically choosing the next node based on a combination of pheromone and heuristic information. After all the ants have constructed their solutions, the pheromone levels update. An ACO iteration typically involves solution construction, optional local search, and pheromone update. By iteratively applying these steps, ACO algorithms can effectively explore the solution space and converge toward optimal or near-optimal solutions for ha-hard CO problems. We follow the settings in Ye et al. (2024a), evaluating MCTS-AHD by designing the heuristic metrics generation functions for TSP, CVRP, MKP, and offline BPP as follows:
For TSP, the function inputs the distance matrix. We adopt the parameter settings in ReEvo (Ye et al., 2024a), the number of ants is set to 30 during heuristic evaluation (when evaluating on the evaluation dataset D), and the number
19

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
of iterations is 100. In testing, we allow more optimization for all ACO baselines and increase the number of iterations to 500.
Functions for CVRP input the distance matrix, coordinates and demands of nodes, and the capacity C. Numbers of ants and iterations are set the same as TSP.
For MKP, the function inputs the values and weights of items. The number of ants is set to 10. The number of iterations is 50 for running on the evaluation dataset D and 100 for test sets.
For offline BPP, the function inputs the size of items and the capacity of bins. The number of ants is set to 20, The number of iterations is 15 for running on the evaluation dataset D and 100 for test sets.
ACO for Black-box Settings Black-box settings are proposed in ReEvo (Ye et al., 2024a) as novel application scenarios for LLM-based AHD. The black-box settings do not provide descriptions for the task P and the predefined general framework for heuristic design. The names of inputs in the to-be-designed key function will also be erased. These settings can simulate the application scenarios that cannot find any linguistic descriptions. This paper will evaluate AHD methods on both regular settings and black-box settings in Appendix F.10. For better initial perception of the heuristic space H, we set NN = 10 for MCTS-AHD in designing heuristics with black- box settings.
C.3. Guided Local Search
The GLS framework uses local search algorithms (e.g., using 2-opt operators) for solution iterations and introduces a penalty mechanism to guide the search process escaping local optima. It shows capability on a wide range of CO problems with manually designed key functions (Voudouris & Tsang, 1999; Alhindi et al., 2019). We use LLM-based AHD methods to matrices in the showledge-guider local search (KGLS)
design the key heuristic function for generating knowledge-basee framework (Aroll & Sörensen, 2019). Taking the TSP as example, KGLS maintains TSP solution while also preserving the ever-encountered best- best-performing solution. In each iteration of KGLS, KGLS first perturbs the TSP solution based on the generated knowledge matrix and then performs local searches using both 2-opt and relocate operators (Sengupta et al., 2019; Tuononen, 2022). We conduct 1200 iterations when running GLS heuristics on both the heuristic evolution process and testing for each CO instance. The number of perturbations to each solution is set to 30.
C.4. Bayesian Optimization
BO (Shahriari et al., 2015) is a method for solving the black-box optimization problem where the objective is to find the global minimum of an unknown function f fx) over a search space X', represented as:
x"
arg min fx). x
(11)
Two core components of BO are the probabilistic surrogate model and the acquisition function (Mockus, 1974; Lam et al., 2016). In each iteration of BO, the probabilistic surrogate model is first trained using the available samples in the search space (BO typically employs Gaussian process (GP) model (Williams & Rasmussen, 2006)). Then, the acquisition function utilizes the posterior information of the surrogate model to guide the subsequent search. Specifically, the next solution to evaluate at iteration 1, denoted as x,, is chosen by maximizing the acquisition function:
= arg max (xx, Mt), xEX
(12)
where Mt represents the information from the surrogate model at iteration f, and axx, .Ma) represents the acquisition function value x. After performing an expensive evaluation at x,, this point added to the available training dataset of samples. BO iteratively executes surrogate benchmark training and sampling based on the acquisition function until termination criterion is met. Finally, the best solution among those evaluated samples is returned as the solution to the problem.
This article focuses on the cost-aware BO (Yao et al., 2024c; Luong et al., 2021; Snock et al., 2012), which takes the number of expensive sample evaluations as the termination criterion. It not only focuses on optimizing the objective function but also considers the cost of evaluating the objective function. This method beneficial in practical applications. especially when the evaluation cost of the objective function is high, like experimental design and hyper- parameereee optimization of
20

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
machine learning models. BO employs a CAF the acquisition function in cost-aware settings to manage the sample efficiency, which is the design focus of the cost-aware BO methods. We adopt LLMM-based AHD methods for designing the CAF. During CAF evolutions, MCTS-AHD and EoH run 5 independent cost-aware BO trails with at most 12 function samples. In testing, we set the evaluation budget to 30 and report the average result of 10 trials.
D. Details of Evaluations & Experiments
In this section, we provide more detailed introduction to the setup of evaluation budgets T and evaluation datasets D used in the heuristic evaluation phase. Evaluation Settings in this paper are generally adopted from Funsearch PRomera-Paredes et al., 2024), EoH (Liu et al., 2024b), and ReEvo (Ye al., 2024a).
The Setting of T. The number of generations in EoH is set to 20, Its population size is 20 for online BPP and 10 for TSP and FSSP (810 evaluations for TSP, FFSP, and 1620 for online BPP). So, this paper designs a similar number for the maximum number of evaluations T, setting the T to 2,000 for online BPP (under the step-by-step construction framework) and setting 7 = 1, 000 for other tasks.
The Setting of D. For most involved tasks, MCTS-AHD adopts the same settings in LLM-based baseline methods (e.g.. EoH, ReEvo, Funsearch) for the evaluation dataset D. As a special case, for online BPP under the step-by-step construction framework, baselines adopt 5 5,000-item WeiBull BPP instances with W=100. However, such a dataset setting often leads to heuristics that completely fail at other scales (e.g.. 5,000-item with W=500), so we used a varying-scale setup (Gao et al., 2024) that included data with different characteristics in the evaluation dataset D. The detailed settings of the evaluation datasets are exhibited in Table 6
Pre-Trained Large Language Models. The pre-trained LLM is 111-4o--ini-2222-07-2 for GPT-44-mini and gpt- 3.5 3.5-uurb--0225 for GPT-3.5-turbo, also use (laule-3.5-sommee222244122 for Claude-3.5-somme and DeepSeek-v3, Qwen2. ----eo--d----sttreeeee in Appendix F.5.
Table 6. Compositions of the evaluation dataset 1 involved general frameworks and tasks.
Framework
Step-by-step Construction
Task
TSP
KP
Evaluation dataset D
64 50-node TSP instances
64 100-item KP instances (W=25)
Framework
Step-by-step Construction
Task
ASP
Online BPP
I instance (n=15, 10)
4 WeiBull BPP instances
1.000-item instance with W=100
Evaluation dataset D
1, 1,000-item instance with 5=500
5. 5,000-item instance with W=100
5,000-item instance with W=500
Framework
ACO
Task
TSP
CVRP
Evaluation datuset D
5 500-node TSP instances
10 50-node CVRP instances
Framework
ACO
Task
MKP
Offline BPP
Evaluation dataset D)
5 100-item MKP instances (m=5)
5 500-item BPP instances (W=150)
Framework
GLS
CAF Design
Task
TSP
10 TSP200 instunces
2 synthetic instances The Ackley instance The Rastrigin instance
Evaluation dataset 1)
Other Parameters. MCTS-AHD adopts the same set of parameters for all tasks involved, and here we will summarize the other parameters of MCTS-AHD in the evaluation phase. The temperature of LLMs is fixed at 1.0. The number of initial nodes N, = 4, the maximum depth of the MCTS tree H = 10, the number of mutations in each expansion = 2, the maximum number of references in action el p E (2, 3, 4, 5, the initial exploration parameter X = 0.1, and the progressive widening parameter a = 0.5. We consider X 0.1 to be the most important setting of these and therefore ablate the main text, and we discuss the rest of the settings Appendix F.9 to illustrate that none of these parameters are sensitive.
21

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
E. Detailed Methodology
E.1. Prompts MCTS Actions
MCTS-AFH contains distinct actions il, el, c2, ml, m2, and sl for MCTS initialization and expansion. Next, we describe the meaning and prompt engineering of each action. These prompts contain the problem description, existing heuristic functions as contexts, function name, input name, and output name according to the task P and the current MCTS. We execute the first LLM call through the following action prompts obtain design idea and its Python implementation for heuristic function. The rest of this subsection provides examples for prompts, in which highlight the unique part of each prompt in red colors (for all actions, we use the TSP task and the step-by steppb construction framework as an example):
Initial Action i1: Action il represents directly getting idea of designing valid heuristic function from scratch and Python implementation directly through LLM.
Prompt for Action i1
Solving Traveling Salesman Problem (TSP) with constructive heuristies. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
First, describe the design idea and main steps of your algorithm in sentence. The description must be inside brace outside the code implementation. Next, implement it in Python as function named 'select next node'.
This function should accept input(s): "current node', 'destination node', 'unvisited nodes', 'distance matrix'. The function should return output(s): "next_node". The select_next_node function takes as input the cur- rent node, the destination node, a set of unvisited nodes, and distance matrix, and returns the next node visit.
Do not give additional explanations.
Crossover Action el: Action inputs several distinct heuristic functions with their codes, their descriptions, and their performances. The prompt asks the LLM to get an idea for new heuristic function different from all these heuristic functions and corresponding Python implementation. The heuristics are selected from 2 to subtrees of the MCTS root.
Prompt for Action e1
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
have existing algorithms with their codes as follows:
1 algorithm's 's description, its corresponding code and its objective value are: # Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code on evaluation dataset.
No.k algorithm's 's description, its corresponding code and its objective value are: Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code evaluation dataset.
Please create a new algorithm that has a totally different form from the given algorithms. Try generating codes with different structures, flows or algorithms. The new algorithm should have relatively low objective value.
First, describe the design idea and main steps of your algorithm in one sentence. The description must inside
22

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
brace outside the code implementation. Next, implement in Python as function named select_next_node
This function should accept input(s): ponreent_node 'destination _odee, 'unvisited _ndess, 'distance distance.matrixx. The function should return output(s): 'next_node'. The select.next.node function takes input the cur- rent node, the destination _noii, a set of unvisited nodes, and a distance matrix, and returns the next node to visit.
Do not give additional explanations.
Crossover Action e2: Action e2 inputs one parent heuristic function (with its code, description, and performance) and one reference heuristic function sampled from a 10-size top-performing elite heuristic function set E (we follow Liu et al. (2024b) in selecting heuristic function from the set, heuristic function the set with rank r; will be sampled with a priority p. + 110) ). The following prompt asks the LLM to design new heuristic function based the parent one and learn from the advantageous designs of the reference one.
Prompt for Action e2
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
have existing algorithms with their codes as follows:
1 algorithm's description, its corresponding code and its objective value # Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code on evaluation dataset.
No.2 algorithm's 's description, its corresponding code and objective value are: # Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code evaluation dataset.
Please create a new algorithm that has a similar form to the No.2 algorithm and is inspired by the No. algorithm. The new algorithm should have an objective value lower than both algorithms.
Firstly, list the common ideas the No.1 algorithm that may give good performances. Secondly, based on the common idea, describe the design idea based the No.len(indivs) algorithm and main steps of your algorithm in one sentence. The description must be inside brace. Next, implement it in Python function named 'oel
This function should accept input(s): 'current node', 'destination node', 'unvisited nodes", 'distance matrix'. The function should return output(s): 'next node". The select.next node function takes as input the cur- rent node, the destination node, a set of unvisited nodes, and distance matrix, and returns the next node visit.
Do not give additional explanations.
Mutation Action ml: Action ml inputs heuristic function with its description and code, it attempts to introduce more new mechanisms and new formulas program segments to the input code through LLM.
Prompt for Action m1
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
23

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
have algorithm with its code as follows.:
# Its Description
# Its Python Code Implementation of A Function
Please create a new algorithm that has a different form but can be a modified version of the provided algorithm. Attempt introduce more novel mechanisms and new equations or programme segments.
First, describe the design idea and main steps of your algorithm in sentence. The description must be inside brace outside the code implementation. Next, implement it in Python function named select_next_node"
This function should accept input(s): 'odrrent_node', 'destination_nod"
wevisited_nndeer 'distance. 'distance.matrix' mmatrx'.. The function should return output(s): 'next_node'. The select_next_not function takes as input the cur- rent node, the destination_node a set of unvisited nodes, and a distance matrix, and returns the next node to visit.
Do not give additional explanations.
Mutation Action m2: Action m2 also inputs the description and implementation heuristic function, it attempts generate heuristic function with different parameter settings through LLM.
Prompt for Action m2
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
have one algorithm with its code as follows.:
Its Description
Its Python Code Implementation of Function
Please identify the main algorithm parameters and help me in creating algorithm that has different parameter settings equations compared to the provided algorithm.
First, describe the design idea and main steps of your algorithm in one sentence. The description must be inside a brace outside the code implementation. Next, implement it in Python as function named 'select next node'.
This function should accept input(s): 'odr'ent 'destination_node 'unvisited 'distance .matrri'..a''. The function should return output(s): 'next_node'. The select_next_noot function takes input the cur- rent node, the destination node, set of unvisited nodes, and distance matrix, and returns the next node to visit.
Do not give additional explanations.
Tree-Path Reasoning Action s1: Action sl is tree-special action that takes all diverse heuristic functions (with their codes, descriptions, and performances) on leaf-to-root tree path as input. The following prompt asks the LLM to get a better heuristic function based on these inputted in-contexts. When there is only one unique heuristic function the tree path, we do not perform the action
Prompt for Action s1
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
24

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
have existing algorithms with their codes as follows:
No.1 algorithm's 's description, its corresponding code and its objective value are: # Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code on evaluation dataset.
No.k algorithm's ss description, its corresponding code and its objective value are: Its Description
# Its Python Code Implementation of A Function
Objective value: # The Objective Value of the heuristic algorithm with the python code evaluation dataset.
Please help me create new algorithm that is inspired by all the above algorithms with its objective value lower than any of them.
Firstly, list some ideas in provided algorithms that are clearly helpful to better algorithm. Secondly, based on the listed ideas, describe the design idea and main steps of your new algorithm in one sentence. The description must be inside brace. Thirdly, implement it in Python as a function named 'select_
This function should accept input(s): 'noreent_node', 'destination_ndee 'unvisite__node The function should return output(s): 'next node'. The select next node function takes as input the cur- rent node, the ddestination_node a set of unvisited nodes, and a distance matrix, and returns the next node to visit.
iissanceemmarix
Do not give additional explanations.
E.2. The Prompt of the Thought-Alligneent Process
After obtaining the design idea and implementation by calling LLMs with the previous action prompts, MCTS-AHD will conduct the second LLM call. In the second LLM call, we will input the design idea and implementation obtained from previous LLM call into the description.
prompt as shown below for more detailed and correlated heuristic function
The thought-alignment Prompt
Solving Traveling Salesman Problem (TSP) with constructive heuristics. TSP requires finding the shortest path that visits all given nodes and returns to the starting node.
Following the Design Idea of a heuristic algorithm for the problem and the code with function name 'select next node" for implementing the heuristic algorithm.
The select_mme ceccct_ext______eeee node function takes as input the current node, the destination _odee set of unvisited nodes, and distance matrix, and returns the next node to visit.
Design Idea:
The Design Idea
Code:
# The Python Code Implementation of A Function
The content of the Design Idea idea cannot fully represent what the algorithm has done informative. So, now you should re-describe the algorithm using less than 3 sentences. Hint: You should reference the given Design Idea and highlight the most critical design ideas of the code. You can analyse the code to describe which variables are given higher priorities and which variables given lower priorities, the parameters and the structure of the code.
25

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
E.3. Examples of LLM Outputs
This subsection provides two examples of LLM oulput designing heuristics with MCTS-AHD. Every single LLM-based heuristic generation includes two LLM calls. The first call generates the Python code of heuristic function with action prompts and the second call generates linguistic descriptions for heuristic functions with thought- -alggtt-ligmment prompts.
Example of LLM output #1: Designing TSP heuristics within the step-by-step solving framework.
First Call Input:
The prompt for MCTS-AHD action.
First Call Output:
{The new algorithm will utilize a hybrid approach that weighs the immediate distance (1.2) more heavily while still considering the connection strength (0.6), ensuring that we select paths that are both cost-effective the short term and reasonable in the longer term by optimizing the total accumulated cost.)
def seeect__eeeeeeeee cic____ex______ _ood__ooddeeoo courrent_node, destination_nen
unvisited_nodes,
distancc_matrixx if not unvisited_nodes: return None
next_node None sin__oobined_com
float (finf()
for candidate unvisited nodes:
immediate_distance distance = distance baceaance_maariileeeeaa connection strertgggssstttthhhhhh = sum (distance matrix candidaat]e [n] for in unvisited nodes if 1))
node] [candidate]
!= candidate) / imax(1en (unvisited_nodes)
total_cost immediate_deee seedlattedistacee current_camee current_candicaate candidate remaining_nodes = anvisited_nodes (candidate)
while remaining_nodes:
best gest_next_nowe = min (eammrrringnnoooee key=lambda node: distance_matrid
ourrent_candidatel [node]] total_cost +-
(best_next_node)
current_candi best_next_nocc
remaining_nodes remove (best_next_nodds
total_cost +=
(arreecctttee [destination_nont
combined_cost (1.2 immediate_Gistance) (0.6
1))
total_cost
if combined_coss < min_combined_cost
nii__combined_cos combined_cost next_node candidate
return next_node
Second Call Input:
The prompt of the thought-alignment process.
Second Call Output:
The algorithm utilizes hybrid approach solve the Traveling Salesman Problem by prioritizing immediate distance (with weight of 1.2) over connection strength (with weight of 0.6) to select the next node visit from set of unvisited nodes. It calculates combined cost that considers the immediate distance to a candidate node, the average connection strength to remaining unvisited nodes, and the total cost of visiting all remaining nodes before returning to the destination. The algorithm systematically evaluates candidate nodes based on this combined cost, ensuring a balance between short-term efficiency and overall path optimization.
26

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Example of LLM output #2: Designing CAF for Cost-aware BO.
First Call Input:
The prompt for an MCTS-AHD action.
First Call Output:
{The new algorithm evaluates the potential improvement the best observed value while incorporating compound risk factor based on both uncertainty and evaluation costs, adjusts the utility through combination of historical performance scaling, and normalizes the results across the test inputs to favor those with high expected returns and low associated costs.}
import torch
def utility (train_x, train_y, best_x, best_y, test_x, mean_test_y, std_test_y, cost_test_y, budget_used, budget_total): # Calculate remaining budget
remaining_budget - budget_total budget_used
Adjust the mean based on uncertainty risk factor = std_test_y (sta_test. + 1e-10) adjusted mean = mean_test
(1
Improvement over the best observed value Improvement_score meea best_y
Calculate cost-effectivenes: with exponential decay based evaluation costs jest_effectiveeess (improvement_scors / (cost_test_y le-10)) torch.exp cost_test_y (remaining le-10))
Eistorical risk/variance for budget scaling
cnttorical_varianee torch. (train unbiased=False)
bodget_scaling remaining_buager (remaining Aistorica_vvarine le -10)
Combine c with budget scaling final_utilio cost_ effeettieeis budget_scalin
Normalize the utility values ut utility_value = (Sinal_utilit) torch torchh.iin(fnaallullll)) / (torch.max (
final_utility) torch.min (final_utility) + 1e-10)
return atility_valus
Second Call Input:
The prompt of the thought-alignment process.
Second Call Output:
The algorithm evaluates potential improvements over the best observed value by leveraging a risk-adjusted mean of the predicted function, where uncertainty is factored in through the standard deviation. incorporates cost- effectiveness by weighing the expected improvement against evaluation costs, applying an exponential decay influenced by the remaining budget. Finally, the utility values are scaled by historical variance to prioritize inputs that promise higher expected returns while accounting for their associated costs, ultimately normalizing the output to facilitate comparison across test inputs.
27

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
E.4. Total Algorithm
Algorithm I provides pseudo-code for the proposed MCTS-AHD method, which provides details of the flow and parameter settings. The procedure of MCTS-AHD mainly includes initialization process (up to line 8) and four-stage MCTS process (line& to line 39).
Algorithm MCTS-AHD. Monte Carlo Tree Search for Automatic Heuristic Design
Input: Evaluation dataset D, The number of initial nodes Ni. Maximal evaluation times T, Maximal tree depth H 10, Action set {il,el el,
ellee e2, ml, m2, ,1), The number of mutation in each expansion k 2, The number of subtrees in action 0.5.
el {2, 4, 5). UCT initial exploration parameter λ 0.1, Progressive widening parameter
2: Output: Code C" for the best found heuristic functions h" I/ The virtual rool node does not contain any codes. // t represents the current number of evaluations. 5: Initialize a code and its description with Action il, and get all other N, - initial nodes with Action el.
3: Initialize a virtual root node n
4: Set 4-00 0.
6: Omaz + -1c5, Qmin
7: Link all the N, nodes to the MCTS root.
8: Evaluating the newly generated codes with evaluation dataset D, setting the Q, N values for these nodes.
9: while & < 'T' do
10: À + Ào * -
|/ Exxploration-decayy
// MCCS Selection Stage: Selecting a node to expand [ Z [Children(n,) then
11:
Expand n, with action el, doing simulation and backpropagation.
Progressive Widening for the root node. // Updating evaluation time t.
t t+1+
14:
end if
f- Yr, 15:
// Selecting from root node.
16: while ne is not a leaf and its depth is less than H do
17:
Te + arg chileech))en(n...) Q(c)--muin +
ia Nin++]
Omaa Qusin
N(c)
18:
[n.)) 2 [Children(n.) (n.) then
19:
Expand ne with action c2, doing simulation and backpropagation. 1+1
PProgressive Widening non-root nodes.
// Updating evaluation time
21:
end if
22:
end while
// MCTS Expansion Stage: Add new nodes to the tree
23:
Conducting action c2, sl, times ml, and times m2 to the n. by LLM. // MCTS Simulation Stage: Gel Q values for newly expanded nodes
24:
Evaluating the newly generated heuristic function with evaluation dataset D, Setting the Q N values for these nodes.
25:
better heuristic function is found, update the best found code C* with its implementation. Updating the elite set F. if new top 10 heuristic functions emerge.
27:
28:
+ t 2k 2.
I/ Updating the number of evaluations t. // Updating qmaz and gmin-
29:
for Children(n.)) do
30:
amaz t max (amx( Q(c)), Jmin + min (9min Q(c) end for
31:
// MCTS Backpropagation Stage: Update Q and N values
32:
while n. is not the root n, do
33:
((n.) +- maXagChilden(n.)) Q(c)
I/ Updating the Q value. // Updating visit times.
34:
(ne) + ((n))) + 2k +
35:
The + Father(n.))
36:
end while
Q(n,)) + max,gchiMren(s..) Q(c)
// Updating the value. Updating visit times.
( NNNNn, 2k +
39: end while
40: Return: The best found code C for heuristics.
28

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
F. Experiment Details
E.. Designing Heuristics with the Step-by-step Construction Framework for ASP
We apply LICTS-AHD to another NP-hard CO problem ASP (Romera-Paredes, et al., 2024). ASP constructs a set of n-dimensional vectors A (named an admissible set) in which each vector {0, 1, and the number of non-zero items in each vector is constrained to be w. ASP aims to maximize the size of the admissible set A with another certain constraint between the vectors in the admissible set (detailed in Appendix B.1). L.LM-based AHD methods
responsible for designing priority function: {0, 1, 2 + R. which is executed iteratively to construct A step by step. We use single instance with n=15 and w=10 as the evaluation dataset D. The experiments in Table 7 test the heuristics on four different scales where MCTS-AHD also exhibits the best results compared to other existing LL.M-based AHD methods in most test sets.
Table Designing step-by-step construction heuristics for ASP. Each LLM-based AHD method run three times for its average performance. The size of A has a theoretically upper bound (.) and we take this value as Optimal. The test set of each scale contains only one instance and we underline the in-domain scale. The best-performing method for each LLM model is shaded and the overall best result in bold.
Task
ASP
Methods
n= 2,u=7
N= 15,w=10:
n= 1,0=1::
n=24, 17:
Optimal
792
3003
43596
237984
LLsM-based AHD: GPT-3.5-turb
Funsearch
612.0
2057.0
10664.0
37323.0
LoH
772.0
2759.0
30869.3
147323.0
MCTS-AHI (Ours)
784.0
2784.0
30608.0
150729.0
LaMe AHD: GPT-4o-mini
Funsearch
622.0
2410.0
10758.7
43217.0
ReFvo
784.0
2733.0
25753.7
115709.0
HSEvo
744.0
2307.0
18756.3
81185.0
BoH
779.0
2776.0
32716.7
160024.0
MCTS-AFI (Ours)
775.0
2780.0
32900.3
163832.0
F22 Guided Local Search Framework
To evaluate the performance of (2024a) in using MCTS-AHD for the key heuristic function to generate the knowledge matrix of KGLS (Arnold et al., 2019) and employing 10 TSP200 instances for performance evaluations (as D). The number of local search iterations in GLS is set to 1200 for both heuristic designs and heuristic testings. We compare MCTS-AHD to LLM-bbsee AHD baselines, NCO methods with GLS frameworks, and the original KGLS with manually designed heuristic functions. As shown in Table 8, the proposed MCTS-AHD refine the KGLS both the TSP200 and TSP500 test sets and MCTS-AHD generally outperforms other LLM-based AHD methods using GPT-4o-mini as the black-box pre- LLM.
in designing the penalty heuristics of the GLS framework, we follow Ye et al.
Table Designing heuristics within the GLS general framework for solving TSP. KGLS, NCO methods, and heuristics from LLM- based AHD allow 1200 iterations of local scarch. The test sets of TSP with N=100 and = 1,000-instande test sets from Table I and for TSP500 and TSP1000, we prepare two 64-instance test sets. For NeuralGLS* and GNNGLS*. we use the results reported in Ye et al. (2024a). The table shows the gaps to optimal and each LLM-based AHD method is three times for the average optimality gaps.
TSP-GLS
N=
100
200
500
1,000
Optimal KGLS
0.0000%
0.0000%
0.0000%
0.0000%
0.0034% %
0.2270%
0.9578%
1.5348 %
NCO methods with the GLS general framework
VRP-DACT (Ma al., 2021)
1.7943%
91.9267%
NeuOpt (Ma el al., 2023)
0.2950%
0.9152%
NeuralGLS (Sui ct al., 2024)
0.470%
3.622%
GNNGLS* (Hudson et al., 2021)
0.705%*
3.522%**
LLM--bused AII:: GPT-4o-mini
BoHl
0.0065%
0.2025 %
0.9534%
1.6083%
ReEvo
0.0076%
0.2210%
0.9993%
1.6155%
MCTS-AHD (Ours)
0.0060%
0.2106%
0.9495%
1.5985%
29

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
E3. Time Consumption of MCTS-AHD Heuristic Evolution
Compared EoH and ReEvo, MCTS-AHD will not cause server efficiency degradation regarding time and token con- sumption. To demonstrate this, shown in Table 9, we provide detailed comparison of the time and token consumption of MCTS-AHD and population-based baselines in five application scenarios. We calculate the token number based on GP'--4o-mnni Results demonstrate that compared to population methods, MCTS-AHD has slight efficiency decrease and maintains a similar level of token consumption compared to LLM-based AHD baselines.
Table Time token consumption designing heuristies with different algorithms.
Frameworks
Construction
ACO
B0
Methods
Problems
TSP
KP
TSP
MKP
CAF
Time
2h
2h
4h
4h
15h
EnH
Tnput Token
0.8M
0.7M
IM
IM
1,2M
Output Token
0.2M
0.2M
0.5M
0.5M
0.5M
Time
2h
5h
5h
ReFvo
Tnput Token
L.M
1.3M
1.3M
Output Token
0.4M
0.6M
0.5M
Time
4h
3h
8h
4h
14h
MCTS-AHD
Tnput Token
IM
IM
1.2M
1.3M
1.3M
Output Token
0.3M
0.2M
0.5M
0.6M
0.6M
F.4 P-values for Significance
The design performance of the LLM-based AHD method follows an implicit distribution. Although running a method three times can preliminarily indicate the advantages and disadvantages of this method, it still cannot prove the significant difference between its performance distribution algorithm and the performance distributions of comparison algorithms. In this section, we introduce the p-value to demonstrate the significant advantage of MCT-AHD compared to the main LLM-based AHD baseline EoH. We employ both EoH and MCTS-AHD to design up ten heuristics for portion of CO problems considered in this paper, and the results and p-values for each shown in Table 10. In any of the four application scenarios, there is at least 96% confidence in satisfying the hypothesis that MCTS-AHD leads compared to an LLM-based AHD baseline with population EoH.
Table 10. Up to ten runs of EoH and MCTS-AHD on a portion NP-hard CO problems with step-hy-step construction frameworks and ACO frameworks. "avg" in the Table below represents the average and "std" means the standard variant. The p-value is calculated with single-tail tailed t-tests.
CO Problem
Methods
runl
run2
run3
run4
run5
run6
run?
run8
run9
run10
avg
p-value
General Framework: Step-by-step Construction, LLM: GPT-4o-mini
EoH
6.452
6.447
6,284
6,386
6.316
6.372
6.480
6.480
6.259
6.388
6.386
0.080
0.002855655
ReEvo
6.3592
6.2681
6.4516
6.3841
6.711
6.437
6,272
6.297
6.388
6.431
6,400
0.128 0.009529994
TSP50
HSEvo
6.4582
6.4468
6.2839
6,360
6,461
6,446
6,400
6,285
6,452
6,376
6.397
0.069 0.000796727
MCTS-AHI
6.174
6.156
6.347
6.356
6.285
6.274
6.257
6.365
6.289
6.302
6,280
0.071
EoH
40.229
40.231
40.232
40.231
40.234
40.264
40.240
40.235
40.229
40.235
40.236
0.010 0.027524885
KP100, W=25
MCTS-AHI
40.259
40.265
40.231
40.236
40.233
40.262
40.264
40.233
40.233
40.262
40.248
0.015
Generul
Framework: ACO, LLM: 4oT-io-mini
FoH
5,827
5.825
5.831
5,830
5.828
5.828
0.003
0.039230447
ReEvo
5,894
5,829
5,844
5,831
5,820
5,844
0.029
0.02477005
TSP50
HSEvo
5.827
5.802
5.799
5.823
5.843
5.819
0.018
0.115934978
MCTS-AHD
5.798
5.779
5.827
5.742
5,830
5.795
0.036
EoHl
23.149
23.133
23.136
23.311
23.266
23.199
0.083
0.037268388
ReEvo
23.310
23.187
23.237
23.291
23.263
23.258
0.048
0.20630356
MKP100, m=5
HSEvo
23.280
23.270
23.279
23.268
23.286
23.277
0.008
0.433650083
MCTS-AHD
23.235
23.284
23.287
23.294
23.294
23.279
0.025
30

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
ES. MCTS-AHD with Other LLMs
Besides using GPT models LLMs (as shown in the other part of this article), MCTS-AHD can cooperate with other open-source or closed-souree LLMs well. This subsection evaluates MCTS-AHD on designing step-by-step construction heuristics for TSP and KP utiliizing other advanced pre-trained LLMs, including closed-source LLM Claude-3.5 and Open-source LLM DeepSeek-v3, Swve2.5-Coder-332---nsss
Performances of the designed heuristics are shown in Table 11, where heuristics design with Claude-3. -.5mmeee,,- DeepSeek-v3,, and Qwen2.5-Coder- 1-1.5---oo-33------ ooder-32bb-nsstucc can still surpass handcrafted heuristics in both TSP and KP test sets and outperform the advanced NCO method POMO (which needs task-specific training) in KP. Moreover, MCTS-AHD runs with GPT-4o-mini exhibit the best performance in each test set, demonstrating that GPT-4o mini could be the best choice in LLM for MCTS-AHD.
Table 1. An extension Table employing both GPT models and open-source LLMs for MCTS-AHD, Each MCTS-AHD result averaged over three runs and we highlight the MCTS-AHD result with the best performance each test set.
TSP
KP
N=
N=50
N=000
N=100,
W=25
N=200,
W=25
Method
Obj-
Gap
Obj-l-
Gap
Obj-t
Gap
Obj.1
Gap
Optimal Greedy Construct
5.675
7.768
40.271
57.448
6.959
22.62%
9.706
24.94%
40.225
0.12%
57.395
0.09%
POMO
5.697
0.39%
8.001
3.01 %
39.676
1.48%
57.271
0.09%
Closed-Source LLMs
MCTS-AHIDXGP3335-aarb))
6,346
11.82%
8.861
14.08%
40.233
0.09%
57.393
0.10%
MCTS-AHDDGPTToomminn)
6.225
9.69%
8.684
11.79%
40.252
0.05%
57.423
0.04%
MCTS-ANIDCCGaud=33--meee)
6.503
14.57%
9.036
16.32%
40.233
0.10%
57.396
0.09%
Open-Source LLMs
MCTSSAAHDDDeepSSeeexe)) MCTSS-AHDDKOeen2255Ccddr222222
6.348
11.85%
8.859
14.04%
40.233
0.10%
57.402
0.08%
6.272
10.52%
8.685
11.81%
40.235
0.09%
57,402
0.08%
F.6. Application on General Optimization Tasks
In this section, we discuss the application of MCTS-AHD on more optimization problems. As an AHD method, MCTS-AHD aims at designing and evolving high-quality heuristics for optimization problems within a given solving framework. There are no heuristics for some optimization problems (c.g.. code search (DeLorenzo al., 2024)), so MCTS-AHD cannot be directly applied to them. When directly implementing MCTS-AHD to code search (e.g., the APPS dataset (Hendrycks et al., 2021)), the current MCTS-AHD cannot handle code bugs and becomes ineffective.
To further assess the generalizability of MCTS-AHD across different domains. We evaluate MCTS-AHD on policy optimization task MountainCar-v based on the Gym framework. Table 12 shows the average steps needed to reach the goal, where the heuristic policy designed by MCTS-AHD is more effective. We run AHD methods three times for the average performance.
Table 12. Results of designing heuristics for MountainCar-vo
EoH
ReEvo
MCTS-AHD
Gym-MoumtainCar-v0
140.3
117.6
115.0
In conclusion, MCTS-AHD demonstrates superiority in designing heuristics for various optimization problems, including combinatorial optimization problems, Bayesian optimization tasks, and policy optimization tasks using the same set of hyperparameters. We believe MCTS-AHD can be useful in a wide range of application scenarios.
31

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Baseed Automatic Heuristic Design
F.7. Results TSPLib: Compare to GP-based AHD Methods
We conduct tests on well-known real-world TSP benchmark TSPLib (Reinelt, 1991) (we adopt instances with nodes less than 500 in this article) to compare the quality of MCTS-AHD GP-based AHD method GHPP (Duflo et al., 2019). Christofides (Christofides, 2022), Greedy (Brecklinghaus & Hougardy, 2015), Nearest insertion, and nearest-greedy (Rosenkraniz et al., 1977) are famous manually designed heuristics for TSP. We use the reported results of these algorithms in the article (Duflo et al., 2019). Meanwhile, the results of GHPP also come from Duflo et al. (2019).
For LLM-based AHD methods EoH and MCTS-AHD, we use the best-performing step-by-step constructive heuristic among their three runs with GPT-4o-mini for their performances. We use the best- pest-performing heuristic of ReEvo according their report in Ye et al. (2024a). On each TSPLib instance, We the heuristics of EoH, ReEvo, and MCTS-AHD three times with different starting nodes for average performance. As shown in Table 13, the heuristic from MCTS-AHD can surpass manually designed baselines, the GP-based AHD method GHPP, and LLM-based AHD baselines in the average optimality gap.
Table 13. Results of GP-based AHD method GPHH, LLM-based methods designing heuristies for TSP with the step-by-step construc- tion framework. Christofides, Greedy, Nearest insertion, and kearest-greedy are manually designed heuristies for TSP where their results are also drawn from (Duflo al., 2019). We report the optimality gap of each instance and heuristics designed by LLM-based AHD methods are run times with different starting nodes for average performances. The leading LLM-designed heuristic on each instance
marked in shaded and the overall best heuristic in bold.
Instance
Christofides
Greedy
Nearest insertion
Nearest- Nearest-greedy
GGHHH-bess
EoH
ReEvo
MCTS AHD
tsp25.tsp
5.67%
5.38%
19.93%
16.82%
7.71%
5.57%
6.56%
10.84%
rat99.tsp
9.43%
22.30%
21.05%
21.79%
14.09%
18.78%
12.41%
10.46%
bier1 1tp
13.03%
19.50%
23.05%
23.255
15.64%
14.05%
10.79%
7.56 %
1itt18.tsp
13.80%
18.75%
24.44%
25.78%
14.30%
14.03 %
16.63%
14.07%
eil
15.18%
13.03%
16.14%
31.96%
10.20%
8.37%
6.47
15.98%
d493.tsp
9.52%
16.68%
20.39%
24.00%
15.58%
12.41% %
13.43%
11.73%
krott00.
9.82%
16.59%
21.53%
26.26%
14.06%
13.46%
12.20%
11.43%
kroC100.tsp
9.08%
12.94%
24.25%
25.76%
16.22%
16.85%
15.88%
8.27%
ch130.tsp
10.09%
28.40%
19.21%
25.66%
14.77%
12.26%
9.40
10.18%
pr299.tsp
11.23% %
31.42%
25.05%
31.42%
18.24%
23.58%
20.63%
11.23%
f1417.tsp
15.57%
12.64%
25.52%
32.42%
22.72%
20.47%
19.15%
10.20%
kroA150.tsp
13.44%
20.24%
19.09%
26.08%
15.59%
18.36%
11.62%
10.08%
pr264.tsp
11.28%
11.89%
34.28%
17.87%
23.96%
18.03%
16.78%
12.27%
pr226.tsp
14.17%
21.44%
28.02%
24.65%
15.51%
19.90%
18.02%
7.15%
1s439.tsp
11.16%
20.08%
24.67%
27.36%
21.36%
21.96%
19.25%
15.12%
Average Gap
11.50%
18.09%
23.11%
25.41%
16.00%
15.87%
13.95%
11.10%
F88 Compare to LLM-as-Optimizer Methods
As discussed in Appendix another LLM-based approach for CO problems, LLM-as-one opttimizee methods cannot achieve outstanding performance in large-scale instances. Here we compare this type of method with the proposed MCTS-AHD, As shown in Table 14, LLM-as-optimizer methods LEMA (Liu et al., 2024e) and OPRO (Yang et al., 2024) can provide better solutions in very-small-scale TSP20 instances, but as the scale increases TSP50, these methods will fail to achieve convergence in based solution optimizations.
Table 14. Comparison of LLM -sMa---onn astopiimieer methods and MCTS-AHD designed heuristics. We display the optimality gap of MCTS-AHD on TSP20 and TSPS0 test sets with 1,000 instances, respectively. Results L.MAA and OPRO are drawn from the original literature the LLM for all methods in this table is
Methods
LEMA*
OPRO*
MCTS-AAID(sseep-by-stee construction)
TSP20
3.94%
4.40%
7.71%
TSP50
133.00%
11.82%
32

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
E9. Discussion: Ablation of Other Parameters
In 5.1, we have provided partial ablation experiments, focusing mainly on verifying that À 0.1 is reasonable setting and validating the effectiveness of the three proposed components (Progressive Widening, Thought Aligmment, and Exploration decay) and MCTS-AII AHD's 's expansion actions. MCTS-AHD also includes other parameters, such as the number of initial solutions N,, the threshold parameter for progressive widening a, and the number of actions ml and m2 in each expansion k. We believe that MCTS-AII is not sensitive to the settings of these parameters. In this section, we will introduce the reasons for their default settings and demonstrate their flexibility through ablation experiments.
N, determines the number of initial nodes (i.e., heuristic samples), which affects the perception of heuristic space by LLM in the early iterations of the heuristic evolution. Table 15 shows that adjusting it to N₂ 10 has no significant effect on the results, indicating that using N, is sufficient. Under the setting of evaluating T times in total, progressive widening allows the maximum number of level-1 tree nodes connected to the root to be most [T Larger settings will drive the MCTS tree shallow, affecting the quality of multi-hop reasoning brought by MCTS. Therefore, we choose to set a 0.5 to balance the depth of the MCTS tree and the importance of progressive wideinig. According to Table 15, changing this setting to a 0.6 does not result in significant effect degradation. The setting of k = 2 allows MCTS to utilize the randomness brought about by LLM in trying different search directions in each expansion, and setting it to k = 1 does not cause a significant degradation in performances as well.
Table 15. Ablation on the number of initial solution Nr. the threshold parameter for progressive widening the number of actions ml and m2 in each expansion The performances MCTS-AHD variants are averaged over five runs.
TSPS0
KP100
(Default Setting MCTS-AHD, runs)
10.661%
0.059%
11.094%
0.047%
0.5 (Default Setting in MCTS-AHD, runs)
10.661%
0.059%
10.891%
0.063%
(Default Sotting in MCTS-AHD, runs)
10.661%
0.059%
11.380%
0.049%
F.10. Discussion: The Advantage Scope of MCTS
MCTS-AHD shows greater strengths in application scenarios with more complex heuristic space H and tasks with more descriptions as knowledge.
Relationship of Space Size and Gap Ratio
35%
TSP-SC-3.5
30%
TSP-SC-40
KP-SC-3.5
25%
KP-SC-4p
Optimality Gap Ratio
20%
ASP-SC-3.5
ASP-SC-4o
15%
TNP-GLS8-4
CAI-BD-4o
10%
TSP-ACO-40
CVRP-ACO-4o
5%
Trend line
0%
.5%
7.5
10.0
12.5
15.0
17.5
20.0
22.5
25.0
Approximate Size of Houristic Space
Figure 5. The relation of approximate heuristic space size n and the optimality gap ratio between BoHl and MCTS-AHD (i.e., Gap Gapares--Ae /GaDEo). We consider EoH baseline for applicability in tasks. We do include tasks with unavailable optimal objective values (c.g., online BPP). The legends have been simplified, for example, TSP-GLS-44 represents designing GLS heuristics for TSP with GPT-4o-mini.
the figure is an abbreviation for step-by-step construction.
Better in Application Scenarios with a More Complex Heuristic Space H. Each heuristic function can be expressed in the form of (ifi(x) + 02f2(x) + azfs(x) + ... + (n)n( representing linear combinations of different sub-
33

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
functions, where x denotes the particular input (ins) of the heuristic function h. The heuristic space H be explored for application scenario can be defined as the set of all meaningful sub-functions, i.e., H Span f1 (z)....} -)- To estimate the size of the set consisting of all meaningful sub-functions, we use OpenAI o o7-mini-2022-00-1 to analyze the top 10 heuristic functions of EoH and MCTS-AV AHD in their respective runs (6 runs and 60 heuristic functions in total), ordering L.M to break functions down into linearly independent sub-functions and use the number of sub-functions n to estimate the size of the heuristic space.
We hypothesize that for more complex heuristic spaces, MCTS-AHD can explore the hcuristic space more comprehen- sively compared to population- based methods such as EoH. To test this hypothesis, in Figure 5, we plot the relation of estimated heuristic space size n and the leads in optimality gap between MCTS-AHD and EoH (the y-axis Figure, ). The results verify our hypothesis. As the trend line demonstrates, MCTS-AHD tends to achieve more significant lead compared to the population- baseline EoH in application scenarios with larger n. It indicates that MCTS-AHD may be more suitable for application scenarios with more complex heuristic spaces H.
-CP
Better in Application Scenarios with More Descriptions. As shown in Table 16, MCTS-AHD demonstrates significant decrease in effectiveness in black-box settings, taking the lead only in the TSP task. This suggests that MCTS-AHD will perform better in application scenarios with more descriptions (e.g., white-bbox cases).
Table 16. Implementing MCTS-AHD on Black-box CO tasks with ACO general frameworks. We follow the settings of Ye et al. (2024a) in heuristic evolution and run each LLM-based method three times for average performance. The white-box results are the Table 2.
TSP
CVRP
MKP
Offline BPP
N=
N=50
N=50, C=50
N=100.m55
N=500,C=150
Methods
Obj.J
Obj-
Obj.1
Obj
ACO
5,992
11,355
22,738
208.828
DecpACO
5.842
8,888
23.093
203.125
White- box Setting: GPT-4o-mini
BoH
5.828
9.359
23.139
204.646
ReEvo
5,856
9.327
23.245
206.693
MCTS-AHD(Ous)
5,801
9.286
23.269
204.094
Black-bo box Setting: GPT-4o-mini
EoH
5,831
9.401
23.240
204.615
ReEvo
5.860
9.404
23.196
206.021
MCTS-AHD(OUsS)
5.830
9.444
23.191
205.375
We can explain that MCTS-AHD's better performance in application scenarios with complex heuristic space is highly beneficial from its ability to explore complex function spaces and escape from local optima.
For its mediocre performance in black-box application scenarios, believe this is mainly because compared to MCTS, which only performs limited expansion on each heuristic, the population structure is computationally intensive and often involves many rounds of LLM-based operations on a heuristic function in the population. So, the effectiveness of MCTS-AHD may require LLMs more on its generation quality in limited number of MCTS expansions. In contrast, black-box application scenarios make it difficult for LLMS to guarantee this condition, these application scenarios will be tough for MCTS-AHD.
G. Examples of Evolution
To visually demonstrate the workflow of MCTS-AHD and its ability on exploration, we provide two examples of the evolution of heuristics in two tasks, as shown in Figure 6.
The two examples of evolution clearly exhibit how MCTS-AHD conducts comprehensive explorations. For example, in designing heuristics with step-by-step construction framework for TSP, MCTS- can expand potential child nodes from nodes (e.g., MCTS node with "Expansion: t=611 1"") that are not among the top 10 optimal ones (the performance range of the top 10 optimal heuristics is the yellow shade), and ultimately reach the best heuristic. It reflects the superiority of employing MCTS as an optimization framework instead of oopulation-bssed EC. Population-based EoH, ReEvo, and HSEvo lack consideration of worse-perfool worse-performing but potential heuristics. These algorithms will be obsessed with processing top-torfooeeeeoo pop-performanc heuristic functions. When the top 10 heuristics cannot obtain new heuristics surpassing the top 10 performances with one L.LM-based operation on heuristics, the evolution of heuristies will trap into local optima.
-LM-d AHD methods such as
34

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Evolution of Step-by-step Constrction heuristics for TSP
Expansice, Laks MCTS
The porfitanee ragge of 1xp10 ticenencs
Expeascos 585,
Achoer sl,
61 --22275144
Cole Descipiet...
Dquanion 611
Antice:
305
Performances g(
Deuupdas
Expessie:
pF 450015
Expanice: Cale
Exsapien:
81
MCTS-Root (Viriual)
Cude..
Expanion:
6-2555
Pipawion: Antoer 18400
Actirt I2.
Oodo:
0
Evolution Steps
1000
0.1
Exploration
Aa
Exploitation
Exploration Decay
(a) An Example of MCTS-AHD Evolution on Designing Step-by-step Construction Heuristies for TSP
Evolution of Step-by-step Constrction heuristics for KP
Eispancon,
MCTS
The pedremeseeeeggee.o tfe Toplo Hourisks
Eapersion 114,
Aatier
13773
lispansee:
Performances g())
MCTS-Root (Virtual)
Experson: (- 15C,
Actict c3,
I 1:400177111
Expurpan 1- 590
Acticts ch,
J 46.346).
Oade
Dest
0
Evolution Stops
1000
0.1
Exploration
An
Exploitation
Exploration Decay
(b) An Example of MCTS-AHD Evolution on Designing Stop-hy-step Construction Hcuristics for KP
Figure 6. Two examples of the heuristic evolution process of MCTS-AHD. We provide the performance function value g(-) of the hcuristic function within each MCTS tree node. The "Action" in each node represents one of the six actions of expanding this node. Codes are simplified by OpenAl GPT to reduce the space occupations.
35

---

Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
H. Baselines & Licenses
For the optimal value Table I and Table 8. We run LKH3 for TSP instances with adopting the commonly used setting in NCO methods (Kool et al., 2018). We set the LKH parameters RUNS 10 and MAX TRAILS 1,0000. For KP instances, we use Google OR-Tools for the optimal value.
For manually designed heuristics with general frameworks, this paper includes Greedy Construct, the ACO algorithm (Dorigo et al., 2006), the KGLS algorithm (Arnold & Sörensen, 2019), and EI (Mockus, 1974), Elpu (Snoek et al., 201 2), El-cools (Lee et al., 2020a) for the CAF design task in BO. We implement KGSL by setting the heuristic matrix to the distance matrix, using the implementation of ACO in DeepACO (Ye et al., 2024b), and use the results reported in Yao et al. (2024c) for EI, Elpu, and El-cools.
For NCO baselines, this article implements POMO (Kwon al., 2020), DeepACO (Ye al., 2024b), VRP-DACT (Ma et al., 2021), and NeuOpt (Ma et al., 2023). For a fair comparison, in Table 1, the reported POMO solutions are from single start and generated without augmentations. The maximum operation solution is set to T 1200 for VRP-DACT and NeuOpt.
For AHD baselines, in TSPLib, we adopt the results of GHPP reported in (Duflo et al., 2019).
For LLM-based AHD baselines, this article considers Funsearch (Romera-Paredes et al., 2024), EoH (Liu et al., 2024b), ReEvo (Ye et al., 2024a), and HSEvo (Dat et al., 2024), we follow all their parameter settings in evolutions (e.g., setting population size M 20 for online BPP and M 10 for other tasks). We try not introduce too much external expert information. However, in implementations, Funsearch needs to maintain 10 relatively independent multiple populations from certain inferior seed heuristic function. ReEvo relies more on the seed heuristic function, and the ReEvo method will become unavailable when all individuals in the elite population have the same objective function value. So, in some application scenarios (e.g., step-by-step construction for the KP task), it is too hard to find a good seed heuristic function that ensures the availability of the algorithm while trying not to provide too much external knowledge.
In experiments, we use the same seed functions for baselines (Funsearch, ReEvo, and HSEvo), using seed functions proposed in Ye et al. (2024a) for ACO frameworks and GLS frameworks, random selection functions for step-by-step constructing TSP and ASP, and the best-known function proposed in Nomera-Paredes et al. (2024) for online BPP. The proposed MCTS-AHD, exhibits better applicability and superior performance in most application scenarios, without the requirement of seed function design. In our seed function settings, ReEvo and its follow-up method HSEvo are not available in some application scenarios (e.g., KP, ACO), where we do not report their effects.
H.1. License
The licenses and URL of baselines are listed in Table 17.
Table 17. A summary of licenses.
Resources
Type
License
URL
T.KH3
Code
Available for academic research use
ht
OR-Tools
License
https http:///eeeoooorr..ooooo
cwtcooggl...oooppooooooo sat http:/ppo///aaaaaao////////////a http///c/////aaaaaaaaaaaaaaa 7h) =ah-or
POMO
Code
Available online
https://github
DecpACO
Code
MIT License
http:::///gtthu.ccooteee yeh/DeepcCa
VRP-DACT
Code
MIT License
NeuOpt
Code
MIT License
Funsearch
Code
Apache License
FoH
License
http:://ggtthho.oooc////e1111112
ReEvo
Code
MIT License
HSEvo
Code
Available online
BBEvo
Synthetic problems
Dataset Available Online
ht:ps::/giituu..comms www. htt.://iiw..oee//eeu3///e/////// ree wwwaa//eaaaeee/eeeeeeeeeeeeeeeee herpeeeeeuee____________
TSPLib
Dataset Available for any nen- nom-coomerrcial use ht:p://comopt.11f/ uni he www.ebeedgeeggge...eee de dt/so//////aeeeeeeeeeeeee stwtwaree woftware/TSPLL33 TSPL1395
36


Reviews:
[{"review_id": "DiG8HAy32j", "reviewer": "Reviewer_x4g3", "summary": "This paper introduces MCTS-AHD, which integrates MCTS into LLM-based AHD to improve heuristic search exploration. MCTS-AHD organizes heuristics in a tree structure, allowing for deeper refinement of temporarily weaker candidates. Key techniques include progressive widening, exploration decay, and tree-path reasoning, enabling more comprehensive heuristic evolution. Experiments on NP-hard optimization tasks (e.g., TSP, KP) and Bayesian optimization demonstrate superior performance over handcrafted heuristics and existing AHD methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and effort in reviewing our work. We are glad to know that you find the proposed MCTS-AHD is an effective method for overcoming local optima, the paper is very well written, and the experiments are detailed.\n\nWe address your concerns as follows.\n\n> **Weakness. Robustness of LLM output and error handling:** The approach relies on LLM-generated code, which may sometimes produce heuristics that are either non-executable or logically flawed. Although the paper introduces a thought-alignment process to mitigate this issue, further analysis on the robustness of LLM outputs and the effectiveness of error handling would be beneficial.\n\n\nThank you for your insightful comment. We agree that LLMs may sometimes produce non-executable code. However, it's worth noting that unlike tasks involving code generation from scratch [1,2], where debugging plays a crucial role, LLM-based AHD methods only design the key heuristic function within predefined solving frameworks. This setup significantly reduces the likelihood of generating invalid codes [3]. Empirically, when using GPT-4o-mini, the probability of MCTS-AHD generating invalid code for step-by-step construction TSP heuristics is only about 15\\%–20\\%. Therefore, we believe that LLM-based debugging for AHD is not indispensable. To mitigate the potential negative impact of invalid codes on AHD, MCTS-AHD discards these invalid heuristic function codes and relies on conducting numerous LLM calls for valid code samples. We will add this discussion to our manuscript.\n\n\n\n> **Question. Time and token costs for other tasks:** The paper mentions running time and token cost for the KP task, similar information is missing for other tasks. Could the authors provide more details for those tasks?\n\nThanks for your comment. As shown in the table below, we provide more statistics on the time and token consumption of MCTS-AHD and the baselines in more application scenarios. We calculate the token numbers based on using GPT-4o-mini as LLMs. Compared to LLM-based AHD baselines, MCTS-AHD demonstrates a slight efficiency decrease and maintains a similar level of token consumption.\n\n|Methods|Consumption|Construction-TSP|Construction-KP|ACO-TSO|ACO-MKP|BO-CAF|\n|-|-|:-:|:-:|:-:|:-:|:-:|\n|**EoH**|Time|2h|2h|4h|4h|15h|\n||InputToken|0.8M|0.7M|1M|1M|1.2M|\n||OutputToken|0.2M|0.2M|0.5M|0.5M|0.5M|\n|**ReEvo**|Time|2h|-|5h|5h|-|\n||InputToken|1.1M|-|1.3M|1.3M|-|\n||OutputToken|0.4M|-|0.6M|0.5M|-|\n|**MCTS-AHD**|Time|4h|3h|8h|4h|14h|\n||InputToken|1M|1M|1.2M|1.3M|1.3M|\n||OutputToken|0.3M|0.2M|0.5M|0.6M|0.6M|\n\n> **Other Comments Or Suggestions. Typo:** page 6 line 298 LMM - LLM problems. \n\nThank you for pointing out the typos. We will correct typos accordingly.\n\n\n> **References**\n\n[1] Zhong, Li, Zilong Wang, and Jingbo Shang. \"Debug like a human: A large language model debugger via verifying runtime execution step-by-step.\" arXiv preprint arXiv:2402.16906 (2024).\n\n[2] Hendrycks D, Basart S, Kadavath S, et al. Measuring coding challenge competence with apps[J]. arXiv preprint arXiv:2105.09938, 2021.\n\n[3] Liu, Fei, et al. \"A systematic survey on large language models for algorithm design.\" arXiv preprint arXiv:2410.14716 (2024).", "claims_and_evidence": "The paper’s primary claims are backed up by reasonably thorough empirical results on multiple NP-hard problems (TSP, KP, BPP, CVRP, etc.). The authors also present ablation studies demonstrating the contributions of individual components (e.g., progressive widening, exploration decay) in MCTS-AHD.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes. I checked the standard MCTS-related proofs.", "experimental_designs_or_analyses": "Yes I check the validity of experimental designs and analyses.", "relation_to_broader_scientific_literature": "This paper is primarily an extension of previous work on LLM for AHD, further incorporating the MCTS algorithm to explore the space of heuristic functions, thereby addressing known limitations of earlier methods.", "essential_references_not_discussed": "Not found", "other_strengths_and_weaknesses": "The paper is very well written and introduce a effective method for overcoming local optima. The experiments are detailed. The approach relies on LLM-generated code, which may sometimes produce heuristics that are either non-executable or logically flawed. Although the paper introduces a thought-alignment process to mitigate this issue, further analysis on the robustness of LLM outputs and the effectiveness of error handling would be beneficial.", "other_comments_or_suggestions": "page 6 line 298  LMM - LLM", "questions_for_authors": "The paper mentions running time and token cost for the KP task, similar information is missing for other tasks. Could the authors provide more details for those tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "742H0iRw49", "reviewer": "Reviewer_ywZb", "summary": "This paper introduces MCTS-AHD, a Monte Carlo Tree Search (MCTS)-based method for automatic heuristic design (AHD) using Large Language Models (LLMs). MCTS-AHD organizes heuristics in a tree structure to enable more comprehensive exploration and refinement. Ultimately, the goal is to generate more efficient, robust, and generalizable heuristic functions for combinatorial optimization (CO) and Bayesian optimization (BO) tasks, enhancing the ability to solve complex optimization problems.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and effort in reviewing our work. We are glad to know that you find MCTS-AHD addressing specific shortcomings of existing approaches and the paper is well-written.\n\nWe address your concerns as follows.\n\n>**Weakness 1. Computational complexity analysis:** There is no computational complexity analysis, which is essential to understand the efficiency and scalability of the approach compared to traditional methods.\n\nThank you for your valuable comment. The time consumption of running MCTS-AHD is from three parts: evaluating the performance of heuristic algorithms, employing LLMs for heuristic function generation, and employing MCTS to select heuristics. The time complexity of the first two parts cannot be represented explicitly. The time consumption of heuristic evaluation is related to the complexity of generated heuristics and the size of the evaluation dataset $D$, while the time consumption of LLM generation is related to the selection of LLMs.\n\nFor the third part, the total time complexity of the heuristic selection in MCTS-AHD with $T$ evaluations is $\\mathcal{O}(HT)$, where H is the maximal height of MCTS. The space complexity is $\\mathcal{O}(T)$ for preserving all LLM-generated heuristics. When maintaining a $M$-size population, the time complexity of heuristic selection in EoH and ReEvo is $\\mathcal{O}(MT)$, and their space complexity is $\\mathcal{O}(M)$.\n\n>**Weakness 1 & 2. Stability and Convergence proof:** The method relies heavily on LLMs for both generating and refining heuristics, making its performance sensitive to the quality and stability of LLM-generated outputs. There is no formal convergence proof.\n\nThanks for your insightful comment. We agree that the effectiveness of all the LLM-based AHD methods largely depends on the stability and ability of LLMs to improve heuristics. There is no formal convergence proof for these methods.\n\n\n>**Weakness 3. Other types of optimization problems, such as code search:** It is recommended to extend the evaluation to other types of optimization problems, such as code search.\n\nThanks for your comments. As an AHD method, MCTS-AHD aims at designing and evolving high-quality heuristics for optimization problems within a given solving framework. Code search [1,2] is indeed a typical optimization problem. However, there are no compelling heuristics to solve the code search tasks so MCTS-AHD cannot be directly applied for code searches. When directly implementing MCTS-AHD to code search (e.g., the APPS dataset [1]), the current MCTS-AHD cannot handle code bugs and becomes ineffective.\n\n|Methods |EoH|ReEvo|MCTS-AHD|\n|-|:-:|:-:|:-:|\n|Gym-MountainCar-v0|140.3|117.6|**115.0**|\n\nTo further assess the generalizability of MCTS-AHD across different domains. We evaluate MCTS-AHD on a policy optimization task ``MountainCar-v0`` based on the Gym framework. The table above shows the average steps needed to reach the goal where the heuristic policy designed by MCTS-AHD is more effective. We run AHD methods three times for average performances and take GPT-4o-mini as LLMs.\n\nIn conclusion, MCTS-AHD demonstrates superiority across combinatorial optimization, Bayesian optimization, and policy optimization using the same set of hyperparameters, so we believe MCTS-AHD can generalize to a wide range of application scenarios.\n\n>**Weakness 4. Numerous LLM evaluations:** MCTS-AHD requires numerous LLM evaluations during its tree search.\n\nThanks for your comment. We agree that due to the proposed thought-alignment procedure, MCTS-AHD requires more LLM calls. In each heuristic design with $T$ performance evaluations, MCTS-AHD conducts $2T$ LLM calls (includes $T$ LLM calls for code generation and $T$ LLM calls for thought-alignment procedures), while EoH requires $T$ LLM calls and ReEvo requires $\\frac{22}{15}T$ LLM calls in this case. \n\nHowever, we want to clarify that the LLM calls for thought-alignment procedures only consume a limited amount of tokens. As shown in the table below, we calculate the total token costs of MCTS-AHD and baselines on a series of representative heuristics design scenarios (setting $T=1000$ and using GPT-4o-mini as LLMs). The results show that MCTS-AHD will not make significantly higher token costs while achieving better heuristic performances.\n\n|Methods|Consumption|Construction-TSP|Construction-KP|ACO-TSO|ACO-MKP|BO-CAF|\n|-|-|:-:|:-:|:-:|:-:|:-:|\n|**EoH**|InputToken|0.8M|0.7M|1M|1M|1.2M|\n||OutputToken|0.2M|0.2M|0.5M|0.5M|0.5M|\n|**ReEvo**|InputToken|1.1M|-|1.3M|1.3M|-|\n||OutputToken|0.4M|-|0.6M|0.5M|-|\n|**MCTS-AHD**|InputToken|1M|1M|1.2M|1.3M|1.3M|\n||OutputToken|0.3M|0.2M|0.5M|0.6M|0.6M|\n\n>**Reference:**\n\n[1] Zhong, Li, Zilong Wang, and Jingbo Shang. \"Debug like a human: A large language model debugger via verifying runtime execution step-by-step.\" arXiv preprint arXiv:2402.16906 (2024).\n\n[2] Hendrycks D, Basart S, Kadavath S, et al. Measuring coding challenge competence with apps[J]. arXiv preprint arXiv:2105.09938, 2021.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "The paper does not provide theoretical claim.", "experimental_designs_or_analyses": "I have checked all the experiments in the experimental section.", "relation_to_broader_scientific_literature": "The key contributions of MCTS-AHD are situated at the combination of automatic heuristic design (AHD), Monte Carlo Tree Search (MCTS), and Large Language Models (LLMs). The paper extends prior research in these domains while addressing specific shortcomings of existing approaches.", "essential_references_not_discussed": "The paper has included the main related works that are crucial for understanding the context.", "other_strengths_and_weaknesses": "Strengths:\n\n1. The topic that leveraging LLMs to automatically enhance heuristics is intresting.\n2. The paper is well-written.\n\nWeaknesses:\n\n1. There is no formal convergence proof, making it unclear whether MCTS-AHD is guaranteed to consistently find optimal or near-optimal heuristics across different search spaces. Also, there is no computational complexity analysis, which is essential to understand the efficiency and scalability of the approach compared to traditional methods.\n2. The method relies heavily on LLMs for both generating and refining heuristics, making its performance sensitive to the quality and stability of LLM-generated outputs.\n3. It is recommended to extend the evaluation to other types of optimization problems, such as code search, to assess the generalizability of the method across different domains.\n4. MCTS-AHD requires numerous LLM evaluations during its tree search, leading to higher computational costs compared to traditional population-based methods, which might limit practical applicability in resource-constrained environments.", "other_comments_or_suggestions": "See weaknesses", "questions_for_authors": "See weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WPyQ5rzVSw", "reviewer": "Reviewer_9L3t", "summary": "This paper introduces MCTS-AHD, a novel method that leverages MCTS to enhance the evolution of heuristic functions generated by LLMs for solving complex optimization tasks. The key contributions include the use of MCTS to organize and evolve heuristics in a tree structure, allowing for comprehensive exploration of the heuristic space and avoiding local optima. The method employs a set of LLM-based actions, including initialization, mutation, crossover, and tree-path reasoning, to iteratively refine heuristic functions. Experiments across various NP-hard combinatorial optimization problems and Bayesian Optimization tasks demonstrate that MCTS-AHD outperforms existing LLM-based AHD methods and handcrafted heuristics.\n\n## update after rebuttal\n\nI have raised my score to accept.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and effort in reviewing our work. We are glad to know that you find the proposed method demonstrates significant improvements and the paper includes comprehensive experiments and ablation studies.\n\nWe address your concerns as follows.\n\n>**Weakness 1. Convergence speed:** The convergence speed of MCTS-AHD could be improved. Future work could explore hybrid methods combining MCTS with population-based approaches to enhance efficiency.\n\nThanks for your suggestion. Yes, as listed in the Conclusion, future work could explore hybrid methods combining MCTS with population-based approaches to enhance the convergence speed of MCTS-AHD.\n\n\n>**Weakness 2. Computational complexity and scalability:** The paper does not provide detailed discussions on the computational complexity and scalability of MCTS-AHD for very large-scale optimization problems.\n\nThank you very much for your comment. We would like to clarify that, unlike learning-based methods, heuristics designed on small-scale optimization instances often have high generalization abilities for large-scale optimization tasks [1]. As shown in the table below where constructive TSP heuristics designed by MCTS-AHD can well generalize to very large-scale instances with lower objective values. \n\n|Scale|N=500|N=1,000|N=2,000|N=5,000|\n|-|:-:|:-:|:-:|:-:|\n|Nearest Neighboor|20.2259|28.5305|39.2111|64.3547|\n|Construction heuristic designed by MCTS-AHD|18.7596|26.4281|37.2608|59.1260|\n\nBesides effectiveness, only heuristics with low time complexity can be easily applied to very large-scale instances. Current MCTS-AHD and other LLM-based AHD baselines do not include mechanisms to confine the algorithm complexity. To achieve trade-offs between heuristic algorithm efficiency and effectiveness, we should consider multi-objective LLM-based AHD methods [2]. We will consider this as future work and provide this discussion in our manuscript.\n\n>**Suggestion. Potential applications of MCTS-AHD in other domains:**\n\nThanks for your valuable suggestion. As an advanced LLM-based AHD method, as discussed in [3,4], we believe MCTS-AHD has the potential to be applied to design heuristics for optimization tasks, machine learning tasks (In response to ``Weakness 3 by Reviewer ywZb``, we show the application of MCTS-AHD on a policy optimization task Gym-CarMountain-v0), and some scientific discovery tasks. We will include this discussion in our manuscript.\n\n>**Question 1. Compare to recent reinforcement learning methods:**\n\nThanks for your comment. Recent test-time scaling methods like reinforcement learning-based reasoning model Deepseek-r1 and Openai-o1 cannot directly solve the AHD task with their thinking process. As shown in the table below, we prompt Deepseek-r1 and o1-preview to design heuristics and report the best-designed heuristic over $100$ LLM calls. The advanced test-time scaling methods can only find low-quality heuristics, which demonstrates the significance of using MCTS-AHD in AHD tasks.\n\n\n|Task|TSP-$N$=50||TSP-$N$=100||KP-$N$=100,$W$=25||KP-$N$=200,$W$=25||\n|-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|Method|Obj.↓|Gap|Obj.↓|Gap|Obj.↑|Gap|Obj.↑|Gap|\n|Optimal|5.675|-|7.768|-|40.271|-|57.448|-|\n|Deepseek-r1 (100 trails)|6.916|21.85%|9.595|23.52%|40.225|0.12%|57.395|0.09%|\n|o1-preview (100 trails)|6.959|22.62%|9.706|24.94%|40.225|0.12%|57.395|0.09%|\n|MCTS-AHD(GPT-4o-mini)|**6.225**|**9.69%**|**8.684**|**11.79%**|**40.252**|**0.05%**|**57.423**|**0.04%**|\n|MCTS-AHD(DeepSeek-v3)|6.348|11.85%|8.859|14.04%|40.233|0.10%|57.402|0.08%|\n\n\n>**Question 2. Time and computational resource requirements:**\n\nThanks for your suggestion. As shown in the table below, we provide a detailed comparison of the time and token consumption of MCTS-AHD and population-based baselines in five application scenarios. We calculate the token number based on GPT-4o-mini. Results demonstrate that compared to population-based methods, MCTS-AHD has a slight efficiency decrease and maintains a similar level of token consumption compared to LLM-based AHD baselines.\n\n|Methods|Consumption|Construction-TSP|Construction-KP|ACO-TSO|ACO-MKP|BO-CAF|\n|-|-|:-:|:-:|:-:|:-:|:-:|\n|**EoH**|Time|2h|2h|4h|4h|15h|\n||InputToken|0.8M|0.7M|1M|1M|1.2M|\n||OutputToken|0.2M|0.2M|0.5M|0.5M|0.5M|\n|**ReEvo**|Time|2h|-|5h|5h|-|\n||InputToken|1.1M|-|1.3M|1.3M|-|\n||OutputToken|0.4M|-|0.6M|0.5M|-|\n|**MCTS-AHD**|Time|4h|3h|8h|4h|14h|\n||InputToken|1M|1M|1.2M|1.3M|1.3M|\n||OutputToken|0.3M|0.2M|0.5M|0.6M|0.6M|\n\n>**Reference:**\n\n[1] Liu, Fei, et al. \"Algorithm evolution using large language model.\" arXiv preprint arXiv:2311.15249 (2023).\n\n[2] Yao, Shunyu, et al. \"Multi-objective evolution of heuristic using large language model.\" arXiv preprint arXiv:2409.16867 (2024).\n\n[3] Liu, Fei, et al. \"A systematic survey on large language models for algorithm design.\" arXiv preprint arXiv:2410.14716 (2024).\n\n[4] Liu, Fei, et al. \"Llm4ad: A platform for algorithm design with large language model.\" arXiv preprint arXiv:2412.17287 (2024).", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence. The authors provide extensive experimental results across multiple tasks, showing that MCTS-AHD consistently outperforms existing methods. The use of MCTS to explore the heuristic space and the proposed LLM-based actions are well-justified and demonstrated through both qualitative and quantitative analyses. The results indicate that MCTS-AHD can escape local optima and develop high-quality heuristics.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria are appropriate for the problem at hand. The authors use a variety of NP-hard combinatorial optimization problems and Bayesian Optimization tasks to evaluate MCTS-AHD, ensuring that the method is tested across diverse scenarios. The evaluation criteria, including optimality gaps and performance improvements, are standard and relevant for these tasks.", "theoretical_claims": "The paper does not present any formal theoretical claims or proofs. The focus is on the empirical evaluation of the proposed method.", "experimental_designs_or_analyses": "The experimental designs are sound and valid. The authors conduct experiments on multiple datasets and tasks, comparing MCTS-AHD against various baselines, including handcrafted heuristics, neural combinatorial optimization methods, and existing LLM-based AHD methods. The results are statistically significant and demonstrate the effectiveness of MCTS-AHD. The authors also provide ablation studies to validate the necessity of the proposed components and actions.", "relation_to_broader_scientific_literature": "The key contributions of the paper are well-related to the broader scientific literature. The use of MCTS for heuristic evolution is novel and builds upon existing work in evolutionary algorithms, combinatorial optimization, and LLM-based heuristic design. The paper cites relevant prior work and clearly positions its contributions in the context of existing research.", "essential_references_not_discussed": "The paper provides a thorough review of related work. However, it might benefit from discussing recent advancements in the application of reinforcement learning techniques for heuristic optimization, which could provide additional context for the proposed method.", "other_strengths_and_weaknesses": "* Strengths:\n\n1. The proposed method demonstrates significant improvements over existing LLM-based AHD methods and handcrafted heuristics.\n\n2. The use of MCTS for heuristic evolution is novel and provides a promising direction for future research.\n\n3. The paper includes comprehensive experiments and ablation studies, which validate the effectiveness of the proposed method and its components.\n\n* Weaknesses:\n\n1. The convergence speed of MCTS-AHD could be improved. Future work could explore hybrid methods combining MCTS with population-based approaches to enhance efficiency.\n\n2. The paper does not provide detailed discussions on the computational complexity and scalability of MCTS-AHD for very large-scale optimization problems.", "other_comments_or_suggestions": "The paper is well-written and presents its contributions clearly. A minor suggestion would be to include a discussion on the potential applications of MCTS-AHD in other domains to further highlight its significance.", "questions_for_authors": "1. How does the performance of MCTS-AHD compare to recent reinforcement learning methods like DeepSeek-R1-Zero, which have shown promise in enhancing LLMs for complex tasks?\n\n2. Can the authors provide a detailed comparison of the time and computational resource requirements of MCTS-AHD versus previous population-based methods? This would help in understanding the trade-offs involved in using MCTS for heuristic evolution.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jBOWgJHSFX", "reviewer": "Reviewer_AcSn", "summary": "This article discusses the limitations of population-based LLM-based automatic heuristic design, which makes it difficult to fully explore the heuristic space. This paper introduces MCTS for heuristic exploration and planning. Overall, in experiments, MCTS-AHD achieves significant performance advantages in various typical applications.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you so much for your time and effort in reviewing our work. We are glad to know that you find the proposed MCTS-AHD achieves significant performance advantages in various typical applications, using MCTS in LLM-based AHD is reasonable and novel and this paper is well-written.\n\nWe address your concerns as follows.\n\n>**Experimental Designs Or Analyses. Baselines:**\n\nThanks for your suggestions. We have complemented the ReEvo and HSEvo results in TSP-GLS and ACO TSP as follows.\n|Methods|TSP-ACO$N$=50|TSP-ACO$N$=100|CVRP-ACO$N$=50|CVRP-ACO$N$=100|MKP-ACO$N$=100|MKP-ACO$N$=200|BPP-ACO$N$=500|BPP-ACO$N$=1000|\n|:-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|DeepACO|0.71%|1.26%|**0.00%**|**0.00%**|0.79%|1.20%|**0.00%**|**0.00%**|\n|HSEvo|0.14%|0.50%|5.19%|9.04%|**0.00%**|0.01%|1.20%|1.38%|\n|MCTS-AHD(Ours)|**0.00%**|**0.00%**|4.48%|5.70%|0.03%|**0.00%**|0.48%|0.53%|\n\n|||TSP-GLS||\n|:-|:-:|:-:|:-:|\n|Methods|$N$=100|$N$=200|$N$=500|\n|KGLS|**0.003%**|0.227%|0.958%|\n|HSEvo|0.006%|0.223%|0.972%|\n|MCTS-AHD(Ours)|0.006%|**0.211%**|**0.949%**|\n\n|||TSP-Construction||\n|:-|:-:|:-:|:-:|\n|Methods|N=50|N=100|N=200|\n|POMO|**0.39%**|**3.01%**|20.45%|\n|HSEvo|12.70%|14.32%|15.68%|\n|MCTS-AHD(Ours)|9.69%|11.79%|**13.19%**|\n\nAs the results above show, on almost all these test sets, MCTS-AHD can demonstrate advantages compared to HSEvo and ReEvo.\n\n>**Other Comments Or Suggestions 1. Heuristics' efficiency:**\n\nMCTS-AHD employs the MCTS to comprehensively explore the heuristic space. Therefore, compared to population-based baselines, MCTS-AHD will design more complex and inefficient heuristic algorithms with superior performance. As a future work, we will consider introducing the idea of multi-objective LLM-based AHD [1] to balance the efficiency and performance of heuristics.\n\n>**Other Comments Or Suggestions 2. Clear descriptions and typos:**\n\nThanks for your suggestion. The Gap refers to the distance between the best-performing algorithm in the current dataset. In each dataset, the best-performing LLM-based AHD will be highlighted.\n\n>**Other Comments Or Suggestions 3. p-values for HSEvo and ReEvo:**\n\nThanks for your suggestions. We have complemented the ReEvo and HSEvo results in Constructive TSP, TSP ACO, and MKP ACO for p-values as follows (the computation of avg, std, and p-value is the same as the Appendix F.3.). Results show that in designing constructive heuristics for TSP, MCTS-AHD can demonstrate clear superiority (with more than 90\\% significance) compared to EoH, ReEvo, and HSEvo. In designing ACO heuristics for TSP and MKP, MCTS-AHD can demonstrate clear superiority to ReEvo and slight advantages to HSEvo.\n\n\n|COProblem|Methods|avg|std|p-value|\n|-|-|-|-|-|\n|**General**|**Framework:**|**Step-by-step**|**Construction**||\n|TSP50|EoH|6.386|0.080|**0.002855655**|\n||ReEvo|6.400|0.128|**0.009529994**|\n||HSEvo|6.397|0.069|**0.000796727**|\n||MCTS-AHD|**6.280**|0.071||\n|**General**|**Framework:**|**ACO**|||\n|TSP50|EoH|5.828|0.003|**0.039230447**|\n||ReEvo|5.844|0.029|**0.02477005**|\n||HSEvo|5.819|0.018|0.115934978|\n||MCTS-AHD|**5.795**|0.036||\n|MKP100|EoH|23.199|0.083|**0.037268388**|\n||ReEvo|23.258|0.048|0.20630356|\n||HSEvo|23.277|0.008|0.433650083|\n||MCTS-AHD|**23.279**|0.025||\n\n>**Question 1. Ablation on normalization:**\n\nTo demonstrate the importance of normalization, we present an additional ablation experiment. According to the table below where values are the optimality gaps, the normalization in MCTS-AHD demonstrates high importance.\n\n||TSP50|KP100|\n|-|-|-|\n|MCTS-AHD(10runs)|10.661%|0.059%|\n|*w/o* Normalization|11.977%|0.083%|\n\n\n>**Question 2. Advanced GPT:**\n\nWe complement the results of MCTS-AHD in designing constructive heuristics for TSP and KP with advanced GPT LLMs as follows. Values in the table are gaps to the optimal. Advanced GPT LLMs cannot produce superior performance and GPT-4o-mini may be the best choice for GPT LLMs. \n\n|Method|TSP$N=50$|TSP$N=100$|KP$N=100$|KP$N=200$|\n|-|:-:|:-:|:-:|:-:|\n|MCTS-AHD(GPT-4o-mini)|**9.69%**|11.79%|**0.05%**|**0.04%**|\n|MCTS-AHD(GPT-4o)|10.24%|**11.69%**|0.08%|0.10%|\n|MCTS-AHD(GPT-4)|10.35%|12.22%|0.10%|0.09%|\n\n>**Question 3. MCTS structure:**\n\nThanks for your comment. Generally, MCTS-based LLM reasoning methods involve self-evaluation or rollout to evaluate a better quality value $Q$ of each state, but these methods may lead to biased evaluation results [2]. Optimization tasks provide reliable performance scores for the $Q$ value, so we believe MCTS-AHD does not need self-evaluations or rollouts for $Q$ value estimation.\n\n>**Reference**\n\n[1] Yao, Shunyu, et al. \"Multi-objective evolution of heuristic using large language model.\" arXiv preprint arXiv:2409.16867 (2024).\n\n[2] Xu, Wenda, et al. \"Pride and prejudice: LLM amplifies self-bias in self-refinement.\" arXiv preprint arXiv:2402.11436 (2024).", "claims_and_evidence": "Generally clear and convincing.", "methods_and_evaluation_criteria": "Make sense.", "theoretical_claims": "This paper does not include theoretical claims.", "experimental_designs_or_analyses": "Some baseline results are missed on some testing problems. I think it is convincing to introduce HSEvo in TSP-GLS and ACO. Meanwhile, according to Figure 3, it seems that ReEvo and HSEvo can run for construction-based TSP. Can you demonstrate the results of the construction heuristic designed by these two algorithms on TSP?", "relation_to_broader_scientific_literature": "Ideas: Using MCTS to better explore and plan heuristics is an interesting and reasonable idea.\n\nResults: Generally achieves better results on plenty of CO and non-CO problems compared to recent methods.", "essential_references_not_discussed": "This paper has included prior related findings.", "other_strengths_and_weaknesses": "As strengths:\n\n1.Using MCTS in LLM-based AHD is reasonable and novel.\n\n2.This paper conducts comprehensive evaluations of MCTS-AHD on both CO problems and non-CO problems. MCTS-AHD seems to have a wide range of application scenarios and can get outstanding performance on NP-hard problems with clear descriptions.\n\n3.This paper is well-written and clearly discusses the proposed method MCTS-AHD.\n﻿\n\nThere are no major weaknesses in this paper, Please refer to **Experimental Designs Or Analyses**, **Other Comments Or Suggestions**, and **Questions For Authors** for my concerns and questions.", "other_comments_or_suggestions": "1.In addition to the heuristic performance, heuristics' execution efficiency can be another metric. I wonder about the efficiency of algorithms designed by MCTS-AHD. \n\n2.There is no clear definition of the Gap and highlights in Table 2. Please provide more descriptions.\n\n3.Appendix F.3 well presents the significant lead of MCTS-AHD compared to EoH, and I believe this significance analysis will be a good supplement to the existing work. Can other baselines such as ReEvo and HSEvo be introduced to calculate the p-value?\n\n4.The ``MCT Root`` in Figure 3 should be the ``MCTS Root``.", "questions_for_authors": "1.The Q value design in MCTS is important. Can you conduct another ablation study on the normalization of the Q value in MCTS-AHD?\n\n2.This paper only involves GPT-4o-mini and GPT-3.5-turbo for OpenAI GPT. Will more advanced GPT models perform better on MCTS-AHD?\n\n3.The MCTS you are using seems to have structural differences from LLM reasoning. Can you further explain why it does not include multi-step exploration processes such as self-evaluation or rollback?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposed a Monte Carlo Tree Search method to enhance LLM based Automatic Heuristic Design. Reviewers acknowledged the novelty and good empirical performance of the proposed method. Several concerns are raised, including missing discussions on the code generation error and efficiency of the generated heuristics. All reviewers are positive, but three of them seems not very familiar with this specific topic.
Decision: Accept (poster)