Planning and task decomposition: Question bank

Some traps assume you know a few neighbours: what a tool call is (6.2.01-Tool-augmented-LMs), what plain step-by-step reasoning is (5.3.02-Chain-of-thought-prompting), and how uncertainty forces replanning (8.1.03-Reasoning-under-uncertainty). Definitions from those pages are used but re-explained inline where needed.

True or false — justify

The speedup formula

O (n^{d}) \to O (k \cdot n^{d / k})

holds for any decomposition of a goal into

k

subgoals.

False. The formula assumes the

k

subgoals are independent — no subgoal needs another's output. If they chain (A feeds B feeds C), you still traverse the full depth

d

and gain nothing; the exponent never shrinks.

Chain-of-thought prompting and task decomposition are the same thing.

False. Chain-of-thought reasons in one forward pass using the model's own text — no external world touched. Decomposition spreads work across grounded steps that each may call a tool, retry, or run in parallel. CoT is a subroutine you can use inside one decomposed step.

A directed acyclic graph is required for a plan; a plan with a cycle is simply a slower plan.

False. A cycle means subtask A depends on B and B on A — there is no valid order to start either, so topological sort fails and the plan is unexecutable, not just slow. "Acyclic" is a feasibility requirement, not a speed preference.

More decomposition steps always give the agent more control and therefore better results.

False. Each step adds latency (an LM call plus tool I/O). Over-decomposing "

2 + 2

" into parse/identify/execute/format is slower and more error-prone than one calculate call. Control has a cost; adaptive decomposition splits only when the task is ambiguous or a first attempt fails.

If all subtasks are independent, running them in parallel is always safe.

True — but the premise is the trap. Genuinely independent subtasks can run concurrently. The mistake is assuming independence: if B secretly reads A's output, parallel execution causes a race condition. Prove independence via the dependency graph before parallelizing.

Backward chaining and forward chaining will always produce the same plan for the same goal.

False. They explore different directions. Forward chaining expands from the current state and can wander toward states irrelevant to the goal; backward chaining expands only preconditions the goal actually needs. For goal-sparse problems they find different (often differently-sized) plans.

ReAct's "Thought" lines are optional decoration — deleting them leaves the agent equally capable.

False. The Thought grounds the next action in the current subgoal. Remove it and the agent tends toward random tool spam, because nothing conditions the action choice on what was just observed.

Spot the error

"We decomposed the goal into 3 subgoals, so search cost drops from

1 0^{6}

to exactly

1 0^{2}

Error: dropped the factor $k$ . With

n = 10, d = 6, k = 3

the decomposed cost is

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

, not

100

. You pay

n^{d / k}

per subgoal and there are

k

of them.

"HTN planning picks the first method that decomposes the task, regardless of the current state."

Error: it must check the state. The 'coffee' example picks Method 1 (grind beans) only if state.has_grinder; otherwise Method 2 (instant). Ignoring state produces a plan that references tools/resources that don't exist — infeasible.

"In LM-Modulo, the verifier's job is to make the plan more creative."

Error: verifier constrains, it doesn't create. Creativity comes from the LM proposing plans. The verifier (solver/physics sim) rejects infeasible ones and returns error feedback. Roles are complementary, not interchangeable.

"For 'Summarize paper X and compare to paper Y', run all five subtasks in parallel to be fast."

Error: violates dependencies. Compare (

S_{5}

) needs both summaries; each summary needs its fetch. Correct schedule:

S_{1} ∥ S_{2}

, then

S_{3} ∥ S_{4}

, then

S_{5}

. Only independent layers parallelize.

"The multi-hop Grammy question: just search 'Grammy Album of the Year' first, then find the 1989 year."

Error: wrong order. You can't query the Grammy of year

Y

until you know

Y

. Backward chaining forces: get 1989's release year (2014) → then the 2015 ceremony → Beck. Reversing the steps has no input for step one.

"Tokyo has ~14M people and New York metro ~19.5M, so New York is bigger."

