Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design

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.

We address your concerns as follows.

Experimental Designs Or Analyses. Baselines:

Thanks for your suggestions. We have complemented the ReEvo and HSEvo results in TSP-GLS and ACO TSP as follows.

As the results above show, on almost all these test sets, MCTS-AHD can demonstrate advantages compared to HSEvo and ReEvo.

Other Comments Or Suggestions 1. Heuristics' efficiency:

MCTS-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.

Other Comments Or Suggestions 2. Clear descriptions and typos:

Thanks 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.

Other Comments Or Suggestions 3. p-values for HSEvo and ReEvo:

Thanks 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.

Question 1. Ablation on normalization:

To 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.

Question 2. Advanced GPT:

We 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.

Question 3. MCTS structure:

Thanks 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.

Reference

[1] Yao, Shunyu, et al. "Multi-objective evolution of heuristic using large language model." arXiv preprint arXiv:2409.16867 (2024).

[2] Xu, Wenda, et al. "Pride and prejudice: LLM amplifies self-bias in self-refinement." arXiv preprint arXiv:2402.11436 (2024).

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.

We address your concerns as follows.

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.

Thanks 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.

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.

Thank 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.

Besides 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.

Suggestion. Potential applications of MCTS-AHD in other domains:

Thanks 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.

Question 1. Compare to recent reinforcement learning methods:

Thanks 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.

Question 2. Time and computational resource requirements:

Thanks 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.

Reference:

[1] Liu, Fei, et al. "Algorithm evolution using large language model." arXiv preprint arXiv:2311.15249 (2023).

[2] Yao, Shunyu, et al. "Multi-objective evolution of heuristic using large language model." arXiv preprint arXiv:2409.16867 (2024).

[3] Liu, Fei, et al. "A systematic survey on large language models for algorithm design." arXiv preprint arXiv:2410.14716 (2024).

[4] Liu, Fei, et al. "Llm4ad: A platform for algorithm design with large language model." arXiv preprint arXiv:2412.17287 (2024).

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.

We address your concerns as follows.

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.

Thank 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.

For 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)$.

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.

Thanks 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.

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.

Thanks 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.

To 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.

In 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.

Weakness 4. Numerous LLM evaluations: MCTS-AHD requires numerous LLM evaluations during its tree search.

Thanks 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.

However, 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.

Reference:

[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).

[2] Hendrycks D, Basart S, Kadavath S, et al. Measuring coding challenge competence with apps[J]. arXiv preprint arXiv:2105.09938, 2021.

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.

We address your concerns as follows.

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.

Thank 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.

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?

Thanks 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.

Other Comments Or Suggestions. Typo: page 6 line 298 LMM - LLM problems.

Thank you for pointing out the typos. We will correct typos accordingly.

References

[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).

[2] Hendrycks D, Basart S, Kadavath S, et al. Measuring coding challenge competence with apps[J]. arXiv preprint arXiv:2105.09938, 2021.

[3] Liu, Fei, et al. "A systematic survey on large language models for algorithm design." arXiv preprint arXiv:2410.14716 (2024).