Planning and Replanning Loops: Plan-and-Execute, Progress State, and Plan Repair

An agent that plans beautifully and then executes a stale plan into a wall is not a planning failure. It is a state failure.

Plan-and-execute agents are easy to demo and hard to operate. The demo works because the world holds still for thirty seconds. The production task does not. A file moves, an API returns a different schema, a user changes the acceptance criteria halfway through, a dependency you assumed was installed is not. The plan was a prediction about all of that, and the prediction just got falsified.

The failure has two directions, and they look nothing alike. One agent keeps executing a plan whose preconditions no longer hold — stale commitment. The other never executes at all: it re-reads project state, re-emits a design, re-plans across turns, and burns the token budget without producing a single artifact. Both are planning and replanning loop failures, and both come from the same missing piece: the agent has no durable representation of what it has actually accomplished, so it cannot tell the difference between "the plan is wrong" and "I should plan again."

The invariant this article builds toward is simple to state and hard to implement: completed work is the asset; the plan is a replaceable projection over that asset. Everything below is about making that sentence true in code.

Why a Plan Is a Bet, Not a Schedule

The classic two-component architecture is well established. A planner prompts a model to generate a multi-step plan for a large task. One or more executors accept the user query plus a single step and invoke tools to complete it. When execution finishes, the agent is re-invoked with a re-planning prompt that decides whether to respond with a final answer or generate a follow-up plan. That is the whole loop. It is a bet with two legs: a bet about the world (these preconditions will hold) and a bet about the agent itself (these steps are within my capability).

Both legs can be falsified mid-execution. When they are, the naive loop has no vocabulary for the event. It only knows "step failed" or "step succeeded," so its only repair move is to call the planner again with the full task — which is exactly how you get planning thrash.

I have watched this failure in the wild. An agent with a design-and-plan skill installed will complete the design phase, write a plan, and then — instead of transitioning to implement and verify — re-invoke the brainstorming skill, or emit "Let me review the current state," or re-read the project files and produce an updated design. This repeats across several user turns, consuming significant budget, until a human intervenes. The model is not confused about the task. It is confused about which phase it is in, because phase is not a piece of explicit state. It is inferred from context, and context is ambiguous.

Two distinctions do most of the diagnostic work here:

• Plan validity asks whether the plan still achieves the goal. A user changing the acceptance criteria breaks validity.
• Plan feasibility asks whether the remaining steps can still be executed given current state. A missing dependency or a moved file breaks feasibility, not validity.

A plan can be valid but infeasible, or feasible but no longer valid. The repair you need is different in each case, and if your loop cannot tell them apart, it will reach for the most expensive repair — full re-plan — every time.

A plan is a prediction with a short half-life. Treat it as a cache of decisions, not as a contract you are obligated to honor.

The Plan Representation: Steps, Dependencies, and Preconditions

Repair quality is bounded by plan representation. This is the constraint most teams hit second, right after they discover they need repair at all.

The cheapest useful representation is a flat step list with variable references. A planner emits interleaved reasoning and E# lines, where later steps reference earlier outputs by name — E2: LLM[Quarterback for the first team of #E1]. The worker substitutes #E1 with its result at call time, so the plan executes without re-planning between steps. This is genuinely effective: each task carries only the context it needs, and the planner is not consulted after every action. But a flat list encodes no dependency structure that repair logic can reason over. When step 4 breaks, you know step 4 broke. You do not know which other steps depended on it.

A DAG representation carries more. Each task holds a tool, arguments, and a list of dependencies. A task-fetching unit schedules tasks as soon as their dependencies are satisfied, which lets independent branches run in parallel — a real runtime win, not a cosmetic one. More importantly for our purposes, a DAG lets repair target a subgraph instead of the whole plan.

The hooks that make surgical repair possible are preconditions and expected effects per step. A precondition is a predicate over world state that must hold before the step runs. An expected effect is what the step promises to change. When a precondition stops holding, you have not just detected a failure — you have identified exactly which steps are invalidated, because invalidation propagates along the dependency edges from the first broken precondition.

Two more fields earn their schema cost:

Field	Values	Why repair needs it
Idempotency	idempotent / not	Whether a step can be safely re-run after repair
Side-effect class	read-only / mutating	Whether re-running duplicates an external effect

