acceptodds
Under review as a conference paper at ICLR 2027

Minimum Sufficient Repair Chains for Stateful Tool Agents

Abstract

Tool agents often fail through coupled errors. Replacing one suspicious action can leave stale evidence, an incorrect calculation, or an invalid transaction in the execution history. We introduce Minimum Sufficient Repair Chains. The framework searches over rollback boundaries and typed repair operators under an explicit cost. A process verifier records the state of the evidence, calculation, payload, transaction, and final response after each replay. A learned predictor ranks candidate interventions. Shadow replay admits a branch only after executable verification. The method returns the least costly verified chain within its constructed candidate space. We evaluate it on 300 medical record agent trajectories from ten MedAgentBench task families. The repair corpus contains 153 failed trajectories, 1,003 intervention candidates, and repeated counterfactual outcomes for 459 candidates. When one task family is held out at a time, the method achieves an 83.7% stable repair rate and 82.8% exact agreement with the minimum verified repair in that space. Its top three candidates cover 92.8% of failed trajectories. These results establish verified minimal intervention search as an effective approach to recovery in structured tool environments with transactions.

Primary area:
reinforcement learning
Keywords:
Tool-using agents, agent recovery, repair chains, executable verification, counterfactual replay, minimum-cost search

Reviews

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

The paper proposes Minimum Sufficient Repair Chains for recovering failed tool-agent trajectories. It combines rollback boundaries, typed repair operators, a structured process verifier, and a learned candidate ranker to select low-cost verified repairs. Experiments on MedAgentBench evaluate repair success, candidate selection, and component ablations using stored replay outcomes.

Critical strengths

The motivation is reasonable: correcting one action may leave other errors unresolved, so preserving partial progress across multiple repairs can be useful. The paper provides repeated execution results and component ablations, with detailed artifacts that help inspect the reported findings.

Critical weaknesses
  1. The methodological novelty and generality remain limited. Although the ablations support the usefulness of individual components, the framework mainly combines rollback, typed repair, ranking, and verification. Its reliance on task-specific rules for retrieval, calculation, and transactions leaves its applicability to new tasks unclear.

  2. The experimental evaluation is far from sufficient. Experiments are limited to MedAgentBench, without validation in other stateful tool environments. Comparisons with relevant recovery methods, such as GA-Rollback and AgentRewind, are also missing, leaving the generality and advantages of the method unclear.

Questions for authors

See weaknesses.

Reviewer_G2ajOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Minimum Sufficient Repair Chains (MSRC), which searches over rollback boundaries and repair operators to recover failed stateful agent trajectories at low cost. A learned predictor ranks candidates, while process verification and isolated replay determine which branches to retain. On 153 failed MedAgentBench trajectories, task-family holdout evaluation reports an 83.7% stable repair rate and 82.8% agreement with the minimum verified repair within the constructed candidate space.

Critical strengths

The formulation makes repair scope and verification explicit. A failed trajectory may require coordinated changes to evidence retrieval, calculations, and transactions, so replacing one action is often insufficient. Searching for a low-cost repair chain is a reasonable way to address these coupled errors. Repeated executable replay provides stronger evidence of recovery than a model’s judgment alone. The paper also clearly limits its minimality claim to the constructed candidate space.

Critical weaknesses

The experimental scale and coverage are insufficient to establish broader effectiveness. Evaluation is limited to one medical environment, with 153 failed trajectories covering seven task families. Holding out task families is useful, but does not establish transfer to different tool interfaces, transaction structures, or failure distributions. The main comparisons also rely on relatively simple selection policies rather than strong existing recovery systems. Moreover, evaluation primarily uses stored candidates and replay outcomes, leaving performance under fresh online candidate generation unclear. The results support MSRC within this particular repair corpus, but provide limited evidence for its effectiveness as a general recovery framework.

Questions for authors
  1. Do you have results in another stateful environment or on failures generated by different agent models?

  2. How does MSRC compare with strong existing recovery methods when candidates are generated online under matched total repair budgets?

Reviewer_ozWzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes MSRC, which repairs failed tool-agent runs by choosing where to roll back and combining different repair actions. Candidate repairs are tested in an isolated environment, while intermediate checks track which problems have been resolved. The method selects the lowest-cost verified chain among the candidates it considers. Experiments on MedAgentBench favor its learned selection strategy over simple alternatives, but mainly evaluate a preconstructed repair pool, and the minimum-cost argument needs to account for branches discarded before a repair is complete.

Critical strengths
  • The repair design addresses linked errors rather than merely rewriting the final answer. It can restore earlier state and combine several corrective actions, which is useful when a wrong observation has already affected later calculations or database writes.

  • Repairs must pass executable checks in an isolated environment rather than merely receive a positive LLM critique. Repeated replay and testing on task families excluded from training provide useful checks on repair reliability.

Critical weaknesses
  • Earlier systems already support rollback and recovery, including GA-Rollback and AgentRewind. MSRC's specialized repair operations and cost-based selection may add value, but the baselines in Section 5.3 are simple selection policies. These comparisons do not establish its advantage over existing recovery systems.

  • The main comparison selects from a stored repair pool that was partly acquired using MSRC's own ranker (Section 5.1). This tests selection from prepared options more directly than recovery of a new failure from start to finish. The reported candidate-inspection count also does not establish the total cost of generating repairs and obtaining the initial replay results used for ranking.

  • Algorithm 1 discards unfinished branches unless a verifier check improves. A necessary early repair may not yet change any check, so a cheap valid chain could be excluded before it is complete. The minimum-cost argument discusses cost pruning but does not show that this additional progress filter preserves the chains it needs to consider.

Questions for authors

Please see the weaknesses above.

1 comment

Given the lack of further discussion with the authors, my original concerns remain unresolved. Therefore, I will keep my score unchanged.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.