CMU AI Agents 2026: 5. Planning, Task Decomposition, and Multi-Agent Coordination

Overview

• Speaker: Daniel Fried
• Channel: Graham Neubig
• Main topic: Planning, Task Decomposition, and Multi-Agent Coordination in LLM Agents
• Purpose: To educate students on how AI agents plan, decompose tasks into sub-goals, and coordinate in multi-agent workflows. The lecture covers planning, task decomposition, and multi-agent coordination for language model agents. It discusses how agents form representations of future work, the role of chain-of-thought, subtask decomposition, and modularity in agentic systems, comparing them with classical AI planning (STRIPS/PDDL) and highlighting trade-offs between planning upfront versus reactive execution.

Topic Map

Introduction to Planning and Task Decomposition

• Explanation: Overview of planning as an agent's representation of future behavior, drawing on chain-of-thought and environmental feedback.
• Key claims:
  • Plans must be revisable based on environmental feedback.
  • Planning bridges the gap between static instructions and dynamic execution.
• Examples:
  • GPU workstation purchasing task involving multiple vendor searches, cluster compatibility checks, and procurement.
• Terminology:
  • Planning
  • Task Decomposition
  • Chain-of-Thought
  • Multi-Agent System
• Why it matters: Planning enables agents to handle long-horizon tasks and manage complex dependencies.

Chain-of-Thought as a Plan

• Explanation: Examining how chain-of-thought generation serves as a primitive form of planning and extra computation for LLMs.
• Key claims:
  • Chain-of-thought provides extra compute and a scratchpad for models.
  • Decomposing complex reasoning into sub-questions improves performance.
• Examples:
  • Kojima et al. (2022) 'Let's think step by step' and Wang et al. (2023) decomposition approaches.
• Terminology:
  • Chain-of-Thought
  • Decomposed Prompting
  • Least-to-Most Prompting
• Why it matters: Understanding the foundation of planning in LLMs helps improve their reasoning capabilities.

Classical Planning vs. LLM Planning

• Explanation: Comparing classical symbolic planning (STRIPS, PDDL) with implicit LLM planning.
• Key claims:
  • Classical planning uses explicit predicates, preconditions, and effects.
  • LLM planning is implicit, leveraging vast pre-training knowledge rather than rigorous search.
• Examples:
  • Blocks world domain with pick-up and put-down actions.
• Terminology:
  • Classical Planning
  • STRIPS
  • PDDL
  • Preconditions
  • Effects
  • Implicit Planning
• Why it matters: Highlights what is hard and what has changed when moving from symbolic AI to neural language agents.

Plan Representations and Workflows

• Explanation: Discussing how plans are represented ranging from text, structured graphs, and code-based policies.
• Key claims:
  • Code-based plans offer programmatic control and API calls.
  • Formal plans are checkable, while language plans are general.
• Examples:
  • Cursor Plan Mode, Claude Code, and CodeX workflows.
• Terminology:
  • Plan Representations
  • Code-Based Plans
  • Workflows
  • Permission Mode
• Why it matters: Choosing the right plan representation affects checkability, flexibility, and execution success.

Modularity, Affordances, and Re-planning

• Explanation: Exploring the decomposition of tasks across multiple specialized agents and the integration of feedback and value functions.
• Key claims:
  • Separating planners from executors allows specialized model training.
  • Re-planning lets models adapt when execution reveals new information.
• Examples:
  • SayCan affordance modeling and Voyager/Odysseys multi-agent architectures.
• Terminology:
  • Modularity
  • Affordances
  • Value Functions
  • Re-planning
  • Execution Horizon
  • Overthinking
• Why it matters: Structuring agents with modularity and re-planning improves success rates on long-horizon tasks.

Multi-Agent Coordination and Failures

• Explanation: Analyzing multi-agent systems, fixed roles, handoffs, and long-horizon failure modes.
• Key claims:
  • Stronger manager agents improve coordination and lift weaker workers.
  • Fixed multi-agent roles can suffer from rigid communication and context drops.
• Examples:
  • Vending-Bench long-horizon task failures and OSWorld ablation studies.
• Terminology:
  • Multi-Agent Coordination
  • Handoffs
  • Long-Horizon Failures
  • Vending-Bench
• Why it matters: Identifies the limitations and pitfalls of multi-agent delegation and execution over extended periods.

Key Points

Planning is a moving target

