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; separate the formal properties a program can check from the semantic properties that need a model critic or a person; 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. Classify a planning architecture along seven design dimensions — plan representation, plan generation time, execution order, executor choice, step verification, replanning, plan provenance — and place Plan-and-Execute, ReWOO, LLMCompiler, ADaPT and AdaPlanner in them.
6. Decide the plan's provenance — generated, fixed in code, or hybrid — and explain why the structure of a generated plan must itself be checked before execution.
7. Model a plan as a DAG: topological order (Kahn), the ready set, the critical path and slack; and mutate it at runtime (insert · prune · re-edge).
8. Handle failure: rejected result vs. hard failure, a retry within the step vs. a retry unrolled as new nodes, verification vs. replanning, 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 planning 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¶

The reliability of a chain is the probability that all of its $n$ dependent steps are correct; it is the product of the conditional reliabilities of the steps and, when every step is correct with the same probability $p$, falls exponentially with $n$.

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 support decomposing a task into sub-tasks — higher reliability, a smaller context per step, and independent steps that run in parallel or are reused — and only the first depends on a check at the boundary between steps.

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 (see Monolithic Prompt vs. Prompt Chain) — 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¶

A monolithic prompt solves all $n$ steps of a task in one generation; a prompt chain issues one model call per step and passes each call the outputs of the earlier calls. The chain raises the per-step success rate only if a step solved in a call of its own succeeds more often than the same step inside the long generation, $p > p_{\text{eff}}$ — an empirical question that the split alone does not settle.

The per-step rate of a monolithic prompt. One generation yields one verdict on the whole task; the outcome of a single step is not observed. The per-step rate $p_{\text{eff}}$ is therefore defined from the task success, as the geometric mean of the conditional step rates:

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

The definition makes $P(X_{1:n}{=}1) = p_{\text{eff}}^{\,n}$ true for every task; it says nothing about how large $p_{\text{eff}}$ is.

A small difference per step becomes a large difference per task, because the task success is the $n$-th power of the per-step rate. At $n = 10$, a per-step rate of $0.8$ instead of $0.9$ (11 % lower) lowers the task success from $0.9^{10} \approx 0.35$ to $0.8^{10} \approx 0.11$ (69 % lower, a factor of $(0.9/0.8)^{10} \approx 3.2$).

Evidence. Zhou et al. (2023) introduce least-to-most prompting, a prompt chain:

"The key idea in this strategy is to break down a complex problem into a series of simpler subproblems and then solve them in sequence." — Zhou et al. (2023), abstract

The task is last-letter concatenation: given a list of $L$ words, output the string of their last letters ("thinking, machine" → "ge"). The monolithic condition is one chain-of-thought generation for the whole list. The chain condition issues one call per prefix of the list — the first word, the first two words, …, all $L$ words — and each call receives the answers to the shorter prefixes and adds the last letter of one word. Measured is the share of 500 random lists per length that the model (code-davinci-002) answers correctly (§3.1, Tab. 4); the per-step rate is computed here as $\text{accuracy}^{1/L}$, one step per word:

The per-step rate of the single generation falls as the generation grows; the per-step rate of the chain stays near 0.98. The two conditions differ in more than the split: the chain's exemplars show how an answer is built from the answer to the shorter prefix, whereas the chain-of-thought exemplars build every answer from the start. The gap therefore measures the method as a whole, not the split alone.

The design pattern. Gulli (2025, Ch. 1) names the chain the prompt chaining pattern (also called the pipeline pattern) and lists the failure modes of a monolithic prompt that it addresses: instruction neglect (parts of the instruction are ignored without notice) · contextual drift (the initial context is lost) · error propagation (an early error is carried into every later part) · context-window pressure · hallucination under load.

Example (Gulli, 2025, Ch. 1). "Analyse this market-research report, summarise it, extract trend data points, and draft an email" — the model may produce a good summary and still fail at 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 check between calls.

Step Reliability with Verification¶

Verification is a check placed after a step that decides whether the step's result is correct; a result that the check rejects is produced again before the next step uses it. The check is a program (unit tests, a schema validator), a language model acting as a critic, or a person (see Kinds of Check).

Result. A check raises the reliability of a step only if it rejects faulty results more often than correct ones. Deterministic checks of a formal artifact meet this condition. A language model used as a critic of programs often does not rank correct and incorrect programs reliably enough for a loop of revisions to beat choosing the highest-scored of several candidates; it comes closer once it is given the result of executing the program.

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}$. An error the check does not detect, a fraction $1-d$ of the faulty results, is passed on at once: with any number of retries the step fails with probability at least $(1-p)(1-d)$.

A step that is checked after every attempt and retried until the check passes needs a random number of attempts $N$; its reliability and its cost follow from one geometric series. The formula $p'$ rests on two assumptions: the check never rejects a correct step, so $d$ is a detection rate, and a retry is a fresh attempt with the same success probability $p$, since detecting an error does not repair it. An attempt is faulty and detected with probability $(1-p)\,d$, and only then is the step attempted again:

$$ p'_\infty \;=\; \sum_{j \ge 0} \big[(1-p)\,d\big]^{\,j}\, p \;=\; \frac{p}{1-d\,(1-p)} , $$

which is $1$ for $d = 1$ and $p$ for $d = 0$, the perfect-check and no-check rows of the table.

Cost. $N \ge 1$ counts the attempts, the first one included, so $N-1$ is the number of retries. The step needs more than $j$ attempts with probability $P(N > j) = [(1-p)\,d]^{\,j}$, so

$$ \mathbb{E}[N] \;=\; \sum_{j \ge 0} P(N > j) \;=\; \frac{1}{1-d\,(1-p)}, \qquad p'_\infty \;=\; p \cdot \mathbb{E}[N] . $$

Reliability rises in proportion to the number of model calls. At $p = 0.9$ and $d = 1$, $\mathbb{E}[N] = 1.11$: 11 % more model calls raise the success probability of a ten-step task from $0.35$ to $1$. At $p = 0.5$ the same perfect check costs $\mathbb{E}[N] = 2$ attempts per step.

A check that also rejects correct results can lower the reliability of a step. The formula $p'$ of the one-retry case 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).$$

Condition. The check raises the reliability of the step exactly when $d > \phi$, that is, when it detects faulty steps more often than it rejects correct ones.

An ungrounded critic, one that reads only the model's own draft, has no evidence that separates a correct draft from a faulty one, so nothing ensures $d > \phi$.

Evidence. Shinn et al. (2023, §4.3, Tab. 3) measure this case with Reflexion, a retry loop for code generation: the model writes a program, runs up to six unit tests that it has generated itself, and after a failed test writes a short explanation of the failure that the next attempt reads; the run stops as soon as all tests pass. On the 50 hardest problems of HumanEval-Rust — the hand-written Python programming problems of HumanEval, each checked by unit tests (Chen et al., 2021), translated to Rust with the MultiPL-E compilers (Cassano et al., 2023) — GPT-4 solves the following share of problems with its final program (pass@1):

Without the tests the loop has no signal that a program is already correct. It therefore runs every iteration and revises correct programs as well; the authors read the 8-percentage-point drop below the no-loop baseline as the effect of these "harmful edits to the implementation".

Design rule. A retry loop needs a check that can say "done"; without one, every iteration is a chance to break a correct result.

Kinds of Check¶

A check is classified by what decides its verdict: a program, a language model, or a person. Pan et al. (2024, §2) separate self-feedback, in which the model judges its own output, from external feedback — tools, other models, knowledge sources, metrics. The three kinds differ in what they can check, in their rates $d$ and $\phi$, and in their cost:

Evidence: a deterministic check is only as good as its tests. In Reflexion's runs, of the programs that pass the unit tests the model wrote itself, 1.4 % fail the benchmark's own tests on HumanEval and 16.3 % on MBPP (Shinn et al., 2023, §4.3). Each such program is a fault the check did not detect: the tests do not cover it.

Evidence: a model critic is measured against people. On open-ended answers, GPT-4 as a judge agrees with human experts on 85 % of pairwise comparisons; human experts agree with each other on 81 % (Zheng et al., 2023).

Design rule. Use a deterministic check wherever the artifact is formal (code, a query, a JSON object); a model critic where no such check exists, with its accuracy measured on the task; and a human at boundaries where an error is irreversible or expensive. A model critic that receives the result of a deterministic check combines the first two (see Grounding of the Critique).

The quality of a critic is measured by its discrimination accuracy. Re-ranking gains from every increase in that accuracy; tree search beats re-ranking only from 90 %, iterative correction only with a perfect critic, and the language-model critics tested on text-to-SQL reach 49–77 %. A generator (also called producer) is the language model that writes the candidate programs; a critic is a model that assigns each candidate program a correctness score. Chen, Ziru, et al. (2024) keep the same generator, CodeLlama-13B, in every experiment and compare three ways of using the critic:

Measured quantity. The critic is evaluated by its discrimination accuracy: over pairs of one correct and one incorrect program for the same task, the share of pairs in which the correct program receives the higher score. For a critic that only passes or flags, a pair is ranked correctly exactly when the correct program passes and the incorrect one is flagged, so the accuracy equals $(1-\phi)\,d$. It is high only when $d$ is high and $\phi$ is low.

