Planning and Execution

The critique loop works on one thing at a time. It assumes the task already exists as a candidate we can hold, inspect and improve.

Some tasks have no draft to hold.

Inspect a project, reproduce the failing test, find the cause, patch the code, rerun the relevant tests, and report what changed.

No single narrow action responsibly completes that goal, and the actions constrain each other. Patching before diagnosis is guesswork wearing the costume of work, and reporting success before observing a passing test is a claim about the world that nothing in the run supports. Worse, if execution reveals that an assumption was wrong, the rest of the route may be wrong too. A runtime choosing each action independently can react to the new observation, but without an explicit representation of the intended route it has nothing concrete to compare the changed world against.

So we need to represent intended work before carrying it out. That representation is a plan.

The word carries baggage, so it is worth being precise. A fluent list of steps is not a plan in any useful sense: a model can produce something that reads as orderly while omitting a dependency, assuming a resource that does not exist, or placing an irreversible action before the evidence that would justify it.

Prose that sounds like a plan gives the runtime nothing to check.

So the definition here is stronger:

A plan is a falsifiable hypothesis about how the current state reaches the goal.

Falsifiable is the load-bearing word. A plan pays for itself by exposing enough structure that the runtime can reject it before execution, and enough declared evidence that later observations can tell us when it has stopped being true.

    flowchart TD
    G["goal + known facts"] --> P["planner"]
    P --> PL["proposed plan"]
    PL --> V{"structure and<br/>semantics valid?"}
    V -->|no| R["reject, or refuse<br/>the task"]
    V -->|yes| S["select a ready step"]
    S --> E["executor"]
    E --> O["observation"]
    O --> C{"does a remaining step<br/>rely on a withdrawn fact?"}
    C -->|no| S
    C -->|yes| P

    classDef model fill:#fbe3cd,stroke:#b8712c,color:#000
    classDef runtime fill:#d8e6f4,stroke:#2b6cb0,color:#000
    classDef execution fill:#eef2f7,stroke:#6b7280,color:#000
    class P model
    class V,S,C,R runtime
    class E execution
  

Colour separates responsibilities rather than pretending every component is a model call. The planner is the probabilistic proposal component. The blue boxes are runtime decisions over explicit data. The executor is an execution component: it may invoke deterministic tools, a model-assisted capability, or some mixture, but it does not own the route. Three constraints matter. The planner never performs side effects while planning, the executor never rewrites the route, and the runtime never treats the plan as authority merely because a model produced it.

That last is the stance the action boundary took towards one proposed action, applied now to a proposed sequence of them.

1. When a plan is worth building

For a task that one action completes, planning adds latency, tokens, and a second thing that can be wrong:

action = decide(state)
observation = execute(action)

Planning pays when success depends on the relationships between actions rather than merely the number of them. Six independent actions may need little more than ordinary orchestration. Three actions where the second consumes evidence produced by the first need that dependency written somewhere the runtime can read it. The question is not how many steps exist, but whether correctness depends on relationships among them that the runtime must preserve.

The distinction is easy to lose, because a model can decompose a goal into prose that looks like planning:

1. inspect the project
2. fix the problem
3. test it
4. report success

Something real has been gained: the work has been named. But every question that determines whether the route is executable remains open. What must be known before step 2 starts? What evidence should step 1 produce? What makes step 3 ready rather than merely next? Which observation would tell us the route is already dead?

Compare two ways of saying the same thing. In prose:

reproduce the bug before diagnosing it

In data:

diagnose.depends_on = ("reproduce",)

The first is advice to a reader. The second is a constraint the runtime can enforce, and the gap between those two is most of this book.

If correctness depends on a relationship, represent the relationship.

2. A plan step is a claim that can be wrong

A step carrying only an instruction is a sentence with extra syntax. To be checkable it must declare what it waits on, what it needs, and what it leaves behind:

from dataclasses import dataclass

@dataclass(frozen=True)
class PlanStep:
    id: str
    action: str
    depends_on: tuple[str, ...] = ()
    requires: tuple[str, ...] = ()
    produces: tuple[str, ...] = ()
    expected_evidence: str = ""

@dataclass(frozen=True)
class Plan:
    steps: tuple[PlanStep, ...]