• Explanation: Agents must balance commitment to a course of action with flexibility to adapt to new environmental information.
• Evidence: Agent tasks in dynamic environments like web browsing require continuous plan revision.
• Practical implication: Agent design must incorporate mechanisms for error detection and re-planning.

Chain-of-Thought acts as a primitive plan

• Explanation: Prompting models to think step-by-step or decompose tasks provides a scratchpad and extra compute before final execution.
• Evidence: Studies like Least-to-Most Prompting show performance gains from subtask decomposition.
• Practical implication: Use structured prompting or decomposition to handle multi-step reasoning tasks.

Classical vs. Neural Planning Trade-offs

• Explanation: Classical planning is explicit and verifiable but brittle; LLM planning is implicit, flexible, but prone to hallucination and execution drift.
• Evidence: Comparison of STRIPS/PDDL state representations against LLM generated natural language text.
• Practical implication: Hybrid approaches combining programmatic structures with neural flexibility are often optimal.

Separating Planner from Executor

• Explanation: Decomposing tasks into planning modules and execution modules allows the use of specialized models and better optimization.
• Evidence: SayCan and related vision-only web agents separate high-level planning from low-level grounding.
• Practical implication: Use strong reasoning models for planning and specialized models or APIs for execution.

Frameworks, Models & Processes

Classical Planning (STRIPS)

• How it works:
• Components:
  • States (predicates)
  • Actions
  • Preconditions
  • Effects
  • Goal state
• When to use: When environment dynamics are fully known and verifiable logical correctness is required.

Code-Based Agentic Workflows

• How it works:
• Components:
  • Developer-defined procedure
  • Fixed list of actions/vendors
  • Model calls
  • Conditional execution
• When to use: When tasks require structured, repeatable, and inspectable execution steps.

Multi-Agent Manager-Worker Framework

• How it works:
• Components:
  • Manager
  • DAG (Dependency Graph)
  • Parallel CUA Sub-agents
  • Follow-up/Replan loop
  • Summary/Deliverables
• When to use: For complex, long-horizon tasks requiring specialized capabilities and parallelization.

Examples & Case Studies

An agent tasked with buying a GPU workstation iterates through multiple vendor sites, checks compatibility on a wiki, and handles supply chain lead time failures.

• Illustrates: The necessity of reactive planning and re-planning when initial vendor options prove suboptimal.
• Lesson: Agents cannot rely solely on upfront linear plans and must adapt to real-world feedback.

Applying Cursor Plan Mode to a software engineering task to generate a markdown checklist before implementation.

• Illustrates: Human-in-the-loop plan review and editing before execution.
• Lesson: Planning mode helps agents gather context and allows human verification, reducing expensive mistakes.

Evaluating multi-agent versus single-agent performance on OSWorld and WebTailBench.

• Illustrates: Stronger manager models significantly improve coordination and boost the success rate of weaker worker models.
• Lesson: Modularity and delegation can lift overall system performance without excessive cost increases.

Actionable Takeaways

• Immediate:
  • Incorporate task decomposition and step-by-step reasoning in agent prompts.
  • Use plan modes or structured checklists to allow human oversight before agent execution.
• Strategic:
  • Balance upfront planning with reactive re-planning based on environmental feedback.
  • Adopt modular multi-agent architectures (manager-worker) to handle complex, long-horizon tasks.
• Questions to investigate:
  • When is planning worth the additional token compute cost?
  • How can we prevent multi-agent handoffs from dropping critical context?

Claims Worth Verifying

• Overthinking in reasoning models correlates with lower issue resolution across benchmark datasets. (empirical research finding)
• Adding a manager agent to weaker worker models lifts task success rates significantly on web navigation benchmarks. (empirical research finding)

Notable Quotes

"A plan is an explicit representation of intended future behavior: the actions or subgoals an agent will attempt, with any ordering or dependencies among them." (at 19:59) "Everybody has a plan until they get punched in the mouth." (at 22:04)

Compressed Summary

• Planning structures future agent behavior and enables task decomposition.
• Chain-of-thought acts as a foundational form of LLM planning.
• Modularity and separation of planner from executor improve web and robotic task success.
• Multi-agent manager-worker frameworks help coordinate long-horizon tasks.
• Keywords: planning, task decomposition, multi-agent, chain-of-thought, modularity
• Core insight: Effective AI agent design requires balancing structured planning and task decomposition with flexible re-planning and environmental feedback.