Exercises — Planning and task decomposition

(a)–(iii): hierarchical planning is top-down recursion (goal → subgoals → primitives). (b)–(ii): forward chaining pushes from the present state forward. (c)–(i): backward chaining pulls from the goal backward to the needed preconditions. Memory hook: Hierarchical splits, Forward pushes, Backward pulls.

This is backward chaining. The final thing we want (the director) sits at the end; but we cannot search for it directly because the year is unknown. So we reason backward from the goal: "to name the director I need the film; to name the film I need the year." We resolve the deepest missing precondition (year) first, then walk back up. See 5.3.02-Chain-of-thought-prompting for the reasoning trace that makes this order explicit.

Naive search explores every path of length $d$, and at each of the $d$ steps there are $n$ choices, so the count is $n^d$: $n^d=10^6=1,000,000\text{ paths.}$

Each subgoal is its own little search of depth $d/k=2$, costing $n^{d/k}=10^2=100$ paths. We do $k=3$ of them, and because they are independent we add (not multiply) their costs: $k\cdot n^{d/k}=3\cdot 10^2=300\text{ paths.}$ Speedup: $\frac{n^d}{k{n}^{d/k}}=\frac{1,000,000}{300}\approx \mathrm{3333.3.}$ The million-path problem became a 300-path problem — a factor of ~3300 saved. See the figure: the tall exponential bar collapses to a sliver.

For $k=2$: $d/k=3$, so $k{n}^{d/k}=2\cdot 10^3=2000$ paths. For $k=3$: $300$ paths (from Ex. 2.2). So $k=3$ wins here. The reason: the exponent $d/k$ shrinks fast as $k$ grows, and the exponential shrinkage beats the linear $k$ growth in front. But "bigger $k$ is always better" is false in the real world — see the L2 trap: each split adds a real LM-call / tool-I/O overhead the formula ignores.

Dependencies: $S_3$ needs $S_1$; $S_4$ needs $S_2$; $S_5$ needs both $S_3$ and $S_4$. $S_1$ and $S_2$ depend on nothing. A topological sort (an ordering where every arrow points forward) that also runs independent tasks together: $\{S_1\parallel S_2\}\to \{S_3\parallel S_4\}\to S_5.$ The $\parallel$ symbol means "run at the same time." Three waves instead of five sequential steps. See the DAG figure — colored bars mark the three waves.

With unlimited workers, wall-clock time = length of the critical path = the longest chain of dependent tasks. That chain is $S_1\to S_3\to S_5$ (or $S_2\to S_4\to S_5$), length 3. Sequential run touches all 5 tasks one after another: 5 time-units. So parallel = 3, sequential = 5. You cannot beat 3 no matter how many workers, because $S_5$ can only start after its inputs finish.

Thought: I need Tokyo's metro population — specify metro, not city proper.
Action: search("Greater Tokyo Area population")
Observation: ~37 million
Thought: Now I need the comparable NY figure — metro area again, same boundary type.
Action: search("New York metropolitan area population")
Observation: ~19.5 million
Thought: Subtract to get the gap: 37 - 19.5 = 17.5 million.
Answer: Greater Tokyo (~37M) is larger by ~17.5M — about 90% larger than NY metro (~19.5M).

Each Thought names the current subgoal so the following Action is grounded — it fetches exactly the missing fact instead of random tool spam. Note the unit discipline: comparing metro to metro (never city-proper Tokyo ~14M to metro NY) keeps the comparison meaningful. Percentage: $(37-19.5)/19.5\approx 0.897\approx 90\%$.

Task: PrepareCoffee
  Method 1 (requires state.has_grinder = True):
      [BoilWater, GrindBeans, Brew]
  Method 2 (requires state.has_grinder = False):
      [BoilWater, UseInstantCoffee]
Selector: if state.has_grinder: use Method 1 else: use Method 2

With has_grinder = False, the selector picks Method 2, and the primitive actions executed are: $[\text{BoilWater},\text{UseInstantCoffee}].$ Checking the state before committing guarantees the plan is feasible given current resources — otherwise the agent would try to grind beans it cannot grind.

Here $n^{d/k}=5^{8/k}$.

• $T(1)=1\cdot 5^8+40\cdot 1=390625+40=390665.$
• $T(2)=2\cdot 5^4+80=2\cdot 625+80=1330.$
• $T(4)=4\cdot 5^2+160=4\cdot 25+160=260.$
• $T(8)=8\cdot 5^1+320=40+320=360.$ Optimal is $k=4$ (cost 260). Beyond $k=4$ the exponential search term is already tiny, so the linear overhead $ck$ takes over and total cost rises again at $k=8$. This is the mathematical face of the L2 trap: there is a sweet spot, not a "more is always better." See the U-shaped curve.

1. Decompose the goal into the DAG $\{S_1,S_2\}\to \{S_3,S_4\}\to S_5$ (task decomposition — parent topic).
2. Schedule by topological sort into 3 waves (dependency analysis, Ex. 3.1).
3. Ground each step with tools: fetch = API call, summarize = LM call — tool-augmented reasoning (6.2.01-Tool-augmented-LMs), interleaved ReAct-style so each Thought sets the subgoal.
4. Verify each output (did the fetch return a paper?) — LM-Modulo generate-then-check.
5. Replan on failure: if $S_1$ throws "not found," regenerate that branch (e.g. switch API to Scholar) without touching $S_2$ — failure isolation.
6. Optionally remember partial results so a retry does not re-fetch what already succeeded (6.2.05-Memory-in-agents); split truly independent fetches across cooperating agents (6.2.03-Multi-agent-systems).

Naive search for $n=10,d=6$ ::: $10^6=1,000,000$ Decomposed with $k=3,d/k=2$ ::: $3\cdot 10^2=300$ Critical-path length of the summarize-and-compare DAG ::: 3 Optimal $k$ in Ex. 5.1 (with overhead $c=40$) ::: $k=4$, cost 260 Direction of planning when you unroll a goal's preconditions ::: backward chaining