🤖 machine learning

PlanningBench: Generating Scalable and Verifiable Planning Data for Evaluating and Training Large Language Models

PlanningBench is a novel framework that transforms planning data creation from fixed collections into a controllable, scalable generation process using a structured taxonomy and constraint-driven synthesis, enabling both rigorous evaluation of current LLM limitations and effective reinforcement learning training to enhance generalizable planning abilities.

Original authors: Ziliang Zhao, Zenan Xu, Shuting Wang, Hongjin Qian, Yan Lei, Minda Hu, Zhao Wang, Shihan Dou, Zhicheng Dou, Pluto Zhou

Published 2026-05-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ziliang Zhao, Zenan Xu, Shuting Wang, Hongjin Qian, Yan Lei, Minda Hu, Zhao Wang, Shihan Dou, Zhicheng Dou, Pluto Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a very smart, but inexperienced, apprentice how to be a master chef. You could give them a single, fixed recipe book (the old way of testing AI), but that only tells you if they can follow that specific book. It doesn't tell you if they can handle a sudden shortage of ingredients, a broken oven, or a customer who changes their order halfway through.

PlanningBench is a new "kitchen simulator" designed to test and train Large Language Models (LLMs) on the complex art of planning. Instead of just handing the AI a static list of problems, the researchers built a machine that can generate infinite, unique, and verifiable planning challenges on the fly.

Here is how the paper breaks down, using simple analogies:

1. The Problem: The "Fixed Menu" Limitation

Before this paper, testing AI planning was like giving a student a fixed menu of 50 math problems. If they got them right, they passed. But:

Limited Variety: The menu only had 50 problems. Once the student memorized them, the test was useless.
Fake Difficulty: The "hard" problems were just longer or had more numbers, not necessarily more logically complex.
No Feedback Loop: If the student got it wrong, the test didn't tell you why or help them learn for the next time.

2. The Solution: The "Infinite Recipe Generator" (PlanningBench)

The authors created a framework called PlanningBench. Think of it as a master chef (the researchers) who wrote a "Cookbook of Constraints" rather than a list of recipes.

The Taxonomy (The Cookbook): They organized real-world planning tasks (like scheduling meetings, planning a wedding, or managing a power grid) into 6 main categories and over 30 specific types.
The Constraints (The Ingredients): They defined rules like "Time Windows" (you can't cook dinner before 5 PM), "Capacity Limits" (the oven only fits 4 pizzas), and "Dependencies" (you can't serve the cake before the meal is eaten).
The Generator (The Machine): This machine takes a "recipe type" (e.g., "Meeting Planning") and randomly mixes in different constraints (e.g., "Room A is broken," "The CEO is only free on Tuesdays"). It creates a unique, self-contained problem every time.

3. The "Closed-Loop" Kitchen

The system doesn't just spit out problems; it runs a three-person team to ensure quality:

The Generator: Creates a new, tricky planning problem.
The Responder (The Apprentice): The AI tries to solve it.
The Critic (The Inspector): A specialized AI checks the answer against a strict "Checklist."
- Did they use the right room?
- Did they run out of budget?
- Did they forget the vegetarian option?

If the Responder solves it too easily, the Critic signals the Generator to make the next problem harder (e.g., "Add a fire drill scenario"). If the Responder fails, the system keeps the problem but notes where the AI went wrong. This creates a difficulty curve that adapts to the AI's skill level.

4. The "Gold Standard" Rule

A crucial finding in the paper is about Determinate Solutions.

The Analogy: Imagine asking the AI to "write a good story." There are a million ways to do that, and it's hard to say which one is "best."
The Fix: PlanningBench forces the AI to solve problems with one clear, optimal answer (like a math problem or a specific schedule).
Why it matters: The paper found that when the AI trains on problems with a single "correct" answer, it learns better. It's like training a runner on a track with a clear finish line, rather than asking them to "run somewhere nice." This clarity gives the AI a stronger signal on how to improve.

5. The Results: Testing and Training

The researchers used this system in two ways:

A. The Exam (Evaluation)
They tested top AI models (like GPT-5.4 and others) on these generated problems.

The Outcome: Even the smartest models struggled. The best model only solved about 63% of the problems perfectly.
The Insight: The AI is good at satisfying local rules (e.g., "I scheduled the meeting") but bad at global consistency (e.g., "But that meeting overlaps with the CEO's flight"). The biggest failure wasn't formatting; it was calculation errors and forgetting constraints (like running out of time or money).

B. The Training Camp (Reinforcement Learning)
They took a model and trained it using the verified data from PlanningBench.

The Outcome: The model didn't just get better at the specific problems it saw; it got better at unseen planning tasks (like travel planning) and even general instruction-following tasks.
The Lesson: Training on these "strict, verifiable" planning problems taught the AI how to juggle multiple rules at once, a skill that transferred to other areas.

Summary

PlanningBench is a tool that turns planning from a "guessing game" into a "measurable science."

It moves away from fixed test banks to infinite, generated scenarios.
It uses a closed-loop system (Generator -> Solver -> Critic) to ensure problems are solvable but challenging.
It proves that clear, single-answer goals are the best way to train AI to plan.
It reveals that current AI models are still quite bad at keeping all the balls in the air when constraints get tight, but they can learn to get better with the right kind of training data.

The paper concludes that to make AI truly "smart" at planning, we need data that is scalable (can grow infinitely), diverse (covers many real-world situations), and verifiable (we can mathematically prove the answer is right). PlanningBench provides exactly that.

Technical Summary: PlanningBench

Problem Statement

Planning is a fundamental capability for Large Language Models (LLMs), requiring the coordination of goals, constraints, resources, and long-term consequences into executable solutions. However, existing planning benchmarks suffer from significant limitations:

Fixed Data Collections: Most benchmarks treat planning data as static, fixed collections of instances rather than controllable generation targets, limiting scenario coverage and diversity.
Superficial Difficulty Proxies: Difficulty is often approximated by surface-level metrics (e.g., prompt length or number of requirements) rather than structural sources such as constraint coupling, hierarchy, or task-specific design.
Lack of Training Support: Existing benchmarks offer limited support for scalable generation, automatic verification, or planning-oriented training, making it difficult to diagnose model limits or improve generalizable planning behaviors.

Methodology: PlanningBench Framework

The authors introduce PlanningBench, a framework for generating scalable, diverse, and verifiable planning data for both evaluation and training. The methodology proceeds in two macro stages:

1. Task and Constraint Taxonomy Construction

Instead of cataloging domains, the authors abstract reusable planning schemas from real-world scenarios (e.g., scheduling, logistics, emergency response) into a structured taxonomy.

Task Taxonomy: Organizes planning tasks into six families based on structural complexity: Scheduling and Timetabling, Allocation and Matching, Shift and Workforce Scheduling, Routing and Travel, Project and Production Operations, and Emergency Response and Public Service. This covers over 30 specific task types and numerous subtasks.
Constraint Taxonomy: Constraints are modeled in three layers to ensure verifiability and controllability:
- General Constraints: Shared across tasks (e.g., input completeness, time windows).
- Task-Specific Constraints: Tied to specific task structures.
- Specialized Stateful Constraints: Dependent on previously executed actions or accumulated state.
Difficulty Levels: Constraints are categorized into Basic (feasibility), Medium (optimization/fairness), and Hard (robustness, infeasibility detection, exception recovery).

2. Constraint-Driven Synthesis Pipeline

PlanningBench employs a closed-loop synthesis process involving three components:

Generator: Samples task-constraint configurations and instantiates self-contained planning problems. It uses a sampling distribution over basic, medium, and hard constraints to control difficulty.
Responder: Attempts to solve the generated problem.
Critic: Verifies the solution against an instance-level checklist.
Adaptive Difficulty Control: If the Responder fully solves an instance ( $u=1$ ), the pipeline shifts the constraint composition toward higher difficulty (increasing weights for medium and hard constraints). If the instance remains unsolved ( $u=0$ ), it is retained at the current difficulty level.
Verification: Each instance is paired with a verification checklist that converts prompt-level constraints into executable checks. The framework favors determinate or well-specified optimal solutions to provide clear reward signals, avoiding loose answer spaces that allow partial feasibility without global consistency.

Key Contributions

Synthetic Data Generation Framework: PlanningBench provides a mechanism to generate scalable, diverse, and verifiable planning data grounded in real scenarios, moving beyond fixed benchmark collections to controllable generation.
Training-Oriented Verification: The framework demonstrates that verified PlanningBench data supports planning-oriented reinforcement learning (specifically GRPO). The authors identify reward determinacy (preference for well-specified optima) as a critical factor for stable and transferable training.
Comprehensive Evaluation Suite: The paper systematically evaluates open-source and closed-source frontier LLMs, revealing that even the strongest models struggle with complete solutions under coupled constraints.

Experimental Results

Evaluation Performance

The authors evaluated 18 representative LLMs (both open and closed-source) on a 467-instance subset of PlanningBench.

Performance Gap: Even the top-performing model, GPT-5.4-xhigh, achieved only 63.17% All-pass (satisfying all checklist items), indicating the benchmark remains challenging and unsaturated.
Local vs. Global Consistency: A significant gap exists between Avg-pass (fraction of checklist items satisfied) and All-pass. For instance, GPT-5.4-medium achieved 90.03% Avg-pass but only 58.09% All-pass, suggesting models often satisfy local constraints but fail to integrate them into a globally consistent plan.
Error Analysis: The primary failure mode across models is Wrong Calculation / Assignment (60.9%–83.5% of errors), followed by Constraint Omitted and State Tracking failures. Formatting errors were negligible.

Training and Transfer

The authors trained a Qwen-A3B-30B model using GRPO on 300 verified PlanningBench instances.

Transfer to Planning Benchmarks: The trained model showed significant improvements on unseen planning benchmarks:
- ChinaTravel: All-pass increased from 50.92% to 58.36%.
- TravelPlanner: All-pass increased from 28.85% to 46.86%.
- The gains were more pronounced than those achieved by training on human-authored data, highlighting the value of structured, verification-oriented synthesis.
Transfer to General Tasks: Training on PlanningBench also improved performance on broader instruction-following and reasoning benchmarks (Multi-Challenge, Inverse IFEval, Collie), with an average score increase of 7.06 points.
Role of Determinate Optima: Models trained on data emphasizing determinate optima (Syn-PlanningBench) showed superior transfer and more stable training dynamics (faster convergence, smoother reward curves) compared to those trained on data with loose optima (Syn-NotDetOptimal).

Significance and Claims

The paper claims that PlanningBench addresses the critical need for scalable, diverse, and verifiable planning data. Its significance lies in three areas:

Diagnostic Power: It provides a fine-grained view of LLM planning capabilities, distinguishing between partial compliance and the ability to maintain global consistency under coupled constraints.
Training Utility: It proves that automatically verifiable planning data can serve as effective training signals for reinforcement learning, improving not just planning but also general instruction-following and reasoning.
Design Principle: The work highlights that reward determinacy is essential for stable planning-oriented training; instances with well-specified optimal solutions provide clearer directional signals than those with many locally acceptable answers.

The authors conclude that controllable data construction, automatic verifiability, and reward determinacy are key to diagnosing and improving the generalizable planning abilities of LLMs.