requires and produces name facts rather than describing them, and that choice is what makes the rest of the chapter possible. A precondition written as "the failure has been reproduced" is prose: the runtime can store and display it, but cannot match it reliably against execution state. Written as the fact name failure_reproduced, expected from an earlier step and consumed by this one, it becomes something a validator can check before execution and an observation can later establish or withdraw.

The distinction between declared and observed facts matters. produces=("failure_reproduced",) is the machine-checkable claim about what successful execution should establish. expected_evidence is the human-readable explanation of what that establishment should look like in the trace; it does not itself promote anything into state. The runtime must not add failure_reproduced merely because the step returned ok=True. Later in the chapter we require the observation itself to carry the facts actually established.

reproduce = PlanStep(
    id="reproduce",
    action="Run the focused failing test and capture its output.",
    requires=("repository_available",),
    produces=("failure_reproduced", "error_trace"),
    expected_evidence="a reproducible failure with a concrete error trace",
)

diagnose = PlanStep(
    id="diagnose",
    action="Identify the smallest code path that explains the failure.",
    depends_on=("reproduce",),
    requires=("failure_reproduced", "error_trace"),
    produces=("root_cause",),
    expected_evidence="a root-cause hypothesis tied to observed code and failure output",
)

A list forces a total order onto work that often has none. Inspecting the logs and running the failing test both need the repository, neither needs the other, and both must finish before diagnosis begins. As a list, one inspection sits arbitrarily blocked behind the other, and nothing distinguishes the orderings that are required from the ones that are incidental.

    flowchart LR
    T["test<br/>→ failure_reproduced"]
    L["logs<br/>→ log_evidence"]
    D["diagnose<br/>→ root_cause"]
    P["patch<br/>→ patch_applied"]
    V["verify<br/>→ tests_pass"]

    T --> D
    L --> D
    D --> P
    P --> V
  

Dependencies turn the plan into a small directed acyclic graph. No graph library is needed to collect the benefit: a depends_on tuple and a topological walk are enough, and keeping it that small means the whole structure stays readable in a log line.

3. The plan and the execution state are different objects

The plan says what we intend. The execution state says what happened. Collapsing them into one mutable object is tempting and expensive.

from dataclasses import dataclass, field

@dataclass
class ExecutionState:
    completed: set[str] = field(default_factory=set)
    observations: dict[str, Observation] = field(default_factory=dict)
    facts: set[str] = field(default_factory=set)
    outcome: str | None = None

facts is the runtime’s small working model of what has been established. Each step’s requires field is checked against it. It starts with facts the environment or task contract supplies, and it grows only from facts supported by observations. A plan may predict what a step will produce; execution state records what the run has actually earned.

Mutate the plan as execution moves and a failed run cannot be diagnosed, because the artefact recording what we intended has been overwritten by what we did. Three quite different failures then leave identical traces: the route was wrong; the route was right and a step executed badly; the route was right and the runtime silently changed it mid-run.

Plan = intended route. Execution state = observed history of that route.

The chapter on runtime state makes this state durable and gives it progress and stopping rules. Here we need only enough of it to check preconditions and record what each step left behind.

4. Structural validation: what the runtime can prove

The action boundary established that model output is a proposal rather than an instruction. A generated plan is a proposal too, and a much larger one, so the same gate belongs in front of it.

Some defects are decidable without knowing anything about the domain: duplicate ids, a dependency on a step that does not exist, a step depending on itself, a cycle, a required field left blank. These are what the action boundary called schema failures, in that the object is malformed regardless of what it means, so we reuse that exception rather than inventing a parallel vocabulary for plans.

def _topological_order(plan: Plan) -> list[PlanStep]:
    by_id = {step.id: step for step in plan.steps}
    order: list[PlanStep] = []
    visiting: set[str] = set()
    visited: set[str] = set()

    def visit(node: str) -> None:
        if node in visiting:
            raise SchemaError(f"dependency cycle reached at {node!r}")
        if node in visited:
            return

        visiting.add(node)
        for dependency in by_id[node].depends_on:
            visit(dependency)
        visiting.discard(node)
        visited.add(node)
        order.append(by_id[node])

    for step_id in by_id:
        visit(step_id)

    return order

