Planning and task decomposition: Visual walkthrough

Related building blocks: 5.3.02-Chain-of-thought-prompting (reasoning inside one model call), 6.2.01-Tool-augmented-LMs (why real agents can't do it all in one pass), 6.2.03-Multi-agent-systems (who runs the parallel pieces), 8.1.03-Reasoning-under-uncertainty (what happens when steps can fail).

Step 1 — What "search" even means for an agent

WHAT. Imagine an agent standing at a starting point. It can take one of several actions (search the web, run code, call an API). After each action it lands in a new situation and again faces a choice of actions. We call each choice-point a node, and each action an edge leading to the next node.

WHY. Before we can count how hard a task is, we must picture the shape of all the ways it could unfold. That shape is a tree: one root (where we start), branching out.

PICTURE. Below, the black dot at the top is the start. From it, $n$ arrows fan out — $n$ is simply the number of actions available at each step. Every arrow lands on a new dot, and each of those fans out again.

Figure — Planning and task decomposition

Step 2 — How deep, and how many leaves

WHAT. A task rarely finishes in one action. It takes several actions in a row. The number of actions in a row before we reach the answer is the depth, written $d$ .

WHY. Difficulty isn't just "how many choices" — it's "how many choices, repeated how many times". Each extra level multiplies the branches again. That multiplication is the whole story.

PICTURE. Count the dots at the bottom row. Level 1 has $n$ dots. Level 2 has $n \times n$ dots (each of the $n$ split into $n$ ). By level $d$ we have $n$ multiplied by itself $d$ times:

total leaf paths n^{d} = choices per step n \times n \times \dots \times n (a total of steps deep d times)

Step 3 — Why $n^{d}$ is a catastrophe (feel the number)

WHAT. Let's put real numbers in. Say $n = 10$ (ten tools/queries to pick from) and $d = 6$ (six steps deep).

WHY. Symbols hide how violent exponential growth is. One concrete plug-in makes it visceral: this is why an agent that tries to plan everything in one giant search simply cannot finish.

PICTURE. Each bar is one more level of depth. The height is the running total of paths. Watch it rocket from 10 to a million in six short steps.

n^{d} = 1 0^{6} = 1, 000, 000 paths

$10$ — after step 1
$100$ — after step 2
$\dots$
$1, 000, 000$ — after step 6

A million grounded tool calls to answer one question is impossible. This is the pain decomposition cures.

Step 4 — The trick: chop the goal into independent pieces

WHAT. Suppose the big goal $G$ secretly splits into $k$ subgoals $G_{1}, G_{2}, \dots, G_{k}$ that don't depend on each other. Each subgoal only needs a fraction of the total depth: $d / k$ steps instead of $d$ .

WHY. This is the key insight. Total work of depth $d$ shared out equally among $k$ helpers means each helper only goes $d / k$ deep. And crucially — because the subgoals are independent — we do not multiply their costs together; we add them.

PICTURE. One tall tree of depth $d$ (left, red, monstrous) becomes $k$ short trees each of depth $d / k$ (right, violet, tiny). The tall tree's leaf count is $n^{d}$ . Each short tree has only $n^{d / k}$ leaves.

Step 5 — Add the little trees: the decomposed cost

WHAT. We total the work of the $k$ short trees.

WHY. Independent ⇒ we run each search separately and sum their costs — not multiply. That switch from multiply to add is where the exponential collapses.

PICTURE. $k$ identical short trees side by side. Each costs $n^{d / k}$ ; there are $k$ of them, so the total is $k$ copies added:

how many pieces k \times cost of ONE short tree n^{d / k} = k \cdot n^{d / k}

Now the same numbers as Step 3, with $k = 3$ :

k \cdot n^{d / k} = 3 \cdot 1 0^{6/3} = 3 \cdot 1 0^{2} = 300 paths

Step 6 — How big is the win? The speedup, term by term

WHAT. Divide the naive cost by the decomposed cost.

WHY. A ratio tells us "how many times faster." Watching the algebra lets us see the exponential survive in the answer — the win keeps growing with depth.

Speedup = \frac{n ^{d} naive}{decomposed k \cdot n ^{d / k}} = \frac{1}{k} \cdot divide powers \Rightarrow subtract exponents n^{d - d / k} = \frac{1}{k} \cdot n^{d (1 - \frac{1}{k})}

$\frac{1}{k}$ — a small tax: more pieces means the $\frac{1}{k}$ shrinks the win a little.
$n^{d (1 - 1/ k)}$ — the prize: still exponential in depth $d$ . This term is why the payoff is enormous.

PICTURE. Speedup plotted against depth $d$ for our numbers: a curve that shoots upward. At $d = 6$ it reads $1, 000, 000/300 \approx 3333 \times$ .

\frac{n ^{d}}{k \cdot n ^{d / k}} = \frac{1 , 000 , 000}{300} \approx 3333 \Rightarrow about 3333 \times faster

Step 7 — The edge cases (don't get fooled)

WHAT. Check the boundaries where the formula behaves strangely.

WHY. The contract: the reader must never meet a case we skipped. Three matter.

Case A — $k = 1$ (no split at all). $k \cdot n^{d / k} = 1 \cdot n^{d /1} = n^{d}$ Splitting into one piece is the original problem. Speedup $= \frac{1}{1} n^{0} = 1$ . No win, no loss — sanity check passed.

Case B — $k = d$ (split as finely as possible). Each piece has depth $d / k = 1$ : a single action. Cost $= d \cdot n^{1} = d \cdot n$ — linear, not exponential! Best case. But watch the parent's over-decomposition warning: each tiny piece still pays real-world latency (an LM call, a tool round-trip), so infinitely fine splitting has its own overhead cost the formula ignores.

Case C — subgoals NOT independent. If every piece needs the previous piece's result, you must chain them: the depths add back up to $d$ and you multiply branches again — you're back to $O (n^{d})$ . Independence is the load-bearing assumption.

PICTURE. Three mini-panels: $k = 1$ (one tall tree, no change), $k = d$ (a flat row of single steps, linear), and "dependent" (short trees stitched into a chain, tall again).

Recall Quick self-test

With $n = 10$ , $d = 6$ , if the three subgoals were dependent instead of independent, roughly how many paths? ::: Back to $1 0^{6} = 1, 000, 000$ — dependence destroys the saving. With $n = 10$ , $d = 6$ , $k = 6$ (finest split), how many paths? ::: $6 \cdot 1 0^{1} = 60$ — linear, the best case.

The one-picture summary

One monstrous tree ( $n^{d}$ leaves) versus $k$ pocket-sized trees ( $k \cdot n^{d / k}$ leaves total), with the speedup arrow between them — the entire derivation on a single canvas.

Recall Feynman retelling — say it in plain words

Picture every way an agent could act as a branching tree. At each step it has, say, ten choices, and it has to make six choices in a row. That's ten, times ten, times ten — six times — a full million routes. Nobody can walk a million routes.

Now here's the escape. If the big job is really three separate little jobs that don't need each other, you don't walk one six-deep tree — you walk three two-deep trees. Two-deep with ten choices is only a hundred routes, and three of those is three hundred. Because the little jobs are independent you add (three hundred), you never multiply (which would give you the million back).

A million versus three hundred — thousands of times less work — and it came purely from noticing the goal was secretly several small goals. The one catch: they must be genuinely independent. The moment one job needs another's answer, you have to stack them, the tree grows tall again, and the magic evaporates. That single word — independent — is the whole trick.