[KongchangAI]
· 2 min read· 1,245 words

When Should AI Agents Repair, Replan, or Abandon? Threshold Theory Gives the Optimal Strategy

When Should AI Agents Repair, Replan, or Abandon? Threshold Theory Gives the Optimal Strategy

The paper derives a threshold theory for optimal repair/replan decisions when AI agent plans fail, revealing the decisive role of plan structure and the price of stability.

The paper establishes a theoretical framework for strategy selection after plan failure in AI agent execution. It models interruptions as damage to a plan's causal support and proves the optimal strategy is a threshold function of effective damage depth: repair shallow damage, replan deep damage, and abandon when too costly. Damage depth depends on the plan dependency graph's structure, with more parallel plans favoring repair. The paper introduces the price of stability to explain how plan commitment is maintained as replanning costs approach zero, and analyzes commitment lag and patch debt under repeated interruptions. Numerical checking found zero violations across 1.6 million evaluations, and the regime diagram reproduces the benchmark's strategy switching.

Introduction: The Planning Dilemma of AI Agents

When an AI agent discovers mid-task that its plan has failed—an action failed or a tool was withdrawn—deployed systems typically rely on retry loops or conventions like "always replan." However, a recent benchmark found that no fixed strategy dominates. This paper theoretically derives the optimal strategy, providing a threshold-theory framework for the agent's plan-commitment problem.

AI agent planning strategy diagram

Core Model: The Trade-off Between Repair, Replan, and Abandon

The paper models an interruption as damage to the causal support of some actions in the plan. Under this model:

  • Repair is a partial reset that preserves the plan structure and only re-validates the damaged actions.
  • Replan is a full reset that generates a new plan from scratch.
  • Changing the plan is costly because others have already conditioned on the original plan.

The optimal strategy takes the form of a threshold on effective damage depth: shallow damage calls for repair, deep damage calls for replanning, and when even a fresh plan is not worth its cost, the goal is abandoned.

Damage depth depends on plan structure

The paper derives that, in expectation, a single failed action forces 1+R(G)/n actions to be re-validated, where R(G) counts the number of action pairs connected by dependency paths. To first order, the raw damage threshold for switching to replanning in a fully serial plan is about one w-th of that for a plan with w parallel chains. This means that the more parallel the plan structure, the more the agent favors repair over replanning.

Causal support is the key concept for understanding this model. In a planning system, an action is executed because it is expected to achieve some subgoal, which in turn serves a higher-level goal. This "action–subgoal–goal" dependency chain constitutes the action's causal support. When an action fails, it does not just invalidate itself; it also removes the reason for existence of all downstream actions that depend on it. Damage depth is therefore not the number of failed actions but the size of the set of actions affected along dependency paths. The paper characterizes plans with a graph structure: nodes are actions, edges represent causal dependencies, and the size of the "downstream closure" of a failed action is the effective damage depth. This formalization allows the trade-off between repair and replanning to be computed precisely rather than relying on heuristic rules.

Price of Stability: When to Keep a Worse Repaired Plan

The paper proposes a closed-form price-of-stability threshold for deciding when to keep a worse repaired plan rather than a better fresh plan. As language-model planners drive the cost of replanning toward zero, the price of stability becomes the only force maintaining plan commitment.

This finding has direct implications for practical system design: when replanning is nearly free, agents may discard existing plans too frequently, leading to unstable behavior. The price of stability provides a theoretical "stickiness" mechanism that prevents agents from completely restructuring their plans under minor disturbances.

Price of stability borrows the term from algorithmic game theory, but its meaning here differs: it measures the loss in plan quality that one is willing to accept in order to maintain plan commitment. Specifically, suppose the repaired plan has expected payoff Δ lower than a fresh replan, but replanning itself has cost c and disrupts coordination expectations already established by other agents. The price of stability is defined as the upper bound on Δ for which repair still beats replanning. When large language models push the replanning cost c very low, this upper bound approaches zero, meaning any quality disadvantage triggers replanning. The price of stability is thus essentially a "commitment premium"—the system needs to explicitly introduce additional mechanisms (such as switching penalties or coordination locks) to replace the natural friction that has disappeared.

Commitment Lag and Patch Debt

Under repeated interruptions, revision friction makes commitment lag optimal: the agent continues to execute a plan it would never choose in a fresh state. Each repair increases "patch debt" until the debt exceeds the cost advantage of repair, at which point the agent rebuilds the plan.

This explains behavior observed in real systems: an agent may maintain a gradually degrading plan for a long time because the short-term cost of local repair is lower than global replanning. But once the debt accumulates sufficiently, rebuilding becomes unavoidable.

Commitment lag describes the systematic deviation between the plan an agent is currently executing and the plan it would choose absent historical constraints. In repeated interruption scenarios, each repair makes local adjustments based on the previous version of the plan, which is itself the product of past repairs. Because repair costs less than replanning, the agent evolves along a "path-dependent" trajectory that gradually drifts away from the optimal choice in a fresh state. Patch debt is the cumulative measure of this deviation: the local suboptimality introduced by each repair is recorded as debt, and the interest on the debt is the risk that future repairs will have to handle more inconsistencies. When the marginal cost of debt exceeds the fixed cost of replanning, rebuilding becomes the rational choice. This mechanism is highly isomorphic to technical debt in software engineering.

The Value of Diagnosis and the Conditions for "Always Replan"

The paper also gives a diagnostic-value result showing when measuring damage depth is worth its computational cost. It also proves that "always replan" is optimal when damage is predictably deep and replanning is the better fallback.

This conclusion reconciles the diversity of strategies observed in benchmarks—different strategies are each optimal under different damage distributions.

Numerical Validation and Benchmark Reproduction

The paper tests each proposition with an independently implemented numerical checker, finding zero violations across 1.6 million static model evaluations. The model's regime diagram qualitatively reproduces the strategy-switching phenomena in the benchmark.

Numerical validation results diagram

Practical Implications

For engineers building AI agent systems, the theory offers several actionable principles:

  1. Set repair/replan thresholds according to plan structure: highly parallel plans should lean toward repair.
  2. Account explicitly for the price of stability: when replanning costs decrease, additional mechanisms are needed to maintain plan commitment.
  3. Monitor patch debt: track the accumulated cost of repairs and trigger rebuilding at the appropriate time.
  4. Evaluate diagnostic cost: measuring damage depth is not always worthwhile; decide based on the expected depth of the damage distribution.

The theory provides a rigorous foundation for designing agent planning strategies, going beyond empirical conventions such as "retry" or "always replan."

One-line Summary

The paper derives a threshold theory for the optimal repair/replan decision when AI agent plans fail, revealing the decisive role of plan structure and the price of stability.

Paragraph Summary

This paper addresses the strategy-selection problem after plan failure during AI agent execution by establishing a theoretical framework. The authors model interruptions as damage to a plan's causal support and prove that the optimal strategy is a threshold function of effective damage depth: repair for shallow damage, replan for deep damage, and abandon when the cost is too high. Damage depth depends on the structure of the plan dependency graph, and more parallel plans favor repair. The paper further introduces the concept of price of stability to explain how plan commitment is maintained when replanning costs approach zero, and analyzes commitment lag and patch debt under repeated interruptions. Numerical checking found zero violations across 1.6 million evaluations, and the regime diagram reproduces the strategy switching observed in the benchmark.

#AI agents#plan repair#replanning#threshold theory#price of stability#commitment lag#patch debt#causal support
Share:

Related articles