def validate_plan_structure(plan: Plan) -> None:
    ids = [step.id for step in plan.steps]
    duplicates = {i for i in ids if ids.count(i) > 1}

    if duplicates:
        raise SchemaError(f"duplicate step ids: {sorted(duplicates)}")

    known = set(ids)

    for step in plan.steps:
        if step.id in step.depends_on:
            raise SchemaError(f"{step.id}: depends on itself")

        unknown = set(step.depends_on) - known
        if unknown:
            raise SchemaError(f"{step.id}: unknown dependencies {sorted(unknown)}")

        if not step.action.strip():
            raise SchemaError(f"{step.id}: empty action")

        if not step.expected_evidence.strip():
            raise SchemaError(f"{step.id}: no expected evidence declared")

    _topological_order(plan)

This cannot show that a plan will work. It shows that a certain class of plans cannot work, which is worth more than it first sounds: a cycle in a generated dependency graph is a common failure and a completely silent one. A runtime without this check discovers it by reaching a point where no step is ready, which is exactly what successful completion also looks like.

The check turns a run that ends in ambiguity into an error raised before the first tool call.

5. Semantic validation: what structure cannot catch

Consider a plan that reproduces the failure, deletes the failing test, and reports that the tests now pass. Every check in the previous section passes: ids unique, dependencies real, no cycle, every field populated. It is also a plan to defeat the goal rather than achieve it, and no amount of structural checking will say so, because the defect lives in what the steps mean.

Semantic checking needs a statement of what the goal actually demands. The runtime cannot infer that from the goal string, and asking the planner to check its own plan puts the same distribution on both sides of the test. So the requirement is declared separately, as a property of the task rather than of the route:

@dataclass(frozen=True)
class GoalContract:
    required: frozenset[str] = frozenset()
    forbidden: frozenset[str] = frozenset()
    must_precede: frozenset[tuple[str, str]] = frozenset()
    given_facts: frozenset[str] = frozenset()
    obtainable_facts: frozenset[str] = frozenset()

Checking a plan against a contract is then four questions, and the fourth is what the requires/produces design was for:

def _ancestors(plan: Plan) -> dict[str, set[str]]:
    closure: dict[str, set[str]] = {}

    for step in _topological_order(plan):
        ancestors = set(step.depends_on)

        for dependency in step.depends_on:
            ancestors |= closure[dependency]

        closure[step.id] = ancestors

    return closure


def validate_plan_semantics(plan: Plan, contract: GoalContract) -> None:
    ids = {step.id for step in plan.steps}
    by_id = {step.id: step for step in plan.steps}

    missing = contract.required - ids
    if missing:
        raise SemanticError(f"required steps absent: {sorted(missing)}")

    banned = contract.forbidden & ids
    if banned:
        raise SemanticError(f"forbidden steps present: {sorted(banned)}")

    ancestors = _ancestors(plan)

    out_of_order = sorted(
        (before, after)
        for before, after in contract.must_precede
        if before in ids
        and after in ids
        and before not in ancestors[after]
    )
    if out_of_order:
        raise SemanticError(f"ordering violations: {out_of_order}")

    for step in plan.steps:
        available = set(contract.given_facts)

        for ancestor_id in ancestors[step.id]:
            available |= set(by_id[ancestor_id].produces)

        unmet = set(step.requires) - available
        if unmet:
            raise SemanticError(
                f"{step.id}: requires facts not supplied by its dependency "
                f"ancestors or initial state: {sorted(unmet)}"
            )

That final check asks whether every required fact is either present in the initial state or declared by a dependency ancestor of the step that consumes it. The ancestry requirement is important. Merely placing an unrelated producer earlier in one valid topological ordering must not satisfy a dependency the plan never represented.

A plan that patches code it never located therefore fails before any tool runs, naming the missing relationship instead of depending on an incidental ordering of otherwise independent steps.

A contract need not be complete to be useful. Four required planning milestones and one forbidden one already catch the delete-the-test plan. In this small implementation those milestones use canonical step ids such as reproduce, diagnose, patch, and verify; a production system may represent them as typed step kinds rather than relying on arbitrary model-generated names.

The contract is also not the final verifier of the user’s goal. It describes planning obligations: work that must appear, work that must not appear, ordering constraints, and facts the route may rely on. Later verification still has to decide whether the resulting environment state actually satisfies the goal.

6. Infeasibility is a result, not a failure

A planner asked to publish a release with no deployment credentials has three options. It can invent steps until the output resembles work. It can produce a plan that runs happily until the last step fails. Or it can report that no route exists from here.

Only the third is honest, and only the third is actionable.

@dataclass(frozen=True)
class PlanningFailure:
    reason: str
    unsatisfiable: tuple[str, ...]

