TLDR: This research introduces a novel approach to improve generalized planning with Large Language Models (LLMs) by refining strategies at the pseudocode level before code generation and enhancing debugging with reflection and multiple code variants. This significantly boosts the reliability and performance of LLM-generated generalized plans across various planning domains, enabling them to solve entire domains with high efficiency and low cost.
Large Language Models (LLMs) have shown remarkable capabilities across various AI tasks, including symbolic planning. However, directly using LLMs to generate plans for individual tasks often falls short compared to traditional symbolic planners, struggling with scalability and incurring high costs due to numerous LLM calls.
A promising alternative is generalized planning, where LLMs create a single program that can solve all tasks within a given planning domain. This approach significantly reduces costs by shifting the LLM’s effort from per-task to per-domain. Previous work, like that by Silver et al. (2024), involved LLMs generating a natural language summary, then a strategy, and finally implementing that strategy as a Python program, which was debugged on example tasks.
Addressing the Strategy Bottleneck
A key limitation of prior methods was that if the initial natural language strategy was flawed, the resulting Python program would also be incorrect. The new research, titled “Improved Generalized Planning with LLMs through Strategy Refinement and Reflection,” by Katharina Stein, Nils Hodel, Daniel Fiˇser, J¨org Hoffmann, Michael Katz, and Alexander Koller, tackles this challenge head-on. Their approach introduces a crucial intermediate step: generating the strategy in pseudocode and enabling its automatic debugging before any Python code is written.
Instead of a simple natural language strategy, the LLM is now prompted to create a detailed pseudocode strategy. This pseudocode is structured to be easily convertible into an executable program, incorporating elements like “for each” and “if” statements. This makes the strategy itself a more precise specification for the subsequent code generation.
Automatic Pseudocode Validation and Refinement
To ensure the pseudocode strategy is correct, the researchers developed an innovative validation process. The LLM is prompted to generate PDDL (Planning Domain Definition Language) plans for a set of debugging tasks by following the pseudocode. These generated plans are then checked for correctness using a symbolic plan validator. If a plan is incorrect, a detailed feedback message is generated.
Crucially, this feedback triggers a “reflection” step. Inspired by human learning, the LLM is prompted to analyze the feedback, identify the specific part of the pseudocode that caused the mistake, and explain why it was inadequate. Only after this reflection does the LLM attempt to correct the pseudocode. This iterative process continues until the pseudocode leads to correct plans for all debugging tasks, or a maximum number of iterations is reached. The best-performing pseudocode is then selected for code generation.
Enhanced Code Generation and Debugging
The improvements don’t stop at the strategy level. The new framework also refines the Python code generation phase. Similar to pseudocode debugging, a reflection step is added to the automatic debugging of the Python programs. When a program fails, the LLM is asked to reflect on the specific code section causing the error and why it’s inadequate, before attempting a revision. This helps the LLM pinpoint and fix logical errors more effectively.
Furthermore, the approach takes inspiration from LLM-based code generation techniques by producing multiple program variants. Instead of just one attempt, the system generates several initial versions of the Python program by subtly changing the order of objects and facts in the input prompt. Each variant is then debugged. The best-performing program, based on its success with debugging tasks, is ultimately chosen.
Also Read:
- Enhancing Robot Dexterity: A New Approach to Vision-Language-Action Planning
- Bridging the Language Gap: How AI is Enabling Robots to Understand Human Instructions
Impressive Results and Efficiency
The researchers evaluated their method on 17 benchmark domains, including those used in previous studies. Using GPT-4o as the LLM, their approach substantially improved performance in 9 domains and never deteriorated it. Remarkably, in 12 of these domains, their best Python programs achieved perfect coverage, meaning they could solve all tasks generated by the respective instance generators. This demonstrates a significant leap in the generalization power of LLM-generated plans.
Beyond coverage, the new method also offers efficiency benefits. While symbolic planners can be computationally intensive, the LLM-generated Python programs are significantly faster at generating plans for individual tasks once the generalized plan is created. On average, the generalized planner took only 0.024 times the time a satisficing symbolic planner required. The monetary cost for LLM calls to obtain these generalized plans was also minimal, typically less than 14 USD per domain.
This research highlights that by focusing on strategy refinement and incorporating reflection at both the pseudocode and code levels, LLMs can be made substantially more effective for generalized planning. The resulting Python programs are not only more accurate but also highly efficient, capable of solving entire planning domains. For more details, you can read the full paper here.
