Abstract
Planning remains a significant challenge for Large Language Model (LLM) agents, particularly in long-horizon tasks with numerous strict constraints. Traditional planning paradigms typically decompose tasks temporally (e.g., day-by-day), which often leads to cascading errors and reasoning overload. This paper introduces DPPM (Decompose, Plan in Parallel, and Merge), a novel framework that shifts the focus from temporal to aspect-based decomposition. By breaking tasks into functional subtasks—such as transportation, accommodation, and dining—and planning them in parallel, DPPM mitigates error propagation and enhances the model's ability to satisfy complex constraints. Evaluated on the TravelPlanner benchmark, DPPM achieves a nearly 60% success rate, a dramatic improvement over traditional methods that frequently fail to reach even 1%.
Introduction: The Fragility of Temporal Planning
While LLMs have demonstrated remarkable capabilities in text generation and coding, their performance in complex planning scenarios—like organizing a multi-day trip with specific budgets, dietary needs, and schedules—remains limited. Existing approaches generally follow two patterns:
- Sequential Planning: The agent plans chronologically (Day 1, then Day 2). This is highly susceptible to "cascading errors," where a single suboptimal choice early on invalidates the entire plan.
- Interleaved Planning: The agent alternates between decomposition and planning. However, attempting to resolve all constraints for a specific time block simultaneously often exceeds the model's reasoning capacity.
The authors identify that these temporal approaches are inherently fragile because they do not isolate constraints effectively.
The DPPM Paradigm
DPPM introduces a fundamental shift by decomposing tasks by aspect rather than time. This allows specialized agents to focus on specific categories of constraints independently before a final integration phase.
1. Constraint-aware Task Decomposition
Instead of splitting a trip into days, the system identifies functional subtasks: Transportation, Accommodation, Attractions, and Meals. Each subtask is assigned a manageable subset of the total constraints, reducing the cognitive load on the LLM.
2. Local Plan Generation
Specialized LLM agents work in parallel to generate candidate sub-plans for their respective aspects. To prevent resource exhaustion (e.g., spending the entire budget on a hotel), agents are provided with "Global Constraint Instructions" that act as a budget buffer, ensuring resources remain for other subtasks.
3. Incremental Merge
A dedicated merging agent integrates these sub-plans step-by-step. The process follows a "skeleton-to-detail" approach: it starts with rigid constraints (Transportation and Attractions), then adds "flesh" (Accommodation), and finally "details" (Meals). This incremental strategy uses a Cartesian product approach to test and find the most compatible combinations of sub-plans.
4. Verification and Refinement
Both local and merging stages incorporate a "Critic" module. This module checks for constraint violations and provides feedback to the agents, allowing for iterative refinement until a valid plan is achieved.
Experimental Evaluation
The researchers evaluated DPPM on two primary benchmarks:
- TravelPlanner: A rigorous environment featuring 1,225 scenarios with 13 different constraint types (e.g., budget, flight numbers, geographic proximity).
- ChinaTravel-M: A modified dataset providing diverse geographic and cultural constraints, adapted to the structured evaluation format of TravelPlanner.
Key Results
The performance gains observed with DPPM are substantial. Using the Qwen2.5-32B-Instruct model:
- Success Rate: DPPM achieved a 58.9% final pass rate on TravelPlanner. In contrast, Direct planning and Chain-of-Thought (CoT) methods achieved only 2.8% and 0.6%, respectively.
- State-of-the-Art Comparison: DPPM outperformed LLM-Modulo, a sophisticated iterative framework, by over 22 percentage points.
- Model Scaling: When integrated with the more powerful DeepSeek-R1 model, DPPM's success rate soared to 87.2%.
Ablation studies highlighted the importance of the Verification and Refinement module; its removal caused the pass rate to drop from 58.9% to 20.0%, underscoring the necessity of iterative feedback in complex planning.
Conclusion and Future Work
DPPM demonstrates that aspect-based parallel planning is a more robust and scalable approach for LLM-based agents than traditional temporal methods. By isolating constraints and merging plans incrementally, the system avoids the pitfalls of error propagation.
While highly effective in travel planning, the authors note that the current decomposition logic is domain-specific. Future research will focus on developing more generalized decomposition templates to apply this paradigm to other complex fields, such as project management and hardware design, and improving the initial decomposition step to ensure all global constraints are captured from the outset.
Summary updated