Decompose, Plan in Parallel, and Merge: A Novel Paradigm for Large Language Models based Planning with Multiple Constraints

Zhengdong Lu, Weikai Lu, Yiling Tao, Yun Dai, Zixuan Chen, Huiping Zhuang, Cen Chen, Hao Peng, Ziqian ZengarXiv 2025 · DOI · arXiv

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:

  1. 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.
  2. 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.

Comparison of planning paradigms: (a) Sequential, (b) Interleaved, and (c) the proposed DPPM.

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.

The detailed DPPM workflow, illustrating task decomposition, parallel local plan generation, and the incremental merging process.

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

Abstract

Despite significant advances in Large Language Models (LLMs), planning tasks still present challenges for LLM-based agents. Existing planning methods face two key limitations: heavy constraints and cascading errors. To address these limitations, we propose a novel parallel planning paradigm, which Decomposes, Plans for subtasks in Parallel, and Merges subplans into a final plan (DPPM). Specifically, DPPM decomposes the complex task based on constraints into subtasks, generates the subplan for each subtask in parallel, and merges them into a global plan. In addition, our approach incorporates a verification and refinement module, enabling error correction and conflict resolution. Experimental results demonstrate that DPPM significantly outperforms existing methods in travel planning tasks.
BibTeX
@misc{lu2025decompose,
  author = {Zhengdong Lu and Weikai Lu and Yiling Tao and Yun Dai and Zixuan Chen and Huiping Zhuang and Cen Chen and Hao Peng and Ziqian Zeng},
  title = {{Decompose, Plan in Parallel, and Merge: A Novel Paradigm for Large Language Models based Planning with Multiple Constraints}},
  year = {2025},
  eprint = {2506.02683},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.02683},
}
Figure