acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , 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 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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agent recovery, minimal repair subtrajectories, trajectory repair, executable verification, long-horizon agents, failure localization, counterfactual replay

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ZfHeOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper defines a Minimal Repair Subtrajectory (MRS): the shortest contiguous span of original steps in a failed agent trace such that replacing it with actions from a fixed candidate library, and then replaying the remaining suffix, makes the task pass an external verifier. It distinguishes a local-recovery certificate from an exact MRS certificate. A training-free doctor–patient–verifier procedure searches for such repairs: the doctor proposes anchors and replacements from the failed trace and the verifier's unmet conditions, and the verifier checks candidates in order of increasing span length. Experiments cover an author-built controlled dependency benchmark, a strict-replay subset of τ², three public environments (ToolSandbox, AppWorld, ALFWorld), a router that chooses between local repair and restart, and the reuse of MRS segments as in-context demonstrations and fine-tuning data.

Critical strengths
  1. The paper isolates repair extent as its own question and defines it cleanly. Most prior work asks which step caused a failure or simply retries the whole episode; this paper asks how much of a failed trajectory must change for the task to succeed. This angle is clearly distinct from failure attribution and from full retry, and the analogy to delta debugging is apt. The paper is explicit that minimality is relative to a declared candidate library, and it separates "a repair was found" from "the repair is provably minimal", which guards against over-reading its results.
  2. Recovery is judged by executable verifiers and reported transparently. Every recovery is decided by the environment's own executable verifier rather than by model self-assessment. Sample filtering and denominators for the public environments are disclosed, comparisons use paired tests on the same failures, and negative results are reported: local repair loses to simple rollback or full restart in some environments. Rather than hiding these, the paper turns them into a routing rule based on whether the prefix can be trusted.
Critical weaknesses
  1. The main controlled findings follow largely from the definition and setup, and the public experiments do not execute MRS. MRS is defined as the shortest passing span and is computed with oracle replacements on failures that are recoverable by construction, so its compactness advantage holds almost by definition. The high share of multi-step repairs also depends on the authors' generator and on replaying the recorded suffix verbatim, which forces downstream actions that consumed corrupted outputs into the span. In the public environments, the suffix is regenerated from a checkpoint, so the method reduces to choosing a rollback point. The authors should report span widths with an adaptive suffix and run bounded-span repair directly in the public environments.
  2. The method relies on the official verifier at repair time, and its gains over simple baselines are not established under matched conditions. The doctor sees the verifier's unmet conditions and uses its verdict to accept candidates, and the method needs a checkpointable, deterministic environment; both are rarely available in deployment. Even so, a short fixed rollback matches or beats the doctor on AppWorld, full restart wins on ALFWorld, no doctor-versus-retry test is significant, and it is unclear whether the two get the same number of verifier-checked attempts. The authors should add an attempt-matched retry baseline and report the doctor without verifier feedback.
Questions for authors
  1. In the public environments, how many original positions does the executed repair actually replace (from the checkpoint to the end of the trajectory), and how does that compare with the MRS width found by the post-hoc audit?
  2. In Table 3, how many verifier-checked attempts do the doctor, fixed rollback, and full retry each receive? Does the doctor use the verifier's pass/fail signal to choose among its candidates?
Reviewer_FH1DOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes the idea of Minimal Repair Subtrajectories, which are the shortest contiguous regions of a failed agent trajectory that can be replaced, replayed, and verified to complete a task. The paper proposes a doctor-patient-verifier procedure that proposes repair locations and replacements, restores checkpoints and accepts repairs when a verifier passes. They study repair width in controlled tasks, test local recovery in tau-bench and use compact repairs as demonstrations/training data.

Critical strengths

The framing of minimal repair subtrajectories is a nice contribution and makes sense, and I like the motivation of trying to make a minimal edit. The figures such as figure 3 also illustrate this process well.

Critical weaknesses

This paper is difficult to read and the general writing style seems like LLMs may have been used too much in the writing process. For instance, I have found that one action that LLMs tend to take in writing up results is simply listing a series of numbers that the readers probably would not care about (e.g. many of the numbers in line 20-27 are not important for a reader to immediately know). The authors are encouraged to clean up the writing and make the most important points more evident.

The results themselves are relatively modest. It seems like the improvements are rather small and the method may not be helpful vs. full restarts in ALFWorld. Also, it seems as if the set of replacement action sequences that the search can try is limited which limits applicability to real scenarios (as can be seen in the weaker results?)

I think that some related work may be missing from the discussion section, in particular [1] which also studies online failure forecasting, while [2] studies the risk of disrupting runs throughout intervention.

[1] https://openreview.net/pdf?id=d3Qq4weuwz

[2] https://arxiv.org/abs/2602.03338

Questions for authors

N/A

