Improved Generalized Planning with LLMs through Strategy Refinement and Reflection

We introduce an approach for generating improved generalized plans in PDDL planning in the form of Python programs using LLMs. Generalized plans are plans that generalize across the tasks of a given PDDL domain.

For example, in the Logistics domain the goal is to transport packages from their initial location to their goal location using trucks and airplanes. A planning task from that has a specified number of cities each consisting of the same number of locations out of which one is an airport. A specified number of airplanes is randomly distributed across all airports. Each task also includes a specified number of trucks, such that there is at least one truck per city. A specified number of packages is distributed over all possible locations. The goal specifies for each package a goal location.

Our approach generates Python programs that can take any of such tasks from the Logistics domain as input and generates the corresponding plan, i.e. the sequence of actions required to transfomr the specific initial state into a state satisfying the goal constraints.

Overview

Previous work (Silver et al. ‘24’) proposed a framework consisting of three steps:

1. the LLM first generates a summary of the domain in natural language,
2. the LLM then generates a strategy for the domain, again in natural language, and
3. the LLM then implements that strategy as a Python program, that gets debugged on example planning tasks.
   

In their 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.

Our contributions

• generation of strategies in the form of pseudocode.
• an approach to automatically debug the pseudocode.

This approach allows:

• to shift most of the work beyond the mere conversion into Python to the step preceding the code generation.
• intermediate form of the strategy is closer to the final target output, has a clearer structure and less ambiguity than NL strategies form previous work (see Figure below).
• to identify and fix errors in the strategy prior to the code generation.

• Additionally, we extend the Python debugging phase with a reflection step prompting the LLM to pinpoint the reason for the observed plan failure.
• 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.

Our pipeline

The following Figure illustrates our full pipeline, also in comparison to the pipeline from Silver et al.
Below you can find examples of the most relevant steps with prompts and outputs for the Logistics domain.

Examples Logistics Domain

2.2 Strategy Generation: pseudocode debugging

• An LLM is prompted to generate the PDDL plan for a given debugging task (in NL) by following the strategy generated in the previous step. The generated plan is then validated using VAL.
• If the plan is incorrect, the validation output is converted into a feedback message about the mistake.
• The feedback is combined with the generated plan and instructions to reflect about the part of the pseudocode that caused the mistake and the reason why that part is incorrect (inspired by e.g. Madaan et al. 2023; Shinn et al. 2023).
• After generating the reflection response, the LLM is then asked to correct the pseudocode by thinking step-by-step.
• This process is continued until the LLM generates correct plans for all debugging tasks or a maximum number of debugging iterations, K_S, is reached.
• The pseudocode that resulted in the highest number of solved tasks is selected for the code generation step.

Data

For our experiments, we focus on domains that have previously been used in research on LLMs in the context of classical planning. In particular, we use the domains from Silver et al. (2024)’s generalized planning experiments and Stein et al. (2025)’s LLM action-choice experiments. Table 2 shows for each of the domains the sources of the tasks we include in our experiments. All tasks included in our experiments are solvable. The right column of Table 2 shows the origin of the instance generators that we used to generate additional tasks for some of the domains, and that we used for the manual evaluation of the generalization power of our generalized plans.

Table 2

Experiments and Results

Evaluation

• Metric: Coverage - The percentage of evaluation tasks for which the Python program generates a correct plan.
  • Average: The average coverage over all 3 runs.
  • Best: The coverage of the best run.
    
• Time limit of 45 seconds for running the programs.
• Each program is ran 4 times with random ordering of ob objects and initial/goal facts and treated as correct if each ordering results in a correct plan.
• Final evaluation based on the best generated program as determined on the debugging data.
• For each configuration, we conducted 3 runs of the complete pipeline, each with a different pair of initial example tasks provided to the LLM.

Our Framework
We test our framework for two different combinations of the maximum number of initial programs (N ) and code debugging steps (KC ) and conduct three ablation experiments to assess the effect of our pipeline extensions.
We also compare the performance of our approach to 2 baselines.

The set-ups tested are the following:

• Re-implementation of Silver et al., adapted for a fairer comparison:
  • more similar phrasing of prompts, including instructions to think step-by-step for NL strategy generation.
  • separation of the three parts of the pipeline.
  • example task an failed task is provided in the Python format during code generation.
  • selection of final program based on debugging data.

Symbolic Baselines

• lm: optimal A* and the LM-Cut heuristic (Helmert et al. 2009), ran with a 30-minute time limit.
• ff: satisficing greedy best-first search with FF heuristic (Hoffmann and Nebel, 2001), ran with a 30-minute time limit.
• ff= and lm=: Like lm and ff but with the same 45s time limit as applied to the execution of generalized plans.

Results:

References

BibTeX

@misc{stein2025improvedgeneralizedplanningllms,
  title={Improved Generalized Planning with LLMs through Strategy Refinement and Reflection}, 
  author={Katharina Stein and Nils Hodel and Daniel Fišer and Jörg Hoffmann and Michael Katz and Alexander Koller},
  year={2025},
  eprint={2508.13876},
  archivePrefix={arXiv},
  primaryClass={cs.AI},
  url={https://arxiv.org/abs/2508.13876},
}
}