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.