Replanning When Agent Execution Fails: Dynamic Plan Revision

Why Perfect Plans Fail in Execution

A plan generated before execution is based on assumptions about the world: which tools will be available, what data sources will return, how long steps will take, and whether the task definition matches what the user actually needs. Every one of these assumptions can be violated during execution. The tool you planned to use may be unavailable. The data source may return empty results. The user may clarify that they wanted something slightly different halfway through.

The agents that handle this gracefully aren't the ones that get the plan perfect upfront, that's impossible with realistic uncertainty. They're the ones that detect plan violations quickly, assess their impact, and revise the plan with minimal wasted work. This requires a fundamentally different architecture than a static plan-then-execute pipeline.

The Static Plan Fallacy

Many agent frameworks treat planning and execution as two separate, sequential phases: first generate a complete plan, then execute it step by step. This works when the environment is fully predictable. In production, with real tools and real data, it fails frequently because each step of execution reveals new information that the plan didn't account for. Dynamic replanning treats planning as an ongoing activity throughout execution, not a one-time upfront phase.

Detecting Replanning Triggers

Trigger Type 1, Tool and Resource Failures

When a critical tool fails permanently, the plan that depended on it is no longer executable. The agent must assess: is there an alternative tool that can fulfill the same role? If yes, the plan can be locally repaired, substitute the alternative tool and continue. If no alternative exists, a deeper replan is required that either changes the approach entirely or accepts that this aspect of the task cannot be completed.

Trigger Type 2, Invalidated Assumptions

Plans are built on assumptions about the state of the world. When an execution step reveals that a key assumption was wrong, all subsequent steps that depend on that assumption must be revised. Tracking which planning assumptions each step depends on enables targeted replanning, only the steps that depended on the invalidated assumption need to change.

Trigger Type 3, Budget Violations

If the agent is tracking towards exceeding its time or token budget, it must replan to scope down. This is a proactive trigger, it fires before the budget is actually exceeded, giving the agent time to gracefully reduce scope rather than abruptly running out of resources mid-task.

Trigger Type 4, Goal Clarification

Mid-task goal clarification from the user represents the most fundamental trigger. When the user says 'actually, I need this in a different format' or 'focus on the cost aspects, not the technical details', the entire plan may need revision. Goal change triggers should be handled with particular care since they represent user intent rather than system failure.

Plan Revision Strategies

Strategy 1, Local Repair (Lowest Cost)

Local repair fixes only the failed step while keeping all other steps intact. Best when the failure is isolated to a specific step that can be fixed independently. Examples: substituting an alternative tool, correcting a parameter that was wrong, adjusting the query to return the expected data. Cost: minimal, only the failed step is re-executed.

Strategy 2, Partial Replan

Partial replanning keeps all completed steps and regenerates the plan from the failure point forward. Best when the failure invalidates only the remaining steps, not the completed ones. The agent takes the current state (all completed step outputs) and asks: given what I've done so far and what I've discovered, what's the best plan to complete the remaining objectives?

Strategy 3, Goal Decomposition

When a step is too complex to execute as specified, decompose it into smaller steps rather than abandoning it. Best when the step's underlying goal is still achievable but the original approach was too direct. Example: a step 'analyze all 500 customer records' fails due to context overflow → decompose into 'analyze records in batches of 50, then synthesize'.

Strategy 4, Full Replan (Highest Cost)

Full replanning discards the current plan entirely and generates a new one from the current state. Reserved for cases where a core assumption underlying the entire plan was wrong. The new plan incorporates all the information gathered during the failed execution as context.

The Planning-Execution-Monitoring Loop

Implementing the Monitor

The monitor runs after each step and evaluates the output against three criteria: correctness (does the output match expectations?), progress (is the overall task advancing?), and plan validity (are the assumptions underlying upcoming steps still valid?). When any criterion fails, the monitor classifies the failure type and selects the appropriate revision strategy.

from enum import Enum, auto
from dataclasses import dataclass

class ReplanTrigger(Enum):
    TOOL_FAILURE = auto()
    ASSUMPTION_INVALIDATED = auto()
    BUDGET_EXCEEDED = auto()
    GOAL_SHIFT = auto()
    QUALITY_GATE_FAILED = auto()

@dataclass
class MonitorResult:
    should_replan: bool
    trigger: ReplanTrigger | None
    revision_strategy: str  # local_repair/partial/decompose/full
    context: str  # explanation for the replanner

