# LLM-Evolved Pattern Generators for Optimal Classical Planning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 44 references that are in the map.
- First posted on arXiv 1 Jun 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)
- [Illuminating search spaces by mapping elites](https://mlsanity.com/paper/1504.04909/) (2015)
- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [Monte Carlo Tree Search for Comprehensive Exploration in LLM-Based Automatic Heuristic Design](https://mlsanity.com/paper/2501.08603/) (2025)
- [Action Schema Networks: Generalised Policies with Deep Learning](https://mlsanity.com/paper/1709.04271/) (2017)
- [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023)
- [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024)
- [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)
- [On Using Admissible Bounds for Learning Forward Search Heuristics](https://mlsanity.com/paper/2308.11905/) (2023)

## Abstract (arXiv)

Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaranteeing admissibility, which makes them unsuitable for optimal classical planning. We present the first method for learning domain-dependent heuristics that are admissible by design and thus preserve the optimality guarantees of A* search. Instead of learning a direct mapping from states to heuristic values, we learn to construct abstractions that induce admissible heuristics. We use an LLM-driven evolutionary program-synthesis framework to obtain, for each domain, a program that produces a pattern collection for any task in that domain, and we combine the resulting patterns admissibly via saturated cost partitioning. Empirically, the learned programs encode interpretable domain-specific insights, run with negligible overhead at test time and yield heuristics that match the coverage of state-of-the-art domain-independent baselines on several domains while evaluating each state substantially faster.