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

arXiv: https://arxiv.org/abs/2501.08603 · HTML: https://mlsanity.com/paper/2501.08603/

## Key facts

- Cited by 109 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 34 of its 115 references that are in the map.
- First posted on arXiv 15 Jan 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 34)

- [Large Language Models as Optimizers](https://mlsanity.com/paper/2309.03409/) (2023)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [A Comprehensive Overview of Large Language Models](https://mlsanity.com/paper/2307.06435/) (2023)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models](https://mlsanity.com/paper/2310.04406/) (2023)
- [Understanding the planning of LLM agents: A survey](https://mlsanity.com/paper/2402.02716/) (2024)
- [ReST-MCTS*: LLM Self-Training via Process Reward Guided Tree Search](https://mlsanity.com/paper/2406.03816/) (2024)
- [Alphazero-like Tree-Search can Guide Large Language Model Decoding and Training](https://mlsanity.com/paper/2309.17179/) (2023)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [LLMs Can't Plan, But Can Help Planning in LLM-Modulo Frameworks](https://mlsanity.com/paper/2402.01817/) (2024)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [Mutual Reasoning Makes Smaller LLMs Stronger Problem-Solvers](https://mlsanity.com/paper/2408.06195/) (2024)
- [Language Model Crossover: Variation through Few-Shot Prompting](https://mlsanity.com/paper/2302.12170/) (2023)
- [System 2 Attention (is something you might need too)](https://mlsanity.com/paper/2311.11829/) (2023)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [Graph Neural Network Guided Local Search for the Traveling Salesperson Problem](https://mlsanity.com/paper/2110.05291/) (2021)
- [A Systematic Survey on Large Language Models for Algorithm Design](https://mlsanity.com/paper/2410.14716/) (2024)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Multi-objective Evolution of Heuristic Using Large Language Model](https://mlsanity.com/paper/2409.16867/) (2024)
- [Algorithm Evolution Using Large Language Model](https://mlsanity.com/paper/2311.15249/) (2023)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2407.00312/) (2024)
- [Make Every Move Count: LLM-based High-Quality RTL Code Generation Using MCTS](https://mlsanity.com/paper/2402.03289/) (2024)
- [Cost-aware Bayesian Optimization](https://mlsanity.com/paper/2003.10870/) (2020)
- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Generating Code World Models with Large Language Models Guided by Monte Carlo Tree Search](https://mlsanity.com/paper/2405.15383/) (2024)
- [Towards Optimizing with Large Language Models](https://mlsanity.com/paper/2310.05204/) (2023)
- [LLM4AD: A Platform for Algorithm Design with Large Language Model](https://mlsanity.com/paper/2412.17287/) (2024)
- [PyBench: Evaluating LLM Agent on various real-world coding tasks](https://mlsanity.com/paper/2407.16732/) (2024)
- [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024)

## Built on by (most cited first, 30 of 109)

- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design](https://mlsanity.com/paper/2508.03082/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [Large Language Models as End-to-end Combinatorial Optimization Solvers](https://mlsanity.com/paper/2509.16865/) (2025)
- [StepORLM: A Self-Evolving Framework With Generative Process Supervision For Operations Research Language Models](https://mlsanity.com/paper/2509.22558/) (2025)
- [HeuriGym: An Agentic Benchmark for LLM-Crafted Heuristics in Combinatorial Optimization](https://mlsanity.com/paper/2506.07972/) (2025)
- [HiFo-Prompt: Prompting with Hindsight and Foresight for LLM-based Automatic Heuristic Design](https://mlsanity.com/paper/2508.13333/) (2025)
- [Glia: A Human-Inspired AI for Automated Systems Design and Optimization](https://mlsanity.com/paper/2510.27176/) (2025)
- [ARS: Automatic Routing Solver with Large Language Models](https://mlsanity.com/paper/2502.15359/) (2025)
- [MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver](https://mlsanity.com/paper/2506.02935/) (2025)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [A Systematic Survey on Large Language Models for Evolutionary Optimization: From Modeling to Solving](https://mlsanity.com/paper/2509.08269/) (2025)
- [Learning to Insert for Constructive Neural Vehicle Routing Solver](https://mlsanity.com/paper/2505.13904/) (2025)
- [Large Reasoning Models are not thinking straight: on the unreliability of thinking trajectories](https://mlsanity.com/paper/2507.00711/) (2025)
- [Generalizable Heuristic Generation Through LLMs with Meta-Optimization](https://mlsanity.com/paper/2505.20881/) (2025)
- [Optimizing Prompt Sequences using Monte Carlo Tree Search for LLM-Based Optimization](https://mlsanity.com/paper/2508.05995/) (2025)
- [Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees](https://mlsanity.com/paper/2505.24627/) (2025)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [iDSE: Navigating Design Space Exploration in High-Level Synthesis Using LLMs](https://mlsanity.com/paper/2505.22086/) (2025)
- [Towards Universal Offline Black-Box Optimization via Learning Language Model Embeddings](https://mlsanity.com/paper/2506.07109/) (2025)
- [MOTIF: Multi-strategy Optimization via Turn-based Interactive Framework](https://mlsanity.com/paper/2508.03929/) (2025)
- [Large Language Models Reasoning Abilities Under Non-Ideal Conditions After RL-Fine-Tuning](https://mlsanity.com/paper/2508.04848/) (2025)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [G-LNS: Generative Large Neighborhood Search for LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2602.08253/) (2026)
- [Reasoning LLMs are Wandering Solution Explorers](https://mlsanity.com/paper/2505.20296/) (2025)
- [Large Language Models in Operations Research: Methods, Applications, and Challenges](https://mlsanity.com/paper/2509.18180/) (2025)
- [PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs](https://mlsanity.com/paper/2601.20539/) (2026)
- [EndoCoT: Scaling Endogenous Chain-of-Thought Reasoning in Diffusion Models](https://mlsanity.com/paper/2603.12252/) (2026)
- [TrajEvo: Trajectory Prediction Heuristics Design via LLM-driven Evolution](https://mlsanity.com/paper/2508.05616/) (2025)
- [An Agentic Framework with LLMs for Solving Complex Vehicle Routing Problems](https://mlsanity.com/paper/2510.16701/) (2025)

## Abstract (arXiv)

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.