Hell or High Water: Evaluating Agentic Recovery from External Failures
Andrew WangSophia HagerAdi Asija, Daniel Khashabi, Nicholas AndrewsJohns Hopkins University { awang116, danielk, noa}@jhu.edu · 2025
Read Hell or High Water: Evaluating Agentic Recovery from External Failures by Andrew WangSophia HagerAdi Asija, Daniel Khashabi, Nicholas AndrewsJohns Hopkins University { awang116, danielk, noa}@jhu.edu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-11027.txt.
Introduction
Wang and co-authors benchmark how well language model agents recover when their tools fail mid-task. As agents tackle harder real-world jobs, they plan across wide search spaces. When a plan breaks for outside reasons, they must find another route to the goal.
Each task is solved by chaining function calls chosen from over four thousand options. Feedback arrives as outputs or error messages from the environment. Some functions suddenly go dark, yet every task stays solvable by design. Top models often pick the right function in calm settings. They falter, though, at forming and running backup plans once failures hit.
Catalog record
| CREATOR | Andrew WangSophia HagerAdi Asija, Daniel Khashabi, Nicholas AndrewsJohns Hopkins University { awang116, danielk, noa}@jhu.edu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-11027
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Hell or High Water: Evaluating Agentic Recovery from External Failures Andrew WangSophia HagerAdi Asija, Daniel Khashabi, Nicholas AndrewsJohns Hopkins University { awang116, danielk, noa}@jhu.edu Abstract 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. 1 1 1 Code and data available here: https://github.com/JHU-CLSP/hell-or-high-water 0 0 footnotetext: ∗ Equal advising. 1 Introduction Large language models (LLMs) are capable of reasoning and planning through natural language. As a result, they now form the backbone of autonomous language model agents that follow user instructions and carry out actions in the real world. Increasingly, these LLM-driven agents are applied to complex or open-ended tasks, such as navigating the internet or automating tasks across a user’s computer desktop environment. Naturally, faults may arise that prevent a plan from working; we categorize faults into two broad classes: (1) internal errors , which arise from mistakes an agent makes such as passing the wrong arguments to a function, and (2) external errors that occur for reasons beyond an agent’s control. As an example of the latter, a flight booking API may not have flights fulfilling the desired criteria, requiring the LLM agent to try alternate carrier booking APIs. In spite of these obstacles, users generally expect an agent to complete tasks come hell or high water. 2 2 2 The phrase “hell or high water” denotes an obligation that should be fulfilled regardless of circumstances beyond one’s control. Prior works have focused on studying the ability of language agents to correct their own mistakes ( Shinn et al. 2023 ; Madaan et al. 2023 ; Chen et al. 2023a ) . In contrast, the effect of external faults has remained understudied, despite their prevalence in the real world. Figure 1: The agent correctly tries to use Func A, but encounters an external error outside its control: Func A is unavailable. Therefore, it must form a backup plan to use the composition of Func B and Func C. We include the full trajectory in Appendix F . Language model agents struggle to identify backup plans when they encounter external errors. We propose the first benchmark that studies the effect of external errors on language agent performance. Our benchmark satisfies a number of properties that make it suitable for studying this phenomenon. First, our evaluation consistently places an agent in a situation where the task cannot be completed without using a backup plan, while ensuring that the task remains solvable. Secondly, tasks in our benchmark are challenging enough to require planning, but straightforward enough that a successful backup plan can be found by interacting with the environment. Furthermore, to actually measure the inherent capabilities of language agents, our tasks are novel relative to the LLM pre-training data, avoiding solutions based on memorized behaviors. Finally, solutions are easily evaluated based on functional correctness—an agent’s answer must match a gold solution. To satisfy this last requirement, we avoid relying on LLM verification to avoid potential biases and to facilitate reproducibility, and instead employ human-curated datasets where functional correctness can be automatically checked. Figure 1 shows an example problem from the benchmark developed as part of this work. Given a question and access to a library of functions for querying and manipulating the relevant knowledge bases, the language agent must formulate a plan—a sequence of one or more function calls—and execute it to obtain the correct answer. Doing so involves not only formulating queries to retrieve the appropriate functions, but also calling these in the right order and with the right arguments. When the language agent executes a function, it is interacting with an external environment, which can respond in unexpected ways. Upon receiving unexpected feedback from the environment (e.g., if the function was called with the wrong arguments, or was unexpectedly disabled), a successful language agent must react accordingly by adjusting its plan. Our benchmark is constructed such that each question can be solved in at least two different ways, involving different functions. In more detail, our proposed benchmark, Hell-or-High-Water , consists of 830 questions and 4450 functions that must be executed in appropriate contexts to obtain the right answer. Our benchmark creation process is completely automatic, converting text-to-SQL datasets into questions and tools. To consistently force a model to resort to a backup plan, we construct these functions such that every question in the dataset can be solved using either of two non-overlapping sequences of function calls. The first function an agent calls to attempt at solving the problem can be automatically disabled, while always leaving possible alternatives to arrive at the correct solution. While problems in our benchmark are straightforward to solve, involving no more than 3 reasoning steps, the presence of so many functions requires the agent to plan. As agents are calling functions to generate the output, rather than generating a natural language output, functional correctness is straightforward for this benchmark. Using the proposed benchmark, we conduct an extensive empirical study of language model agents which focuses on the following main questions: • Are language agents capable of fault-tolerant planning? All LLMs evaluated have significant difficulty recovering from unexpected errors, including commercial models such as GPT-4 and Gemini 2.0. • How does size of the search space impact fault-tolerant planning? We compare performance in two distinct settings: (1) when all required functions are included in-context; (2) when the language model agent must generate search queries to retrieve relevant tools. We find that the need to search for relevant tools results in significantly harder challenge. • Is fault-tolerant planning a property of model size? While larger models perform better in terms of absolute accuracy, all models tested displayed decreased performance in the face of external errors, suggesting that resilience to such errors benefits weakly from model scaling.