Improved Generalized Planning with LLMs through Strategy Refinement and Reflection
Katharina Stein, Nils Hodel, Daniel Fišer, Jörg Hoffmann, Michael Katz, Alexander Koller · 2025
Read Improved Generalized Planning with LLMs through Strategy Refinement and Reflection by Katharina Stein, Nils Hodel, Daniel Fišer, Jörg Hoffmann, Michael Katz, Alexander Koller (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-13876.txt.
Introduction
Katharina Stein and five co-authors improve a pipeline that lets language models write one program solving a whole family of planning problems, in this 2025 paper. A generalized plan is a single strategy, expressed as code, that handles every task in a domain, from any number of blocks to stack or packages to deliver. Earlier systems had the model draft a strategy in prose, then code it directly. One wrong strategic idea poisoned the result.
The new approach writes the strategy as pseudocode first, a sketch that can be machine-checked and debugged before any real program exists. A reflection step then asks the model to explain each failed plan, and several candidate programs are generated so the best can be picked. Tested on seventeen benchmark domains with two reasoning models, the repairs steadily raise the share of domains solved correctly.
Catalog record
| CREATOR | Katharina Stein, Nils Hodel, Daniel Fišer, Jörg Hoffmann, Michael Katz, Alexander Koller |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-13876
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Improved Generalized Planning with LLMs through Strategy Refinement and Reflection Katharina Stein, Nils Hodel, Daniel Fišer, Jörg Hoffmann, Michael Katz, Alexander Koller Abstract LLMs have recently been used to generate Python programs representing generalized plans in PDDL planning, i.e., plans that generalize across the tasks of a given PDDL domain. Previous work proposed a framework consisting of three steps: the LLM first generates a summary and then a strategy for the domain, both in natural language, and then implements that strategy as a Python program, that gets debugged on example planning tasks. In that work, only one strategy is generated and passed directly to the program generation. If the strategy is incorrect, its implementation will therefore result in an incorrect generalized plan. Here, we introduce an approach that generates the strategy in the form of pseudocode and enables automatic debugging of the pseudocode, hence allowing us to identify and fix errors prior to the generation of the generalized plan itself. Additionally, we extend the Python debugging phase with a reflection step prompting the LLM to pinpoint the reason for the observed plan failure. Finally, we take inspiration from LLM code generation to produce several program variants and pick the best one. Running experiments on 17 benchmark domains, we show that these extensions substantially improve (and never deteriorate) the quality of the generalized plans. In 12 of the domains, our best Python programs solve all tasks that can be generated with the respective instance generator. Introduction Large Language Models (LLMs) have revolutionized a large variety of tasks not only from the field of natural language processing but also from other areas of AI research. One very active area of research deals with LLMs in the context of reasoning problems, and there has been growing interest in using LLMs for symbolic planning in the PDDL language ( McDermott 2000 ; Haslum et al. 2019 ) . First approaches use LLMs to directly generate a plan based on the PDDL or natural language (NL) definition of the task. However, LLMs tend to not perform well in this set-up and are significantly worse than symbolic planners ( Stein et al. 2025 ; Kambhampati et al. 2024 , e.g.) . Improvements have been achieved by incorporating thoughts and automatic corrections based on feedback into the process ( Stein et al. 2025 ; Stechly, Valmeekam, and Kambhampati 2025 ; Valmeekam et al. 2023 , e.g.) , but scalability to larger tasks is still much inferior compared to the symbolic state-of-the-art. In addition, these approaches tend to be very costly in the number of LLM calls, which grows at least linearly in plan length and often with increasing context length. Indeed, Stein et al. 2025 ran only a subset of IPC benchmarks because they limited monetary costs to 150 USD per domain. Silver et al. 2024 proposed an approach that has the potential to overcome these issues. Instead of using LLMs to generate plans for individual planning tasks, they prompt the LLM to produce a generalized plan , that generalizes across the tasks of a given PDDL domain ( Srivastava, Immerman, and Zilberstein 2011 , e.g.) . Such a generalized plan is a structure containing branches (if-then-else behavior) as well as loops to deal with different cases and scaling task size. Silver et al. 2024 show how to use LLMs to generate Python programs representing such plans. This solves the issue regarding cost for LLM calls, as that cost is now per-domain instead of per-task. It also potentially addresses the scalability issue – to the extent that the generalized plan is correct, planning tasks of arbitrary size can be solved. Figure 1: Overview of the framework of Silver et al. 2024 (top) and our framework (bottom). The main three parts for both are the NL generation, the strategy generation and lastly the code generation, i.e. the generation of the generalized plan. Silver et al. let an LLM generate strategy a in NL for the given PDDL domain. They then prompt the LLM to generate Python code for that strategy, that is then debugged (see Figure 1 , top part). Silver et al.’s approach achieves good performance on tasks of varying size in 5 out of 7 tested domains when using GPT-4. However, when extending their evaluation to a larger set of domains, we find that their approach struggles with generating correct generalized plans. A key bottleneck of their approach is the strategy generation step: they use a simple prompting approach to let the LLM create a generalizing NL strategy, which is directly passed to the code generation. If the strategy is incorrect, the LLM is hence prompted to generate a Python function that implements an inadequate logic. Here we address this limitation by treating the strategy generation not only as a Chain-of-Thought (CoT) step ( Wei et al. 2022 ) but as a central part of the generalized planning framework that is responsible for an important sub-task. Figure 1 (bottom) provides an overview of our pipeline. Our main contribution is an approach that allows us to automatically validate and refine the strategy before passing it to the code generation. Furthermore, our approach generates the strategy in the form of pseudocode , that is already closer to the final target structure. For the refinement, we let an LLM generate PDDL plans for a set of debugging tasks based on the pseudocode, and we check correctness of these plans. We then pass the feedback about errors into a reflection step (inspired by e.g. Shinn et al. 2023 , Shinn et al. 2023 ; Madaan et al. 2023 , Madaan et al. 2023 ). In that step, the LLM is prompted to identify the responsible location in the pseudocode, and the reason for the mistake. The LLM is then prompted to update the pseudocode accordingly. We select the best pseudocode based on the debugging tasks as the strategy to be implemented. We also introduce some improvements over Silver et al.’s approach in the code generation step. First, we also add a reflection step to the automated debugging of the Python programs. Second, we take inspiration from LLM-based code generation to produce several initial versions of the program ( Tang et al. 2024 ; Wang et al. 2024 , e.g.) . We pick the best program based on performance on the debugging tasks. We empirically evaluate our method on 17 PDDL domains, including the ones Silver et al. ran their experiments on. We use GPT-4o as the LLM. Compared to Silver et al., our approach improves performance substantially in 9 of the domains and exhibits mildly worse performance only in 1 domain. In 12 domains, our approach achieves perfect coverage; indeed, we manually verified that in all these domains our best Python program solves all tasks that can be generated with the respective instance generator. 1 1 1 All code and data will be made available. Background Classical planning. In classical planning the task is to find a sequence of actions (a plan) that leads from a given initial state into a state that satisfies a goal condition. A commonly used formalism to define classical planning tasks is the Planning Domain Definition Language (PDDL) ( McDermott 2000 ; Haslum et al.