A read-only search can be re-run freely. A payment, a file write, or a sent message cannot. If your plan schema does not distinguish these, your repair logic will either re-run mutating steps and corrupt state, or refuse to re-run anything and collapse to full replan. Neither is acceptable.

The tradeoff is honest: richer plan structure costs planner tokens and schema discipline. The payoff is that repair becomes a local operation. I will take that trade every time the task is long enough that discarding work is expensive.

Progress State: What Survives a Replan

This is the section that matters most, because it is the one most implementations get wrong.

Progress state should record completed steps with their verified outputs, not a step index. An index is meaningless the moment the plan changes shape — and the plan is going to change shape. If your progress tracker says "we are on step 5 of 9" and repair rewrites the plan into 7 steps, you have lost the thread entirely.

Separate three layers, and be ruthless about which one is disposable:

Layer	Contents	Survives replan?
Goal state	What success means; acceptance criteria	Yes — changes only on intent change
World state	Observed facts, artifacts produced, tool outputs	Yes — this is ground truth
Plan state	The current intended path	No — disposable by design

Only plan state is disposable. Goal state and world state are the durable substrate. When you replan, you regenerate plan state from goal state plus world state, and you reuse every completed step whose effects are still present in world state.

Artifacts must be first-class. A file path, a tool output, an intermediate value that later steps reference — each needs an address independent of the step that produced it. If #E1 resolves to "the output of step 1," then rewriting step 1 destroys the reference. If it resolves to a named artifact in world state, rewriting step 1 leaves the artifact intact and the reference valid. This is the difference between a plan you can repair and a plan you can only replace.

Invalidation is a marking operation, not a deletion. When a precondition breaks, mark affected steps invalid. Do not delete them. Their outputs may still be reusable even if the step must be re-run, and the marking is the audit trail that explains why the agent changed course.

Progress must be verifiable, not self-reported. A step the agent claims is done but whose effect is unobserved is a latent replan trigger waiting to fire. If the agent says "I created the config file" and nothing checked that the file exists, you have a step that will be re-executed later, possibly with different arguments, possibly against a world that already changed. Verify the effect or do not mark the step complete.

This builds directly on the loop's state/observation contract. The question here is narrower: which parts of that state must persist across plan revisions? Goal and world state persist. Plan state does not.

A Concrete Invalidation Trace

Abstract propagation rules hide the hard cases. Walk one small DAG through a mid-run event.

The plan: fetch a config file, parse it into a settings object, then run two independent consumers — one that provisions a database, one that generates a report. The report depends on the parsed settings; the database depends on the parsed settings and on a schema artifact fetched separately.

S1 fetch_config      -> artifact: config_raw
S2 parse_config      -> artifact: settings   (depends: config_raw)
S3 fetch_schema      -> artifact: schema     (independent)
S4 provision_db      -> artifact: db_handle  (depends: settings, schema)
S5 generate_report   -> artifact: report     (depends: settings)

Execution completes S1 through S3. Then S4 fails: the schema artifact is missing a required table, so the precondition schema.has_table("users") is false. That is a precondition violation, not a task failure — S4 never ran to completion.

Marking proceeds along dependency edges from the broken predicate:

Step	Status before	Status after	Artifact	Reusable?
S1	complete	complete	config_raw	Yes — untouched
S2	complete	complete	settings	Yes — precondition still holds
S3	complete	complete	schema	Yes — but flagged as the cause
S4	pending	invalid	db_handle	No — precondition false
S5	pending	pending	report	Yes — depends only on settings

The first invalidated predicate is schema.has_table("users"). It invalidates S4. It does not invalidate S5, because S5 does not depend on the schema. A naive "invalidate everything downstream of the failure" rule would wrongly kill S5 and discard a report that could still be generated. This is the case that separates a real dependency graph from a linear step list: S5 is downstream in execution order but not in the dependency graph.

Repair here is a subgraph rewrite of S4 alone. The planner re-fetches the schema, re-checks the precondition, and re-runs S4. S1, S2, S3, and S5 are untouched. The repaired S4 consumes the same settings artifact reference it always did, so nothing upstream needs to change.

The preservation rule that makes this work: reuse an artifact only when its postcondition is verified against the current world-state version or the assumptions it was produced under. S2's settings artifact is reusable because nothing in the event touched config_raw or the parse assumptions. If the event had been "the config file changed on disk," S1 and S2 would both be invalid, and S5 would fall with them — because settings would no longer be trustworthy.

