Improved Generalized Planning with LLMs through Strategy Refinement and Reflection

1. Problem Statement

The paper addresses the challenge of Generalized Planning in the context of classical planning (PDDL). Unlike standard planning, which solves a single specific task, generalized planning seeks to generate a single policy or program (e.g., a Python script) that can solve all tasks within a given PDDL domain, regardless of the number of objects or specific initial/goal states.

While Large Language Models (LLMs) have shown promise in generating plans for individual tasks, they struggle with:

• Scalability: Generating plans for every new instance is computationally expensive and token-heavy.
• Generalization: Directly generating generalized plans often fails because the LLM cannot abstract high-level logic from specific examples.
• Error Propagation: Previous approaches (e.g., Silver et al., 2024) generate a natural language (NL) strategy and immediately convert it to code. If the NL strategy is flawed, the resulting code is inevitably incorrect, and debugging the code alone cannot fix the underlying logical error in the strategy.

2. Methodology

The authors propose a refined pipeline that introduces Strategy Refinement and Reflection at two distinct levels: the strategy level (pseudocode) and the code level (Python). The framework consists of three main phases:

A. Natural Language (NL) Generation

• The LLM generates a natural language summary of the domain and specific example tasks based on the PDDL domain definition. This serves as the context for subsequent steps.

B. Strategy Generation and Validation (The Core Innovation)

Instead of generating a simple NL summary, the LLM is prompted to generate a Pseudocode Strategy.

• Pseudocode Format: The strategy is expressed in structured pseudocode (using keywords like for, if, continue) rather than free-form text. This bridges the gap between natural language and executable code.
• Strategy-Level Debugging: Since pseudocode is not directly executable, the system validates it indirectly:
  1. The LLM is prompted to generate a PDDL plan for a set of "debugging tasks" by strictly following the provided pseudocode strategy.
  2. A symbolic plan validator (VAL) checks if the generated plan is valid.
  3. Reflection Step: If the plan fails, the LLM receives feedback and is prompted to reflect on why the strategy failed (identifying the specific logical gap) before revising the pseudocode.
  4. This loop continues until the strategy produces valid plans for all debugging tasks. The best-performing pseudocode is selected for the next phase.

C. Code Generation and Refinement

• Multi-Variant Generation: Inspired by code generation techniques, the system generates multiple initial Python program variants. To ensure diversity without relying on temperature sampling (which can be unstable), the authors randomly shuffle the order of objects and facts in the input prompt.
• Code-Level Debugging & Reflection:
  1. Each Python program is run on the debugging tasks.
  2. If a program fails (timeout, exception, or invalid plan), the system provides feedback.
  3. Reflection: Similar to the strategy phase, the LLM is prompted to analyze the error (e.g., "Why did this action fail?") before attempting to fix the code.
  4. The system also includes positive feedback, showing tasks the code solved correctly to reinforce valid logic.
• Selection: The final generalized plan is the Python program that achieves the highest coverage on the debugging tasks.

3. Key Contributions

1. Strategy Refinement via Pseudocode: Moving strategy generation from pure natural language to structured pseudocode allows for earlier detection of logical errors before code generation begins.
2. Two-Level Reflection Mechanism: Introducing a reflection step where the LLM must explicitly identify the cause of an error (both in strategy and code) before attempting a fix significantly improves correction accuracy.
3. Indirect Strategy Validation: A novel method to validate non-executable pseudocode by having the LLM generate intermediate PDDL plans and using a symbolic validator to provide ground-truth feedback.
4. Diverse Code Sampling: Generating multiple program variants by perturbing input ordering rather than model temperature, ensuring robust exploration of the solution space.

4. Experimental Results

The authors evaluated their approach on 17 PDDL domains (including 7 from previous work and 10 new ones) using four LLMs: GPT-4o, Llama 3.3, DeepSeek-V3.2, and Qwen3-30B-A3B-Thinking.

• Performance Improvement:
  • The best configuration (F5-3 with DeepSeek) achieved an average coverage of 82% across all domains.
  • Compared to the baseline (Silver et al., 2024), the new approach improved performance by 12–23 percentage points depending on the model.
  • In 14 out of 17 domains, the approach achieved 100% coverage in at least one run.
• Generalization:
  • Manual analysis confirmed that programs achieving 100% coverage on evaluation data generalized to arbitrary task sizes and all tasks generatable by the domain's instance generator.
  • The approach performed well on "costumed" domains (where names were changed but logic remained the same), indicating the LLMs are reasoning about the strategy rather than memorizing training data.
• Efficiency vs. Quality:
  • While the generation process is more computationally expensive per domain (due to multiple iterations), the resulting Python programs execute significantly faster (up to 97% of tasks faster) than symbolic satisficing planners (FF) during execution.
  • The generated plans are only slightly longer (approx. 1.1x) than optimal plans.

5. Significance

This paper represents a significant step forward in Neuro-Symbolic Planning.

• Bridging the Gap: It effectively bridges the gap between the reasoning capabilities of LLMs and the rigor of symbolic planning by using LLMs to generate high-level control structures (strategies) and symbolic tools to validate them.
• Scalability: By generating a single generalized program per domain, the method eliminates the need for LLM calls during the actual planning phase, making it scalable to large, unseen problem instances.
• Reliability: The introduction of reflection and multi-stage validation addresses the "hallucination" problem common in LLMs, ensuring that the generated plans are not just plausible but logically sound and executable.

The work demonstrates that with the right iterative refinement and validation loops, LLMs can be trained to produce robust, generalizable planning policies that outperform both previous LLM-based methods and, in terms of execution speed, traditional symbolic planners.