# Hell or High Water: Evaluating Agentic Recovery from External Failures

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 33 of its 46 references that are in the map.
- First posted on arXiv 14 Aug 2025.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 33)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [Emergent Abilities of Large Language Models](https://mlsanity.com/paper/2206.07682/) (2022)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [Gorilla: Large Language Model Connected with Massive APIs](https://mlsanity.com/paper/2305.15334/) (2023)
- [Instruction-Following Evaluation for Large Language Models](https://mlsanity.com/paper/2311.07911/) (2023)
- [Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task](https://mlsanity.com/paper/1809.08887/) (2018)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [CRITIC: Large Language Models Can Self-Correct with Tool-Interactive Critiquing](https://mlsanity.com/paper/2305.11738/) (2023)
- [Executable Code Actions Elicit Better LLM Agents](https://mlsanity.com/paper/2402.01030/) (2024)
- [AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents](https://mlsanity.com/paper/2407.18901/) (2024)
- [TravelPlanner: A Benchmark for Real-World Planning with Language Agents](https://mlsanity.com/paper/2402.01622/) (2024)
- [Self-critiquing models for assisting human evaluators](https://mlsanity.com/paper/2206.05802/) (2022)
- [Tool Learning with Foundation Models](https://mlsanity.com/paper/2304.08354/) (2023)
- [ToolSandbox: A Stateful, Conversational, Interactive Evaluation Benchmark for LLM Tool Use Capabilities](https://mlsanity.com/paper/2408.04682/) (2024)
- [ToolQA: A Dataset for LLM Question Answering with External Tools](https://mlsanity.com/paper/2306.13304/) (2023)
- [GPT4Tools: Teaching Large Language Model to Use Tools via Self-instruction](https://mlsanity.com/paper/2305.18752/) (2023)
- [ToolkenGPT: Augmenting Frozen Language Models with Massive Tools via Tool Embeddings](https://mlsanity.com/paper/2305.11554/) (2023)
- [TALM: Tool Augmented Language Models](https://mlsanity.com/paper/2205.12255/) (2022)
- [Toward Self-Improvement of LLMs via Imagination, Searching, and Criticizing](https://mlsanity.com/paper/2404.12253/) (2024)
- [AnyTool: Self-Reflective, Hierarchical Agents for Large-Scale API Calls](https://mlsanity.com/paper/2402.04253/) (2024)
- [Chain of Code: Reasoning with a Language Model-Augmented Code Emulator](https://mlsanity.com/paper/2312.04474/) (2023)
- [Making Language Models Better Tool Learners with Execution Feedback](https://mlsanity.com/paper/2305.13068/) (2023)
- [ToolHop: A Query-Driven Benchmark for Evaluating Large Language Models in Multi-Hop Tool Use](https://mlsanity.com/paper/2501.02506/) (2025)
- [ChatCoT: Tool-Augmented Chain-of-Thought Reasoning on Chat-based Large Language Models](https://mlsanity.com/paper/2305.14323/) (2023)
- [Benchmarking Language Model Creativity: A Case Study on Code Generation](https://mlsanity.com/paper/2407.09007/) (2024)
- [Not All LLM Reasoners Are Created Equal](https://mlsanity.com/paper/2410.01748/) (2024)

## Built on by (most cited first, 9 of 9)

- [From Fluent to Verifiable: Claim-Level Auditability for Deep Research Agents](https://mlsanity.com/paper/2602.13855/) (2026)
- [Feedback That Backfires: Why Small Language Model Agents Repeat the Call They Just Watched Fail](https://mlsanity.com/paper/2608.23651/) (2026)
- [Robust Agent Compensation (RAC): Teaching AI Agents to Compensate](https://mlsanity.com/paper/2605.03409/) (2026)
- [Where Does Exactly-Once Live? Model, Harness, and Tool-Contract Effects on Duplicate Side Effects in LLM Agents](https://mlsanity.com/paper/2609.29095/) (2026)
- [Better, Faster, Stronger: Programmatic Skill Learning Best Reduces Agent Cost](https://mlsanity.com/paper/2608.11338/) (2026)
- [Recoverability as a System Primitive for Long-Horizon AI Agents](https://mlsanity.com/paper/2609.13672/) (2026)
- [Agentic Cognitive Depth: Operational Criteria for Evaluating LLM Agents](https://mlsanity.com/paper/2610.04168/) (2026)
- [State Representation Shapes Long-Horizon Agent Learning and Transfer: An Empirical Study](https://mlsanity.com/paper/2610.15407/) (2026)
- [Beyond Perfect Teammates: Multi-Agent Collaboration with Unreliable Colleagues](https://mlsanity.com/paper/2610.16117/) (2026)

## Abstract (arXiv)

As language model agents are applied to real world problems of increasing complexity, they will be expected to formulate plans across large search spaces. If those plans fail for reasons beyond their control, how well do language agents search for alternative ways to achieve their goals? We devise a specialized agentic planning benchmark to study this question. Each planning problem is solved via combinations of function calls. The agent searches for relevant functions from a set of over four thousand possibilities, and observes environmental feedback in the form of function outputs or error messages. Our benchmark confronts the agent with external failures in its workflow, such as functions that suddenly become unavailable. At the same time, even with the introduction of these failures, we guarantee that the task remains solvable. Ideally, an agent's performance on the planning task should not be affected by the presence of external failures. Overall, we find that language agents struggle to formulate and execute backup plans in response to environment feedback. While state-of-the-art models are often able to identify the correct function to use in the right context, they struggle to adapt to feedback from the environment and often fail to pursue alternate courses of action, even when the search space is artificially restricted. We provide a systematic analysis of the failures of both open-source and commercial models, examining the effects of search space size, as well as the benefits of scaling model size in our setting. Our analysis identifies key challenges for current generative models as well as promising directions for future work.