Minimal Repair Subtrajectories: Verifier-Certified Local Recovery for Long-Horizon Agents

Long-horizon agents can fail because one incorrect tool action makes several later actions incompatible. Step repair may then be too narrow, whereas restarting discards a useful prefix. We introduce the Minimal Repair Subtrajectory (MRS): the shortest contiguous original span for which an admissible replacement, followed by executable replay, restores verifier-confirmed success. Minimality is explicit about its candidate space. Our training-free doctor–patient–verifier procedure first returns a bounded local-recovery certificate; exhaustive elimination of shorter admissible spans upgrades it to an exact MRS certificate. On ${\tau }^2$, bounded search recovers 34 of 53 strict-replay-eligible failures, including five multi-step repairs. Across 960 controlled failures, MRS retains 100% verifier success while covering 1.98–3.16$\times$ fewer original positions than successful wider units, and its compact supervision outperforms full trajectories under matched budgets. An exhaustive audit certifies exact MRS boundaries for at least 32 of 41 successful public-environment recoveries. Across three such environments, a family-disjoint router raises recovery from 10.46% to 14.38% over always restart and reduces normalized cost by 15.8% while passing registered recovery non-inferiority and cost gates.