Error: comparing different boundaries. 14M is Tokyo city proper; 19.5M is New York metro area. Compare like with like: Greater Tokyo metro (~37M) vs NY metro (~19.5M) — Tokyo is larger. Mixing city-vs-metro makes the comparison meaningless.

Why questions

Why does decomposition give failure isolation that a single giant LM call cannot?

Because each subtask has bounded inputs/outputs, a failure is localized — you retry that one branch. A monolithic call that fails must restart from scratch, discarding all partial progress.

Why is a topological sort the natural way to order a plan's subtasks?

A topological sort lists nodes so every dependency comes before the task that needs it — exactly the "don't start B before its input A is ready" rule. It exists precisely when the graph is acyclic, which is why plans must be DAGs.

Why does interleaving Thought and Action (ReAct) help more than dumping all reasoning up front?

Because the Observation from each Action can change the plan. Reasoning up-front commits before seeing real tool results; interleaving lets each new observation re-condition the next thought — essential under uncertainty (8.1.03-Reasoning-under-uncertainty).

Why must an agent support replanning rather than trusting its first plan?

Tools error, pages 404, assumptions turn out wrong. Without replanning the agent gives up at the first failure; with it, the agent regenerates from the failed point or swaps in an alternative method (Wikipedia miss → Google Scholar).

Why does the speedup formula turn an exponential into something linear in $k$ ?

Independence lets each subgoal be solved to shallow depth

d / k

instead of the full

d

. The dominant exponential term collapses to

n^{d / k}

, and you simply add

k

of those — a sum (linear in

k

) replaces a product-of-branches (exponential in

d

Why can decomposition be worse than plain chain-of-thought for a self-contained reasoning task?

If no external tool is needed, decomposition's per-step LM/tool latency is pure overhead. One CoT pass answers it in a single call. Decompose only when steps must be grounded in external actions.

Edge cases

What happens to the speedup formula when

k = 1

(no decomposition)?

It reduces to

\frac{1}{1} \cdot n^{d (1 - 1)} = n^{0} = 1

— speedup of exactly 1, i.e. no gain. Correct: one subgoal is the original problem.

What happens as

k \to d

(decompose into as many subgoals as there is depth)?

Each subgoal has depth

d / k \to 1

, so cost

\approx k \cdot n

— linear in the number of pieces. Great if they're truly independent, but as

k

grows so does coordination/latency overhead, so real gains flatten and can reverse.

What is the plan for a goal that is already primitive (a single tool call)?

The plan is just

[action]

— HTN's base case returns immediately with no decomposition. Forcing a split here is exactly the over-decomposition mistake.

What happens when every HTN method for a task fails its state check?

The recursion has no feasible refinement and returns FAIL up the tree, signalling the parent to try a different method or triggering replanning. FAIL is a real, expected output — not a crash.

What if two subgoals are independent for ranking but share a rate-limited API (only 1 request/sec)?

They are logically independent (no data dependency) yet cannot truly run in parallel due to a resource constraint. The dependency graph says parallel; the scheduler must still serialize them — logical independence ≠ physical parallelizability.

What does the DAG look like for a purely linear pipeline (Search → Fetch → Parse → Plot)?

A single chain with no branches — a degenerate DAG where every node has exactly one predecessor. Topological order is forced and unique; no parallelism is possible because each step consumes the previous step's output.

What if a subgoal's output is uncertain (a search that might return nothing)?

The plan must branch on the observation — success continues the pipeline, empty result triggers a fallback method (e.g. CSV instead of API). This is where planning meets reasoning under uncertainty: the plan is conditional, not fixed.

Recall Quick self-check

Cover the answers. Can you state (a) the one assumption behind the speedup formula, (b) why ReAct needs Thoughts, and (c) what $k = 1$ gives? Answers ::: (a) subgoal independence; (b) to ground the next action in the current observation; (c) speedup $= 1$ , no gain.

See also: 6.2.03-Multi-agent-systems (decomposition across agents, not just steps) and 6.2.05-Memory-in-agents (where intermediate subtask outputs are stored between steps).