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

Overview

Graham Neubig presents planning as a task-specific, revisable representation of future actions that can improve long-horizon agents through decomposition, parallel execution, human oversight, and environment feedback. Across examples including GPU procurement, Cursor plan mode, Vending-Bench, and multi-agent computer use, he compares natural-language, code, and graph plans and shows why replanning can improve success—while adding complexity, cost, and less predictable behavior.

Key takeaways

Represent independent investigations, such as searching four GPU vendors, as parallel subtasks; delay dependent checks such as compatibility until the vendor information is available.
Choose plan structure to match the task: natural language is easy for people to inspect, code supports control flow and retries, and dependency graphs make ordering and parallelism explicit.
Use workflows when the task structure is known and predictability matters; allow replanning when the environment can invalidate assumptions or reveal new work.
Ground proposed actions in current capabilities and observations: SayCan combines language-model likelihood with an affordance score, while ALFRED-style feedback lets a robot revise an unexecutable plan.
Long-horizon reliability depends on both per-step accuracy and recovery from past errors; Vending-Bench’s 222-day tasks illustrate how mistakes compound and context can carry them forward.
For multi-agent systems, a strong manager can improve task decomposition while cheaper worker agents execute subtasks; allowing the manager to revise a dependency graph can substantially increase success.

Chapters

0:00 GPU Procurement Shows Why Agent Plans Must Be Revisable

A GPU research task requires comparing vendors, checking compatibility with an existing cluster, and potentially placing a purchase order.
Investigating four vendors can be parallelized, but compatibility checks depend on the gathered vendor information.
When the only compatible GPUs have a 20-week lead time, the agent may need to search more vendors or ask a person before buying.
Replanning means changing a structured task representation in response to observations from the environment.

7:00 Cursor, Claude Code, and Codex Use Plans for Human Oversight

Coding-agent plan modes first gather context through nondestructive actions such as reading files, then propose steps for review.
People can edit a plan or provide feedback before an agent begins implementation; Cursor, Claude Code, and Codex offer versions of this workflow.
Plans can make complex work more understandable, support progress tracking, prevent wasted actions, and enable parallel work by subagents.
A plan is a task-specific proposal of future actions and dependencies, unlike a reusable skill; the agent may need to deviate as conditions change.

14:15 Chain-of-Thought Prompting Established Plans as a Reasoning Scratchpad

Kojima et al. found that prompting models to “think step by step” improved performance on reasoning tasks.
Chain of thought provides extra tokens for intermediate computation and a scratchpad for retaining partial results.
Early chain-of-thought systems generated reasoning and answers in one pass; agent planning can also use plans as conditioning context for later actions.
Reasoning research, including STaR and DeepSeek work, explored training models to produce useful reasoning traces rather than relying only on prompting.

18:00 Least-to-Most Prompting Decomposes Questions into Easier Subtasks

Least-to-Most Prompting splits a complex math problem into subquestions, then answers them in sequence using earlier answers as context.
The decomposition can reduce the context needed for each step; researching one GPU vendor does not require reasoning about every other vendor.
Decompose prompting assigns subtask types, allowing different prompts or specialized models to handle different question-answering needs.
Structured orchestration can pass earlier answers into later subtasks, while general code offers a more flexible way to control that process.

24:00 Classical STRIPS Planning Contrasts with LLM Agent Planning

Classical planning represents the world as predicates, actions, preconditions, and effects; STRIPS and PDDL are established representations.
A classical planner searches for a valid action sequence from an initial state to a goal, using methods such as BFS, DFS, or A*.
LLM agents usually lack explicit action preconditions and effects, so they must test actions in an environment and observe whether they work.
For LLM agents, planning is often less about searching a fully specified state space and more about checking whether a plausible plan is feasible.

30:00 Code Gives Agent Plans Structure, Control Flow, and Retry Logic

Plans can be represented as formal action sequences, natural-language steps, or code that calls domain-specific APIs.
A robotics program might detect blocks and bowls, then call manipulation primitives to stack blocks on a target.
Code can express loops, retries, and postcondition checks, but depends on reliable APIs and can be more rigid than natural language.
API calls can invoke specialized neural models, combining programmatic control with learned perception or other flexible capabilities.

33:30 Anthropic Workflows Trade Adaptability for Predictability