PlanResult = Plan | PlanningFailure

The type is where refusal becomes representable. The planning pipeline should be allowed to return either an admissible route or a structured statement that no route is currently available. In this implementation the runtime can derive that refusal from the task’s fact and capability contract rather than trusting the planner to declare itself unable to proceed.

PlanResult therefore belongs to the planning boundary even if the model-facing propose() function still emits a candidate Plan. The caller must handle both outcomes: a route that can be attempted and a task that is not currently feasible.

Detection reuses the fact vocabulary, asking a different question from the semantic check:

def refuse_if_impossible(
    plan: Plan,
    contract: GoalContract,
) -> PlanningFailure | None:
    reachable = contract.given_facts | contract.obtainable_facts
    needed = {fact for step in plan.steps for fact in step.requires}
    impossible = tuple(sorted(needed - reachable))

    if not impossible:
        return None

    return PlanningFailure(
        reason="required facts cannot be produced by any available capability",
        unsatisfiable=impossible,
    )

The semantic check asks whether this plan arranges its prerequisites coherently. Feasibility asks a broader question against the declared capability model: are the facts this route requires either already given or obtainable through capabilities the runtime knows about? A route can be structurally clean and still be infeasible under that model because it eventually depends on a fact no declared capability can establish.

That distinction changes the failure we report. If deployment_credentials are neither given nor declared obtainable, asking the planner for a differently worded deployment route is wasted work under the current capability model. The planning subsystem should return the missing prerequisite explicitly rather than pretending another sample has created an ability the runtime does not possess.

    flowchart LR
    PP["proposed plan"] --> S{"structure"}
    S -->|SchemaError| SR["malformed:<br/>cycle, unknown id,<br/>empty field"]
    S -->|ok| F{"feasibility"}
    F -->|PlanningFailure| FR["no admissible route under<br/>current capabilities:<br/>required fact is not obtainable"]
    F -->|ok| M{"semantics"}
    M -->|SemanticError| MR["well-formed but wrong:<br/>forbidden step, missing<br/>verification, unmet ordering"]
    M -->|ok| X["execute"]
  

Recognising infeasibility is a capability rather than an absence of one, and it is measured as such: the Agent Planning Benchmark tests unsolvable tasks and calibrated refusal alongside long-horizon planning and broken tools, reporting refusal calibration as a systematic weakness across the models it evaluates.[5]

A runtime that cannot represent refusal cannot exhibit it, whatever the model would have said.

7. The planner proposes, the executor performs

The planner’s output is data, not action. The executor’s input is one approved step, not the goal. Both halves are constraints, and each buys a diagnostic.

Let the planner perform side effects while planning and plan quality stops being separable from execution quality, because the plan we would grade no longer exists as an object: it has dissolved into the trace. Give the executor unconstrained authority to pursue the whole goal and it may introduce actions that appear in no approved route and are justified by no explicit planning record.

A narrow execution contract holds the line:

Execute only the step you were given.

Return:
- what was attempted
- what was observed
- whether the expected evidence was produced
- any fact a remaining step depends on that no longer holds

Suppose the approved step is to run the focused failing test and the executor finds the fixture is broken. Rewriting the fixture first may well be right. Doing it silently is the problem, because the plan the runtime still validates against no longer describes what is happening, and the discovery that would have justified a new route is buried in a tool log.

The fix is not to forbid the discovery, which would make the executor stupid on purpose. It is to route it through the observation channel execution already has:

Observation(
    ok=False,
    kind="precondition_withdrawn",
    data={"step": "reproduce", "fact": "fixture_valid"},
)

def withdrawn_facts(observation: Observation) -> set[str]:
    if observation.kind != "precondition_withdrawn":
        return set()
    return {observation.data["fact"]}

Reusing the Observation type from the action boundary makes this nearly free. Execution already had a channel for reporting information that changes what the runtime may believe about the current state. A withdrawn precondition is precisely that: a fact the plan relied on that a new observation no longer supports.

8. Let route-invalidating evidence trigger replanning

Planning happens against the facts known when the planner ran. Execution produces new facts and can also invalidate facts the route relied on. Replanning after every observation would turn ordinary execution into repeated resampling of the plan, so the trigger here is deliberately narrower:

Did this observation invalidate a fact required by the remaining route?

