Task Decomposition¶

Agentic AI · L-Decomp

A chain of dependent steps decays exponentially, and no prompt fixes an exponent. What fixes it is a boundary with a check. Then the plan itself — a DAG the harness owns, scheduled, parallelised and repaired — and the three published architectures that implement it: Plan-and-Execute, ReWOO, LLMCompiler.

Prerequisite Directed graphs, DAGs, topological sort, longest/critical path.

Learning Objectives¶

By the end you can:

1. Derive $p^{\,n}$ for a chain of dependent steps, and explain why plain chain-of-thought does not escape it.
2. Compute what a verifier at a boundary is worth — $p' = p + (1-p)\,d\,p$ — and say when a critic is worth adding at all ($d > \phi$).
3. Decide what the check reads: the step's artifact, never its narration; and design the structured contract that crosses a step boundary.
4. Separate the outer decomposition strategy from the inner executor, and pick the most deterministic executor a sub-task admits.
5. Read the three published planning architectures — Plan-and-Execute, ReWOO, LLMCompiler — as one skeleton with five places changed: plan time, loop domain, input binding, executor choice, replanning; and choose between them.
6. Decide the plan's provenance — generated, fixed in code, or hybrid — and name the three structural defects a generated plan can carry.
7. Model a plan as a DAG: topological order (Kahn), the ready set, the critical path and slack; mutate it at runtime (insert · prune · re-edge); and say what parallelism costs in tokens and rate limits.
8. Handle failure: verdict vs. hard failure, unrolling a retry as a new node, and repair by rebuilding the context rather than appending to it.

Overview¶

Task decomposition divides a task into steps, places a check on each boundary between two steps, and represents the plan as an object that the harness — the runtime around the model — schedules and repairs. Part I derives what a boundary with a check is worth, Part II states how three published architectures construct the plan, Part III how a runtime orders, parallelises and repairs the plan as a dependency graph, and Part IV where decomposition is applied and how an architecture is selected:

Part I — Boundaries and Checks¶

A chain of dependent steps succeeds only if every step succeeds, so its success probability falls exponentially with the number of steps: task decomposition places a boundary between two steps, and the boundary raises the success probability only if a check of the step's result is placed on it.

Reliability of a Chain of Steps¶

Suppose the task needs $n$ dependent steps. Let $X_i$ be the indicator random variable of step $i$, with values $x_i \in \{0,1\}$: $X_i{=}1$ means "step $i$ came out correct". Write $X_{1:i}{=}1$ for "steps $1$ through $i$ are all correct". The task succeeds exactly when $X_{1:n}{=}1$, and the chain rule factorises that conjunction exactly:

$$ P(X_{1:n}{=}1) \;=\; \prod_{i=1}^{n} P(X_i{=}1 \mid X_{1:i-1}{=}1). $$

Assumption. Solved in its own focused context, each step succeeds with the same probability given a correct prefix: $P(X_i{=}1 \mid X_{1:i-1}{=}1) = p$. Then

$$ P(X_{1:n}{=}1) = p^{\,n}. $$

With $p = 0.9$ and $n = 10$ that is $0.9^{10} \approx 0.35$ — worse than a coin flip.

Plain chain-of-thought does not escape this. CoT (Wei et al., 2022) writes the $n$ steps out, but it writes them open-loop, inside one generation: nothing between step $i$ and step $i+1$ inspects the result, so the same $n$ draws still multiply. The comparison this week turns on is therefore not CoT versus no CoT but a chain with no boundary versus a chain with boundaries you can check at.

The exponent is the problem, and no prompt fixes an exponent.

