Research map / Large language models / Agents, code and math
Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MCTS-AHD, which organizes all LLM-generated heuristics in an MCTS tree with progressive widening and exploration-decay to replace population-based evolution for LLM-based automatic heuristic design.
Problem
Population-based LLM-based automatic heuristic design discards low-performing heuristics that may later become strong, causing premature convergence to local optima in complex heuristic spaces.
Approach
Store all LLM-generated heuristics in a tree and run MCTS with progressive widening, LLM actions (init, two mutations, two crossovers, tree-path reasoning), exploration-decay, and thought-alignment descriptions, so underperforming heuristics can still be developed.
Key results
- On TSP N=50 with GPT-4o-mini, MCTS-AHD reached 9.69% gap versus 12.00% for FunSearch and 12.67% for EoH (step-by-step construction).
- On online BPP average gap, MCTS-AHD achieved 0.89% versus 0.99% (FunSearch), 1.17% (EoH), 1.71% (ReEvo), 1.13% (HSEvo).
- Ablation: removing progressive widening raised TSP50 gap from 10.661% to 12.132%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use MCTS-AHD instead of POMO | step-by-step TSP heuristic design · TSP N=200 | Obj.: 12.897 -> 12.120 | Helped |
| use MCTS-AHD instead of POMO | step-by-step KP heuristic design · KP N=100 W=25 | Obj.: 39.676 -> 40.252 | Helped |
| use MCTS-AHD instead of DeepACO | ACO TSP heuristic design · TSP N=50 | Obj.: 5.842 -> 5.801 | Helped |
| use MCTS-AHD instead of DeepACO | ACO MKP heuristic design · MKP N=100 m=5 | Obj.: 23.093 -> 23.269 | Helped |
| use MCTS-AHD instead of DeepACO | ACO CVRP heuristic design · CVRP N=50 C=50 | Obj.: 8.888 -> 9.286 | Hurt |
| use MCTS-AHD instead of Funsearch | online BPP heuristic design · Online BPP average | Gap: 0.99% -> 0.89% | Helped |
| use MCTS-AHD instead of EoH | BO acquisition-function design · Ackley | Gap: 2.45% -> 2.40% | Helped |
| add Progressive Widening (ablation) | MCTS-AHD · TSP50 | Optimality gap: 12.132% -> 10.661% | Helped |
| add Thought-alignment (ablation) | MCTS-AHD · TSP50 | Optimality gap: 11.640% -> 10.661% | Helped |
| add Exploration-decay (ablation) | MCTS-AHD · TSP50 | Optimality gap: 11.606% -> 10.661% | Helped |
| add tree-path reasoning action s1 (ablation) | MCTS-AHD · TSP50 | Optimality gap: 11.919% -> 10.661% | Helped |
| add mutation action m1 (ablation) | MCTS-AHD · KP100 | Optimality gap: 0.083% -> 0.059% | Helped |
Surprising findings
- MCTS-AHD with GPT-4o-mini beats POMO, an NCO method trained for the task, on 200-node TSP and KP test sets.
Limitations
- Convergence speed of MCTS-AHD can still be improved.
- Relies on LLM API calls and task descriptions for heuristic generation.
Experimental setup
Datasets: TSP instances (64 N=50 for evaluation) 0-1 Knapsack instances (64 N=100, W=25) Weibull online BPP instances CVRP, MKP, offline BPP instances following prior work BO synthetic instances (Ackley, Rastrigin)
Benchmarks: TSP KP online BPP CVRP MKP offline BPP BO cost-aware acquisition function tasks
Metrics: optimality gap objective value average gap to lower bound
Baselines: Nearest-greedy ACO EI GHPP POMO DeepACO FunSearch EoH ReEvo HSEvo
Builds on: EoH FunSearch ReEvo Monte Carlo Tree Search progressive widening
Closest papers by meaning
- HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs (AAAI 2025 · similarity 0.89)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.88)
- Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (ICML 2024 · similarity 0.86)
- PathWise: Planning through World Model for Automated Heuristic Design via Self-Evolving LLMs (ICML 2026 · similarity 0.86)
- Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code (NeurIPS 2025 · similarity 0.85)
- OptiTree: Hierarchical Thoughts Generation with Tree Search for LLM Optimization Modeling (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.