Evidence: the accuracy each method needs. The authors replace the critic by a simulated one that returns the true score with probability $\tau$ and the inverted score otherwise, so $\tau$ bounds its accuracy. Tree search solves fewer tasks than re-ranking for $\tau \le 0.8$ and overtakes it only from $\tau = 0.9$; iterative correction does not differ from re-ranking below $\tau = 1.0$ (Chen, Ziru, et al., 2024, Fig. 3).

The Verifier's Target: Artifact vs. Narration¶

A verifier — the check of a step — measures the correctness of the step only when it examines the artifact the step produced, not the model's account of how it was produced. A step of a language model yields two outputs:

• the artifact — the deliverable that the next step uses: a patch, a JSON object, an SQL query, a number;
• the narration — the reasoning text the model generates before or beside the artifact (a chain of thought).

A verifier that grades the narration measures whether the explanation is plausible. That is a different quantity, because the narration need not contain what determined the artifact: a reasoning text can support an answer that a bias in the prompt caused, without mentioning the bias (Turpin et al., 2023).

Design rule. A verifier checks the artifact. The narration is used to diagnose a failure and is never taken as the record of what determined the answer.

Robust Checks, by Domain¶

Every robust check is deterministic: it compares the artifact with a reference that the model's output does not contain — a test, a schema, a database, the source text — and returns a verdict the harness can branch on.

A robust check decides only a formal property of the artifact: whether the tests pass, the object matches the schema, the query runs or the quoted span occurs in the source. Whether the artifact does what the sub-task asks is a semantic property; a deterministic check decides it only where a reference for it exists, and otherwise a model critic or a person checks it (see Kinds of Check).

The Reflection Loop¶

Reflection is a loop in which an output is evaluated and the evaluation is used to revise the output, until the output passes or a retry limit is reached. Gulli (2025, Ch. 4) defines the pattern:

"The Reflection pattern involves an agent evaluating its own work, output, or internal state and using that evaluation to improve its performance or refine its response." — Gulli (2025, Ch. 4)

Reflection is the check-and-retry of Step Reliability with Verification with one change: the retry receives the critique, the result of the evaluation, instead of starting again from the same input. Pan et al. (2024, §2) call the loop post-hoc correction: the finished output is revised, and the parameters of the model are not changed. Reflexion (Shinn et al., 2023) is one published construction of the loop, not a second name for it.

The loop runs at a step boundary, before the step's output is passed downstream:

1. Execute — the producer, the model call that performs the sub-task, produces an artifact.
2. Evaluate — the critic checks the artifact against the step's criteria; its result is the critique. The critic is the producing model under a critic prompt, a second model, or a program such as a test suite (see The Producer–Critic Pattern).
3. Refine — the producer revises the artifact using the critique, without re-running the rest of the task.
4. Iterate — return to the evaluation, until the check passes or a retry cap $\kappa$ is reached.

The detection rate $d$ of the loop is the detection rate of its evaluation step. It depends on what the evaluation reads: the artifact alone, or also the result of executing it (see Grounding of the Critique).

The Producer–Critic Pattern¶

The producer–critic pattern assigns the reflection loop to two roles: a producer, the generator that performs the task, and a critic that evaluates the result. Each role is a separate call with its own prompt; the two calls may use the same model or two different models (also generator–critic, producer–reviewer; Gulli, 2025, Ch. 4):

Gulli (2025, Ch. 4) gives the reason: "While a single agent can perform self-reflection, using two specialized agents (or two separate LLM calls with distinct system prompts) often yields more robust and unbiased results."

Evidence: a different model as critic. Chen, Lingjiao, et al. (2025) build a reflection loop with three modules — generator, critic, refiner — and assign a model to each module. The metric is accuracy, the share of problems solved. On LiveCodeBench, a benchmark of programming problems, the best single model for all three modules is Claude 3.5 Sonnet with 89 %. 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." With Claude 3.5 Sonnet as generator and refiner and GPT-4o as critic, the accuracy is 95 %.

Design rule. The critic is a separate call; where a second model is available, it is tested as the critic first.

Grounding of the Critique¶

A critique is grounded when the critic reads evidence that the producer did not generate — a test result, a tool output — and ungrounded when the critic reads only the task and the producer's output. Three published constructions of the reflection loop assign the critic role in different ways and give the critic different evidence:

A critic that reads its evidence never ends below the same loop without that evidence; without it, the effect of the loop ranges from a loss to a gain. In the Reflexion row, the results of the unit tests are the grounding of the critique. The loop without the tests scores below a single attempt: it has no signal that a program is already correct, so it revises correct programs as well (see Step Reliability with Verification); with the test results the same loop raises the share of solved problems from 60 % to 68 %. In the CRITIC row, the tool output (search results, the output of the Python interpreter) is the grounding of the critique: without it the critique lowers some results and raises others; with it no result is lower than without it.

Evaluator, Actor and CRITIC are the papers' own names. CRITIC is the name of a method, not the critic role: in CRITIC the producing model takes the critic role, and the tool supplies the evidence it reads. All three constructions are instances of the producer–critic pattern; only the evidence of the critic separates the grounded from the ungrounded ones.

Gou et al. (2024) state the conclusion:

"Exclusive reliance on self-correction without external feedback may yield modest improvements or even deteriorate performance." — Gou et al. (2024)

Mechanism. Gou et al. attribute the result to the generation–discrimination–critique gap: a model that can generate a correct answer cannot reliably decide whether the answer it generated is correct.

Design rule. A reflection loop is designed from the critic's evidence: the loop is added only where the critic can read a test result, a tool output or a schema that the deployed system has — never the answer key of a benchmark.

A repair loop that ends worse than re-ranking fails in one of two ways, and only one of them is repaired by more attempts. Re-ranking samples several candidates and returns the one the critic scores highest. Chen, Ziru, et al. (2024, Tab. 6) classify the cases in which re-ranking finds the correct program and iterative correction or tree search does not, on Spider and Bird, two text-to-SQL benchmarks, and on GSM8K, each with the strongest critic of the task — 9 to 48 cases per combination of benchmark and method:

In every combination, discrimination errors are at least half of the losses, and a larger budget does not repair them.

Evidence: a correct answer overwritten. On Spider, in 15 of iterative correction's 29 discrimination errors the correct program had already been generated in an earlier round. The critic scored a later, incorrect revision higher, so the early exit was never triggered and the correct program was replaced.

Design rule. The loop keeps the best-scored candidate of all rounds outside the loop and returns it. A later round can then lower the result only if the critic scores an incorrect candidate above every earlier one.

Structured Output as the Inter-Step Contract¶

Structured output is a step output in a fixed, machine-readable format, typically a JSON object that conforms to a JSON Schema, a specification of the required fields and their types. At the boundary between two steps of a decomposed task, it lets the harness check by program the object that the next step reads. Such a boundary lies between a step and the step that reads its result, and between the planner and the runtime that parses its plan into a dependency graph (see Part II — The Plan as an Object). The schema is the contract between the two steps: the format that the producing step must deliver and on which the reading step relies. Free text has no format that a program can check: if the next step misreads a free-text output, no check detects the error, and the next step continues from a wrong input (Gulli, 2025, Ch. 1).

The output of a trend-extraction step as a JSON object (Gulli's example; the figures are his illustration):

{
  "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."}
  ]
}

Two mechanisms ensure that a step's output conforms to its schema, and they act at different times:

The arguments of a tool call are checked against the tool's schema in the same way.

What a schema check detects. A schema validator is a deterministic check (see Step Reliability with Verification) of a formal property of the object (see Robust Checks, by Domain). With a correct schema it never rejects a well-formed object, so $\phi = 0$. It detects unparseable output, missing fields and wrong types, and nothing else: a well-formed object with a false value, such as an invented figure, passes it. Its detection rate covers format faults only.

Design rule. Every step boundary at which a program reads the output (a parser, the scheduler, the arguments of a tool call, a step that reads named fields) carries a schema, and the harness validates the object before the next step reads it. An output that a person reads next, such as the final answer, needs no schema: wrapping it in an object checks only the wrapper. A check of the content is added wherever the content can be checked.

What a schema adds depends on what performs the step. A step is performed by a tool, by a single model generation or by a ReAct loop, and the three differ in the output they produce without a schema:

A JSON Schema is one checkable format among several. Code and SQL have the grammar of their language as their format, checked by a parser or a compiler, and their robust check is execution (see Robust Checks, by Domain). A plan is a structured list of sub-tasks with their dependencies, so that the runtime can parse it into a dependency graph.

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. Huang, Xu, et al. define a plan more narrowly, as the sequence of actions that a model generates for a goal in an environment (Huang, Xu, et al., 2024, §1); a plan in this part names sub-tasks, and an executor turns each sub-task into actions. The plan object also fixes where the check of a step's result sits and what a rejected result triggers: a retry of the step, a new plan, or nothing (see Step Verification).

Two Levels: Strategy and Executor¶

A decomposed task is planned at two levels: the decomposition strategy splits the goal into sub-tasks, and an executor carries out one sub-task. The strategy, the outer level, decides which sub-tasks exist and in which order they run. The executor, the inner level, performs one of them: a tool call, a single model generation, or a whole ReAct loop.