Anthropic’s “Building Effective Agents” recommends starting with workflows: fixed programmatic sequences of language-model calls.
A GPU workflow could inspect a predetermined vendor list, check compatibility, select the cheapest option, and purchase it.
Fixed workflows are predictable and may be cheaper or faster, but can fail when the vendor list or task requirements change.
More adaptive agents can choose new vendors or alter their approach, though that flexibility increases uncertainty and may be safer only when the model handles the domain well.

38:00 Web Agents Combine Strong Planners with Specialized Executors

Computer-use systems separated high-level planning from visual execution when strong language models struggled to click precise page elements.
UGround trained a smaller 7-billion-parameter model on synthetic data to ground natural-language instructions in web-page elements.
Plan-and-Act creates planner training data by filtering successful trajectories and having a teacher model segment and label their actions.
Modularity lets teams improve a planner or executor independently, but passing context between modules can lose information and fixed roles can limit adaptation.

45:00 SayCan Scores Plans by Whether Actions Are Actually Executable

A language model may propose a plausible action such as picking up an apple even when no apple is visible to the robot.
SayCan combines language-model action probabilities with an affordance model that estimates whether each subtask is executable in the current context.
The combined score multiplies the language model’s probability with the affordance model’s probability.
In a robotics setting, locating an unseen apple may be more feasible than immediately picking it up or placing it elsewhere.

47:30 Environment Feedback Enables Replanning—and Can Beat Overthinking

In the ALFRED simulated-home environment, a robot that cannot find a potato can use feedback that it sees a fridge to replan: open the fridge, then continue.
A comparison of reasoning and interaction found that spending tokens on more environment interactions often outperformed spending them on longer reasoning before each action.
A coding-agent study linked overthinking behaviors—including excessive planning, unhelpful state-changing actions, and premature task termination—to worse SWE-bench performance.
Replanning is most useful when new observations matter, but agents still need to balance deliberation with taking informative, safe actions.

54:00 Vending-Bench Exposes Long-Horizon Error Accumulation

Vending-Bench asks an agent to operate a vending-machine business for as many as 222 days, potentially using 25 million tokens.
Even high per-step accuracy compounds poorly over long trajectories: a 90% chance of success at each step makes an entirely correct sequence unlikely.
Errors in an agent’s history can make later errors more likely because models condition on past context; reinforcement learning can improve recovery.
Analysis of Qwen 3 models found that the 32-billion-parameter version could be especially susceptible to degradation when past-context errors were introduced.

1:00:00 Recursive Agent Optimization Trains Models to Plan in Python

Recursive Agent Optimization trains a model to write executable code that decomposes tasks and launches subagents.
For a three-day Kyoto trip, a plan can assign subtasks such as finding cherry blossoms and locating a quiet temple.
Python async/await supports parallel or sequential subagent work, and subagents can recursively delegate to further agents.
Training rewards both task success and useful decomposition; results show generalization from medium-depth training tasks to harder tasks.

1:03:30 Structured Web Plans Resist Injected Reviews and Cursor Shows Editable Plans

A structured shopping plan can search noise-cancelling headphones under $200, compare products, and add the best qualifying option to a cart.
Website reviews can contain prompt injections such as “ignore the price”; adversarial image changes can also manipulate what a model perceives.
Explicit selection logic can make decisions depend on measurable criteria such as price and average rating rather than injected text.
Cursor plan mode gathers codebase context, asks clarifying questions, creates a Markdown plan and to-do list, and lets a person approve or steer the work before building.

1:08:00 Multi-Agent Computer Use Uses Dependency Graphs and Replanning

The Odyssey benchmark uses opt-in real browsing histories to create long-horizon tasks, including collecting information across websites into a spreadsheet.
Multi-agent computer use represents task decomposition as a directed acyclic graph, with dependencies determining which subtasks can run and when.
A manager LLM dispatches independent subtasks to parallel agents, inspects their results, and can retry work or add graph nodes when information is missing.
For a brunch decision in San Francisco, agents can separately investigate weather and locations before combining findings into a structured result.

1:12:00 Manager Quality and Replanning Improve Long-Task Success

Keeping a relatively inexpensive worker model fixed while improving the manager can raise performance without a large increase in per-task cost.
On a challenging long-horizon benchmark, requiring the initial graph to remain unchanged produced about 25% success; allowing more replanning steps raised success further.
Planning adds complexity, so assess whether tasks have separable subtasks, whether specialist models help, and whether a human or another model should steer execution.
The central design choice is how much to commit to a plan versus allowing the agent to adapt as it learns from the environment.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Graham Neubig.