New facts can make additional planned work ready without requiring a new plan. Replanning is reserved for the stronger case in which the declared route can no longer be reached from the state the runtime now has.

def ready_steps(plan: Plan, state: ExecutionState) -> list[PlanStep]:
    return [
        step
        for step in _topological_order(plan)
        if step.id not in state.completed
        and set(step.depends_on) <= state.completed
        and set(step.requires) <= state.facts
    ]

def reachable_route(
    plan: Plan,
    state: ExecutionState,
) -> tuple[set[str], set[str]]:
    """Facts and steps the remaining route could reach if future steps succeed."""
    facts = set(state.facts)
    hypothetically_completed = set(state.completed)
    remaining = [
        step for step in _topological_order(plan)
        if step.id not in state.completed
    ]

    changed = True
    while changed:
        changed = False
        for step in remaining:
            if step.id in hypothetically_completed:
                continue
            if not set(step.depends_on) <= hypothetically_completed:
                continue
            if not set(step.requires) <= facts:
                continue

            hypothetically_completed.add(step.id)
            facts |= set(step.produces)
            changed = True

    return facts, hypothetically_completed

def invalidated_steps(plan: Plan, state: ExecutionState) -> tuple[PlanStep, ...]:
    _, reachable_steps = reachable_route(plan, state)
    return tuple(
        step
        for step in plan.steps
        if step.id not in state.completed
        and step.id not in reachable_steps
    )

The second is subtler than it looks, and getting it wrong is expensive. A step whose facts are not yet in state.facts is usually not broken: it may be waiting for an earlier remaining step to establish them. But simply unioning every future produces set is too optimistic, because two blocked steps can appear to satisfy each other on paper.

reachable_route() therefore computes a small fixed point. It starts from facts and completed steps already established, then repeatedly marks a remaining step hypothetically reachable only when both its declared dependencies and required facts could be satisfied. The step’s declared outputs are then added to the hypothetical fact set for the next round. A remaining step is invalidated only when this closure can no longer reach it.

None of those hypothetical outputs enter ExecutionState. They exist only inside the reachability calculation; runtime facts still require actual observations.

The calculation still reasons over declared plan facts rather than predicting whether tools will succeed. That is intentional. It asks whether the route remains structurally possible from the current state, not whether future execution is guaranteed.

Replanning is expensive and it has variance. A system that replans after every observation spends more of its budget revising intentions than acting on them, and each new plan is another sample from a distribution that has already produced one route it was willing to abandon. ReWOO reached a related conclusion from the other direction, building the plan up front to stop reasoning being repeated on every tool call.[2] This chapter keeps one thing that design gives up: observations can still falsify the remaining route.

When the check fires, the planner should be handed the run rather than the goal. A replanner given only the original goal produces something close to the original plan, because that is the input it had the first time. It needs the completed steps and the facts they produced, the step that failed, the fact withdrawn, and the constraints that still apply.

Construct a route from the current observed state, preserving completed work that remains valid.

Preservation needs an identity rule. ExecutionState.completed records step ids, so a revised plan must not reuse the id of a completed step for different work. If diagnose has already completed, a replanner cannot redefine diagnose to mean inspect a different subsystem and rely on the scheduler to notice; the scheduler will correctly treat that id as already done. Completed ids therefore belong to completed work. Materially different work needs a new id, while retained completed steps must preserve their meaning.

That makes replan quality measurable rather than a matter of impression:

def redundant_remaining_work(
    state: ExecutionState,
    revised: Plan,
) -> tuple[str, ...]:
    return tuple(sorted(
        step.id
        for step in revised.steps
        if step.id not in state.completed
        and step.produces
        and set(step.produces) <= state.facts
    ))

Keeping a completed step in the revised plan is not itself repeated work: ready_steps() will skip ids already present in state.completed. The more useful signal is a remaining step whose declared outputs are already established. Under this fact model, that is work the new route appears ready to perform even though its result is already held.

redundant_remaining_work() is therefore a diagnostic rather than a proof. A step may have a side effect not represented by its facts. But a replanner that repeatedly schedules many remaining steps whose outputs are already established is probably regenerating the route instead of repairing only what changed.

9. Attributing a failure to the planner or the executor

This is the diagnostic the whole separation was built to enable, and the reason to accept the extra moving parts.

A plan of patch → report success, executed flawlessly, can be a planning failure despite a perfect executor score. A plan of reproduce → diagnose → patch → verify that passes the planning contract and then dies while applying the patch points first to execution rather than planning.

