# LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 28 May 2026.

## Builds on (most cited first, 12 of 12)

- [AlphaEvolve: A coding agent for scientific and algorithmic discovery](https://mlsanity.com/paper/2506.13131/) (2025)
- [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014)
- [Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limits](https://mlsanity.com/paper/2109.10129/) (2021)
- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code](https://mlsanity.com/paper/2503.18809/) (2025)
- [Successor-Generator Planning with LLM-generated Heuristics](https://mlsanity.com/paper/2501.18784/) (2025)
- [Improved Generalized Planning with LLMs through Strategy Refinement and Reflection](https://mlsanity.com/paper/2508.13876/) (2025)
- [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025)
- [Symmetry-Aware Transformer Training for Automated Planning](https://mlsanity.com/paper/2508.07743/) (2025)

## Built on by (most cited first, 1 of 1)

- [LLM-Guided Evolutionary Search for Constraint Model Reformulation to Improve Solver Efficiency](https://mlsanity.com/paper/2607.28268/) (2026)

## Abstract (arXiv)

Heuristic search is the dominant paradigm in symbolic AI planning, and the strongest heuristics are the result of decades of work by planning researchers. Recent work has shown that large language models (LLMs) can design heuristics for individual planning domains, but no LLM-generated heuristic has so far worked on arbitrary planning tasks. In this paper, we use evolutionary search to produce the first LLM-generated domain-independent heuristics that exceed the hand-engineered state of the art. We let an LLM mutate parent heuristics written in C++, store candidates in a MAP-Elites archive keyed on informedness and speed and calculate fitness scores by blending coverage with solving time. To place the evolved programs in context, we additionally benchmark a broad set of hand-engineered heuristics on their informedness-speed tradeoff, which to our knowledge has not been done before. On unseen testing domains, our best evolved heuristic solves more tasks than even the strongest baseline, with our full heuristic suite spanning the Pareto frontier of said tradeoff. We also find that seeding evolution from the trivial blind heuristic outperforms seeding from the strong FF heuristic, even when the resulting program is itself an FF variant, and that LLM reasoning effort affects how often candidates compile much more than the quality of those that do. Because the evolved programs are plain C++, they slot into existing planners as drop-in replacements and inherit the soundness and completeness guarantees of the underlying search.