Planning and task decomposition: Worked examples

This page is the "throw everything at it" companion to Planning and task decomposition. Before we work examples, let's list every kind of situation a planning problem can throw at you, so that no scenario surprises you later.

Two ideas from the parent note power everything below. Let us re-earn them in plain words:

The one formula we lean on (parent note, re-stated):

The scenario matrix

Every planning problem this chapter can pose falls into one of these cells. The examples afterward each announce which cell they cover.

#	Case class	What makes it special	Covered by
A	Independent split ( $k$ clean pieces)	subgoals share no data → full speedup	Ex 1
B	Degenerate $k = 1$	"decomposition" that splits nothing	Ex 2
C	Extreme $k = d$	one subgoal per step → over-splitting	Ex 3
D	Dependent chain (backward chaining)	step B needs step A's output	Ex 4
E	Mixed DAG (parallel + serial)	some independent, some dependent	Ex 5
F	Failure + replanning	a branch dies, retry only that branch	Ex 6
G	Real-world word problem	pick strategy + count savings	Ex 7
H	Exam twist: is splitting worth it?	overhead per step beats raw path count	Ex 8

The examples below hit every cell A–H.

Example 1 — Cell A: the clean independent split

Forecast: guess now — will the improvement be a small factor like $3 \times$ , or something dramatic?

Naive cost. With no split, count all routes of depth 6: $n^{d} = 1 0^{6} = 1, 000, 000$ . Why this step? This is the baseline $n^{d}$ — every complete path explored.
Depth per subgoal. Each of the 3 subgoals is only $d / k = 6/3 = 2$ steps deep. Why this step? Independence means we never need one subgoal's later steps while solving another; each is a shorter, self-contained search.
Cost per subgoal. $n^{d / k} = 1 0^{2} = 100$ routes. Why this step? Same $n^{d}$ rule, but now with the smaller depth 2.
Total decomposed cost. Pay that 3 times: $k \cdot n^{d / k} = 3 \cdot 100 = 300$ . Why this step? We solve 3 separate small searches, not one big one.
Speedup. $\frac{1 , 000 , 000}{300} \approx 3333$ .

Figure — Planning and task decomposition

Verify: the general formula $\frac{1}{k} n^{d (1 - 1/ k)} = \frac{1}{3} \cdot 1 0^{6 (1 - 1/3)} = \frac{1}{3} \cdot 1 0^{4} = 3333. \overline{3}$ . Matches $1, 000, 000/300$ . ✓ The savings are dramatic, not linear — the exponent collapsed from 6 to 4.

Example 2 — Cell B: the degenerate $k = 1$

Forecast: should the decomposed cost equal the naive cost exactly, or differ?

Plug $k = 1$ . $k \cdot n^{d / k} = 1 \cdot 1 0^{6/1} = 1 0^{6}$ . Why this step? A single "piece" of full depth 6 is just the original problem.
Speedup. $\frac{1}{k} n^{d (1 - 1/ k)} = \frac{1}{1} \cdot 1 0^{6 \cdot 0} = 1 0^{0} = 1$ . Why this step? $1 - 1/ k = 0$ kills the exponent, so speedup $= 1$ : no gain.

Verify: decomposed cost $1 0^{6}$ equals naive $1 0^{6}$ ; speedup exactly $1$ . ✓ The formula degrades gracefully — $k = 1$ is a no-op, exactly as intuition demands.

Example 3 — Cell C: the extreme $k = d$ (over-splitting the math)

Forecast: does making every step its own subgoal give the biggest possible speedup?

Depth per subgoal. $d / k = 6/6 = 1$ . Each subgoal is a single action. Why this step? Maximal splitting means each piece is one step deep.
Cost. $k \cdot n^{d / k} = 6 \cdot 1 0^{1} = 60$ . Why this step? Six one-step searches of 10 options each.
Speedup vs naive. $1 0^{6} /60 \approx 16, 667$ .

Verify: $\frac{1}{6} \cdot 1 0^{6 (1 - 1/6)} = \frac{1}{6} \cdot 1 0^{5} = 16, 666. \overline{6}$ . Matches $1 0^{6} /60$ . ✓

Example 4 — Cell D: a dependent chain (backward chaining)

Forecast: will a 2-hop dependent chain of $n = 10$ options behave like $k = 2$ independent split (cost $\approx 20$ ) or like a chain (cost $\approx 10 + 10 = 20$ but forced serial)?

Backward chain from the goal. Goal $=$ "Grammy AotY winner in year $Y$ ". This needs $Y$ first. Why this step? Reasoning must respect what depends on what — you cannot search step 2 before step 1 resolves.
Resolve $Y$ . search("1989 Taylor Swift release year") → $Y = 2014$ . Why this step? This is the precondition of the final query.
Resolve winner. search("Grammy Album of the Year 2015") → Morning Phase by Beck (2015 ceremony honours 2014 albums). Why this step? Now that $Y$ is known, the second hop is well-posed.
Cost structure. Two hops, each ~ $n = 10$ candidate queries: $10 + 10 = 20$ tries, but they are serial — the second cannot start early. Why this step? Dependency forbids parallelism; you still avoid $1 0^{2} = 100$ because you never combinatorially pair every hop-1 with every hop-2.

Verify: naive joint search $n^{2} = 100$ ; chained search $= n + n = 20$ ; ratio $100/20 = 5$ . A real speedup, but only $5 \times$ , far below Example 1's $3333 \times$ — because dependency forbids independent multiplication. ✓ Answer to the trivia: Beck.