The executor is the step, not a component between two steps. Between two steps lies the check of Step Reliability with Verification: the executor's result is checked before the next sub-task reads it, and a rejected result sends the sub-task back to its executor. A step in Part I — Boundaries and Checks is anything that succeeds with probability $p$; in this part it is one sub-task carried out by its executor, and the executor determines $p$. The question "which pattern should be used?" has one answer at each level, and the two answers are chosen independently.

The two levels are filled from different menus: what sits outside is a way of splitting a goal; what sits inside is a way of acting. They are the two steps into which Huang, Xu, et al. divide task decomposition: the "decompose" step, which splits the goal, and the "sub-plan step", which plans each part (Huang, Xu, et al., 2024, §3). The survey divides decomposition by when the goal is split. In decomposition-first planning the whole goal is split into sub-tasks before the first action; in interleaved decomposition "each decomposition only reveals one or two sub-tasks at the current state". The two further outer entries lie outside that division: recursive decomposition splits a sub-task only after it has failed, and search is the survey's separate direction multi-plan selection, in which several candidate plans are generated and one is selected (§4).

Outer — how is the goal split?

• Interleaved (also called just-in-time) — decide the next step each turn (ReAct); no plan object
• Decomposition-first — the whole plan before the first action, then execute it; with one model call per step, the plan is an object outside the model
• Recursive (as-needed decomposition in ADaPT, Prasad et al., 2024) — decompose a sub-task only when it is still too big or has failed
• Search over candidate steps (multi-plan selection in the survey) — score candidates, explore the good ones (ToT, → L-ToT)

Inner — how is one sub-task finished?

• a deterministic call — a tool, a code execution, a schema-validated parse
• a single CoT generation
• a ReAct loop — reason, act, observe

The two lists are independent menus: any outer strategy can be combined with any inner executor, so a decomposition-first plan may hand one step to a tool call and the next to a ReAct loop that acts.

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

In $p^{\,n}$ the outer level fixes the exponent $n$, the number of steps, and the inner level fixes the base $p$, the probability that one step succeeds. The cheapest way to raise a chain's reliability is therefore not a better prompt but a step that cannot be got wrong, which raises $p$ towards $1$ — 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.

A calculator error is a step handed to the wrong executor, not a reasoning failure. 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, and 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 called by the harness, like a subroutine. 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 keeps the outer level's context proportional to the number of steps rather than to the work done inside them. A delegation to a subagent returns an artifact in the same way; it differs in the caller. There, a model decides what to hand over and must state it in a contract — an objective, an output format, guidance on tools and sources, and task boundaries (Hadfield et al., 2025) — while here the harness code fixes the interface.

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 trajectory lengthens with every level — the condition under which, for interleaved decomposition, "excessively long trajectories may lead to LLM experiencing hallucinations, deviating from the original goals" (Huang, Xu, et al., 2024, §3.3). 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).

Notation for the Pseudocode¶

Every pseudocode box this lecture 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¶

Decompose-then-solve is the control structure in which the agent first decomposes the goal into sub-tasks and then solves the sub-tasks; every planning architecture of this part is a variation of it. It is decomposition-first planning in its multi-call form — one model call writes the plan, one call solves each sub-task — which is the structure of least-to-most prompting (Zhou et al., 2023): the prompt chain of Monolithic Prompt vs. Prompt Chain with the plan written out. The agent loop of → L-ReAct and this one differ in a single line (1). $\text{Solve}_i$ in the box is the executor of one sub-task; it does not compose the final answer.