The qualifier matters because a planning score is always relative to the contract used to grade it. A weak contract can approve a route that still fails the user’s actual goal.

End-to-end success collapses both into one number, and a team optimising that number cannot tell which component to change. That is the problem the Agent Planning Benchmark was built around: evaluations reporting only end-to-end success make it difficult to determine whether a failure originated in planning or execution.[5]

There is a fourth failure the table does not catch, and it is the one most often misdiagnosed as a model problem:

    flowchart TD
    F["run failed"] --> A{"did the plan pass<br/>the contract?"}
    A -->|no| PLAN["planner defect:<br/>grade plans offline"]
    A -->|yes| B{"did steps produce<br/>the evidence they declared?"}
    B -->|no| EXEC["executor defect:<br/>rerun against a frozen plan"]
    B -->|yes| C{"was a fact withdrawn<br/>mid-run?"}
    C -->|yes| ENV["environment moved:<br/>measure replan quality"]
    C -->|no| CON["contract too weak:<br/>the goal needed a constraint<br/>nobody wrote down"]
  

A run in which the declared plan executed correctly and all declared evidence appeared, yet the user goal still failed, is strong evidence that the planning contract or later verification specification omitted something important. That should be investigated before blaming the planner or executor, because a stronger prompt cannot recover a requirement the runtime never represented.

10. Grading a plan without executing it

To find out whether the planner improved, freeze execution out of the experiment. Build tasks whose correct constraints are known, ask for a plan, and score the plan.

The GoalContract written for validation is already the answer key:

CASES = {
    "parser-fix": GoalContract(
        required=frozenset({"reproduce", "diagnose", "patch", "verify"}),
        forbidden=frozenset({"delete_test", "skip_test"}),
        must_precede=frozenset({
            ("reproduce", "diagnose"),
            ("diagnose", "patch"),
            ("patch", "verify"),
        }),
        given_facts=frozenset({"repository_available"}),
        obtainable_facts=frozenset({
            "failure_reproduced", "error_trace",
            "root_cause", "patch_applied", "tests_pass",
        }),
    ),
}

@dataclass(frozen=True)
class PlanGrade:
    admissible: bool
    required_recall: float
    forbidden_present: tuple[str, ...]
    order_violations: tuple[tuple[str, str], ...]

def grade_plan(plan: Plan, contract: GoalContract) -> PlanGrade:
    ids = {step.id for step in plan.steps}
    required_recall = (
        len(contract.required & ids) / len(contract.required)
        if contract.required
        else 1.0
    )

    ancestors: dict[str, set[str]] = {}
    structurally_valid = False

    try:
        validate_plan_structure(plan)
        structurally_valid = True
        ancestors = _ancestors(plan)

        refusal = refuse_if_impossible(plan, contract)
        if refusal is not None:
            admissible = False
        else:
            validate_plan_semantics(plan, contract)
            admissible = True
    except (SchemaError, SemanticError):
        admissible = False

    order_violations: tuple[tuple[str, str], ...] = ()
    if structurally_valid:
        order_violations = tuple(sorted(
            (before, after)
            for before, after in contract.must_precede
            if after in ids
            and (before not in ids or before not in ancestors[after])
        ))

    return PlanGrade(
        admissible=admissible,
        required_recall=required_recall,
        forbidden_present=tuple(sorted(contract.forbidden & ids)),
        order_violations=order_violations,
    )

Writing the contract once buys a validator during the run and a grader during evaluation, which is worth more than either alone. The offline grade is aligned with properties the runtime genuinely checks — required milestones, forbidden work, ordering, and admissibility — so improvements are interpretable in terms of the deployed control logic. They are not, by themselves, proof of higher end-to-end task success.

The grade also has a shape a single score does not. A planner scoring 1.0 recall with three ordering violations has a different problem from one scoring 0.5 with none: the first knows what the work is and not how it fits together, the second is dropping steps. Formal planning benchmarks find the gap between fluent and executable output persistent,[3] which is the reason to grade structure directly rather than infer it from downstream success.

11. Testing the executor against a frozen plan

Now invert the experiment. Give the executor a plan already known to be admissible and remove its ability to choose the route at all. Then measure only whether it performed the step it was given, produced the evidence that step declared, stayed in scope, and how often it acted outside the plan.