Example 5 — Cell E: mixed DAG (parallel + serial)

Forecast: with 5 tasks, does the agent need 5 serial rounds, or fewer?

Build the dependency graph (DAG). Edges: $S_{1} \to S_{3}$ , $S_{2} \to S_{4}$ , $S_{3} \to S_{5}$ , $S_{4} \to S_{5}$ . Why this step? A multi-agent/parallel scheduler needs to know which arrows point where before it can run anything.
Topological sort into layers.
- Layer 1: $S_{1} ∥ S_{2}$ (no incoming edges).
- Layer 2: $S_{3} ∥ S_{4}$ (their inputs are ready).
- Layer 3: $S_{5}$ . Why this step? Tasks in the same layer share no dependency, so they run at once.
Critical path. Longest chain is $S_{1} \to S_{3} \to S_{5}$ (length 3). That's the minimum number of serial rounds. Why this step? You can never finish faster than the longest dependency chain.

Verify: 5 tasks, but only $3$ serial rounds. Serial-everything would take $5$ rounds → parallelism saves $5 - 3 = 2$ rounds. ✓ Layer sizes $2 + 2 + 1 = 5$ = total task count (no task lost or duplicated). ✓

Example 6 — Cell F: failure and localized replanning

Forecast: how much work does backtracking save here — a little, or most of it?

Restart-from-scratch cost. Redo everything: $T_{1}, T_{2}$ (already done!) plus $T_{3}, T_{4}, T_{5}$ = $5$ units. Why this step? Naive agents with no memory re-execute succeeded steps. Wasteful.
Replan-from-failure cost. Keep $T_{1}, T_{2}$ outputs (this is where agent memory earns its keep), regenerate only from $T_{3}$ onward with an alternative method: $T_{3}^{'}, T_{4}, T_{5}$ = $3$ units. Why this step? Failure isolation means only the broken branch is redone.
Saved work. $5 - 3 = 2$ units, i.e. the two already-completed steps are not repeated.

Verify: restart $= 5$ , replan $= 3$ , saving $= 2$ ; saving fraction $= 2/5 = 0.4$ = 40% less work. ✓

Example 7 — Cell G: real-world word problem (pick the strategy + count)

Forecast: independent fetches → do we get the multiplicative $8^{?}$ blow-up, or the additive savings?

Identify independence. The 3 fetch sources don't depend on each other → this is Cell A structure with $k = 3$ . Why this step? Correctly labelling independence is what unlocks the additive (not multiplicative) cost.
Naive joint search. Treating all three fetches as one depth- $d$ search with $d = k \cdot 2 = 6$ : $n^{d} = 8^{6} = 262, 144$ . Why this step? This is the "explore every combination of every source's every endpoint" trap.
Decomposed search. $k \cdot n^{d / k} = 3 \cdot 8^{2} = 3 \cdot 64 = 192$ . Why this step? Each independent fetch is its own depth-2 search; solve, then move on.
Then serial tail. Parse and plot are one dependent chain after the fetches — cheap, unaffected by the split.

Verify: speedup $= 8^{6} /192 = 262144/192 = 1365.33...$ ; and formula $\frac{1}{3} 8^{6 (1 - 1/3)} = \frac{1}{3} 8^{4} = \frac{4096}{3} = 1365.33...$ . ✓ Decomposition helps enormously → use it.

Example 8 — Cell H: exam twist ("but is it actually worth it?")

Forecast: the exponent math from Ex 3 loved $k = 6$ — will overhead overturn that?

Cost model. $Total (k) = k \cdot n^{d / k} + c \cdot k$ , with $c = 5000$ . Why this step? Real agents pay per step, so we add $c$ once per subgoal — the piece the pure path-count formula ignored.
$k = 1$ : paths $1 0^{6} = 1, 000, 000$ , overhead $5000 \cdot 1 = 5000$ → total $1, 005, 000$ .
$k = 3$ : paths $3 \cdot 1 0^{2} = 300$ , overhead $5000 \cdot 3 = 15, 000$ → total $15, 300$ .
$k = 6$ : paths $6 \cdot 10 = 60$ , overhead $5000 \cdot 6 = 30, 000$ → total $30, 060$ . Why this step? Beyond $k = 3$ the shrinking path count can't outrun the growing overhead.
Winner. $k = 3$ ( $15, 300$ ) beats both $k = 1$ ( $1, 005, 000$ ) and $k = 6$ ( $30, 060$ ).

Verify: min over ${1, 005, 000, 15, 300, 30, 060}$ is $15, 300$ at $k = 3$ . ✓ This is the quantitative face of the parent's "over-decomposing" mistake: the sweet spot is interior, not $k = d$ .

Recall Quick self-test

Cloze the pattern, then reveal:

Decomposed path cost for $k$ independent subgoals ::: $k \cdot n^{d / k}$ Speedup vs naive ::: $\frac{1}{k} n^{d (1 - 1/ k)}$ Why $k = 1$ gives speedup $1$ ::: the exponent $d (1 - 1/ k)$ becomes $0$ , so $n^{0} = 1$ — no split, no gain What Example 8 adds that the pure formula omits ::: per-subgoal overhead $c \cdot k$ , which makes very large $k$ expensive Why a dependent chain (Ex 4) beats naive by only a small factor ::: dependency forbids independent multiplication, so cost is additive $n + n$ not divided-exponent

See also: 6.2.01-Tool-augmented-LMs · 5.3.02-Chain-of-thought-prompting · back to Planning and task decomposition.