async def monitor_step_output(
    step: dict,
    output: object,
    plan: list[dict],
    budget: dict,
    llm_judge,
) -> MonitorResult:
    # 1. Check budget
    if budget["tokens_used"] > budget["tokens_limit"] * 0.85:
        return MonitorResult(
            should_replan=True,
            trigger=ReplanTrigger.BUDGET_EXCEEDED,
            revision_strategy="partial",
            context=f"Token budget {budget['tokens_used']}/{budget['tokens_limit']}, scope down remaining plan",
        )

    # 2. Check step quality via LLM judge
    score = await llm_judge(step["success_criteria"], output)
    if score < 3:
        return MonitorResult(
            should_replan=True,
            trigger=ReplanTrigger.QUALITY_GATE_FAILED,
            revision_strategy="local_repair",
            context=f"Step quality score {score}/5, retry with corrected approach",
        )

    # 3. Check assumption validity using LLM
    assumption_check = await llm_judge(
        f"Do these observations invalidate any upcoming plan steps? "
        f"Observations: {output}\nUpcoming steps: {plan[step['index']+1:]}",
        None,
    )
    if assumption_check < 4:
        return MonitorResult(
            should_replan=True,
            trigger=ReplanTrigger.ASSUMPTION_INVALIDATED,
            revision_strategy="partial",
            context=f"Observations contradict assumptions in upcoming steps",
        )

    return MonitorResult(should_replan=False, trigger=None,
                         revision_strategy="none", context="")

Preserving Completed Work During Replan

Replanning must preserve completed work. If steps 1–4 have produced valuable outputs before step 5 triggers a replan, those outputs should be incorporated into the new plan, not discarded.

State Preservation Protocol

• Serialize completed step outputs before replanning: Package all completed results in a structured format that the replanner can read and reference.
• Inform the replanner of completed work: Include completed step summaries in the replanning prompt. 'Steps 1–4 are complete. Step 1 found X, step 2 concluded Y, step 3 produced Z.'
• Mark completed steps as untouchable: The replanner must not re-schedule completed steps. Only pending and failed steps are in scope for revision.
• Carry forward key findings: Explicitly extract the most important conclusions from completed steps and include them as context for the new plan.

Scoping the Replan: Local vs Global

The scope of a replan should be the minimum necessary to address the failure. Replanning too broadly wastes the value of correctly-completed work. Replanning too narrowly fails to address root causes that will cause future failures.

Impact Analysis Before Replanning

Before deciding the replan scope, perform an impact analysis: which downstream steps depend on the failed step? Which assumptions do those steps make that are now known to be wrong? Only steps in the transitive dependency closure of the failure point need to be replanned. Steps outside this closure remain valid.

Tracking and Validating Planning Assumptions

Making planning assumptions explicit enables targeted replanning. When you know what assumptions each step depends on, validating those assumptions during execution tells you immediately which steps need revision when reality diverges from the plan.

Assumption Documentation in Plans

For each step in the plan, document: 'This step assumes [X]. If X is not true, this step should be replaced with [alternative].' This assumption-alternative pair makes replanning mechanical for common failure scenarios rather than requiring the agent to reason from scratch each time.

Escalation Criteria: When Replanning Cannot Help

Not every failure can be resolved by replanning. When replanning itself would fail, because the task is fundamentally impossible with available tools, the goal is contradictory, or resources are exhausted, the agent must escalate rather than replanning repeatedly.

Escalation Triggers

• Maximum replan count reached: If the agent has already replanned N times (typically 3), further replanning has diminishing returns. Escalate to a human or return a partial result.
• No viable alternative exists: All available tools have been tried and failed. The task requires a capability the agent doesn't have.
• Contradictory constraints: The task specification contains constraints that cannot be simultaneously satisfied. Escalate to clarify with the user.
• Persistent quality failures: Multiple replans have produced outputs below quality threshold. The root cause may be in the task definition or the model's capabilities, not the plan.

Managing Replan Cost and Frequency

Frequent replanning is expensive, each replan requires LLM calls to generate the new plan, evaluate its quality, and potentially update downstream steps. Implement cost controls to prevent runaway replanning.

Replan Budget

• Maximum replans per task: Hard limit of 3–5 replans before escalating. Most tasks should complete with 0–1 replans; frequent replanning indicates a structural problem.
• Minimum quality improvement threshold: Only replan if the revised plan is estimated to score significantly better than the current plan. Don't replan for marginal improvements.
• Replan cost tracking: Track token cost per replan event. Replanning should cost less than re-running all remaining steps from scratch, if it doesn't, the replan scope is too large.

Testing Replanning Logic

Replanning logic is complex and its failure modes are subtle, it's the part of the agent most likely to have untested edge cases. Testing must cover each trigger type, each revision strategy, and the interactions between them.

Replanning Test Scenarios

• Single trigger, local repair: Inject a tool failure at step N. Verify the agent substitutes the correct alternative tool and continues without replanning the full plan.
• Single trigger, partial replan: Inject an assumption invalidation at step N. Verify the agent regenerates only the steps downstream of N, preserving steps 1 through N-1.
• Multiple triggers: Inject two successive failures. Verify the agent handles the second trigger correctly given the already-revised plan from the first trigger.
• Escalation threshold test: Inject failures that trigger the maximum replan count. Verify the agent escalates cleanly rather than triggering a Nth replan.
• Budget trigger: Simulate token consumption that approaches the budget threshold. Verify the agent proactively scopes down the plan before the budget is fully exhausted.