If the system still fails under those conditions, planner work will not fix it.

That reads as obvious and is routinely violated. A great deal of prompt engineering goes into better decomposition for systems whose actual failure is an executor that cannot reliably run a command and read its output. The frozen plan is the planning equivalent of the planted-defect test used for the critic in the chapter on critique and revision: hold one component known-good so the other has nowhere to hide.

12. The ablation that tests whether planning earns its cost

Comparing a planning agent against an entirely different stack answers nothing, because too much moved at once. Add one mechanism at a time over the same task set.

Report plan grade, executor error rate, goal success, unnecessary actions, model calls and latency for every row. The informative comparisons are between adjacent rows, because each pair isolates one mechanism.

If structured plans beat prose decomposition but validation adds nothing on top, the planner was already producing well-formed graphs and the gates are insurance rather than improvement. If validation adds a great deal, the planner was generating plans that could not run, and the next thing to buy is a richer contract rather than a stronger model.

Either result gives a much more specific signal about where to spend engineering effort than aggregate success alone.

Did explicit planning improve the computation enough to justify the extra planning step?

13. Assembling the runtime

Everything above composes into one loop. Only the top-level function appears here; the types and validators are exactly as defined above, and the companion repository carries the runnable version with its tests.

from typing import Callable

def prepare_plan(plan: Plan, contract: GoalContract) -> PlanResult:
    validate_plan_structure(plan)

    refusal = refuse_if_impossible(plan, contract)
    if refusal is not None:
        return refusal

    validate_plan_semantics(plan, contract)
    return plan

def observed_facts(observation: Observation) -> set[str]:
    if not observation.ok or not isinstance(observation.data, dict):
        return set()

    return set(observation.data.get("facts", ()))


def completed_step_changes(
    old: Plan,
    new: Plan,
    completed: set[str],
) -> tuple[str, ...]:
    old_by_id = {step.id: step for step in old.steps}
    new_by_id = {step.id: step for step in new.steps}

    return tuple(sorted(
        step_id
        for step_id in completed
        if step_id in old_by_id
        and (
            step_id not in new_by_id
            or new_by_id[step_id] != old_by_id[step_id]
        )
    ))

def run_plan(
    goal: str,
    contract: GoalContract,
    propose: Callable[[str, GoalContract, ExecutionState, Plan | None], Plan],
    execute_step: Callable[[PlanStep, ExecutionState], Observation],
) -> ExecutionState:
    state = ExecutionState(facts=set(contract.given_facts))
    plan = prepare_plan(propose(goal, contract, state, None), contract)

    if isinstance(plan, PlanningFailure):
        state.outcome = f"refused: {plan.reason}"
        return state

    while ready := ready_steps(plan, state):
        step = ready[0]
        observation = execute_step(step, state)
        state.observations[step.id] = observation

        # Observations may invalidate assumptions whether or not the attempted
        # action otherwise returned success.
        state.facts -= withdrawn_facts(observation)

        if observation.ok:
            established = observed_facts(observation)
            missing = set(step.produces) - established

            if missing:
                state.outcome = (
                    f"expected_evidence_missing: {step.id}: {sorted(missing)}"
                )
                return state

            state.completed.add(step.id)
            # The environment may establish more than the plan predicted.
            # Preserve those observed facts; intention does not cap reality.
            state.facts |= established

            if not invalidated_steps(plan, state):
                continue

        elif not invalidated_steps(plan, state):
            state.outcome = f"step_failed: {step.id}"
            return state

        revised = prepare_plan(
            propose(goal, contract, state, plan),
            contract,
        )

        if isinstance(revised, PlanningFailure):
            state.outcome = f"replanning_refused: {revised.reason}"
            return state

        if revised == plan:
            state.outcome = "replanning_produced_no_new_route"
            return state

        changed_completed = completed_step_changes(
            plan,
            revised,
            state.completed,
        )
        if changed_completed:
            state.outcome = (
                "replanning_changed_completed_work: "
                f"{list(changed_completed)}"
            )
            return state

        plan = revised

    # This is completion of the declared planning milestones, not verified
    # success of the user's goal. Final goal verification belongs elsewhere.
    state.outcome = (
        "plan_complete"
        if contract.required <= state.completed
        else "blocked"
    )
    return state

