Evidence-Guided Recovery for AI Agents with Ambiguous Tool Outcomes and Partial Execution
Authors: Genliang Zhu, Xiaobo Chen, Ziyuan Wang, Chu Wang
Organizations: Accentrust, Vancouver, Canada and Georgia Institute of Technology, School of Computer Science, Atlanta, Georgia, USA · University of Massachusetts Amherst, Amherst, Massachusetts, USA · Duke University, Durham, North Carolina, USA · Accentrust, Vancouver, Canada and University of Illinois Urbana-Champaign, Department of Computer Science, Urbana, Illinois, USA
Tool timeouts can leave AI agents facing ambiguous tool outcomes and partial execution: an action may have failed, committed or remained in flight while other workflow steps have already completed. We formulate evidence-guided task recovery over approved obligations, provider capabilities and states compatible with public evidence. A shared admissibility check handles key expiry, authorization timing, dependencies and residual effects; a terminal certificate separates actual goal satisfaction from publicly supported safe completion. The known-model implementation combines standard observation-contingent planning with a separately implemented effect-history adjudicator. In a finite study of 37 assignments, planning and three active controls each certify 28 completions; four saved synthetic fee units incur additional computation. A preregistered assignment-held-out comparison then evaluates planning advice against evidence prompting with two local model bundles. Across 58 paired units in 19 previously developed task families, advice certifies 30 completions versus 9, a 36.2-percentage-point difference (exact family sign-flip p=0.0078), using 272 proposals versus 399. All 116 trajectories pass independent replay. Both models exhibit a positive completion difference. The comparison measures the evaluated advice interface under a common shield; search-versus-rule advice requires a separate matched comparison. Unknown and handoff outcomes remain explicit, with guarantees tied to the declared provider capabilities rather than arbitrary third-party exactly-once execution.
Figures & tables
Object
Evidence
Interpretation
Evidence and completion
Separate effect-history replay and finite-tail checks
Public completion differs from actual private goal satisfaction; unknown remains explicit.
Policy selection
37 assignments, five policies; complete-layer and root-vector audits
Four active policies tie at 28/37; search trades synthetic fee savings for computation.
30 versus 9 certificates under the shared shield; not a search-versus-rule-advice comparison.
Native persistence
Eight executor qualifications; separate upstream demo/smoke
Qualified call paths, not planner–provider end-to-end effectiveness.
Table 1. Recovery claims and executed evidence. The common shield, policy choice and model interface are distinct layers.
Capability
Decision-relevant meaning
Deduplication
Stable intent key, validity interval, and atomic suppression of a previously accepted same-key write.
Query
Current-state versus attempt/history scope, authority, visibility delay, and supported operation binding.
Commit bound
A trustworthy upper bound for previously accepted requests; distinct from a bound on later attempts.
Final response
Whether a response certifies a settled attempt, rather than merely reception.
Compensation
Reversible effect class, reverse action, its deduplication behavior, and dependency conditions.
Authorization
Validity interval and whether authority is checked at acceptance or at effect commit.
Table 2. Capabilities used in recovery decisions. A missing capability is not supplied by the local journal.
Figure 1. The primary policies differ at selection, not at the safety boundary. The private effect ledger is used only by adjudication and is not an arrow into the controller. A six-node loop from public contracts through compatible support and shared safety checks, policy selection, one recovery action, and the resulting public observation.
Policy
Safe
Goal
New
Handoff
Fee
Actions
Time
Immediate stop
2/37
9
0
0
0
0
0
Verify–wait rules
28/37
30
0
6
191
106
109
Capability rules
28/37
30
0
6
192
105
108
Greedy selection
28/37
30
0
6
195
94
113
Joint planning
28/37
30
0
6
188
103
108
Table 3. Complete finite enumeration after the planning revision. Goal is private goal satisfaction at the deadline; new violations are episodes with at least one recovery-introduced violation. Fees and time are synthetic units. Logical actions include waiting and handoff.
Policy
Episode
Selection
Median
p95
Cutoff
Fallback
Immediate stop
35.82
24.36
0.37
2.41
0
0
Verify–wait rules
173.81
134.39
0.73
3.86
0
0
Capability rules
180.83
139.83
0.70
3.55
0
0
Greedy selection
168.76
132.66
0.73
5.01
0
0
Joint planning
9576.16
9531.66
24.78
288.53
90
20
Table 4. Measured computation in the complete source-bound enumeration. Episode and selection totals and per-decision median/p95 are host wall times in milliseconds, not provider latency. Cutoff counts truncated search decisions; fallback counts joint decisions selected by the common capability rules. Shared-host timings are descriptive and not monetary totals.
Strategy
N
Safe
Goal
Certified
Handoff
Attempts
Rejected
Evidence prompt
16
2
8
2
0
114
111
Planning assisted
16
7
12
7
2
79
51
Table 5. Authored local-model qualification pilot. Safe is certified safe completion; goal is private goal satisfaction at the deadline. Attempts count model proposals, and rejected counts proposals blocked before execution. The 32 cells are development qualification evidence, not confirmatory population evidence.
Strategy
Certified
Actual goal
Handoff
Attempts
Evidence prompt
9/58
15/58
0/58
399
Planning assistance
30/58
33/58
4/58
272
Table 6. Assignment-held-out confirmation with a common admissibility shield. Each strategy has 58 model-by-assignment episodes; public task families were used in development.
Strategy
Unsafe proposals
False claims
Prompt tok.
Completion tok.
Evidence prompt
317
218
273,983
8,310
Planning assistance
123
76
196,822
5,686
Table 7. Recorded model resources and rejected proposals in the confirmatory study. Prompt and completion totals are observed tokens; reasoning is reported separately and is not added again to completion tokens. Planner computation is additional CPU work.
Stratum
Pairs
Evidence
Advice
gpt-oss-20b
29
5
15
glm-4.7-flash
29
4
15
expired-key-recovery
4
0
4
billing-chain
4
0
2
approval-independent
4
0
3
retirement-already-inflight
4
0
1
Table 8. Post-hoc confirmation breakdown. Each row reports paired units; counts are certified completion. Families listed separately have a nonzero net difference; the remaining eleven are aggregated without omission.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Public template
Assignments
Rules
Greedy
Joint
billing–chain
2
2
2
2
stock–diamond
4
4
4
4
file–fork
1
1
1
1
approval–independent
2
2
2
2
batch–items
2
2
2
2
valid–key–recovery
2
2
2
2
Appendix
Table 9. Assignment coverage and certified safe completions by public template. Template names are identifiers, not independent population samples or proof that every named action was executed.
Template
Fee saved
Actions saved
Extra seconds
Break-even
billing–chain
0
0
1.494
–
stock–diamond
0
0
4.302
–
file–fork
0
0
0.475
–
approval–independent
0
0
0.539
–
batch–items
0
0
0.714
–
valid–key–recovery
1
-1
0.065
0.065
Appendix
Table 10. Persistent per-template comparison on the original 185-row mechanism-003 collection. Positive savings favor joint planning versus capability rules; extra selection seconds are host wall time, not CPU billing. Break-even is seconds per saved synthetic fee unit, not a measured monetary benefit. Full per-assignment costs and Pareto sets are in the separate diagnostic artifact.
Tool-using AI agents are increasingly deployed across enterprise software systems, yet widely used benchmarks primarily evaluate nominal task completion, conflating baseline planning competence with operational fault recovery. We introduce UndoBench, a benchmark spanning 36 base workflows and 36 fault scenarios across 8 enterprise domains, decoupling task competence from recovery capability via counterfactual paired trials under identical seeds alongside wire-level effect-history and environment-state oracles. On 12 held-out TEST workflows across two open-weight models, two frameworks, and three recovery paradigms (5,760 executions / 2,880 paired trials) in the frozen lost-acknowledgment study, nominal competence reached 83.54% while conditional recovery success rate (CRSR) fell to 46.72%, with naive retry producing duplicate external effects in 53.33% of trials. Extensions to commercial API models reproduced this competence-recovery separation. Evaluations across complementary execution boundaries show that recovery is phase-dependent: before mutation, methods perform similarly without duplicate effects among capable trials; during partial mutation, naive retry, per-call idempotency, and zero-privilege journaling collapse on the evaluated composite workflows; after commit but before acknowledgment, verification and server-side idempotency substantially improve safety. These findings demonstrate that evaluating nominal completion alone masks critical, phase-dependent recovery vulnerabilities in autonomous agents.
A durable agent can resume a consequential action while its authority changes and the action's external outcome remains uncertain. We study execution-time reliability of tool-using AI agents, isolating recovery decisions from language-model behavior. Checkpoint state, permission to dispatch, evidence of an external effect and permission to reconcile are distinct obligations. We present a finite conformance study that checks these obligations through histories scored against a provider effect ledger hidden from the recovering application. A prospectively frozen campaign executes 336 histories on native LangGraph and Temporal hosts, crossing 14 schedules, three provider contracts and four matched application policies. All 168 paired host cells have identical checked outcomes. Per host, retained-ledger reconciliation passes all 42 histories: 21 checked completions, 15 denials and six unknown outcomes with reservations retained. Cached retry, revalidation before retry and stable-key retry pass 30, 36 and 31 histories respectively. A separate 16-case component study of InfinityOS, an enterprise AI platform developed by Arya.ai, exercises exported authority, worker, recovery and settlement code over repository fakes. The results isolate the roles of current authority, provider contracts and retained observations in recovery, with safety, completion and unresolved obligations reported separately for the declared application profile.
When a tool call times out, the agent sees the failure and can route around it. A cached error page or negative price can instead arrive in the expected format and be consumed as fact. We introduce Outcome Monitors, which detect violations of outcome contracts mined from task-disjoint traces or derived from public schemas. On a violation, the monitor preserves the result and issues a nonbinding receipt naming the violated property and public recovery tools. In frozen, prespecified evaluations with injected failures, Outcome Monitors raise ToolMaze completion from 10.9% to 28.1% across four models in two provider families and replicate in a third. In tau-bench retail, completion improves by 14.0 and 12.0 points on two tiers. In separate ToolMaze controls, removing the recovery-tool list eliminates the measured gain and restoring it recovers the effect; diagnostic detail and timing produce no detectable differences. Gains concentrate where the fault blocks completion. On a suite transcribed from a published incident taxonomy, detection outside the mined vocabulary falls to 46%, though delivery continues and completion is unchanged. Recovery tools are the active receipt content in these controls; extending detection beyond the contract vocabulary remains open.