Reviewer_qF6cOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper addresses the problem of repairing failed multi-step trajectories, where single-step edits often fail due to multi-step dependencies, while full-trajectory restarts or suffix replacements are overly costly and destructive. To bridge this gap, the authors introduce MRS, a candidate-space-relative repair unit that combines minimal contiguous trajectory coverage with verifier-backed replay. To find these repair units, the paper proposes a training-free "doctor–patient–verifier" search framework that yields certified recoveries within a bounded verification budget. By decoupling repair granularity from replacement quality on controlled dependency tasks (as well as evaluating on the public τ2benchmark), the authors empirically demonstrate that MRS achieves 100% recovery—matching coarse-grained baselines like full-trajectory or window replacements—while modifying 1.98× to 3.16× fewer original trajectory positions. Finally, the paper demonstrates the practical utility of MRS by converting failed trajectories into high-density supervision signals and training a prefix-validity router, which dynamically decides when to repair versus restart, outperforming the "always restart" baseline in both recovery rate and computational cost.

Critical strengths
  • Clear problem formulation and rigorous distinction between "successful repair" and "minimal repair":** Section 3 cleanly defines MRS as the shortest contiguous repair span within a given candidate space, explicitly distinguishing between an execution-verified recovery certificate and an exact minimality certificate obtained by exhausting all shorter candidates.
  • Clean isolation of repair granularity and honest quantification of trade-offs: By fixing replacement quality across 960 controlled failures (Table 1), the paper effectively isolates the impact of repair granularity. While single-step and 3-step window repairs achieve only 14.9% and 46.2% recovery respectively, MRS reaches 100% recovery while covering an average of just 2.53 positions (compared to 8.00 for full-trajectory replacement). The authors also transparently compare against non-contiguous minimal repairs (2.26 positions), honestly acknowledging the slight structural cost of enforcing contiguity. (Note: This 100% reflects an oracle controlled setting rather than the practical search recovery rate on public benchmarks.)
  • Strong practical value in supervision reuse and conditional routing. By controlling for both sample size and token budget in fine-tuning, the paper convincingly validates the benefit of compact supervision. Moreover, recognizing that local repair is not always optimal, the authors operationalize a prefix-validity router to arbitrate between repair and restart. Validated under held-out family and leave-one-environment-out splits, the router recovers 44/306 failures compared to 32/306 for "always restart" (p≈0.0042_p_≈0.0042) while cutting normalized cost by 15.8%.
Critical weaknesses
  • Inconsistent and confusing notation/abbreviations: The manuscript suffers from pervasive ambiguity in its abbreviations. For example, does τ2 refer to τ2-bench? If so, please use τ2-bench consistently throughout the text; otherwise, explicitly define it in the Abstract and Introduction. Furthermore, τ2 is cited alongside two different works (τ-bench and τ2-bench), leaving the reader confused as to which benchmark is actually evaluated. Many similar undefined or inconsistent abbreviations appear throughout the paper. I strongly encourage the authors to thoroughly proofread the manuscript and align their notation and presentation standards with the top-tier venue papers cited in their Related Work.
  • Discrepancy between theoretical formulation and experimental evaluation: There is a fundamental mismatch in how trajectory repair is defined versus how it is evaluated. Equation (1) requires replacing a contiguous span and re-executing the originally recorded suffix actions. However, the public benchmark experiments primarily regenerate the suffix from the checkpoint onward. These are two fundamentally different interventions: suffix regeneration can alter multiple actions outside the annotated repair span, meaning task recovery might stem from downstream replanning rather than the local edit itself. For the minimality guarantees of Equation (1) to hold in practice, the authors must clarify how regenerated suffixes are incorporated into the candidate space and how these downstream alterations are accounted for when measuring repair coverage.
  • Lack of theoretical foundations and formal guarantees for the Minimal Repair Subtrajectory (MRS): Early on, the paper states its central research question: "what is the smallest verified part of a failed trajectory that must change, under a declared repair library?" (Lines 40–41). While the authors propose MRS to formalize this concept, they provide no rigorous proof or theoretical characterization for it. Specifically, certifying an MRS requires proving two things: (i) there exists a valid replacement for the span that succeeds (a recovery witness), and (ii) all valid replacements for all strictly shorter spans within the declared repair library fail (a minimality certificate). Building upon this, the paper lacks a fundamental theoretical treatment of the problem's nature:
    1. Existence and Library Conditions: What theoretical principle guarantees that an MRS is indeed the "smallest verified part"? How does this guarantee depend on the declared repair library—specifically, what formal conditions or properties must the repair library satisfy to ensure the existence and identifiability of the smallest verified part?
    2. Multiplicity and Upper Bounds: Can a single failed trajectory contain multiple distinct "smallest verified parts" (i.e., multiple disjoint or overlapping minimal spans)? If so, what is the theoretical upper bound on their number?
    3. Uniqueness and Granularity within a Span: Is the replacement for a smallest verified part unique? For example, in a search task, an agent might derive a correct search query in a single step via direct reasoning, or in a single step by writing a verification script. Both are 1-step interventions leading to task success—do both qualify as the "smallest verified part"? Furthermore, can (or should) minimality be defined at a finer granularity than trajectory steps (e.g., token- or operation-level)? If not, why is step-level granularity sufficient?
  • As it stands, the paper merely presents empirical enumeration results under a specific set of experimental configurations. However, the ICLR community expects a rigorous methodological framework—for instance, proving that under assumptions A, B, and C on the declared repair library, a principled algorithm is guaranteed to provably and exactly recover the smallest verified part. If the authors wish to study this problem seriously, I strongly encourage them to ground their work in this theoretical direction.
Questions for authors

See Weaknesses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.