$$ \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(\tau_i,\ \textit{results}\big) \qquad \text{// not the goal, not the plan} \\ 5: \quad \qquad r_i \gets \text{Solve}_i(\textit{prompt}_i) \qquad \text{// the executor chosen for this sub-task} \\ 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.

Writing the plan in line 1, before any action, changes how the run terminates, what each step reads and what a failed step can change:

• Termination moves out of the model. The ReAct loop 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 its sub-task and the results so far — not the goal, not the rest of the plan, and not the transcripts that produced the results. That is "context stays small" made concrete, and it is why a single step can be retried on its own. A sub-task written for this prompt must therefore be intelligible without the goal: "compute the ratio of #E1 and #E2", not "compute the ratio".
• Nothing returns to line 1. A failed step cannot change the plan. A plan that is not revised during the run is static; a plan that a replanning step revises from what the run observed is dynamic.

The Step Check in the Skeleton¶

The check of a step's result is harness code, not a decision of the executor: the harness calls a subroutine that solves the sub-task and checks the result, and only a result that the check has accepted enters $\textit{results}$. Decomposition creates the boundary, the result $r_i$ of one call that the next call reads; the check at that boundary raises the reliability of the step from $p$ to $p'$ (see Step Reliability with Verification). The skeleton with the check differs from Decompose-then-Solve in the subroutine that line 5 calls and in line 6, which receives a failure report:

$$ \begin{array}{l} \textbf{Decompose-then-Solve-with-Check}(\textit{goal}) \\ \hline \textbf{Input: } \textit{goal} \text{; the tool set; the retry cap } \kappa \\ \textbf{Output: } \text{the final answer, or a failure report} \\ \hline 1: \quad [\,\tau_1, \dots, \tau_n\,] \gets \text{LLM}_{\text{plan}}(\textit{goal}) \\ 2: \quad \textit{results} \gets [\;] \\ 3: \quad \textbf{for } i = 1 \dots n \textbf{ do} \\ 4: \quad \qquad \textit{prompt}_i \gets \text{Render}\big(\tau_i,\ \textit{results}\big) \\ 5: \quad \qquad r_i \gets \textbf{Checked-Step}_i(\textit{prompt}_i) \qquad \text{// was } \text{Solve}_i(\textit{prompt}_i) \text{: solve AND check} \\ 6: \quad \qquad \textbf{if } r_i \text{ is a failure report } \textbf{then return } r_i \qquad \text{// the plan is static: no repair} \\ 7: \quad \qquad \textit{results}.\text{append}\big((\tau_i,\, r_i)\big) \qquad \text{// only checked results} \\ 8: \quad \textbf{return } \text{LLM}_{\text{answer}}(\textit{goal},\ \textit{results}) \\ \hline \end{array} $$

$\textbf{Checked-Step}_i$ is the subroutine of line 5. It takes the prompt, as $\text{Solve}_i$ does, calls the executor $\text{Solve}_i$, and checks the result:

$$ \begin{array}{l} \textbf{Checked-Step}_i(\textit{prompt}_i) \\ \hline \textbf{Input: } \text{the prompt of sub-task } \tau_i \text{; the retry cap } \kappa \\ \textbf{Output: } \text{a checked result } r_i \text{, or a failure report} \\ \hline 1: \quad \textit{prompt} \gets \textit{prompt}_i \\ 2: \quad \textbf{repeat } \kappa \textbf{ times} \\ 3: \quad \qquad r_i \gets \text{Solve}_i(\textit{prompt}) \\ 4: \quad \qquad v \gets \text{Check}_i(r_i) \qquad \text{// reads the artifact, not the transcript} \\ 5: \quad \qquad \textbf{if } v \text{ accepts } r_i \textbf{ then return } r_i \\ 6: \quad \qquad \textit{prompt} \gets \textit{prompt}_i \oplus v \qquad \text{// the original prompt and the latest critique} \\ 7: \quad \textbf{return } \text{a failure report for } \tau_i \qquad \text{// the cap is reached} \\ \hline \end{array} $$

• The retry prompt is rebuilt, not extended. Line 6 starts again from the original $\textit{prompt}_i$ and adds only the latest verdict $v$, so the retry reads the critique, not the failed attempt and not the earlier critiques (see Context Poisoning and Context Confusion).
• Without the critique in line 6 the subroutine is the check-and-retry from which $p'$ is derived: with $\kappa = 2$ the step ends correct with probability $p'$, and with $\kappa \to \infty$ with $p'_\infty$, provided that a retry is a fresh attempt with the same $p$. With the critique it is the reflection loop.
• $\text{Check}_i$ is chosen per sub-task, like $\text{Solve}_i$: a deterministic check where $r_i$ is a formal artifact (code, a JSON object), a model critic where it is not (see Kinds of Check).
• A check left to the executor is a different design. A ReAct executor may call the tests itself, but then the model decides whether the check runs, the harness receives the model's statement that it checked rather than a verdict, and a retry runs in the failed context.
• A failure report ends the run (line 6 of Decompose-then-Solve-with-Check), because the plan is static. The planning architectures below differ in where such a report goes.

Design Dimensions of a Planning Architecture¶

A planning architecture is fixed by its answers to seven design questions: how the plan is represented, when it is written, by which rule its steps are ordered, who picks the executor of each step, whether the result of a step is checked, when the plan is revised, and who authors its structure. Each question is a place where an architecture departs from the Decompose-then-Solve skeleton, and each architecture of this part is one combination of answers (see Planning Architectures).

The questions are independent; some answers constrain each other.

• A scheduler that runs steps in parallel needs a plan that states its dependencies, so the ready set as execution order presupposes a DAG, a directed acyclic graph of the steps.
• A plan that is revised after every step behaves like interleaved decomposition, although it is written in full before the first step.
• Step verification and replanning are the two repairs of one feedback loop: verification retries a step, replanning changes the remaining plan.

Plan Representation¶

The plan representation is the form in which the plan exists during the run, and it decides what the harness can do with the plan. It fixes how the steps and their dependencies are stored.

A dependency is stated by a name in the step, in a separate list, or not at all. A step that receives earlier results by context finds them in its rendered prompt, and the plan says nothing about which results it needs. A step that receives them by name carries a placeholder in its argument string (ReWOO's #E1, LLMCompiler's $1), which a program replaces by the stored result. The placeholder is the edge: the parser derives the graph from the text of the plan. A separate depends_on list states the same fact a second time and can contradict the steps it describes.

The Plan as a Text File¶

A plan object need not be a data structure: coding agents store the plan as a Markdown file that the agent writes, a human reads and approves, and a later phase executes. The file is inspected by a person, not by a scheduler. It has no schema, so the harness can compute no ready set from it, and its dependencies are implicit in the order of the steps.

• Plan mode (Claude Code). During planning the runtime blocks the file-editing tools; shell commands still run, each reviewed by a classifier (a second model that approves or blocks an action) or by the user (Anthropic, 2026, Choose a permission mode). The plan is written to a Markdown file and presented for approval, and the user may edit the file before approving it. Approval unblocks the editing tools.
• ExecPlan (Codex). A Markdown plan that must be self-contained ("it should always be possible to restart from only the ExecPlan and no other work"), with sections the agent keeps current while it executes the plan: Progress, Surprises & Discoveries, Decision Log and Outcomes & Retrospective (Friel, 2025).

Design rule. A plan that a person must approve before execution is written as a text file; a plan whose steps a scheduler dispatches is written as a graph.

Plan Generation Time¶

Plan generation time is the point in the run at which the plan, or a part of it, is written. Huang, Xu, et al. (2024, §3) divide decomposition by this point into decomposition-first and interleaved decomposition (see Two Levels: Strategy and Executor); two further times occur in published architectures:

Each mode of decomposition has one advantage and one cost, and the cost of each is the advantage of the other (Huang, Xu, et al., 2024, §3.3). Task forgetting is the loss of the original goal in the course of a long run.

Two costs apply to both modes: the decomposition itself incurs "additional time and computational costs", and a task "decomposed into dozens of sub-tasks" makes the planning "constrained by the context length of the LLM". The survey states the trade-off as a synthesis of the works it reviews; it does not measure it.

Design rule. A decomposition-first plan is paired with a mechanism that adjusts it — replanning, which the survey files as the refinement step of reflection and refinement (Huang, Xu, et al., 2024, §6); an interleaved run is given a bound on the length of its trajectory.

Execution Order¶

The execution order is the rule by which the next step is chosen; a scheduler is the runtime component that applies the rule.

A ready-set scheduler requires a DAG. Whether a step is ready is computed from its dependencies, so a plan that states none can only be executed in list order. A DAG makes parallel execution possible; a scheduler that reads the dependencies carries it out. ReWOO's plan is a DAG, but its Worker executes the steps in the order the planner listed them, so two steps that do not depend on each other run one after the other, although they could run in parallel.

The ready set, its computation by Kahn's algorithm and the bound that the critical path places on parallelism are derived in Topological Order & the Ready Set.

Executor Choice¶

Executor choice is the decision which executor carries out a sub-task: a tool call, a single model generation or a ReAct loop. The dimension records who makes the decision.

The executor sets the base $p$ of $p^{\,n}$, and the most deterministic executor that a sub-task admits raises $p$ the most (see Two Levels: Strategy and Executor). A fixed ReAct executor gives up this choice for every step. A planner that names the tool turns the choice into model output, which can name a tool that does not exist.

Step Verification¶

Step verification is the check of a step's result before a later step uses it. Three properties describe it: the point at which the result is read, what decides (a program, a model, or nobody), and what a rejected result triggers. The point at which a result is read decides what a negative decision can repair: one step, the remaining graph, or nothing.

None of the three published architectures checks the result of a step robustly. Their deterministic checks are formal and apply to the plan and the tool calls (the schema of the plan, the dependencies parsed from the placeholders, the arguments of a call), while every reading of a result is a model call. A robust check of a result is the designer's addition, made per sub-task as $\textbf{Checked-Step}_i$ with a deterministic $\text{Check}_i$ (see Robust Checks, by Domain).

A check per graph raises the success probability of a chain less than a check per step, because its retry repeats all $n$ steps. The comparison keeps the assumptions of $p'$: one retry, a retry is a fresh attempt with the same $p$, and the check rejects no correct result. With a check after every step, each step ends correct with $p' = p + (1-p)\,d\,p$, and the chain with $(p')^{\,n}$. With one check after the whole graph, $d$ is the probability that the check detects a faulty run; a detected run is executed once more, and if the retry derives all $n$ tasks again it succeeds with $p^{\,n}$:

$$ P_{\text{step}} = \big(p + (1-p)\,d\,p\big)^{n}, \qquad P_{\text{graph}} = p^{\,n} + (1-p^{\,n})\,d\,p^{\,n}. $$

At $p = 0.9$, $n = 10$ and $d = 1$: $P_{\text{step}} = 0.99^{10} \approx 0.90$ and $P_{\text{graph}} \approx 0.35 + 0.65 \cdot 0.35 \approx 0.58$. A per-graph check detects a fault only after every dependent task has consumed it, and the retry is again a chain of $n$ unchecked steps.

Design rule. A sub-task whose result can be checked by program is checked at its own boundary, inside its step. A model call per graph, such as LLMCompiler's Joiner or a replanner, decides what only the set of all results shows: whether the results suffice to answer the goal.

Replanning¶

Replanning is the revision of a plan from what the run has observed; in the survey of Huang, Xu, et al. it is the refinement step of the direction reflection and refinement (Huang, Xu, et al., 2024, §6). Two properties describe it: what triggers a revision, and how much of the plan is rewritten.

Verification and replanning are the two repairs of one feedback loop: the harness reads a result, decides against a criterion, and repairs. Verification decides whether the result of one step is correct and repairs by retrying that step. Replanning decides what remains to be done and repairs by changing the remaining plan.

The two repairs work in layers. Each architecture can call $\textbf{Checked-Step}$ in place of its executor: a rejected result is first retried within its step, and only a failure report that remains after $\kappa$ attempts reaches the replanner. A replanning call that states no criterion of correctness (Plan-and-Execute), or that decides whether the observations suffice (LLMCompiler), reads a result without verifying it.

Plan Provenance¶

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 fourth row is the survey's external planner-aided planning (Huang, Xu, et al., 2024, §5): in LLM+P the model writes the problem in PDDL, the Planning Domain Definition Language, and a classical planner produces the plan (Liu et al., 2023).

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.

Planning Architectures¶

A published planning architecture is one combination of answers to the seven design questions. Five are worked through below:

• Plan-and-Execute — In the LangChain tutorial for a family of graphs, after Plan-and-Solve prompting (Wang et al., 2023), a single call with no plan object, and BabyAGI (The LangChain Team, 2024). The LangGraph version analysed here (LangGraph, 2025) replans after every step: decomposition-first when it writes the plan, interleaved in its behaviour.
• ReWOO (Xu et al., 2023)
• LLMCompiler (Kim et al., 2024)
• ADaPT (Prasad et al., 2024)
• AdaPlanner (Sun et al., 2023)

In every row the plan is generated by the model; ADaPT generates it inside a controller program that is fixed in code (see Plan Provenance).

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

Plan-and-Execute writes a plan, executes one step of it, and then replans the remaining steps from the result of that step (LangGraph, 2025). Position in the design space: a list, rewritten after every step · only its first step is executed · one ReAct agent for every step · no step check · replanning after every step. $$ \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 \textit{reply} \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 } \textit{reply} \text{ is a Response } \textbf{then return } \textit{reply} \\ 9: \quad \qquad [\,\tau_1, \dots, \tau_n\,] \gets \textit{reply}.\textit{steps} \qquad \text{// here } \textit{reply} \text{ is a Plan: "only what still NEEDS to be done"} \\ \hline \end{array} $$

Line 5 passes the executor the current plan, the steps that the replanner has not yet removed, as context: the plan shows the executor which part of the task is its own and what the later steps will do. The results so far go only to the replanner (line 7), which is instructed to give each remaining step all the information it needs; the executor never receives $\textit{results}$ (LangGraph, 2025, Plan-and-Execute, execute_step and the replanner prompt).

Cost of the design. Each executed step costs one replanning call; in exchange, the plan is revised after every observation. The steps run one after the other: "each task is still executed in sequence, meaning embarrassingly parallel operations all add to the total execution time" (LangGraph, 2025, Plan-and-Execute, Conclusion). The fixed ReAct executor runs every step, whatever the step is, so the choice of the most deterministic executor is given up.

ReWOO — Planner · Worker · Solver¶

ReWOO (Xu et al., 2023) removes the replanning entirely: the plan is written before any tool runs, and never revised. Position in the design space: a DAG written as a list, with #E names · written before execution · list order · the planner names the tool · no step check · no replanning.

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 \textit{blueprint} \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}(\textit{blueprint}) \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} $$

Difference from the skeleton. A step's arguments are completed by substituting a named value (line 5) instead of re-rendering a prompt from $\textit{results}$; that change turns the plan into a graph. The planner also names the tool of each step, $\textit{tool}_s$.

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"]

Passing results by name removes a 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. HuggingGPT writes its plans in such a format: a task lists its prerequisites in a field dep and reads their outputs as <resource>-k in its arguments (Shen et al., 2023).

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. LLMCompiler removes that limitation.

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 takes its vocabulary from compilers. Position in the design space: a DAG with $k names · streamed · ready set, in parallel · the planner names the tool · no step check · replanning on demand.

Three components for parallel function 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.

The final model call, which either answers or requests a new plan, is not a component in Kim et al. (2024): the paper implements it as a finish task at the end of every plan. The name Joiner, used for that call from here on, is LangChain's (The LangChain Team, 2024).

(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 placeholders $1 and $2 of task 3 with the outputs of tasks 1 and 2 before it fetches task 3 to 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 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; the parser reads each task's } \textit{deps} \text{ off its placeholders} \\ 5: \quad \qquad \textit{obs} \gets \text{Schedule}(G,\ \textit{obs}) \qquad \text{// the Task Fetching Unit: Schedule without } \text{Check}_\tau \text{, } \textit{onfail} \text{ and } \textit{blocked} \\ 6: \quad \qquad \textit{reply} \gets \text{LLM}_{\text{join}}(\textit{goal},\ \textit{obs}) \qquad \text{// the JOINER: a Response, or Replan} \\ 7: \quad \qquad \textbf{if } \textit{reply} \text{ is a Response } \textbf{then return } \textit{reply} \\ 8: \quad \qquad \textit{context} \gets \textit{reply}.\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.

LLMCompiler adds two mechanisms to the DAG: the planner streams the graph, and the remaining graph is replanned when it cannot be fixed in advance.

• 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". On its own, streaming lowers latency by a factor of up to 1.3.
• 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, LLMCompiler lowers both latency and cost, because the plan removes LLM invocations instead of adding them:

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

ADaPT — Decomposition on Failure¶

ADaPT runs an executor on a task first and decomposes the task only when the executor fails (Prasad et al., 2024). Position in the design space: sub-tasks joined by AND or OR · written on failure · ordered by a recursive controller program · one ReAct executor · the executor's own report of success as the step check · replanning by decomposing the failed sub-task.

• The controller is a program, not a model. It calls the executor, a ReAct loop, on the task. If the executor reports success, the controller returns. Otherwise, if the depth $k$ is below a maximum depth $d_{\max}$, it calls the planner, which writes 3–5 sub-tasks joined by AND (every sub-task must succeed) or OR (one suffices), and calls itself on each sub-task. With $d_{\max} = 1$ the system is plain ReAct.
• The step check is weak. The report of success or failure is generated by the model itself.

Evidence. With GPT-3.5 as executor and planner, success rate on the test splits of three text environments (Prasad et al., 2024, Tables 1–2):

Try Again calls the executor as often as ADaPT does but never decomposes, so the difference between the last two columns measures decomposition, not repetition.

AdaPlanner — Assertions and Plan Refinement¶

AdaPlanner writes the plan as Python code in which every sub-goal ends with an assertion on the environment's observation; a failed assertion halts execution, and the model rewrites the plan and resumes it at the failed sub-goal (Sun et al., 2023). Position in the design space: code, one assertion per sub-goal · written before execution · the order of the code · the code calls the actions · a deterministic check of every sub-goal · replanning on a failed assertion.

def solution(agent, start_from=1):
    ...
    assert 'clean' in observation, f'Error in [Step 3]: I cannot clean {found_lettuce} using the sinkbasin 1. {agent.report()}'

• In-plan feedback, an observation that matches the prediction, is parsed by a model call (ask_LLM()) and the plan continues.
• Out-of-plan feedback, a failed assertion, sends the trajectory so far to a refiner, which rewrites the plan; execution resumes at the failed sub-goal through start_from.

The check is deterministic, its criterion is not. The harness evaluates the assertion, but the model writes it as part of the plan; a missing or wrong assertion is an undetected fault.

Evidence. On the 134 ALFWorld tasks, success rate: AdaPlanner (text-davinci-002) 91.79 %, Reflexion (GPT-3 and GPT-3.5) 88.06 %, ReAct (text-davinci-002) 61.94 % (Sun et al., 2023, Table 2). The assertions, the refinement and the code-style prompt are measured together; the table does not separate the contribution of the check.

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.

A retry changes the plan only when it crosses a node boundary. The static plan that the scheduler sorts is a DAG: $\tau_1 \to \tau_2 \to \tau_3$. The execution trace contains a cycle, try → fail → retry: $\tau_2 \to \texttt{tests\_failed} \to \tau_2' \to \tau_3$.

• A retry inside $\textbf{Checked-Step}_\tau$ stays within one node. Its attempts are local to the call, and the node returns a checked result or a failure report; the plan is unchanged.
• A retry that crosses a node boundary is unrolled. This happens when the retries of a step are exhausted, or when a check node reports a fault that lies in one of its predecessors. The retry becomes a new node ($\tau_2'$, attempt 2) or, when a check node reported the fault, a copy of the faulty predecessor and of every node between it and the blocked dependents, so the expanded graph stays acyclic and can be scheduled.

The cycle lives in the control loop of the caller, not in the DAG that is sorted topologically.

Graph Mutation at Runtime¶

Graph mutation is the modification of the plan DAG while the plan is executed: nodes are inserted or pruned and dependencies are added or removed, in response to a failed step or to a new observation. Graph mutation is replanning at the granularity of single nodes and edges (see Replanning); Plan-and-Execute and LLMCompiler replan coarsely, by regenerating the remaining steps or the remaining graph.

Mutating a graph that a scheduler is already walking is safe as long as two invariants hold:

• 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. The check is simpler than the algorithm that produced the order and independent of it; it is a deterministic check of a formal property of the plan (see Robust Checks, by Domain).

$$ \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 } \textit{inDegree}[v] \gets 0 \\ 2: \quad \textbf{for each } (u, v) \in E \textbf{ do } \textit{inDegree}[v] \gets \textit{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 } \textit{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 } v \text{ with } (u, v) \in E \textbf{ do} \\ 10: \quad \qquad \qquad \textit{inDegree}[v] \gets \textit{inDegree}[v] - 1 \\ 11: \quad \qquad \qquad \textbf{if } \textit{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} $$

In a plan, the vertices $V$ are the sub-tasks $T$ and the edges $E$ are the dependencies.

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¶

The DAG of a plan determines which sub-tasks may run at the same time, and its critical path bounds how fast the plan can finish. A topological order gives one sequential schedule; two sub-tasks with no path between them are independent and may run in parallel.

The critical path is the path through the DAG with the largest total duration. With unlimited workers, the minimum time to finish the plan, the makespan, is the 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 sub-task $\tau_i$ (not the detection rate $d$ of a check).

• No number of workers finishes the plan sooner than the length of the critical path.
• A sub-task off the critical path has slack, the time by which it can be delayed without delaying the plan; shortening it does not shorten the makespan. Shortening a sub-task on the critical path shortens the makespan by the same amount, until another path becomes the longest.
• The critical path depends on the durations, not only on the edges: changing one duration can move it to another path.

Complexity. A longest path in a general graph is NP-hard to find; in a DAG it is found in $\Theta(|T|+|E|)$ time by a topological sort followed by dynamic programming. Critical path, slack and makespan are the terms of 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 language model prompted to answer in JSON, returns one object per sub-task with a field depends_on that names its predecessors. These fields are the edges, so the parsed plan is the graph in the figure. The plan states its dependencies in a separate list (see Plan Representation); a plan with placeholders would derive them from the arguments of each sub-task. 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 edges, not the durations. The model emits id and depends_on: which sub-task needs the output of which, a fact it can read from the task statement. It does not emit dur. A duration depends on the runtime (the latency of a tool, the network, the load of a worker) and is known only from measurement, such as the latency of earlier runs of the same kind of step (→ L-Eval). The critical path and the slack are computed from these measured durations.

In the example, the critical path is read_spec → fetch_data → write_code → run_tests → report, with length $1+3+4+1+1 = \mathbf{10}$ time units.

• No number of workers finishes the plan sooner. Executed one after another, the six sub-tasks take 12 time units, so parallel execution saves 2.
• write_tests lies off the critical path and has 5 time units of slack: it may start up to 5 units late, or take up to $2+5=7$ units, before the makespan changes.

A spurious edge causes no error; it reduces the slack. fetch_data precedes write_code but not write_tests, because an edge states what a step needs as input, not what runs first. The code must match the dataset's columns and quirks, so it needs the data; the tests encode the contract from the spec, which is known before any data arrive. With the edge fetch_data → write_tests added, the makespan stays 10, but write_tests is no longer independent and its slack falls from 5 to 2.

Prioritization among Ready Tasks¶

When more sub-tasks are ready than workers are free, the scheduler ranks the ready sub-tasks. A topological order states only which orders are legal; the ranking chooses one of them.

• Criteria: urgency (a deadline), importance, cost, or dependency leverage: a delay of a sub-task on the critical path delays the whole plan by the same amount.
• Effect of the ranking. With $m$ workers, every rule that never leaves a worker idle while a sub-task is ready finishes within $2 - 1/m$ times the optimal makespan (Graham, 1969). The ranking therefore changes the makespan by less than a factor of 2, and the length of the critical path is a lower bound under every ranking.
• Priorities change during the run: a new deadline or a failed step changes the ranking, as replanning changes the plan.

Scheduling vs. prioritization. A topological sort answers which sub-tasks may run; prioritization answers which of the ready ones runs first. Prioritization matters only when fewer workers are free than sub-tasks are ready.

Execution, Failure & Recovery¶

Execution runs the sub-tasks of a plan in dependency order; a failure is a sub-task that returns no verified result; recovery changes the plan or the context so that the run can continue. The three responsibilities belong to different components: the scheduler executes and reports failures, and its caller, the planning architecture that handed it the plan, repairs them.

Data flows along the edges. A sub-task $\tau_j$ receives as inputs the outputs of every $\tau_i$ with an edge $\tau_i \to \tau_j$. In a placeholder architecture an edge exists exactly where the planner wrote a reference to $\tau_i$ into the arguments of $\tau_j$: the edge and the variable binding are the same symbol. The scheduler executes the ready sub-tasks, independent ones in parallel, and passes each output to the sub-tasks that depend on it.

A rejected result and a hard failure are both called "failure"; which of the two occurred decides who can repair the step.

At plan level, a retry adds new nodes and revisits none. Feeding the error back changes the input, so the restarted step is a different task instance $\tau'$, added to the graph as a node of its own, and every step derived again from it is added as a new copy as well. The attempts inside $\textbf{Checked-Step}_\tau$ are local to the call and add no node. Without a limit the graph grows without bound; a retry cap $\kappa_{\text{plan}}$ limits how often a run may replan around the same failure. It is the plan-level counterpart of the cap $\kappa$ on the attempts of one step in the reflection loop. The caller sets the cap, because the caller adds the retry nodes.

The Scheduler Loop¶

A scheduler repeats four steps until no sub-task is ready and none is running.

1. Ready set. Compute the sub-tasks that may run now: not yet attempted, not running, not blocked, with every predecessor finished.
2. Dispatch. Start as many of them as workers are free, each through $\textbf{Checked-Step}_\tau$, without waiting for them.
3. Wait. Take the next sub-task to finish and record its artifact or its failure report.
4. Block. After a failure report, block the descendant cone of the failed sub-task. Under the policy stop the scheduler returns at once and cancels what is still running; under drain it finishes what is still ready.

An empty ready set alone does not end the loop: the remaining sub-tasks may wait for one that is still running.

The scheduler detects and reports; it does not repair. It returns the results, the failure reports and the blocked sub-tasks; the caller, the planning architecture, repairs the plan with new nodes and calls the scheduler again.

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.

The scheduler neither plans nor repairs. The plan $G$ is an input of the Schedule procedure, not something it produces. Schedule is the runtime to which a planning architecture hands its plan: the contents of the $\text{Schedule}$ call that the LLMCompiler box leaves closed. Replanning and unrolling therefore stay with the caller, and the scheduler returns what it could not run instead of working around it.

$$ \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 a failure report} \,\} ;\quad \textit{running} \gets \emptyset \\ 2: \quad \textbf{while } \big(\textit{ready} \gets \text{ReadySet}(G,\ \textit{done},\ \textit{blocked},\ \textit{running})\big) \neq \emptyset \;\vee\; \textit{running} \neq \emptyset \textbf{ do} \\ 3: \quad \qquad \textbf{for each } \tau \in \text{Pick}(\textit{ready}) \textbf{ do spawn } \textbf{Checked-Step}_\tau\Big(\text{Render}\big(\tau,\ \{\, \textit{out}[u] \mid u \in \operatorname{pred}(\tau) \,\}\big)\Big) ;\ \textit{running} \gets \textit{running} \cup \{\tau\} \qquad \text{// dispatch, no wait} \\ 4: \quad \qquad (\tau,\ r_\tau) \gets \text{WaitAny}(\textit{running}) ;\quad \textit{running} \gets \textit{running} \setminus \{\tau\} \qquad \text{// the next sub-task to finish} \\ 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 a failure report } \textbf{then} \qquad \text{// a hard failure OR a rejected result — 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} \qquad \text{// running sub-tasks are cancelled; their results are lost} \\ 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 (line 6), because a dispatcher can do the same about either: block the cone. The difference matters only to the caller, which reads $\textit{out}[\tau]$ to tell the two apart. The plan $G$ stays acyclic: a retry that crosses a node boundary is not a cycle in $G$ but new nodes that the replanner adds between two calls of Schedule.

Lines 3–4 dispatch without waiting. Line 3 starts every sub-task that $\text{Pick}$ selects and does not wait for it; line 4 waits for the next sub-task to finish. The loop ends only when no sub-task is ready and none is running: an empty ready set alone does not mean that the plan is finished, because the remaining sub-tasks may wait for one that is still running.

Line 1 lets the caller call Schedule again on a repaired graph. $\textit{blocked}$ is derived from the store rather than reset: a cone whose failed node was not repaired stays blocked when the scheduler is called again, while re-pointing the dependents onto a repair node removes them from the cone. A repair node, being fresh, is in nobody's cone.

Line 8 applies the blocking policy $\textit{onfail}$. Under $\textit{stop}$ the scheduler returns the moment a cone is blocked and cancels the sub-tasks still running: their results are lost, and a later call executes them again. Under $\textit{drain}$ it re-enters the loop and finishes everything still ready, returning once nothing is left to run.

Which node a rejecting verdict concerns. A result that the step's own check rejects is retried within $\textbf{Checked-Step}_\tau$, and only a failure report that remains reaches line 6. A rejecting verdict of a check node, such as red tests from run_tests, concerns a predecessor: the caller extends the plan with retry nodes from the predecessor it diagnoses as faulty on (see Unrolling a Failed Test 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¶

A failed test run is a rejecting verdict: the step run_tests executed and produced the signal the plan exists to obtain. report stays blocked while the failure stands. The replanner lifts the block by adding new nodes and re-pointing report onto them:

• The figure is the plan $G'$ after the first replanning round. run_tests (dashed) has failed and stays in the graph with its failure report in $\textit{out}$. report has been re-pointed: its edge from run_tests is removed, because a node with a failed predecessor stays blocked, and an edge from run_tests' is added. A second red run repeats the construction with write_code'' and run_tests'', until the cap $\kappa_{\text{plan}}$ is reached.

• The failing test report enters write_code' through its prompt, not through an edge. The replanner writes the distilled report into the arguments of write_code'. An edge run_tests → write_code' would place write_code' in the descendant cone of the failed node, and line 1 of Schedule, which rebuilds the blocked set from every failure report in $\textit{out}$ when the replanner calls it again, would block it. run_tests' is a new node as well, because an attempted node is never dispatched again, and it reads write_tests as run_tests does.

• write_code' is a new node, not write_code executed again. Its input is larger: the spec, the data, and the failing test report. A re-run with the original input receives no information about the failure.

• The choice of the node to unroll is a diagnosis. A failed test means that the code is wrong (write_code'), the test is wrong (write_tests'), or the data differ from what the spec assumed (fetch_data', after which every sub-task downstream is derived again). A wrong choice spends one of the $\kappa_{\text{plan}}$ attempts without repairing the cause.

• The cap $\kappa_{\text{plan}}$ is part of the plan, like the step cap of the ReAct loop. It counts replanning rounds, not tool calls, because each round adds one new copy of write_code and of run_tests. A loop of textual self-correction is not guaranteed to converge, that is, to reach a correct result and stop changing it: "the convergence of this textual form of update currently lacks a guaranteed proof" (Huang, Xu, et al., 2024, §6). Only the cap stops it, or a check that accepts the result.

Outcome of a Failed Step¶

A failed step leaves content in the run that later model calls read, and one kind of it is not recorded as a failure. Which content a step leaves depends on the kind of failure, a rejected result (the step ran, and the check rejected its result) or a hard failure (the step produced no output; see Execution, Failure & Recovery), and on whether a check detected the fault. The content is written by a model, by the harness, or by the environment, the interpreter, test runner, API or file system on which the executor acts:

An undetected wrong result occurs with probability $(1-p)(1-d)$ per checked step (see Step Reliability with Verification), and with probability $1-p$ per step without a check.

Retry Input¶

A retry is a further attempt after a failed step, and its input is either rebuilt from the original task or accumulated from the failed attempt. A retry occurs at two levels, and at plan level it may repeat several steps:

• Step level: the loop of $\textbf{Checked-Step}_\tau$, lines 2–6 — an attempt, a check, and a further attempt while the check rejects the result, up to the cap $\kappa$.
• Plan level: a replanner that receives the result of a failed step and writes new steps or nodes, up to the cap $\kappa_{\text{plan}}$ on replanning rounds. Such a retry covers the step at which the replanner restarts, the failed step or a predecessor it diagnoses as faulty, and every step derived again from it: after a failed test run, write_code' and run_tests' repeat two steps (see Unrolling a Failed Test Run), and LLMCompiler's recompilation replaces the whole remaining graph. Restarting at the last verified node is the checkpoint rollback of Recovery Strategies.

A rebuilt input holds the original task and a verdict or a failure report. An accumulated input holds the failed attempt itself: the wrong artifact, the reasoning that produced it and the error messages.

The content of a failed step reaches the next attempt, the replanner, the new nodes and the component that composes the answer, and each of them reads a rebuilt or an accumulated input:

Context Poisoning and Context Confusion¶

Context poisoning is the state in which a hallucination or another error has entered the context and is referenced again at every later turn — "when a hallucination or other error makes it into the context, where it is repeatedly referenced" (Breunig, 2025). Context confusion is the state in which "superfluous content in the context is used by the model to generate a low-quality response" (Breunig, 2025). Which of the two a reader is exposed to depends on the content of a failed step that its input holds (see Outcome of a Failed Step):

A rebuilt input does not remove an undetected wrong result. The replanner reads it as an ordinary result, whether its input is rebuilt or accumulated, and writes it into the arguments of the new nodes, which read it as part of their instruction. A hard failure poisons nothing. Breunig (2025) does not discuss tool errors; the assignment follows from the two definitions.

Superfluous content lowers accuracy, as two measurements show:

• A single distractor lowers accuracy, and the loss grows with input length, across 18 models on deliberately simple tasks (Hong et al., 2025). A failed attempt and the copies of an error message act as such distractors.
• The position of the relevant fact matters. Accuracy over that position is U-shaped: with the answer in the middle of the context, GPT-3.5-Turbo answers fewer questions correctly than with no documents at all, its closed-book accuracy (Liu et al., 2024). In a long retry transcript, the inputs given before the first attempt end up in the middle of the context.

Retry Input by Architecture¶

The published planning architectures differ in which component reads the result of a failed step, and in whether that component's input is rebuilt or accumulated.

Plan-and-Execute, LLMCompiler and AdaPlanner pass the failed attempt to their replanner, and none of the three separates it into the kinds of content of Context Poisoning and Context Confusion. Plan-and-Execute, ReWOO and LLMCompiler have no step check (see Step Verification), so every result they pass on may be an undetected wrong result. None of the sources measures what the accumulated input costs in poisoning or confusion; the last column states what it supplies to the replanner, read from the prompts and the code.

Recovery Strategies¶

A recovery strategy is chosen by the content it must keep out of the next call, and a rebuilt input keeps out only what is recorded as a failure.

Why a rebuilt input keeps the failed attempt out. A step executed in a context of its own returns only what it reports. Sub-agents return "a condensed, distilled summary of its work" (Rajasekaran et al., 2025), not everything they read; an error in the failed attempt can therefore reach the next attempt only through the report.

Design rule. A retry reads the failure report, not the failed reasoning: it is a fresh attempt with a better input, not the same attempt with a longer context. At step level, $\textbf{Checked-Step}_\tau$ rebuilds the prompt from the original and the latest critique (line 6). At plan level, the replanner reads the failure reports that $\textbf{Checked-Step}_\tau$ returns, not the earlier attempts, and the retry starts with a new node whose arguments carry the report; the error message thus enters the retry once. The failure report therefore carries what the replanner would otherwise take from an accumulated input: the current state of the environment, where earlier actions have changed it; the evidence for the choice of the node at which the retry starts; and the error message, once. The harness assembles the report from the last verdict and the error message instead of having a model summarize the attempt: a report written by a model, or carrying the verdict of a model critic, is model output and can carry an error to the replanner.

Recovery and the Step Check¶

Recovery applies the check-and-retry of a single step to the plan: the check of a step decides that the step failed, and the recovery strategy decides what the retry reads and at which node it starts. The check-and-retry of a single step is derived under Step Reliability with Verification.

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. AdaPlanner makes this comparison an assertion on the observation that the plan predicted (see AdaPlanner — Assertions and Plan Refinement).

(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.

Scheduling and Flow Patterns in a Framework¶

A developer rarely writes the scheduler: a graph library or a workflow engine supplies it, and the concepts of this part are the settings it is configured with. pydantic-graph, the graph library of Pydantic AI, shows the correspondence:

The repair policy is left to the caller. A failure stops the run unless the caller sends a new task; the library has no blocked cone and no drain or stop policy, and the failure report names what failed only if the step's exception says so.

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¶

A coding agent changes a code base to complete a task, such as fixing a reported bug; a web agent completes a task by operating a web browser. Both tasks take many steps, and both are built from the parts of this lecture: the decomposition strategy fixes the order of the sub-tasks, and the executor of each sub-task is a short ReAct loop that calls the tools (see Two Levels: Strategy and Executor).

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 and write files, list a directory, run a command or the tests, search the code base. In CodeAct the action itself is executable code, and the interpreter returns its results and errors as the observation (Wang, Xingyao, et al., 2024).
• The test suite is the check. Each run of the tests returns a verdict that the model did not write, and a traceback names the failing line. It is a deterministic check in the sense of Kinds of Check: its detection rate is bounded by what the tests cover. The test run is a check node: red tests can point to faulty code, faulty tests or data that differ from the spec, so the repair begins with the choice of the node to retry (see Unrolling a Failed Test Run).
• Decomposition: locate the cause → reproduce the failure → fix → test, possibly across several files.
• Safety: code written by the model is executed in a sandbox behind a policy boundary (→ L-Gateway).
• Benchmark: SWE-bench (Jimenez et al., 2024): 2,294 GitHub issues from 12 Python repositories; an issue counts as resolved when the tests that the original fix made pass also pass with the agent's patch.

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

• Tools: open a URL, convert the page to text, click, type, scroll, go back. The page is passed to the model as cleaned text or as its accessibility tree, the tree of page elements with their roles and labels that the browser provides for screen readers, and not as raw HTML.
• The observation problem: a whole page exceeds the context budget, so the agent extracts the relevant part (retrieval, → L-RAG).
• Decomposition: a research question is split into sub-queries, each browsed independently, and the findings are synthesised: fan-out and fan-in.
• No predefined workflow. Navigate · read · extract · act names the tool repertoire, not a pipeline. Which sub-queries are issued, how many and in what order is a plan written at runtime and replanned as pages show what they contain. The planner fixes the intent ("book the flight"); a short ReAct loop acts on one page and returns a state summary ("logged in, three candidate flights, cheapest is X"), not the page structure it traversed.
• The step check is weak. The result of a page task, a fact read or a form filled in, can seldom be checked by a program, so the check of a step is a model critic that reads the state summary (see Kinds of Check), unless the task supplies a checkable result such as an expected answer.
• Untrusted input: page content enters the model's context, so text on a page can carry instructions that the model may follow (prompt injection).
• Benchmarks: WebArena (Zhou, Shuyan, et al., 2024), 812 tasks on self-hosted websites of four kinds (shopping, forum, software development, content management), where the best GPT-4 agent completes 14.41 % and humans 78.24 %; GAIA (Mialon et al., 2024), 466 questions with one short answer each that require browsing and tools, of which human respondents answer 92 % correctly and GPT-4 with plugins 15 %.

Architecture Choice — a Decision Table¶

The choice among the architectures of this lecture follows from seven properties of the task, tested in a fixed order: the first question answered yes decides.

Design rule. Every boundary created by the decomposition carries a check; the design states what the check reads, the retry cap $\kappa$, and what a failure report that remains after $\kappa$ attempts triggers: replanning, with its cap $\kappa_{\text{plan}}$, or the end of the run. A check that a program can perform belongs inside the step, as $\textbf{Checked-Step}$ or as an assertion per sub-goal (AdaPlanner); the published planning architectures contain no such check, so the designer adds it. A boundary without a check makes the context smaller and allows parallel execution, but it does not raise reliability.

In Practice / This Week's Lab¶

lecture-Decomp-exercises.ipynb — by hand, in the order of the lecture: the reliability of a chain with and without a check, false positives, formal vs. semantic checks; the design dimensions of an architecture, a check per step vs. a check per graph; a plan's DAG, its topological orders and their check, and a trace of the scheduler with a failing step and its repair.

lecture-Decomp-lab.ipynb — Pydantic AI and its graph library pydantic-graph, introduced as tutorials: an agent with a typed output, a graph of steps with a fork and a join, and a run stepped through event by event, in which the caller repairs a failing step with a new task; then ReWOO's planner, worker and solver on a typed plan that a program checks and compiles into a graph of steps, which executes independent steps concurrently, and a loop that replans when a step fails.

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. A robust check decides a formal property; whether the artifact does what was asked is a semantic property, checked by a model critic, which helps only if $d > \phi$ and only when it reads evidence that the producer did not generate.
• The cheapest artifact check is a schema; it belongs at every boundary at which a program reads the output, 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.
• Writing the plan before any action (decomposition-first) turns it into an object: inspectable, schedulable, approvable, retryable step by step.
• A planning architecture is one combination of answers to seven design dimensions — plan representation · generation time · execution order · executor choice · step verification · replanning · provenance. Plan-and-Execute replans after every step and runs serially; ReWOO writes dependencies as variable bindings and never replans; LLMCompiler streams a DAG, dispatches on a ready set in parallel, and replans on demand (recompilation); ADaPT decomposes a sub-task when its executor reports failure; AdaPlanner checks every sub-goal with an assertion and rewrites the plan when one fails.
• None of the three published architectures checks the result of a step robustly; verification (retry the step) and replanning (change the remaining plan) are the two repairs of one feedback loop.
• 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.
• Parallelism is bounded by the critical path: no number of workers finishes the plan sooner.
• A rejected result is first retried within its step; a failure report that remains, or a rejecting verdict of a check node, extends the plan with new nodes; a hard failure blocks a cone. Repair works by rebuilding the context, never by appending to the one that already holds the mistake.

Part IV — domains and architecture choice

• The architecture follows from properties of the task, tested in a fixed order: the first question answered yes decides.
• A coding agent's test run is a check node: red tests start a diagnosis of the node to retry. A web agent's step check is mostly a model critic on a state summary, a weak check.
• Every boundary carries a check; the design states what it reads, the retry cap $\kappa$, and what a failure report that remains after $\kappa$ attempts triggers.

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.
• Cassano, Federico, et al. "MultiPL-E: A Scalable and Polyglot Approach to Benchmarking Neural Code Generation." IEEE Transactions on Software Engineering, vol. 49, no. 7, 2023, pp. 3675–3691. arXiv:2208.08227. — HumanEval and MBPP translated from Python to 18 other languages; the source of HumanEval-Rust.
• Chen, Jiawei, et al. "Benchmarking Large Language Models in Retrieval-Augmented Generation." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 38. 2024, pp. 17754–17762. arXiv:2309.01431. — counterfactual robustness: false content in five retrieved documents is followed although the model answers correctly without them.
• 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. arXiv:2402.10890. — 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. doi:10.1137/0117039. — list scheduling is within $2-1/m$ of the optimal makespan.
• Horling, Bryan, and Victor Lesser. "A Survey of Multi-Agent Organizational Paradigms." The Knowledge Engineering Review, vol. 19, no. 4, 2004, pp. 281–316. doi:10.1017/S0269888905000317. — hierarchy, holarchy, coalition, team and market as organizational paradigms.
• Huang, Jie, et al. "Large Language Models Cannot Self-Correct Reasoning Yet." International Conference on Learning Representations. Vol. 2024. 2024. arXiv:2310.01798. — intrinsic self-correction defined; without an oracle label every model tested loses accuracy on every benchmark.
• 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. doi:10.1145/368996.369025.
• 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, pp. 160–173. doi:10.1145/1460299.1460318. — 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.
• Pan, Liangming, et al. "Automatically Correcting Large Language Models: Surveying the Landscape of Diverse Automated Correction Strategies." Transactions of the Association for Computational Linguistics, vol. 12, 2024, pp. 484–506. arXiv:2308.03188. — the language model / critic / refine model as typed functions; intrinsic self-correction.
• 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.
• Shen, Yongliang, et al. "HuggingGPT: Solving AI Tasks with ChatGPT and its Friends in Hugging Face." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2303.17580. — a plan as JSON tasks with an explicit dependency field and resource references: each edge stated twice; independent tasks executed in parallel.
• 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.
• Sun, Haotian, et al. "AdaPlanner: Adaptive Planning from Feedback with Language Models." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2305.16653. — the plan as code with one assertion per sub-goal; a failed assertion triggers a rewrite of the plan from that sub-goal.
• Tarjan, Robert E. "Edge-Disjoint Spanning Trees and Depth-First Search." Acta Informatica, vol. 6, no. 2, 1976, pp. 171–185. doi:10.1007/BF00268499. — 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 bias in the prompt lowers accuracy by up to 36.3 percentage points 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. doi:10.1038/s41467-025-63804-5. — 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.
• Xu, Hanwen, et al. "TPS-Bench: Evaluating AI Agents' Tool Planning & Scheduling Abilities in Compounding Tasks." Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2026, pp. 34949–34961. arXiv:2511.01527. — the missing edge measured: one-turn parallel tool calls against sequential ones on tasks with strict sub-task dependencies.
• 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.
• Zheng, Lianmin, et al. "Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena." Advances in Neural Information Processing Systems. Vol. 36. 2023. arXiv:2306.05685. — GPT-4 as a judge agrees with human experts on 85 % of pairwise comparisons, against 81 % between experts; position, verbosity and self-enhancement bias.
• 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. 4, where a prompt chain against one chain-of-thought generation keeps 74.0 % against 31.8 % on 12-word lists.
• 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 %.
• Chen, Mark, et al. "Evaluating Large Language Models Trained on Code." arXiv preprint arXiv:2107.03374 (2021). — HumanEval, 164 hand-written Python programming problems checked by unit tests.
• 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.
• Liu, Bo, et al. "LLM+P: Empowering Large Language Models with Optimal Planning Proficiency." arXiv preprint arXiv:2304.11477 (2023). — the model as the writer of a PDDL problem, a classical planner as the planner.
• 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.
• Willard, Brandon T., and Rémi Louf. "Efficient Guided Generation for Large Language Models." arXiv preprint arXiv:2307.09702 (2023). — constrained decoding: a token that cannot continue a valid string receives probability zero.
• 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 separates stepwise prompting from the split, with the same test-and-repair loop in every arm (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.
• Durfee, Edmund H. "Distributed Problem Solving and Planning." Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, edited by Gerhard Weiss, MIT Press, 1999, ch. 3. — task sharing: decomposition, allocation, accomplishment, synthesis.
• 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

• Anthropic. "Choose a permission mode." Claude Code documentation, retrieved 2026-10-25. https://code.claude.com/docs/en/permission-modes — plan mode as a gate on the file-editing tools; shell commands under a classifier or a prompt; no enforcement in interactive sessions with bypass permissions.
• Anthropic. "Claude Code plan mode as the default starting point." The AI-native SDLC playbook, Claude Academy, 2026. https://academy.claude.com/courses/ai-native-sdlc-playbook/plan-mode — the plan approved by the engineer, committed as plan.md and kept in sync with the diff. ⚠ Reports no measurements; cited for the workflow only.
• Anthropic. "Explore the .claude directory." Claude Code documentation, retrieved 2026-10-25. https://code.claude.com/docs/en/claude-directory — the retention sweep that deletes plan files after cleanupPeriodDays.
• Anthropic. "Settings reference." Claude Code documentation, retrieved 2026-10-25. https://code.claude.com/docs/en/settings-reference — plansDirectory.
• 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.
• Friel, Aaron. "Using PLANS.md for multi-hour problem solving." OpenAI Cookbook, 2025. https://developers.openai.com/cookbook/articles/codex_exec_plans — the ExecPlan: a self-contained Markdown plan with mandatory progress and decision sections. ⚠ Reports no measurements, and marked archived by its publisher; cited for the mechanism only.
• 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.
• Katta, Kishore. "ReAct vs Plan & Execute: Choosing the Right Agent Thinking Pattern in Oracle Integration." Oracle Integration blog, 29 Apr. 2026. https://blogs.oracle.com/integration/react-vs-plan-execute-choosing-the-right-agent-thinking-pattern-in-oracle-integration — a product sold as Plan & Execute with no replanning. ⚠ Vendor documentation, no measurements.
• Kim, Sehoon, et al. "LLMCompiler: Reference Implementation." SqueezeAILab/LLMCompiler, GitHub, commit a00c9d3, 2024. https://github.com/SqueezeAILab/LLMCompiler — the Task Fetching Unit as a central polling loop (0.01 s); tool calls without an error handler.
• LangGraph. "Planning-agent tutorials: Plan-and-Execute, ReWOO, LLMCompiler." langchain-ai/langgraph, commit 23961cff, 2025. https://github.com/langchain-ai/langgraph/tree/23961cff/docs/docs/tutorials — 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.
• Pydantic. "Graph Builder." Pydantic AI documentation, retrieved 2026-10-01. https://pydantic.dev/docs/ai/graph/builder/ — steps, decision nodes, fork and join.
• Pydantic. "Parallel Execution." Pydantic AI documentation, retrieved 2026-10-28. https://pydantic.dev/docs/ai/graph/builder/parallel/ — fork (broadcast, spread) and join; reduction in completion order.
• Pydantic. "pydantic_graph.graph_builder." Pydantic AI API reference, retrieved 2026-10-28. https://pydantic.dev/docs/ai/api/pydantic_graph/graph_builder/ — GraphRun, ErrorMarker, override_next.
• Pydantic. "Agents: Usage Limits." Pydantic AI documentation, retrieved 2026-10-28. https://pydantic.dev/docs/ai/core-concepts/agent/ — UsageLimits, a request limit of 50 by default.
• Pydantic. "Planning." Pydantic AI Harness documentation, retrieved 2026-10-28. https://pydantic.dev/docs/ai/harness/planning/ — a task list with dependencies, kept in a store; no executor.
• Pydantic. "Dynamic Workflow." Pydantic AI Harness documentation, retrieved 2026-10-31. https://pydantic.dev/docs/ai/harness/dynamic-workflow/ — sub-agents as async functions of one script; failures as exceptions; a cap on sub-agent calls.
• Qwen Team. Qwen Code: The Open-Source AI Coding Agent for Your Terminal. GitHub repository, v0.26.1, 2026. — the partition of one response's tool calls into parallel and sequential batches by tool kind. https://github.com/QwenLM/qwen-code
• 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.