# Same Winners, Different Success Rates: Evaluating How LLM Agents Recover from Failures

arXiv: https://arxiv.org/abs/2609.34215 · HTML: https://mlsanity.com/paper/2609.34215/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reinforcement learning for LLM agents, one of 16 directions in LLM agents and tool use.
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 28 Sep 2026.

## Placed in

- LLM agents and tool use / [Reinforcement learning for LLM agents](https://mlsanity.com/agents/reinforcement-learning-for-llm-agents/)

## Builds on (most cited first, 26 of 26)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [AutoGen: Enabling Next-Gen LLM Applications via Multi-Agent Conversation](https://mlsanity.com/paper/2308.08155/) (2023)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Selective Classification for Deep Neural Networks](https://mlsanity.com/paper/1705.08500/) (2017)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Time-uniform, nonparametric, nonasymptotic confidence sequences](https://mlsanity.com/paper/1810.08240/) (2018)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [WorkflowLLM: Enhancing Workflow Orchestration Capability of Large Language Models](https://mlsanity.com/paper/2411.05451/) (2024)
- [Causal Agent Replay: Counterfactual Attribution for LLM-Agent Failures](https://mlsanity.com/paper/2606.08275/) (2026)
- [When Tools Fail: Benchmarking Dynamic Replanning and Anomaly Recovery in LLM Agents](https://mlsanity.com/paper/2606.05806/) (2026)
- [Do Repetitions Matter? Strengthening Reliability in LLM Evaluations](https://mlsanity.com/paper/2509.24086/) (2025)
- [Finding Replicable Human Evaluations via Stable Ranking Probability](https://mlsanity.com/paper/2404.01474/) (2024)
- [Auditing Provenance Sensitivity in LLM Agent Action Selection](https://mlsanity.com/paper/2607.20827/) (2026)
- [The Replay Gap: Static Evaluation of Model Switching in LLM Agents Scores the Wrong World](https://mlsanity.com/paper/2608.08239/) (2026)
- [Proof-Carrying Agent Actions: Model-Agnostic Runtime Governance for Heterogeneous Agent Systems](https://mlsanity.com/paper/2606.04104/) (2026)
- [Safeguarding LLM Agents from Misalignment through Provenance Analysis](https://mlsanity.com/paper/2607.01236/) (2026)
- [CAVA: Canonical Action Verification and Attestation for Runtime Governance of Agentic AI Systems](https://mlsanity.com/paper/2607.13716/) (2026)
- [Optimal Decision Rules Under Partial Identification](https://mlsanity.com/paper/2111.04926/) (2021)
- [Optimal Decision Rules when Payoffs are Partially Identified](https://mlsanity.com/paper/2204.11748/) (2022)
- [Can LLMs Really Recover Microservice Failures? A Recovery-Aware Evaluation of Diagnosis-to-Action Reasoning](https://mlsanity.com/paper/2607.04623/) (2026)
- [Optimal Best-Arm Identification under Fixed Confidence with Multiple Optima](https://mlsanity.com/paper/2505.15643/) (2025)
- [When Can Agents Safely Checkpoint, Fork, Restore, and Merge? Exact Checking for Execution Edits](https://mlsanity.com/paper/2608.22928/) (2026)

## Abstract (arXiv)

Evaluating how LLM agents recover from mid-task failures is central to deploying reliable agentic systems. Existing checkpoint-based benchmarks measure recovery by comparing which action is selected as best across independent runs, a quantity known as set agreement. However, set agreement is a purely ordinal measure that records which action wins without reflecting the absolute level of performance. When all actions fail, they tie at zero reward, and independent runs produce the same tied set with high probability, creating an illusion of stability that masks near-zero recovery success. We formalize this limitation through a set-path symmetry result, proving that for equal-cost Bernoulli actions the success probabilities (0.9, 0.8) and (0.2, 0.1) yield identical best-action-set distributions at every sample size. No procedure based solely on which action wins can distinguish these two regimes. We further prove that certifying exact population ties is impossible in finite time, and that the assignment of outcomes to checkpoints carries information beyond marginal outcome distributions. The pooled success probability is the missing scalar that resolves the ordinal ambiguity. Experiments on 864 frozen RecoveryBench episodes and two planning cohorts totaling 3,456 responses confirm the theoretical predictions. Agreement and held-out quality can move in opposite directions, and permuting checkpoint-to-action bindings changes 8 to 13 percent of cell-level conclusions. Based on these findings, we propose reporting four diagnostic quantities (agreement, all-zero fraction, held-out success, and pooled success) that expose this failure mode with no additional data collection.