S1 fetches config, S2 parses settings, S3 fetches schema, S4 provisions the database from settings and schema, and S5 generates a report from settings.

Repair Strategies: Local Patch, Subgraph Rewrite, Full Replan

Repair scope is a decision ladder, and the cost of climbing it is real. The general principle is incremental repair: reuse the valid portions of the previous plan and repair only the invalid parts, rather than planning from scratch on every change. Brute-force replanning — planning from scratch whenever the environment changes — is often impractical precisely because the computational cost scales with the whole task rather than the changed region.

The three rungs:

Local patch. Replace or re-parameterize a single step when its precondition changed but the surrounding plan is still valid. Cheapest, narrowest blast radius. If a search step returned a different result and the next step just needs the new value, patch the argument and move on. Do not call the planner.

Subgraph rewrite. Recompute the dependency subtree rooted at the first invalidated step, reusing all completed work outside that subtree. This is the workhorse. Most mid-execution constraint changes invalidate a region, not the whole plan, and a subgraph rewrite preserves everything upstream and everything on independent branches.

Full replan. Discard the plan and regenerate from goal state plus current progress state. Justified when the goal itself changed, or when invalidation is so broad that the surviving plan is a fragment. This is the expensive rung, and it should be a deliberate choice, not the default.

The trigger determines the rung. Distinguish at least three event classes:

• Task failure — a step ran and did not produce its expected effect. Usually local patch or subgraph rewrite.
• Precondition violation — a step's precondition no longer holds. Invalidation propagates along dependencies; usually subgraph rewrite.
• User intent change — the goal moved. This is the one case where full replan is the right answer, because goal state changed and every plan derived from the old goal is suspect.

The cost model is a straight trade: repair scope buys planner tokens and latency against the risk of carrying forward a subtly wrong assumption. A local patch is cheap and fast but assumes the surrounding plan is still sound. A full replan is expensive but discards every stale assumption. Pick the rung that matches the trigger, and log which rung you picked so you can audit the choice later.

The Repair Loop as Pseudocode

The decision ladder is easy to agree with and easy to get wrong in code. The failure mode is calling the planner when execution should continue. Here is the control flow, framework-neutral:

def run_loop(goal, world, plan, budget):
    while not goal.satisfied(world):
        if budget.exhausted():
            return escalate("budget_exhausted")

        step = plan.next_ready_step(world)

        if step is None:
            # No step is ready: either the plan is complete but the goal
            # is unmet, or dependencies are blocked.
            trigger = classify_blockage(plan, world)
            plan = repair(goal, world, plan, trigger, budget)
            continue

        if not step.preconditions_hold(world):
            # Precondition violation: mark, do not delete.
            invalidated = mark_invalid(plan, step, world)
            trigger = Trigger.PRECONDITION_VIOLATION
            plan = repair(goal, world, plan, trigger, budget,
                          invalidated=invalidated)
            continue

        result = execute(step, world)

        if not verify(step.expected_effect, result, world):
            trigger = Trigger.TASK_FAILURE
            plan = repair(goal, world, plan, trigger, budget,
                          failed_step=step)
            continue

        # Verified effect: commit the artifact and advance progress.
        world = world.commit(step.artifact, result)
        plan = plan.mark_complete(step)
        budget.record_progress(step)   # progress is artifact-based

    return goal.finalize(world)


def repair(goal, world, plan, trigger, budget, **ctx):
    budget.record_repair(trigger)

    if trigger == Trigger.USER_INTENT_CHANGE:
        return replan_from_scratch(goal, world)   # full replan

    scope = choose_scope(plan, world, trigger, ctx)

    if scope == Scope.LOCAL:
        return patch_step(plan, ctx)              # no planner call
    if scope == Scope.SUBGRAPH:
        return rewrite_subgraph(plan, world, ctx) # planner on subgraph only

    return replan_from_scratch(goal, world)

Two lines carry the whole design. budget.record_progress(step) is called only after a verified effect, so a replan that produces no new artifact does not reset the no-progress counter — that is what terminates thrash. And repair returns to the top of the loop, where the next iteration either executes a ready step or repairs again; the planner is never invoked speculatively between steps.

The current loop executes a step, verifies its effect, commits the artifact, calls the planner unconditionally, and only then looks for the next ready step.

Termination and Budgets for the Repair Loop

The repair loop can become the planning-thrash failure mode. Bound it explicitly.

Termination conditions must be enumerated, not implied:

• Goal satisfied.
• Goal unreachable (a precondition that cannot be satisfied by any available action).
• Budget exhausted.
• Repair attempted N times without progress.

That last one is the important one, and it requires a definition of progress. Progress is measured against artifacts, not against plan revisions. A replan that produces no new completed step is a no-progress iteration. It does not matter how different the new plan looks. If world state did not advance, the loop spun.

Budget accounting should cover planner calls, executor calls, wall-clock, and tool cost separately, because thrash shows up disproportionately in planner calls. An agent that is re-planning instead of executing will look normal on executor spend and pathological on planner spend. If you only track a single total, you will not see it.

Make phase explicit state. An agent that has to infer whether it is in planning or execution from context will eventually infer wrong, and the self-reinforcing loop that follows is expensive.

When the repair budget is exhausted, escalate. Hand off to a human or a fallback strategy. The agent should be able to request help — that is a termination condition, not a failure. An agent that loops forever because it has no way to say "I am stuck" is worse than one that stops and asks.

Observability: Making Repair Decisions Auditable

Repair behavior is invisible unless you log it. The trace you want, per repair event:

• The trigger (task failure, precondition violation, intent change).
• The invalidated subgraph.
• The steps reused.
• The resulting plan delta.

That trace is what explains why the agent changed course. Without it, debugging a replanning loop is archaeology.

Track two aggregate metrics per task class: repair rate (repairs per task) and repair depth (how much of the plan gets rewritten per repair). A high repair rate on tasks that should be stable usually means the planner is under-specified, not that the world is chaotic. A high repair depth on every event means your invalidation is too aggressive — you are marking more steps invalid than the change actually affects.

Distinguish replanning caused by genuine environment change from replanning caused by the agent's own uncertainty or a missing observation. These look identical in the trace unless you tag them, and they call for opposite fixes: the first needs better repair logic, the second needs better observation.

Turning the Mutation Test into Assertions

Replaying a recorded trajectory with a mutated constraint is the right experiment, but "did it repair locally?" is too coarse to attribute a failure. Make it a small matrix of trace assertions, each tied to one claim about your representation:

Assertion	What it proves	Failure attribution
Unchanged completed artifact is reused	Artifact identity is stable across replan	Representation — references are step-bound
Invalidated artifact is not reused	Invalidation actually propagates	Repair logic — marking is too weak
Independent branch stays available	Dependency graph is real, not linear	Representation — flat step list
Mutating action is not duplicated	Idempotency/side-effect fields are honored	Executor — re-run guard missing
Repair budget terminates thrash	Progress is artifact-based	Loop control — progress is plan-based

Run the mutation, then read the trace against this table. The first failing row tells you which layer to fix. If the agent started over, the fix is almost never a better planner prompt.

When Not to Build a Replanning Loop

Replanning machinery is expensive, and it is overkill more often than people admit.

If the environment is static and the plan is short, a single plan-and-execute pass with a verification step beats a repair loop. You get the cost savings and the speed without maintaining invalidation logic.

If constraints change rarely, full replan on change is simpler to reason about and debug than incremental repair. Incremental repair earns its complexity only when replans are frequent or expensive. Do the arithmetic before you build the ladder.

If the task is genuinely open-ended with no stable goal, the bottleneck is goal specification, not plan repair. Adding repair machinery to an undefined objective produces a well-engineered agent that confidently pursues nothing.

If the agent cannot verify step outcomes, repair decisions are guesses. Invest in observation quality before investing in repair logic. A repair loop built on unverified progress is a machine for confidently redoing work.

The rule of thumb: build repair when the cost of discarding completed work exceeds the cost of maintaining progress state and invalidation logic. Below that line, you are paying for machinery you will not use.

The Next Move

Instrument one existing agent loop to emit a repair trace — trigger, invalidated subgraph, reused steps, plan delta — then run it against a task where you deliberately mutate a constraint mid-execution. Change a file path, revoke a permission, or rewrite the acceptance criteria after the plan is generated.

Then read the trace against the assertion table above. Which row failed first? That row names the layer to fix: artifact identity, invalidation propagation, dependency structure, executor guards, or loop control.

That answer tells you whether your plan representation carries enough structure to support surgical repair, and whether your progress state is durable enough to survive a plan that changed shape. If the agent started over, the fix is almost never a better planner prompt. It is a better representation of what the agent already accomplished.