Read the loop for what it never does. It does not invent the next route inside the scheduler; it computes what is permitted to run next from dependencies and established facts. The planner is invoked only when a route must be proposed or repaired. execute_step may itself use deterministic tools or model-assisted capabilities, but it receives one approved step rather than authority over the plan.

The other important change is easy to miss: a successful return code does not automatically promote every fact listed in step.produces into execution state. The observation must explicitly establish those expected facts. If required evidence is missing, the step does not complete. If an observation establishes additional facts the plan did not predict, the runtime preserves them rather than discarding them. Planner predictions constrain expectations; they do not overwrite what execution actually reported.

The final line is deliberately named plan_complete, not success. Running out of ready steps is ambiguous between exhausting the declared route and becoming blocked, so the planning contract distinguishes those cases. Whether the user’s goal was actually achieved still belongs to the external verification mechanism built later in the book.

What the loop lacks is a reason to stop that is not “nothing is ready”. It has no budget, no notion of progress, and no defence against a step that fails, triggers a replan differing cosmetically, and arrives back in the same position one model call poorer. The revised == plan guard catches the exact repeat and nothing subtler.

Those are not planning questions, and bolting them on here would bury termination logic inside the component whose job is routing.

14. What the representation bought

Nothing here made the model better at planning. The planner is the same model that would otherwise have decided each action as it arrived. What changed is that its output stopped being control flow and became an object.

Once intended work is an object, four things become possible that were not explicit before. It can be rejected before tool execution or side effects, because a cycle or a missing required milestone is visible in the data. It can be graded without being executed, separating whether the route was sound from whether the tools worked. It can be compared against what actually happened, because the intention survived the run instead of being overwritten by it. And the planning boundary can represent refusal explicitly instead of forcing every request into an action-shaped answer.

The cost is not small: another model call, another latency budget, another artefact that can be wrong, and a contract someone must write and keep current. Formal planning studies show that fluent model output can still fail executability checks,[3] while LLM-Modulo work argues for combining generated proposals with external model-based verification.[4] This chapter arrives at the same engineering shape from first principles: generation proposes; runtime checks; execution produces evidence.

The planner proposes a route. The runtime decides whether the route is admissible. The environment decides whether it survived.

Research roots

This chapter is an engineering reconstruction rather than a survey, and the references are selective: each is cited because it settles a specific question the design had to answer.

1. Wang et al. — Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models (ACL 2023). Splits multi-step reasoning into devising a plan and then carrying out the subtasks, providing evidence on its evaluated reasoning tasks that explicit decomposition can reduce missing-step errors relative to Zero-shot-CoT. https://arxiv.org/abs/2305.04091
2. Xu et al. — ReWOO: Decoupling Reasoning from Observations for Efficient Augmented Language Models (2023). Builds the plan before tool observations to stop reasoning being repeated on every call, cited here for the demonstration that planning and execution can be separate modules rather than one interleaved trace. https://arxiv.org/abs/2305.18323
3. Valmeekam et al. — On the Planning Abilities of Large Language Models: A Critical Investigation (NeurIPS 2023). Tests LLMs on formal planning domains and separates plausible-looking output from executable valid plans, which is the empirical basis for validating a generated plan rather than trusting it. https://arxiv.org/abs/2305.15771
4. Kambhampati et al. — LLMs Can’t Plan, But Can Help Planning in LLM-Modulo Frameworks (ICML 2024). Argues for compound systems in which generated candidate plans meet external model-based critics or verifiers; the structural and semantic gates built here are a small instance of that arrangement. https://arxiv.org/abs/2402.01817
5. Sun et al. — Agent Planning Benchmark: A Diagnostic Framework for Planning Capabilities in LLM Agents (2026). Diagnoses planning as an upstream capability separately from execution across 4,209 multimodal cases in 22 domains, including broken-tool and unsolvable-task settings, and reports long-horizon planning and calibrated refusal as systematic weaknesses. https://arxiv.org/abs/2606.04874

Next: Runtime State, Progress, and Termination

The runtime now records enough execution state to route work: completed steps, observations and established facts. What it does not yet represent is its own progress through the computation.

It cannot say whether ten actions were spent to accomplish what one should have done, whether the last three produced anything genuinely new, whether it is returning to the same state under different wording, or whether the remaining budget justifies another attempt. The loop above can fail a step, replan, and arrive back at essentially the same position one model call poorer; the equality check catches only an identical replacement plan.

Those are no longer planning questions. They are questions about progress, budgets, repetition and termination.