# Classical Planning with LLM-Generated Heuristics: Challenging the State of the Art with Python Code arXiv: https://arxiv.org/abs/2503.18809 ยท HTML: https://mlsanity.com/paper/2503.18809/ ## Key facts - Cited by 18 papers in the map (data through 14 Oct 2026). - Builds on 34 of its 92 references that are in the map. - First posted on arXiv 24 Mar 2025. ## Builds on (most cited first, 30 of 34) - [DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learning](https://mlsanity.com/paper/2501.12948/) (2025) - [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022) - [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024) - [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023) - [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024) - [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022) - [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024) - [LLM+P: Empowering Large Language Models with Optimal Planning Proficiency](https://mlsanity.com/paper/2304.11477/) (2023) - [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023) - [Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning](https://mlsanity.com/paper/2305.14909/) (2023) - [Generalized Planning in PDDL Domains with Pretrained Large Language Models](https://mlsanity.com/paper/2305.11014/) (2023) - [Chain of Thoughtlessness? An Analysis of CoT in Planning](https://mlsanity.com/paper/2405.04776/) (2024) - [S*: Test Time Scaling for Code Generation](https://mlsanity.com/paper/2502.14382/) (2025) - [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023) - [The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks](https://mlsanity.com/paper/1401.3839/) (2014) - [On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)](https://mlsanity.com/paper/2302.06706/) (2023) - [Learning Domain-Independent Planning Heuristics with Hypergraph Networks](https://mlsanity.com/paper/1911.13101/) (2019) - [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) - [Thought of Search: Planning with Language Models Through The Lens of Efficiency](https://mlsanity.com/paper/2404.11833/) (2024) - [Learning Domain-Independent Heuristics for Grounded and Lifted Planning](https://mlsanity.com/paper/2312.11143/) (2023) - [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022) - [NL2Plan: Robust LLM-Driven Planning from Minimal Text Descriptions](https://mlsanity.com/paper/2405.04215/) (2024) - [Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning](https://mlsanity.com/paper/2403.16508/) (2024) - [Exploring and Benchmarking the Planning Capabilities of Large Language Models](https://mlsanity.com/paper/2406.13094/) (2024) - [Planning in Strawberry Fields: Evaluating and Improving the Planning and Scheduling Capabilities of LRM o1](https://mlsanity.com/paper/2410.02162/) (2024) - [LLMs Can Plan Only If We Tell Them](https://mlsanity.com/paper/2501.13545/) (2025) - [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022) - [Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generation](https://mlsanity.com/paper/2412.10675/) (2024) - [Successor-Generator Planning with LLM-generated Heuristics](https://mlsanity.com/paper/2501.18784/) (2025) ## Built on by (most cited first, 18 of 18) - [Teaching LLMs to Plan: Logical Chain-of-Thought Instruction Tuning for Symbolic Planning](https://mlsanity.com/paper/2509.13351/) (2025) - [Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policies](https://mlsanity.com/paper/2508.18507/) (2025) - [Frontier Large Language Models Rival State-of-the-Art Planners](https://mlsanity.com/paper/2511.09378/) (2025) - [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025) - [RunAgent: Interpreting Natural-Language Plans with Constraint-Guided Execution](https://mlsanity.com/paper/2605.00798/) (2026) - [Coding Agents for Generalized Task and Motion Planning Problems](https://mlsanity.com/paper/2609.30233/) (2026) - [Agentic LLM Planning via Step-Wise PDDL Simulation: An Empirical Characterisation](https://mlsanity.com/paper/2603.06064/) (2026) - [Planning in the LLM Era: Building for Reliability and Efficiency](https://mlsanity.com/paper/2605.21902/) (2026) - [LLM-Evolved Domain-Independent Heuristics for Symbolic AI Planning](https://mlsanity.com/paper/2605.29649/) (2026) - [Scaling Multi-Agent Epistemic Planning through GNN-Derived Heuristics](https://mlsanity.com/paper/2508.12840/) (2025) - [Iterative Deployment Improves Planning Skills in LLMs](https://mlsanity.com/paper/2512.24940/) (2025) - [Personalized Medication Planning via Direct Domain Modeling and LLM-Generated Heuristics](https://mlsanity.com/paper/2601.03687/) (2026) - [Hierarchical Task Network Planning with LLM-Generated Heuristics](https://mlsanity.com/paper/2605.07707/) (2026) - [Property-Guided LLM Program Synthesis for Planning](https://mlsanity.com/paper/2605.16142/) (2026) - [LLM-Evolved Pattern Generators for Optimal Classical Planning](https://mlsanity.com/paper/2606.02438/) (2026) - [Learning Admissible Heuristics via Cost Partitioning](https://mlsanity.com/paper/2606.04597/) (2026) - [Training the Orchestrator: A Supervised Approach to End-to-End PDDL Planning with LLM Agents](https://mlsanity.com/paper/2606.21740/) (2026) - [Planning with Transformers: Chain of Computation and Structured Context Windows](https://mlsanity.com/paper/2607.17710/) (2026) ## Abstract (arXiv) In recent years, large language models (LLMs) have shown remarkable capabilities in various artificial intelligence problems. However, they fail to plan reliably, even when prompted with a detailed definition of the planning task. Attempts to improve their planning capabilities, such as chain-of-thought prompting, fine-tuning, and explicit "reasoning" still yield incorrect plans and usually fail to generalize to larger tasks. In this paper, we show how to use LLMs to generate correct plans, even for out-of-distribution tasks of increasing size. For a given planning domain, we ask an LLM to generate several domain-dependent heuristic functions in the form of Python code, evaluate them on a set of training tasks within a greedy best-first search, and choose the strongest one. The resulting LLM-generated heuristics solve many more unseen test tasks than state-of-the-art domain-independent heuristics for classical planning. They are even competitive with the strongest learning algorithm for domain-dependent planning. These findings are especially remarkable given that our proof-of-concept implementation is based on an unoptimized Python planner and the baselines all build upon highly optimized C++ code. In some domains, the LLM-generated heuristics expand fewer states than the baselines, revealing that they are not only efficiently computable, but sometimes even more informative than the state-of-the-art heuristics. Overall, our results show that sampling a set of planning heuristic function programs can significantly improve the planning capabilities of LLMs.