Multi-agent planning is the problem of turning a shared goal into an ordered set of actions that several LLM agents can carry out together. A single agent planning for itself already searches a tree of possible action sequences; add more agents and that tree grows in a way that is easy to underestimate and expensive to ignore. This piece stays on the planning question specifically — how the plan is structured, decomposed, and repaired — rather than on how agents argue, bid, or divide credit. We walk it from first principles: what a joint plan is, the planner-executor split that makes it tractable, how a goal becomes subgoals, why the search cost is combinatorial, and how monitoring turns a brittle open-loop script into something that survives a messy world — keeping one eye on the small-model, CPU-bound case, where every planning token is a cost you can feel.
What planning means for a team
For one agent, a plan is a sequence of actions that transforms an initial state into a goal state: s_0 → a_1 → s_1 → ... → s_T where s_T satisfies the goal. Multi-agent planning keeps that shape but the actions are now distributed across n agents, and at each step the world advances under a joint action — one choice per agent that acts.
Two things change immediately. First, actions can interact: two agents editing the same file, or one consuming a result the other has not produced yet, create dependencies and conflicts a solo plan never has. Second, no agent typically sees the whole state; each reasons from a partial view. So a team plan is not ‘a longer to-do list.’ It is a structure that respects ordering constraints, assigns who does what, and stays consistent even though the agents executing it hold different, incomplete pictures. Getting that structure right is the game.
Joint plans versus individual plans
There are two ends of a spectrum. A joint plan is one artifact that prescribes the whole team’s behavior, naming each agent’s action at every step. It is maximally coordinated because every interaction is resolved up front, but it is also the most expensive to build and the most fragile — one agent slipping off-script can invalidate the rest.
At the other end, each agent holds its own individual plan and the team relies on those local plans being compatible. This is cheap and robust to local variation, but it risks conflicts and duplicated or dropped work when the plans quietly disagree about a shared resource or ordering. Real systems live in between: a lightweight joint skeleton — milestones, hand-off points, shared dependencies — pins down the interactions, while each agent expands its own share into detailed local steps. The skeleton is what keeps the individual plans from drifting apart.
The planner-executor split
The dominant architecture for LLM teams separates planning from execution. A planner (a stronger model, or the same model in a ‘think’ role) produces a structured plan; executors (weaker, cheaper models or tool-driven workers) each carry out an assigned piece. The planner reasons over the whole goal; the executor reasons over one bounded task.
This split matters because planning and doing have different cost profiles. Planning is a small amount of high-quality reasoning done once; execution is a large amount of lower-stakes work done many times. Putting expensive capacity on the leverage point — the plan — and cheap capacity on the volume — the steps — makes a team economical. It also creates a clean interface: the planner emits subgoals with success criteria, and an executor need only understand its own subgoal, not the mission. That narrowing lets a small model act as a competent executor even when it could never have authored the plan.
Decomposing a goal into subgoals
The heart of planning is decomposition: turning one large, abstract goal into smaller subgoals that are individually achievable and that, composed in order, imply the goal. Formally you build a partial order of subgoals g_1, ..., g_k with dependency edges g_i → g_j meaning ‘g_i must hold before g_j can start.’ That partial order is the plan’s real structure; a flat list is just one linearization of it.
Good decomposition balances two properties. Subgoals should be independent enough that agents pursue them in parallel without stepping on each other, and complete enough that satisfying all of them achieves the goal with no silent gap. These pull against each other: cut too coarsely and subgoals conflict; too finely and you drown in coordination overhead. The dependency edges are where parallelism lives — subgoals with no path between them run at the same time, and makespan is set by the longest dependency chain, not total work.
A shared plan representation
For several agents to act on one plan, they need a shared representation of it — a single source of truth that says what the subgoals are, who owns each, what depends on what, and which are done, in-progress, or failed. Without it, each agent reconstructs the plan from its own conversation history and the reconstructions diverge.
In LLM systems this is usually explicit and inspectable: a task list, a dependency graph, or a structured document (JSON or a scratchpad) agents read before acting and update after. Two pressures shape it. It must be compact, because every agent that reads it pays for those tokens on every turn. And it must be current, because a stale plan is worse than none: agents confidently act on subgoals already completed or invalidated. The best representations carry just enough state to coordinate — status flags and dependencies — and push verbose detail down into each executor’s local memory where the rest of the team need not see it.
Why the search cost is combinatorial
Here is the number that governs everything. If one agent chooses among b actions per step, a team of n agents faces a joint action space up to b^n per step, and a plan of horizon T searches a tree on the order of (b^n)^T = b^(nT).
1 agent, horizon T: b^T
n agents, joint: b^(n*T)
b = 5, T = 8:
1 agent: 5^8 ≈ 3.9 x 10^5
3 agents: 5^24 ≈ 6.0 x 10^16The exponent carries the agent count, so naive joint planning is hopeless past a handful of agents. Every practical method is a way of not searching that full space: decompose into near-independent subgoals so agents plan locally over b^T each, and let the dependency structure — not exhaustive search — handle the few genuine interactions. The combinatorics are exactly why the decomposed, hierarchical approach is a computational necessity, not a stylistic choice.
Monitoring and replanning on failure
A plan built up front assumes a world that will cooperate, and it never fully does: a tool errors, a subgoal turns out infeasible, a result contradicts an assumption. An open-loop plan — decide once, then execute blindly — breaks the moment reality diverges. Robust systems are closed-loop: they monitor outcomes against the plan’s expected state and act on the gap.
The cheap response is local repair — retry the failed step or patch a single subgoal — leaving the rest of the plan intact at almost no cost. The expensive response is replanning: discard the affected portion and have the planner build a new subplan from the current state. The art is choosing the smallest scope that fixes the problem, because replanning the whole mission on every hiccup burns budget and risks thrashing. Because the plan records which subgoals are done, a scoped replan preserves completed work and re-searches only the broken subtree.
A worked example
Say the goal is ‘produce a researched, fact-checked report.’ The planner decomposes it into subgoals with dependencies: g_1 gather sources, g_2 draft sections (needs g_1), g_3 fact-check (needs g_2), g_4 assemble (needs g_2, g_3). Sources split into three topics, so g_1 and g_2 fan out to three executors running in parallel.
The chain g_1 → g_2 → g_3 → g_4 has length 4, so even with nine units of work across three agents the makespan is four stages, not nine. Now a fact-check fails: one drafted claim is unsupported. Monitoring catches the mismatch and repairs just that section’s g_2/g_3 pair, while the other topics’ completed subgoals and the assembly plan stay untouched — decomposition, dependency-graph parallelism, and scoped replanning all at once.
What it means for small CPU-hosted models
On a small CPU-hosted model, planning is not free reasoning — it is tokens, and tokens are latency. Every subgoal, status update, and replan re-reads context a slow machine processes one token at a time. So prefer a shallow, wide decomposition — more parallel subgoals along short dependency chains — to keep makespan low even when each step is slow, and keep the shared plan ruthlessly compact, since it is re-read by every agent on every turn and context length is the dominant CPU cost.
Lean on the planner-executor split: one careful planning pass sets the structure, and executors stay on tight subgoals a small model can handle without re-deriving the mission. And bias toward local repair over full replanning — a retry is a few tokens, a fresh whole-plan search is a small model’s worst case. The team’s speed is set less by how fast any agent thinks than by how little redundant thinking the plan forces on all of them.
b^(n*T), so searching it directly is hopeless — every workable method instead decomposes the goal into a partial order of subgoals agents can pursue mostly independently, coordinated through a compact, current shared plan and a planner-executor split that spends expensive reasoning on the plan and cheap capacity on the steps. Parallelism comes from the dependency graph, and makespan is set by the longest chain, not total work. Because no up-front plan survives a messy world intact, robustness comes from closed-loop monitoring and scoped repair. For small CPU-hosted models the same advice sharpens: shallow-and-wide decomposition, a lean shared plan, and local repair over full re-search keep a slow team from drowning in coordination tokens.