(That the decay is real and not merely arithmetic is measured: Dziri et al. (2023) model a task as a computation graph and grow it — accuracy on multi-digit multiplication, a logic puzzle and a dynamic-programming problem falls to near zero as the graph deepens, even for models fine-tuned on the fully written-out steps. Read $n$ as that graph's depth.)

Three arguments, and only the first one needs a verifier.

1. Reliability compounds. Splitting the task does raise the per-step rate a little — a focused sub-task is easier than a stage buried in one long prompt (next slide) — but that alone leaves the exponent untouched. What decomposition really buys is a boundary after every step, where a check can catch and repair an error before it propagates.
2. Context stays small. Each sub-task carries only its inputs, not the whole problem (the context budget). Smaller prompts are cheaper, more accurate, and carry less that can quietly steer the answer.
3. Structure enables parallelism and reuse. Independent sub-tasks run in parallel; named sub-results are reused by later steps.

Arguments 2 and 3 follow from the structure alone. Argument 1 is an empty promise until something is actually checked at the boundary — which is the rest of Part I.

Monolithic Prompt vs. Prompt Chain¶

Why should $p$ be higher once the task is split? A monolithic prompt — all $n$ steps inside a single generation — offers no per-step draw to observe: one sample, one end-to-end verdict. So define the rate it implies as the geometric mean of the same conditionals,

$$ p_{\text{eff}} \;:=\; \Big( \prod_{i=1}^{n} P(X_i{=}1 \mid X_{1:i-1}{=}1) \Big)^{1/n}, \qquad\text{so that}\qquad P(X_{1:n}{=}1) = p_{\text{eff}}^{\,n} $$

holds by construction. The claim decomposition rests on is empirical: $p > p_{\text{eff}}$ — a sub-task solved in its own focused context beats the same stage buried in one long prompt. And because $x \mapsto x^{\,n}$ is steep, a small drop is amplified $n$-fold: at $n = 10$, $p_{\text{eff}} = 0.8$ instead of $0.9$ takes the task from $\approx 0.35$ to $\approx 0.11$.

Measured directly on C → assembly, where a compiler and a unit-test suite decide success: 90.2 % monolithic → 95.1 % with a check after every step → 99.5 % once the input is also split into independently solvable parts (GPT-4.1; Zhang et al., 2025) — the boundary and the split priced apart, and both worth more to a weaker model than to a stronger one.

What the monolithic prompt does wrong (Gulli, 2025): instruction neglect (parts silently ignored) · contextual drift · error propagation · context-window pressure · hallucination under load.

Example. "Analyse this market-research report, summarise it, extract trend data points, and draft an email" — the model may summarise well yet botch the extraction or the email. As a chain: summarise → identify the top-3 trends with their supporting data (from output 1) → draft the email (from output 2). Each step is one focused prompt, with a checkpoint between calls.

Step Reliability with Verification¶

Put a check after each sub-task — a test, a schema validation, a critic — and allow one retry. Write $d$ for the probability that the check detects a faulty step. A step then ends correct with

$$ p' \;=\; \underbrace{p}_{\text{right first time}} \;+\; \underbrace{(1-p)\,d\,p}_{\text{caught, and the retry comes out right}} . $$

With a perfect check and $k$ attempts the step fails only if every attempt fails, so $p' = 1 - (1-p)^{k}$. Undetected errors — the fraction $1-d$ — escape immediately, which is a ceiling no number of retries can lift.

A loop can be worth nothing — or less than nothing. The formula above assumed the check only ever fires on a faulty step. Let $\phi$ be the false-positive rate: the probability that the check flags a step that was actually correct. One retry then gives

$$p' \;=\; \underbrace{p\big[(1-\phi) + \phi\,p\big]}_{\text{was correct; wrongly flagged, then redone}} \;+\; \underbrace{(1-p)\,d\,p}_{\text{was faulty; caught, then redone}} \;=\; p \;+\; p\,(1-p)\,(d - \phi).$$

The design rule. A check is worth having exactly when $d > \phi$ — when it catches more real faults than it manufactures. Setting $\phi = 0$ recovers $p' = p + (1-p)dp$.

An ungrounded critic — one that reads only the model's own draft — has $d \approx 0$ while $\phi$ stays positive, so it keeps "fixing" correct work. Strip the unit tests out of Reflexion and the agent starts "performing harmful edits" because it cannot tell it is already done, scoring below the no-loop baseline (Shinn et al., 2023).

And $d$ is measurable — this is what it measures out at. Chen, Ziru, et al. (2024) hold the generator fixed and vary only the critic, scoring it by pairwise discrimination accuracy: given one correct and one incorrect candidate, how often does the correct one score higher? Sweeping a deliberately corrupted oracle across that range shows a threshold: a critic-driven loop — iterative correction or tree search — only beats plain re-ranking of $k$ samples once accuracy reaches about 90 %; at 80 % and below, search is worse than re-ranking. And on the two text-to-SQL benchmarks no critic they test clears that bar — GPT-4-Turbo scores 76.5 and 76.2, CodeLlama-13B 58.2 and 49.4 (only GPT-4 on GSM8K, 93.8, gets there). So the $d > \phi$ rule is not a formality: with an ungrounded LLM critic it is routinely violated, and end-to-end no critic-driven method they test significantly beats plain re-ranking.

The fix is the one this section already argues for, now with a price on it. Two deterministic observations — refuse to score a program that does not run, and put its execution result in the critic's prompt — raise discrimination accuracy by up to +30.2 points, enough that a 13B open-weight critic (83.6 / 79.6) beats an unaided GPT-4 (76.5 / 76.2). Grounding the critic buys more than ten times the model.

The Verifier's Target: Artifact vs. Narration¶

Every step produces two things, and only one of them is checkable:

• the narration — the reasoning trace, the model thinking out loud;
• the artifact — the concrete deliverable: a patch, a JSON object, an SQL query, a number.

The rule. A verifier earns a detection rate $d$ only when it tests the artifact. Grading the narration measures whether the model sounds correct, which is a different quantity.

Why, measured (Turpin et al., 2023). Plant a misleading hint in the prompt:

• the hint moves the model's answer by up to 36 percentage points;
• across 426 explanations supporting the biased answer, exactly one mentions the hint;
• 15 % of those unfaithful explanations contain no visible reasoning error at all.

The trace is not an audit trail: what moved the answer may never appear in it. Use the chain for task performance and debugging; check the artifact.

Robust Checks, by Domain¶

Every robust check has the same shape: it is deterministic, it reads something the model did not write, and its verdict is a value the harness can branch on.

The Reflection Loop¶

A boundary is a place for a check; reflection is the local loop you put there. It runs on a single step, before that step's output is passed downstream:

1. Execute — perform the sub-task, producing an artifact.
2. Evaluate — check that artifact against the step's criteria.
3. Refine — use the critique to fix the artifact, without re-running the rest of the task.
4. Iterate — until the check passes, or a retry cap $\kappa$ is reached.

The step's own reliability $p$ comes from its executor; the loop's $d$ comes from what the critic is allowed to read.

The Producer–Critic Pattern¶

Split the loop into two roles rather than one self-critiquing model (also generator–critic, producer–reviewer; Gulli, 2025):

The separation avoids the self-review blind spot: an agent grading its own work brings to the review the same assumptions that produced the error.

And the split that pays is across models, not personas. Chen et al. (2025) optimise which model runs which module of a generator · critic · refiner system. On LiveCodeBench, Claude 3.5 Sonnet is the best single model for the whole system (89 %) — yet as its own critic it "fails to realize its own generation is incorrect", while GPT-4o as the critic "correctly identifies the initial generation is incorrect." Keeping Claude as generator and refiner and swapping only the critic reaches 95 % (CommonGenHard: 75 % → 84 %).

Grounding of the Critique¶

Three primary sources build the same loop and differ in one place — where the critique's evidence comes from. Read together, they measure what that choice is worth:

The rule this yields. "Exclusive reliance on self-correction without external feedback may yield modest improvements or even deteriorate performance" (Gou et al., 2024). The named mechanism is the generation–discrimination–critique gap: a model that can produce a correct answer cannot reliably tell whether the answer it produced is correct. So the design question is never "should I add a reflection loop?" but "what does the critic get to read?"

And where a repair loop loses. When a loop returns a worse answer than a single pass, the loss is one of exactly two kinds (Chen et al., 2024), and they have different remedies:

The asymmetry is the point: the majority of losses sit in the column that spending more cannot fix. Raising $d$ is not one lever among several; it is the lever.

And the sharpest single failure they record has no name in the reflection literature: on Spider, 15 of iterative correction's 29 discrimination errors had already generated the correct program in an earlier round and then overwrote it, because the critic preferred a later wrong draft and never triggered the early exit. A loop with $d < \phi$ does not merely fail to improve — it destroys work it had already done. The cheap defence is to keep the best-so-far outside the loop and return that, which costs nothing and bounds the damage at "no improvement".

Structured Output as the Inter-Step Contract¶

A chain is only as reliable as the data passed between steps. If one step's output is free-form, the next step can misread it — and that failure is invisible to both.

Fix: each step emits a schema-validated object, and the boundary validates it.

{
  "trends": [
    {"trend_name": "AI-Powered Personalization",
     "supporting_data": "73% of consumers prefer brands that personalise their experience."},
    {"trend_name": "Sustainable & Ethical Brands",
     "supporting_data": "ESG-claim products grew 28% over 5 years vs. 20% without."}
  ]
}

• Machine-readable → precise parsing, and insertion into the next prompt without re-reading prose.
• Same idea as native tool calls: constrain the model to a schema so the boundary is reliable.
• The schema validator is the cheapest verifier there is — deterministic, instant, and it reads the artifact. It is a large part of $d$ for free.

(A concrete chain: summarise → extract trends as JSON → draft an email. Three focused prompts, two validated boundaries, instead of one prompt that must do all three — Gulli, 2025.)

Part II — The Plan as an Object¶

A plan is the sequence of steps intended to reach the goal: a ReAct loop holds the plan only implicitly in its transcript, whereas Plan-and-Execute, ReWOO and LLMCompiler store it as a data object outside any single generation, so that the harness can inspect, validate and schedule the plan and retry a single step.

Two Levels: Strategy and Executor¶

Agent planning runs at two separate scopes, and most confusion about "which pattern should I use?" comes from mixing them.

The two levels are filled from different menus, and the asymmetry is the point: what sits outside is a way of splitting a goal; what sits inside is a way of acting.

Choosing an executor: take the most deterministic one the sub-task admits.

The exponent in $p^{\,n}$ lives at the inner level, so the cheapest way to raise a chain's reliability is not a better prompt but a step that cannot be got wrong — a tool call where the answer is computable, a schema-validated parse where the question is one of format, and a model generation only where judgment is genuinely required.

One measurement. Wei et al. (2022) categorise 50 failed chains on a maths benchmark by what minimal change would fix them: 8 % were correct except for a calculator error. That is not a reasoning failure at all — it is a step handed to the wrong executor, and swapping in an external calculator lifted that model's accuracy from 14.3 to 17.3. Part of what looks like a low per-step $p$ is a routing decision.

And the executor is a subroutine call, not a delegation. The harness calls the inner program; the call has a frame. The sub-task's intermediate observations are that frame's locals — they live for the duration of the call and are discarded on return, so what crosses the boundary is the sub-task's artifact, never its transcript. That is what keeps the outer level's context proportional to the number of steps rather than to the work done inside them.

What the composition licenses, and the one arrangement it does not.

The measured nesting is plan or search outside, act inside:

The single ✗ is not a prohibition but a consequence: a ReAct loop nested in a ReAct loop that shares the parent's transcript has no frame and therefore no return — the inner turns are outer turns, nothing is discarded, and the goal is diluted along a trajectory that lengthens with every level (Huang et al., 2024). Give the inner loop its own context, prompt and tools and the frame exists — but then it is a subagent, a different design with a different bill (→ L-MAS).

ADaPT (Prasad et al., 2024) is the clean instance of the composition: a controller — "a pre-determined and recursive algorithm", ordinary code — runs a ReAct executor on the whole task first and calls a planner to split it into 3–5 sub-steps only when that executor fails, recursing to depth $d_{\max}$. Decomposition is a failure handler, not an opening move, and "with $d_{\max} = 1$, ADaPT solely relies on this executor" — at depth 1 the system is plain ReAct. Measured on GPT-3.5: ALFWorld 43.3 → 71.6, TextCraft 19.0 → 52.0, WebShop 17.0 → 44.0.

Notation for the Pseudocode¶

Every pseudocode box this week is written against the same names, so that the differences between them are the only thing that changes. The shared names are collected here; the three boxes that add names of their own — ReWOO, LLMCompiler and the execution scheduler — list them immediately before their own box.

⚠ And $\Theta$ carries two. Here it is asymptotic cost — $\Theta(V+E)$ for Kahn's algorithm. In ReWOO's token equations it is that paper's notation for a token count. The two are unrelated; each use says which is meant.

Decompose-then-Solve — the Skeleton¶

Everything in this part is a variation on one control structure, so it is worth having that structure in front of you before the variations. The agent loop of → L-ReAct and this one differ in a single line (1).

$$ \begin{array}{l} \textbf{Decompose-then-Solve}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; the tool set} \\ \textbf{Output: } \text{the final answer} \\ \hline 1: \quad [\,\tau_1, \dots, \tau_n\,] \gets \text{LLM}_{\text{plan}}(\textit{goal}) \qquad \text{// ONE call, before any action is taken} \\ 2: \quad \textit{results} \gets [\;] \qquad \text{// one entry per finished step — results, not transcripts} \\ 3: \quad \textbf{for } i = 1 \dots n \textbf{ do} \qquad \text{// the loop is bounded by the PLAN, not by a turn budget} \\ 4: \quad \qquad \textit{prompt}_i \gets \text{Render}\big(\textit{goal},\ [\tau_1 \dots \tau_n],\ \tau_i,\ \textit{results}\big) \\ 5: \quad \qquad r_i \gets \text{Solve}_i(\textit{prompt}_i) \qquad \text{// the executor CHOSEN FOR THIS SUB-TASK — a tool call, a CoT generation, a ReAct loop} \\ 6: \quad \qquad \textit{results}.\text{append}\big((\tau_i,\, r_i)\big) \\ 7: \quad \textbf{return } \text{LLM}_{\text{answer}}(\textit{goal},\ \textit{results}) \qquad \text{// one synthesis call} \\ \hline \end{array} $$

Line 1 is the whole difference. The ReAct loop has no counterpart to it: there the plan exists only as the accumulated history. Here it is an object, produced before anything is executed — which is what makes it inspectable, schedulable, approvable and retryable step by step.

Three consequences fall out of that one line:

• Termination moves out of the model. The loop of counts turns and exits when the model emits no tool call; this one counts the steps of the plan, so the length of the run is known to the harness in advance.
• The context is rebuilt, not accumulated. Each step is handed the goal, the plan, its sub-task and the results so far — not the transcripts that produced them. That is "context stays small" made concrete, and it is why a single step can be retried on its own.
• Nothing returns to line 1. A failed step cannot change the plan — that is what static means.

And five places carry every variation that follows. The three published architectures change some of these, and nothing else. Each gets a name here, because every architecture below numbers its own box differently — "line 4" means something else in each of them:

Planning Architectures¶

In this section, we analyze three primary agent planning strategies:

• Plan-and-Execute inspired from Plan-and-Solve Prompting (Wang et al., 2023) — a family name, not one algorithm: its variants differ in when they replan, and the version analysed here is the one the LangGraph reference graph implements (LangGraph, 2025)
• ReWOO (Xu et al., 2023)
• LLMCompiler (Kim et al., 2024)

Explicit Plan Object:

• ReAct: No explicit plan. Operates strictly in a Think -> Act -> Observe loop, deciding one step at a time.
• Plan-and-Execute, ReWOO, and LLMCompiler: Yes. All three generate a multi-step plan object ahead of execution.

Plan Structure:

• Plan-and-Execute: Linear list. A simple sequential list of steps.
• ReWOO: Linear chain with variable bindings. A sequential plan that uses placeholders (e.g., #E1, #E2) to pass intermediate outputs between steps.
• LLMCompiler: Directed Acyclic Graph (DAG). A structured graph where tasks explicitly define their incoming dependencies, enabling non-dependent tasks to run concurrently.

Replanning Strategy:

• ReAct: No ahead-of-time planning, so no formal replanning phase.
• Systems shipped as Plan-and-Execute range from no replanning at all to a replan after every task — evaluating progress and generating a new plan after every single step.
• ReWOO: None. Executes the entire generated plan from start to finish without dynamic replanning.
• LLMCompiler: On-demand / conditional. Executes the DAG until an error occurs, missing data is hit, or dynamic decision-making requires altering the remaining graph.

Scheduler for LLMCompiler only:

• What it is: A programmatic runtime component that manages DAG task execution.
• What it does:
  • Tracks task dependencies in real time.
  • Resolves variable placeholders as soon as prerequisite tasks complete.
  • Dispatches independent tasks immediately to run in parallel.

Plan-and-Execute — One Step per Replanning Round¶

Nodes: planner → agent → replan → {agent, END}. The name says plan and execute; the graph is plan → execute one → replan the remainder (LangGraph, 2025).

$$ \begin{array}{l} \textbf{Plan-and-Execute}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; the tool set} \\ \textbf{Output: } \text{the final answer} \\ \hline 1: \quad [\,\tau_1, \dots, \tau_n\,] \gets \text{LLM}_{\text{plan}}(\textit{goal}) \\ 2: \quad \textit{results} \gets [\;] \\ 3: \quad \textbf{loop} \qquad \text{// NOT } \textbf{for } i = 1 \dots n \text{ — the plan is replaced, never walked} \\ 4: \quad \qquad \tau \gets \tau_1 \qquad \text{// only the FIRST step of the current plan is executed} \\ 5: \quad \qquad r \gets \text{ReAct-Executor}\big(\tau,\ [\tau_1 \dots \tau_n]\big) \qquad \text{// a subroutine call with its own frame} \\ 6: \quad \qquad \textit{results}.\text{append}\big((\tau,\, r)\big) \\ 7: \quad \qquad a \gets \text{LLM}_{\text{replan}}\big(\textit{goal},\ [\tau_1 \dots \tau_n],\ \textit{results}\big) \qquad \text{// a Response, or a new Plan} \\ 8: \quad \qquad \textbf{if } a \text{ is a Response } \textbf{then return } a \\ 9: \quad \qquad [\,\tau_1, \dots, \tau_n\,] \gets a.\textit{steps} \qquad \text{// "only what still NEEDS to be done"} \\ \hline \end{array} $$

Against the skeleton. Plan time is re-entered every round (from this box's line 7); loop domain stops being a for over the plan and becomes an unbounded loop that always takes $\tau_1$; replanning fires after every executed step. So the plan is replaced wholesale each round at the price of one planner call per step — the most expensive point on the static–dynamic axis, bought for adaptivity. It is decomposition-first in name and interleaved in behaviour, and it pays a second named cost: "each task is still executed in sequence, meaning embarrassingly parallel operations all add to the total execution time."

Executor choice is the one that looks like an omission and is not: one prebuilt ReAct agent runs every step, whatever the step is. That forfeits the "most deterministic executor" saving, and buys a graph with a single executor node in it.

The executor receives neither the goal nor the results so far. The plan is its entire context, so every step must be intelligible on its own, and a step cannot consume what an earlier step returned except through a replanning round.

ReWOO — Planner · Worker · Solver¶

ReWOO (Xu et al., 2023) removes the replanning entirely: the plan is written before any tool runs, and never revised.

Notation for ReWOO¶

ReWOO adds the following to the shared list under Notation for the Pseudocode; none of them appears in any other box.

ReWOO, written out. The three modules are lines 1, 4–6 and 7.

$$ \begin{array}{l} \textbf{ReWOO}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; the tool set} \\ \textbf{Output: } \text{the final answer} \\ \hline 1: \quad P \gets \text{LLM}_{\text{plan}}(\textit{goal}) \qquad \text{// ONE call — the PLANNER; plan text, never re-entered} \\ 2: \quad \big[\,(\tau_s, e_s, \textit{tool}_s, \textit{args}_s)\,\big]_{s=1}^{n} \gets \text{Parse}(P) \qquad \text{// step text, evidence NAME, tool, argument string} \\ 3: \quad \textit{evidence} \gets \{\;\} \qquad \text{// the evidence store: name} \mapsto \text{result} \\ 4: \quad \textbf{for } s = 1 \dots n \textbf{ do} \qquad \text{// strictly the planner's order — nothing is scheduled} \\ 5: \quad \qquad \textit{args} \gets \text{Substitute}(\textit{args}_s,\ \textit{evidence}) \qquad \text{// a name in the argument string} \mapsto \text{its value — THE EDGE} \\ 6: \quad \qquad \textit{evidence}[e_s] \gets \textit{tool}_s(\textit{args}) \qquad \text{// the WORKER runs one tool} \\ 7: \quad \textbf{return } \text{LLM}_{\text{solve}}\big(\textit{goal},\ [\tau_1 \dots \tau_n],\ \textit{evidence}\big) \qquad \text{// the SOLVER} \\ \hline \end{array} $$

Against the skeleton. Plan time and loop domain are unchanged — one call up front, all $n$ steps in order — and there is no replanning at all. The one real change is the input binding: instead of re-rendering a prompt from results, a step's arguments are completed by substituting a named value. That single change is what turns the plan into a graph. (Executor choice moves into the plan too: the planner names $\textit{tool}_s$ per step.)

The edges are variable bindings. A later step depends on an earlier one "by referring to $\#E_s$ from previous steps in the instructions given to Workers" — and that reference is the edge:

Plan: Find Company A's 2024 revenue.
#E1 = Search["Company A 2024 annual revenue"]
Plan: Find Company B's 2024 revenue.
#E2 = Search["Company B 2024 annual revenue"]
Plan: Compute the ratio of the two.
#E3 = Calculator["#E1 / #E2"]

This is worth dwelling on, because it removes a whole class of bug. A format that passes results by name derives its dependency graph from the text itself: step 3 depends on steps 1 and 2 because it reads #E1 and #E2. A format that declares dependencies in a separate depends_on list states the same fact twice — and can contradict itself.

The plan above is already a DAG. ReWOO does not exploit it: the Worker runs the steps in the order the planner listed them, so #E1 and #E2 are executed serially even though nothing connects them. Removing exactly that limitation is what the next architecture is for.

LLMCompiler — a Streamed DAG with Ready-Set Dispatch¶

LLMCompiler (Kim et al., 2024) keeps ReWOO's variable bindings, makes the DAG explicit, and dispatches every task the moment its dependencies resolve. The paper's vocabulary is a compiler's, deliberately.

Three components for parallel fuction calls in LLMCompiler¶

1. Function Calling Planner for formulating execution plans for function calling.
2. Task Fetching Unit for dispatching function calling tasks
3. Executor for executing tasks in parallel.

(from Kim et al., 2024)

1. search("Company A 2024 annual revenue")
2. search("Company B 2024 annual revenue")
3. math("$1 / $2")
4. join()

The task-fetching unit replaces the placeholder $1 and $2 of sub-task 3 with the corresponding values before it was fetched from the executor.

Tasks 1 and 2 have no dependencies, so they run at the same time; task 3 waits for both. The Task Fetching Unit is "inspired by the instruction fetching units in modern computer architectures", and "fetches tasks to the Executor as soon as they are ready for (parallel) execution based on a greedy policy" — which is exactly the ready set of the scheduler in Part III.

Notation for LLMCompiler¶

LLMCompiler adds the following to the shared list under Notation for the Pseudocode; none of them appears in any other box.

$$ \begin{array}{l} \textbf{LLMCompiler}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; the tool set} \\ \textbf{Output: } \text{the final answer} \\ \hline 1: \quad \textit{obs} \gets \{\;\} \qquad \text{// the observation map: task index} \mapsto \text{that task's output} \\ 2: \quad \textit{context} \gets \varnothing \\ 3: \quad \textbf{loop} \\ 4: \quad \qquad G \gets \text{LLM}^{\text{stream}}_{\text{plan}}(\textit{goal},\ \textit{context}) \qquad \text{// STREAMS a DAG: nodes } \tau = (\textit{idx},\ \textit{tool},\ \textit{args},\ \textit{deps}) \text{, EDGES the } \textit{deps} \\ 5: \quad \qquad \textit{obs} \gets \text{Schedule}(G,\ \textit{obs}) \qquad \text{// ready-set dispatch — runs tasks IN PARALLEL} \\ 6: \quad \qquad a \gets \text{LLM}_{\text{join}}(\textit{goal},\ \textit{obs}) \qquad \text{// the JOINER: a Response, or Replan} \\ 7: \quad \qquad \textbf{if } a \text{ is a Response } \textbf{then return } a \\ 8: \quad \qquad \textit{context} \gets a.\textit{context} \qquad \text{// what this attempt learned — RECOMPILATION} \\ \hline \end{array} $$

The Joiner is line 6 of this box, and the parallelism is all inside Schedule — which Execution, Failure & Recovery opens up.

Against the skeleton. Plan time becomes a stream. Loop domain is replaced by Schedule, which walks the ready set instead of an index and therefore runs independent tasks at once. Input binding is a placeholder substitution, performed inside Schedule. Executor choice sits in the plan, as $\operatorname{tool}(\tau)$. And replanning fires only when the Joiner asks for it, not once per step.

Two mechanisms beyond the DAG, and both matter in practice.

• The planner streams. The graph is emitted incrementally, so a task can start "as soon as its dependencies are all resolved" rather than waiting for planning to finish — "analogous to instruction pipelining in modern computer systems". Worth up to 1.3× on its own.
• Dynamic replanning — the paper calls it recompilation. Where the graph cannot be fixed in advance, "the intermediate results are sent back from the Executor to the Function Calling Planner which then generates a new set of tasks with their associated dependencies", and the cycle repeats. The unit of replanning is the whole remaining graph. ⚠ Reported, not measured: every benchmark configuration in the authors' own repository caps the loop at max_replans: 1, so the latency and accuracy figures that follow are single-pass runs with recompilation switched off (Kim et al., 2024, repository a00c9d3).

Measured against a ReAct baseline — and note that both latency and cost improve, because the plan removes LLM invocations rather than adding them:

Cost falls 3.37× / 6.73× / 4.65× on the three benchmarks, "because it involves less frequent LLM invocations."

And executor choice, the fifth. The bare skeleton lets the harness pick one per sub-task. Plan-and-Execute fixes a single ReAct agent for all of them. ReWOO and LLMCompiler move the choice into the plan: the planner names the tool for each step, which is why their boxes write $\textit{tool}_s$ and $\operatorname{tool}(\tau)$ rather than a Solve. It is the deepest of the five differences — it decides whether "which executor?" is a harness policy or something the model gets to hallucinate.

A decision rule.

• The "how" is genuinely known in advance → do not plan at all: write a fixed workflow.
• Steps are independent and latency matters → LLMCompiler-shaped: an explicit DAG, ready-set dispatch, parallel execution.
• Steps are dependent but the environment is known, and token cost matters → ReWOO-shaped: one plan, variable bindings, no replanning.
• The environment is unknown and must be observed → ReAct; add a plan object only if you need it inspectable or approvable, and expect to pay a replan per step.

Plan Provenance — Generated, Fixed, Hybrid¶

Who authors the plan's structure is a decision separate from how it is executed — and it decides where that structure's reliability comes from.

The design question (Gulli, 2025): does the "how" need to be discovered, or is it already known? Known and repeatable → fix the workflow. Must be discovered → a planning agent. Don't grant autonomy you don't need.

The rows differ in what the exponent ranges over. If the graph is code, no step can depend on an edge that does not exist, and $p^{\,n}$ is a statement about the content of the steps alone. If the model emits the graph, its structure is one more thing that can be wrong — and it is wrong before the first step runs.

The size of the effect is measured, and it is not small. On Blocksworld with ≤ 5 blocks — a domain whose actions, preconditions and effects are stated in the prompt — GPT-3 produced a valid plan in 1 % of instances and Instruct-GPT3 in 6.8 %, against 78 % for human participants (Valmeekam et al., 2023). The same picture holds for navigation: GPT-4 finds a shortest path one cluster away in 0 of 30 runs, and never above 10 % at any temperature; in that evaluation the graph structure contributes more to success than the choice of model, and temperature does not contribute at all (Momennejad et al., 2023). The defect is structural, so a sampling knob does not reach it.

So a generated plan is itself an artifact to be checked. Validate it against the tool catalogue and the step preconditions before executing anything — the cheapest verification available, because it runs once, before any step costs money.

Hybrid Graph Architectures¶

Production systems sit at neither end. The common arrangement is a hard-coded execution graph in which selected nodes are agentic: the edges, the branch conditions and the retry budget live in code, and a node facing an unpredictable environment runs a short-horizon ReAct loop with its own context, tools and step cap.

The outer level here is a program, not a model; the model appears only as an executor inside a node. What the hybrid buys is that autonomy is scoped — it exists where the path genuinely has to be discovered, and nowhere else. Mostly workflow, selectively agentic.

Plan approval — human in the loop. A deep research agent writes a plan, then works it with retrieval tools for tens of steps. What is new in it is not the machinery — ReAct over a plan, with reflection and retrieval — but the gate: the plan is shown to the user to review and edit before execution, so the long and expensive part starts from an approved plan. A plan object is what makes such a gate possible at all.

Part III — Scheduling and Recovery¶

A plan whose steps depend on the results of other steps is a directed acyclic graph (DAG): the runtime derives an execution order from the graph, executes in parallel the steps whose dependencies are complete, and repairs the graph when a step fails.

The Plan as a DAG¶

Nodes are sub-tasks $\tau_1,\dots,\tau_n$; a directed edge $\tau_i \to \tau_j$ means "$\tau_i$ must finish before $\tau_j$" — a dependency, and in practice a data flow. A sensible plan has no cycles, so it is a Directed Acyclic Graph.

• Sources (in-degree 0): no prerequisites — can start immediately ($\tau_1$).
• Sinks (out-degree 0): final results ($\tau_5$).
• An adjacency matrix $A \in \{0,1\}^{n \times n}$ with $A_{ij} = 1 \iff \tau_i \to \tau_j$ makes the degrees literal sums: out-degree = row sum, in-degree = column sum, sources = zero columns.

What a real planner stores is the adjacency list — one record per sub-task with its predecessors (blockedBy): $\Theta(V+E)$ space and $\Theta(1)$ work per completed prerequisite. Plan DAGs are sparse, so the matrix is for the maths, not for the implementation (Cormen et al., 2022, §20.1).

🔁 Prior knowledge (your Algorithms course): Grundlagen der Graphen · Graphensuche (BFS/DFS) · Dijkstra.

Static plan vs. dynamic execution graph — a common confusion, and it is worth keeping straight before anything is scheduled.

• The static plan you schedule is a DAG: $\tau_1 \to \tau_2 \to \tau_3$.
• The execution trace contains cycles: $\tau_2 \to \texttt{tests\_failed} \to \tau_2' \to \tau_3$ (try → fail → retry).

They are reconciled by unrolling: each retry becomes a new node ($\tau_2'$ = "attempt 2"), so the expanded graph stays acyclic and schedulable. The cycle lives in the agent's control loop, not in the DAG you topologically sort.

Graph Mutation at Runtime¶

Two invariants keep this safe to do to a graph a scheduler is already walking:

• Acyclicity is preserved. An insertion is always a new node, never a back edge — so a topological order exists at every moment of the run.
• Executed nodes are immutable. Mutation touches only the unexecuted frontier; re-editing a node whose result has already flowed downstream is a prune-and-reinsert, not an edit.

Topological Order & the Ready Set¶

A topological sort orders the sub-tasks so that every edge $\tau_i \to \tau_j$ points forward. That is exactly a legal order to execute the plan.

Existence. A topological order exists iff the graph is a DAG. A cycle has no valid starting point, so no ordering can respect all its edges.

Kahn's algorithm, in one sentence: start with all sources, emit one, remove it, decrement its successors' in-degrees, and any successor that reaches in-degree 0 becomes newly available. Emit all $n$ nodes ⇒ it is a DAG; get stuck with nodes left ⇒ there is a cycle.

Cost. $\Theta(V+E)$ time, $\Theta(V)$ extra space on an adjacency list — one pass for the in-degrees, then every node dequeued once and every edge relaxed once (Kahn, 1962; Cormen et al., 2022, §20.4).

The ready set is what may be executed immediately — every sub-task not yet executed whose inputs are all available. In the residual graph (the plan minus the finished nodes) those are the in-degree-zero nodes, which is why Kahn's algorithm is an execution scheduler's loop. That set, not the sorted list, is what a scheduler actually consumes.

Producing vs. checking. Verifying a given order is one pass over the edges — check $\mathrm{pos}(\tau_i) < \mathrm{pos}(\tau_j)$ for every edge — simpler than the algorithm that produced it, and independent of it. Cheap checks on expensive steps: the same move as a verifier on a decomposition boundary.

$$ \begin{array}{l} \textbf{Kahn-TopoSort}(G) \\ \hline \textbf{Input: } \text{directed graph } G = (V, E) \\ \textbf{Output: } \text{a topological ordering of } V \text{, or } \text{CycleDetectedError} \\ \hline 1: \quad \textbf{for each } v \in V \textbf{ do } inDegree[v] \gets 0 \\ 2: \quad \textbf{for each } (u, v) \in E \textbf{ do } inDegree[v] \gets inDegree[v] + 1 \\ 3: \quad Q \gets \text{empty queue}, \quad \textit{order} \gets \text{empty list} \\ 4: \quad \textbf{for each } v \in V \textbf{ do} \\ 5: \quad \qquad \textbf{if } inDegree[v] = 0 \textbf{ then } Q.\text{enqueue}(v) \\ 6: \quad \textbf{while } Q \text{ is not empty} \textbf{ do} \\ 7: \quad \qquad u \gets Q.\text{dequeue}() \qquad \text{// } Q \text{ IS the ready set} \\ 8: \quad \qquad \textit{order}.\text{append}(u) \\ 9: \quad \qquad \textbf{for each } (u, v) \in E \textbf{ do} \\ 10: \quad \qquad\quad inDegree[v] \gets inDegree[v] - 1 \\ 11: \quad \qquad\quad \textbf{if } inDegree[v] = 0 \textbf{ then } Q.\text{enqueue}(v) \\ 12: \quad \textbf{if } |\textit{order}| = |V| \textbf{ then return } \textit{order} \\ 13: \quad \textbf{else raise } \text{CycleDetectedError} \\ \hline \end{array} $$

Why Kahn and not the DFS reverse-postorder sort (both $\Theta(V+E)$): Kahn yields the frontier incrementally, so the ready set is available during the run; DFS only produces an order after the whole traversal, and grouping independent steps out of it takes a second pass. Kahn's queue also swaps for a priority queue without changing anything else, and it is iterative — no $O(V)$ call stack on a deep plan. DFS keeps one advantage: on a cycle its recursion stack holds the offending path, which Kahn cannot report (Kahn, 1962; Tarjan, 1976).

Parallelism & the Critical Path¶

A topological order gives a sequential schedule — but the DAG also says what can run at the same time. Independent sub-tasks (no path between them) execute in parallel.

The critical path is the longest-duration path through the DAG. With unlimited workers the minimum time to finish — the makespan — is the cumulative duration along it:

$$ \text{makespan} \;=\; \max_{\pi \in \Pi} \sum_{\tau_i \in \pi} d_i $$

where $\Pi$ is the set of all directed paths, $\pi$ a path $(\tau_{i_1}, \dots, \tau_{i_k})$ following the edges, and $d_i$ the duration of task $\tau_i$.

• The critical path is the plan's irreducible latency — no amount of parallelism beats it.
• A task off it has slack: speeding it up saves nothing. Speeding up a task on it saves time step for step.
• It is a property of the weighted graph, never of the shape alone: change one duration and it can move.

🔁 Longest path on a general graph is NP-hard; on a DAG it is $\Theta(V+E)$ by topological sort + dynamic programming. (Critical path, slack and makespan are the Critical Path Method — Kelley & Walker, 1959.)

Worked Example — a Coding Task as a DAG¶

Request: "Fetch the sales dataset, write a function that computes the per-group mean, test it, and report." The planner — here the LLM itself, prompted to emit JSON — answers with structured steps, one object per sub-task, each naming what it depends_on. Those fields are the edges, so the parsed plan is this graph. The second number on each node is its duration.

• Source: read_spec. Sink: report.
• fetch_data and write_tests depend only on read_spec → they can run in parallel.
• run_tests needs both write_code and write_tests — a fan-in.

The planner supplies the graph, not the weights. The model emits id and depends_on — what needs what, which it can know from the task. It does not emit dur: an LLM has no calibrated sense of how long a step takes, and the critical path and every "speeding this up saves nothing" verdict are properties of exactly those weights. Durations come from measurement — the latency of prior runs of the same step type (→ L-Eval).

Reading the schedule off the graph.

• The critical path is read_spec → fetch_data → write_code → run_tests → report, of length $1+3+4+1+1 = \mathbf{10}$ — the plan cannot finish sooner, however many workers you have. The serial sum is 12, so parallelism buys 2.
• write_tests is off it and has 5 steps of slack: it may start late, or take up to $2+5=7$ steps, before the finish time moves at all.

A wrong edge does not crash — it quietly removes freedom. Why does fetch_data precede write_code but not write_tests? An edge is a claim about what a step needs as input, not a guess about what will run first. The code must match the dataset's columns and quirks, so it needs the data in hand; the tests encode the contract from the spec, which is known before any data arrives. Model it the other way and the makespan stays 10 — but write_tests loses its independence and its slack falls from 5 to 2. That is the spurious edge defect, seen from the scheduler's side.

Prioritization among Ready Tasks¶

A topological order says only what is legal to run. When several tasks are ready at once and workers are limited, the scheduler must rank them.

• Criteria: urgency (a deadline), importance, cost, or dependency leverage — a task on the critical path unblocks the most downstream work.
• How much does the ranking matter? Less than the graph does: with $m$ workers, any rule that never idles a free worker finishes within $\big(2 - \tfrac{1}{m}\big)$ times the optimum (Graham, 1969). A priority rule buys the constant; the critical path buys the order of magnitude.
• Priorities are dynamic — a new deadline, a failed step → re-prioritise, just as you replan.

Scheduling vs. prioritization. Topological sort answers "what may run?"; prioritization answers "of the ready ones, which first?" — and the second only matters under resource constraints.

Execution, Failure & Recovery¶

Data flows along the edges: $\tau_j$ receives the outputs of every $\tau_i \to \tau_j$ as its inputs — in a placeholder architecture, exactly to the extent the planner wrote those references into $\tau_j$'s arguments, since the edge and the binding are the same token. The scheduler walks the ready set, running independent nodes in parallel and threading outputs into their dependents.

Two different things are called "failure", and the difference decides who can repair them.

A retry is a new node, not a revisited one. Feeding the error back changes the input, so the second attempt is a different task instance $\tau'$ — the unrolling rule, now as an execution rule rather than a drawing convention. Cap the unrolling with a retry cap $\kappa$ — a limit on how often a run may re-plan around the same failure — or the plan grows forever. The cap belongs to the caller, because the unrolling does.

The scheduler neither plans nor repairs. $G$ is a parameter of the box below, not something it produces: what follows is the runtime a planning architecture hands its plan to — the contents of the $\text{Schedule}$ call the LLMCompiler box leaves closed. Both the replanning and the unrolling therefore stay with the caller, and the scheduler returns what it could not run instead of answering around it.

Notation for the Scheduler¶

The scheduler adds its own names to the shared list under Notation for the Pseudocode; none of them appears in any other box.

$$ \begin{array}{l} \textbf{Schedule}(G = (T, E),\ \textit{out},\ \textit{onfail}) \\ \hline \textbf{Input: } \text{a plan DAG } G \text{ with sub-tasks } T \text{ and dependency edges } E \text{; the store } \textit{out} \text{ so far; a policy } \textit{onfail} \in \{\textit{stop}, \textit{drain}\} \\ \textbf{Output: } \text{the updated } \textit{out} \text{, and the tasks left blocked} \\ \hline 1: \quad \textit{done} \gets \operatorname{dom}(\textit{out}) ;\quad \textit{blocked} \gets \bigcup \{\, \operatorname{desc}(\tau) \mid \tau \in \textit{done},\ \textit{out}[\tau] \text{ is not a verified result} \,\} \\ 2: \quad \textbf{while } \big(\textit{ready} \gets \text{ReadySet}(G,\ \textit{done},\ \textit{blocked})\big) \neq \emptyset \textbf{ do} \\ 3: \quad \qquad \tau \gets \text{Pick}(\textit{ready}) \qquad \text{// prioritization; the whole ready set may be dispatched at once} \\ 4: \quad \qquad r_\tau \gets \text{Solve}_\tau\big(\tau,\ \{\, \textit{out}[u] \mid u \in \operatorname{pred}(\tau) \,\}\big) \qquad \text{// the inputs that flow along the edges} \\ 5: \quad \qquad \textit{out}[\tau] \gets r_\tau ;\quad \textit{done} \gets \textit{done} \cup \{\tau\} \qquad \text{// ATTEMPTED — an artifact, or a failure report} \\ 6: \quad \qquad \textbf{if } r_\tau \text{ is not a verified result } \textbf{then} \qquad \text{// a hard failure OR a negative verdict — the scheduler does not distinguish} \\ 7: \quad \qquad \qquad \textit{blocked} \gets \textit{blocked} \cup \operatorname{desc}(\tau) \qquad \text{// nothing downstream can run on an input that never arrived} \\ 8: \quad \qquad \qquad \textbf{if } \textit{onfail} = \textit{stop} \textbf{ then return } \textit{out},\ \textit{blocked} \\ 9: \quad \textbf{return } \textit{out},\ \textit{blocked} \qquad \text{// the caller reads } \textit{out}[\tau] \text{ to see WHICH it was, and repairs} \\ \hline \end{array} $$

The scheduler detects and reports; it does not repair. Both kinds of failure take the same branch here, because the difference between them is not a difference in what a dispatcher can do about them — it is a difference in what the caller does next, and the caller reads $\textit{out}[\tau]$ to tell them apart. This is the static plan vs. dynamic execution graph distinction made operational: the retry cycle lives in the control loop, not in the DAG being topologically sorted, so the node that inserts a retry is the replanner, not this loop.

Line 1 is what makes the box re-entrant. $\textit{blocked}$ is derived from the store rather than reset, so a cone blocked in an earlier round stays blocked when the scheduler is called again on a repaired graph — and a repair node, being fresh, is in nobody's cone.

Line 8 is a policy, not a default. Under $\textit{stop}$ the scheduler returns the moment a cone is blocked; under $\textit{drain}$ it re-enters the loop and finishes everything still ready, returning once nothing is left to run.

(Line 2 recomputes the ready set as its own loop condition: a completed sub-task may unblock its successors.)

Unrolling a Failed Test Run¶

run_tests comes back red. That is a verdict — the step ran and produced exactly the signal the plan exists to obtain. report is blocked for as long as the failure stands — and the replanner then lifts it, by appending fresh nodes and re-pointing report onto them:

• write_code' is not write_code run again. Its input is larger: the spec, the data, and the failing test report. That is why the retry can succeed where the original failed — and why a blind re-run usually cannot.
• Which node you unroll is a diagnosis. Red tests can mean the code is wrong (write_code'), the test is wrong (write_tests'), or the data is not what the spec assumed (fetch_data' — and then everything downstream is re-derived). Choosing wrongly burns an attempt.
• The cap $\kappa$ is part of the plan, exactly like the step cap in the ReAct loop — and it counts re-planning rounds, not tool calls, because the round is what the diagram's attempt 1 and attempt 2 label. Without it a textual self-correction loop has no convergence guarantee to stop it (Huang et al., 2024, §6).

Context Poisoning in the Retry Loop¶

The cheapest-looking repair is to leave the failed attempt in the context and append "that was wrong, try again". It is also the one that loops, and the mechanism has a name: context poisoning — "when a hallucination or other error makes it into the context, where it is repeatedly referenced" (Breunig, 2025). The wrong result does not stay an attempt; at every later turn it is re-read as established fact.

Two measurements say why this is structural rather than a matter of prompting harder:

• A single distractor already costs accuracy, and the penalty grows with input length, across 18 models on deliberately trivial tasks (Hong et al., 2025). A failed attempt is a distractor carrying the model's own authorship.
• Position matters. Accuracy over the position of the relevant fact is U-shaped; with the answer placed mid-context, GPT-3.5-Turbo falls below its own closed-book accuracy (Liu et al., 2024). A long retry transcript pushes the goal into exactly that trough.

Telling a poisoned context that it made a mistake does not remove the poison — it adds a turn.

Recovery Strategies¶

What works instead is structural — change what the retry is allowed to read.

The first is the containment argument of a sub-agent boundary: a step that runs in its own window returns "a condensed, distilled summary of its work" rather than everything it read (Rajasekaran et al., 2025), so what a poisoned attempt can contaminate is bounded by what it may hand back.

The rule. Repair by rebuilding the context, not by appending to it. A retry that reads the failure but not the failed reasoning is a new node with a better input; a retry that reads the whole transcript is the same node with a longer one.

Flow Patterns & Their Failure Modes¶

Most plans are built from a few reusable shapes — all DAG motifs — and each has a characteristic way of going wrong. Knowing which one you built tells you what to check for.

The first three go wrong inside a step or at its boundary — a per-step verifier and a validated contract catch them. The last two are structural: the step succeeded and the plan was wrong about it, so detection there must compare the observation against the plan, not against the step's own output.

(Fan-in has a primary of its own: Besta et al. (2024) make aggregation — a node of in-degree > 1 merging sub-results — the defining operation of Graph-of-Thoughts,.)

Routing: Adaptive Control Flow¶

A chain is a fixed pipeline. Routing adds conditional logic: classify the input or the state, and dispatch to the right branch — a specialised sub-agent, a tool, or another chain (Gulli, 2025).

Routing applies at the start (classify the task), mid-chain (pick the next step), or to choose a tool. In a state machine it is a conditional transition (→ L-Orch); with role-agents it is the supervisor.

Part IV — Domains and Architecture Choice¶

Task decomposition is applied in long-horizon domains whose results can be verified, with coding agents and web agents as the two standard cases; the fitting architecture is determined by whether the procedure is known in advance, whether the environment is known before the run, and whether latency or token cost is the binding constraint.

Coding & Web Agents¶

Decomposition matters most in long-horizon, verifiable domains. Both canonical ones are assembled the same way: a macro-planner fixes the shape of the work, and short-horizon ReAct executors run inside its nodes.

The coding agent — edit · run · observe. $$ \text{edit code} \;\to\; \text{run tests} \;\to\; \text{observe output \& errors} \;\to\; \text{fix} \;\to\; \dots $$

• Tools: read/write files, list a directory, run a command / tests (a code action), search the codebase.
• The test suite is the verifier. The runtime hands back an external correctness signal for free — a traceback is a tool-produced critique nobody had to design (Wang, Xingyao, et al., 2024). It is among the highest-$d$ settings available, which is a large part of why agents do well here.
• Decomposition: locate → reproduce → fix → test, often across several files; the planner localises the change and each file goes to an isolated executor that reports a result, not its edit history.
• Safety: running model-written code belongs in a sandbox behind a policy boundary (→ L-Gateway).
• Benchmark: SWE-bench (Jimenez et al., 2024).

The web agent — navigate · read · extract · act.

• Tools: open a URL, serialise the page (usually the accessibility tree or cleaned text, not raw HTML), click, type, scroll, go back. (In the lab: Playwright.)
• The observation problem: a whole page blows the context budget → the agent must extract the relevant part (→ retrieval, → L-RAG).
• Decomposition: a research question fans out into sub-queries, each browsed independently, then the findings are synthesised — fan-out / fan-in.
• No predefined workflow. Navigate · read · extract · act names the tool repertoire, not a pipeline. Which sub-queries, how many and in what order is a plan written at runtime and replanned as pages reveal what is there. The macro-planner fixes the intent ("book the flight"); a short-horizon ReAct loop acts on one page and returns a state summary ("logged in, three candidate flights, cheapest is X"), not the DOM it walked.
• Grounding & risk: the page is untrusted input → prompt injection from page content is a real threat.
• Benchmarks: WebArena (Zhou, Shuyan, et al., 2024), GAIA (Mialon et al., 2024).

Architecture Choice — a Decision Table¶

Read down the questions; the first yes decides.

And, orthogonally to all of it: put a check on every boundary you create, decide what that check reads, and give it a retry budget. A boundary without a verifier buys context and parallelism — but not reliability.

In Practice / This Week's Lab¶

lecture-Decomp-exercises.ipynb — by hand: a plan's DAG from structured steps, adjacency matrix and in/out-degrees, a topological order (Kahn) and its cost, the check that a given order is valid, matrix powers and reachability, the reliability of a decomposed plan with a check.

lecture-Decomp-lab.ipynb:

• Part A — the scheduler. Implement the topological order, the critical path and slack, a linear-time check of a given order; detect a cycle; read a task-graph scheduler.
• Part B — the domain. First let the LLM write the plan — structured steps whose depends_on fields are the edges — validate it (unknown prerequisites, cycles, unknown tools) and hand it to the scheduler from Part A. Then build a small web/coding agent (your agent from → L-ReAct + Playwright) that decomposes a task just-in-time instead, browses/reads or reads/runs code, and produces an answer. The two halves are the lecture's static vs. dynamic pair, run end to end.

Summary¶

Part I — boundaries and checks

• $n$ dependent steps decay as $p^{\,n}$, and plain CoT does not escape it: it writes the steps open-loop. The axis is a chain without boundaries versus one with them.
• A boundary is not a check. With one: $p' = p + (1-p)\,d\,p$; with a fallible one: $p' = p + p(1-p)(d - \phi)$, so a critic is worth having exactly when $d > \phi$.
• The check must read the artifact, never the narration — and the cheapest artifact check is a schema, which is why structured output is the contract between steps.

Part II — the plan as an object

• Planning runs on two levels: an outer decomposition strategy and an inner executor. Take the most deterministic executor a sub-task admits; the executor is a subroutine call with a frame, so only its artifact crosses the boundary.
• Plan time — one planner call before any action — is what turns a plan into an object: inspectable, schedulable, approvable, retryable step by step.
• All three are the same skeleton with five places changed — plan time · loop domain · input binding · executor choice · replanning. Plan-and-Execute replans after every step and runs serially; ReWOO writes dependencies as variable bindings and never replans (removing the static-prompt and quadratic-trace token terms); LLMCompiler streams a DAG, dispatches on a ready set in parallel, and replans on demand (recompilation).
• Provenance is a separate decision: generated (adaptive, structurally fallible), fixed in code (reliable, blind to the unforeseen), or hybrid — which is what production systems look like.

Part III — scheduling and recovery

• A plan is a DAG; a topological order is a legal schedule and Kahn's ready set is the scheduler's loop; the critical path is the irreducible makespan and slack says where optimisation is wasted.
• Streaming the plan buys latency and gives up cycle detection and in-degree counting — you cannot topologically sort a graph you have not finished receiving.
• Parallelism is bounded above by the critical path and below by rate limits and token multipliers; fan-out multiplies prompts while planning removes them.
• A verdict extends the plan, a hard failure blocks a cone; a retry is a new node; and repair works by rebuilding the context, never by appending to the one that already holds the mistake.

Next week: searching over decompositions — Tree-of-Thoughts.

References¶

Peer-reviewed papers

• Besta, Maciej, et al. "Graph of Thoughts: Solving Elaborate Problems with Large Language Models." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 2024. arXiv:2308.09687. — aggregation as the fan-in motif made primary, and §7.3's granularity rule.
• Chen, Ziru, et al. "When is Tree Search Useful for LLM Planning? It Depends on the Discriminator." Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2024, pp. 13659–13678. — the detection rate $d$ measured: pairwise discrimination accuracy, the ≥ 90 % threshold, and grounding worth more than the frontier model.
• Dziri, Nouha, et al. "Faith and Fate: Limits of Transformers on Compositionality." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.18654. — tasks as computation graphs; accuracy decaying with graph depth.
• Gou, Zhibin, et al. "CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing." International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2305.11738. — the critique produced through a tool; the w/o Tool ablation and the generation–discrimination–critique gap.
• Graham, Ronald L. "Bounds on Multiprocessing Timing Anomalies." SIAM Journal on Applied Mathematics, vol. 17, no. 2, 1969, pp. 416–429. — list scheduling is within $2-1/m$ of the optimal makespan.
• Jimenez, Carlos E., et al. "SWE-bench: Can Language Models Resolve Real-World GitHub Issues?" International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2310.06770.
• Kahn, Arthur B. "Topological Sorting of Large Networks." Communications of the ACM, vol. 5, no. 11, 1962, pp. 558–562.
• Kelley, James E., and Morgan R. Walker. "Critical-Path Planning and Scheduling." Papers Presented at the December 1–3, 1959, Eastern Joint IRE-AIEE-ACM Computer Conference. 1959. — critical path, slack and makespan.
• Kim, Sehoon, et al. "An LLM Compiler for Parallel Function Calling." International Conference on Machine Learning. Vol. 235. 2024. arXiv:2312.04511. — the plan as a streamed DAG with placeholder variables; the Task Fetching Unit as ready-set dispatch; dynamic replanning / recompilation; 1.80×–3.74× latency and 3.37×–6.73× cost against ReAct.
• Liang, Tian, et al. "Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate." Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. Vol. 2024. 2024, pp. 17889–17904. arXiv:2305.19118. — the definition of Degeneration-of-Thought.
• Liu, Nelson F., et al. "Lost in the Middle: How Language Models Use Long Contexts." Transactions of the Association for Computational Linguistics, vol. 12, 2024. arXiv:2307.03172. — the U-shaped accuracy curve over the position of the relevant text.
• Madaan, Aman, et al. "Self-Refine: Iterative Refinement with Self-Feedback." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2303.17651. — the minimal reflection loop; actionable and specific feedback; the 94 % "everything looks good" result on maths.
• Mialon, Grégoire, et al. "GAIA: a benchmark for General AI Assistants." International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2311.12983.
• Momennejad, Ida, et al. "Evaluating Cognitive Maps and Planning in Large Language Models with CogEval." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2309.15129. — three measured failure modes of the bare model (hallucinated edges, non-shortest routes, loops), the edge-listing dissociation, and graph structure as the dominant factor.
• Prasad, Archiki, et al. "ADaPT: As-Needed Decomposition and Planning with Language Models." Findings of the Association for Computational Linguistics: NAACL 2024. 2024, pp. 4226–4252. arXiv:2311.05772. — a ReAct executor inside a recursive controller; at $d_{\max}=1$ the system is plain ReAct.
• Shinn, Noah, et al. "Reflexion: Language Agents with Verbal Reinforcement Learning." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2303.11366. — Actor / Evaluator / Self-Reflection; the ablations separating detection from repair, and the false-positive rate $\phi$ measured.
• Tarjan, Robert E. "Edge-Disjoint Spanning Trees and Depth-First Search." Acta Informatica, vol. 6, no. 2, 1976, pp. 171–185. — topological sort as DFS reverse postorder.
• Turpin, Miles, et al. "Language Models Don't Always Say What They Think: Unfaithful Explanations in Chain-of-Thought Prompting." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.04388. — a planted hint moves the answer by up to 36 pp and is named in 1 of 426 explanations.
• Wang, Lei, et al. "Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models." Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics. Vol. 1. 2023. arXiv:2305.04091. — the single-call collapse of the same idea; Tab. 6, where a plan halves missing-step errors and leaves semantic misunderstanding unchanged.
• Wang, Xingyao, et al. "Executable Code Actions Elicit Better LLM Agents." International Conference on Machine Learning. Vol. 235. 2024. arXiv:2402.01030. — code as the action space; the interpreter's traceback as automated feedback.
• Webb, Taylor, et al. "A brain-inspired agentic architecture to improve planning with LLMs." Nature Communications, vol. 16, 2025, p. 8633. — six specialised LLM modules routed by a program; the ablation in which removing the per-action checker costs 74 % → 27 % and drives invalid actions 0 % → 31 %, more than removing decomposition or search.
• Wei, Jason, et al. "Chain-of-Thought Prompting Elicits Reasoning in Large Language Models." Advances in Neural Information Processing Systems. Vol. 35. 2022. arXiv:2201.11903. — the CoT primary; the error taxonomy (8 % calculator-only) and the ablation showing that content-free intermediate tokens perform at baseline.
• Yao, Shunyu, et al. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.10601. — the two-sided sizing constraint for a step.
• Yao, Shunyu, et al. "ReAct: Synergizing Reasoning and Acting in Language Models." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2210.03629.
• Zhou, Denny, et al. "Least-to-Most Prompting Enables Complex Reasoning in Large Language Models." International Conference on Learning Representations. Vol. 2023. 2023. arXiv:2205.10625. — the multi-call decompose-then-solve architecture; Tab. 12, where decomposition costs on 2-step problems and pays at ≥ 5 steps.
• Zhou, Andy, et al. "Language Agent Tree Search Unifies Reasoning, Acting, and Planning in Language Models." International Conference on Machine Learning. Vol. 235. 2024, pp. 62138–62160. arXiv:2310.04406. — search at the outer level with a ReAct step at every node.
• Zhou, Shuyan, et al. "WebArena: A Realistic Web Environment for Building Autonomous Agents." International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2307.13854.

Preprints & other non-peer-reviewed papers

• Chen, Lingjiao, et al. "Optimizing Model Selection for Compound AI Systems." arXiv preprint arXiv:2502.14815 (2025). — swapping only the critic to another model lifts LiveCodeBench 89 % → 95 %.
• Huang, Xu, et al. "Understanding the planning of LLM agents: A survey." arXiv preprint arXiv:2402.02716 (2024). — the decomposition-first vs. interleaved split and its two failure modes; §6 on the absence of a convergence guarantee for self-correction.
• Valmeekam, Karthik, et al. "On the Planning Abilities of Large Language Models (A Critical Investigation with a Proposed Benchmark)." arXiv preprint arXiv:2302.06706 (2023). — Blocksworld plan generation at 1–6.8 % against a 78 % human baseline.
• Xu, Binfeng, et al. "ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models." arXiv preprint arXiv:2305.18323 (2023). — Planner / Worker / Solver; dependency edges as variable bindings (#E1); the input-token arithmetic and its measurement (64 % fewer tokens at +4.4 accuracy); the tool-failure asymmetry; and §4's "enumerate all possible plans" limit on upfront planning.
• Zhang, Shuoming, et al. "LEGO-Compiler: Enhancing Neural Compilation Through Translation Composability." arXiv preprint arXiv:2505.20356 (2025). — the three-arm ablation that prices the checked boundary apart from the split (90.2 → 95.1 → 99.5 % on GPT-4.1), and translation composability, $T(P_1 \circ P_2) \equiv T(P_1) \cdot T(P_2)$, as the precondition a decomposition assumes.

Textbooks & monographs

• Cormen, Thomas H., et al. Introduction to Algorithms. 4th ed., MIT Press, 2022. — §20.1 representations, §20.4 topological sort.
• Gulli, Antonio. Agentic Design Patterns: A Hands-On Guide to Building Intelligent Systems. Springer Nature, 2025. — Ch. 1 prompt chaining, Ch. 2 routing, Ch. 3 parallelization, Ch. 4 Reflection (the producer–critic model and its cost/latency/memory trade-off), Ch. 6 planning, Ch. 12 exception handling and recovery.

Blogs, documentation & other web sources

• Hadfield, Jeremy, et al. "How we built our multi-agent research system." Anthropic Engineering, 2025. https://www.anthropic.com/engineering/multi-agent-research-system — the bill for fan-out: the authors report ≈ 4× a chat's tokens for an agent and ≈ 15× for a multi-agent system, and the criterion that follows — the pattern needs "tasks where the value of the task is high enough to pay for the increased performance." ⚠ Internal figures, no method given; cited for the criterion and the order of magnitude, not as a measurement.
• Breunig, Drew. "How Long Contexts Fail." dbreunig.com, 2025. https://www.dbreunig.com/2025/06/22/how-contexts-fail-and-how-to-fix-them.html — cited for the terminology only: the name context poisoning and its definition.
• Hong, Kelly, et al. "Context Rot: How Increasing Input Tokens Impacts LLM Performance." Chroma, 2025. Technical report. https://research.trychroma.com/context-rot — a single distractor already costing accuracy, with the penalty growing in length.
• LangGraph. "Planning-agent tutorials: Plan-and-Execute, ReWOO, LLMCompiler." langchain-ai/langgraph, commit 23961cff, 2025. https://github.com/langchain-ai/langgraph — the reference implementations, cited for what the code does: one-step-then-replan; a regex-parsed plan with no graph; readiness by polling a shared observation map, with the streaming assumptions stated in a source comment.
• Rajasekaran, Prithvi, et al. "Effective context engineering for AI agents." Anthropic Engineering, 2025. https://www.anthropic.com/engineering/effective-context-engineering-for-ai-agents — sub-agents returning "a condensed, distilled summary" as the containment measure behind a fresh-context retry.
• Schluntz, Erik, and Barry Zhang. "Building Effective Agents." Anthropic Engineering, 2024. https://www.anthropic.com/engineering/building-effective-agents — workflows ("orchestrated through predefined code paths") against agents ("dynamically direct their own processes and tool usage").
• The LangChain Team. "Plan-and-Execute Agents." LangChain blog, 2024. https://www.langchain.com/blog/planning-agents — the taxonomy only (Plan-and-Execute · ReWOO · LLMCompiler) and the three claimed advantages over a ReAct loop; it reports no measurements of its own, and one second-hand number already disagrees with the paper it cites.