When Tools Fail: Benchmarking Dynamic Replanning and Anomaly Recovery in LLM Agents

Dongsheng Zhu; Xuchen Ma; Yucheng Shen; Xiang Li; Yukun Zhao; Shuaiqiang Wang; Lingyong Yan; Dawei Yin

Source-linked AI summary

When Tools Fail: Benchmarking Dynamic Replanning and Anomaly Recovery in LLM Agents

Dongsheng Zhu, Xuchen Ma, Yucheng Shen, Xiang Li, Yukun Zhao, Shuaiqiang Wang, Lingyong Yan, Dawei Yin

arXiv:2606.05806v1Jun 4, 2026cs.AI

TL;DR

Existing TIR benchmarks largely assume stable, truthful tool environments, leaving resilience to failures and deceptive responses underexamined. ToolMaze evaluates recovery across DAG complexity and tool-failure modes, finding sharp degradation under implicit semantic failures, including a 37.15% recovery-rate drop versus explicit errors.

Problem
Existing TIR benchmarks largely assume stable, truthful tool environments, leaving resilience to failures and deceptive responses underexamined.
Method
ToolMaze benchmarks dynamic path discovery and error recovery across progressively complex DAG topologies and a two-dimensional taxonomy of tool perturbations.
Results
Perturbations degrade performance across nearly all models, with implicit semantic failures causing recovery rates to plummet by 37.15% compared to explicit errors.
Takeaways & Limitations
Dynamic recovery is a distinct foundational capability that current model scaling and prompting do not adequately address.
Takeaways & Limitations
The benchmark prioritizes procedurally generated DAG topologies, leaving extension to unstructured, open-domain workflows for future work.

Abstract

from arXiv · show

Existing benchmarks evaluate Tool-Integrated Reasoning (TIR) in LLMs on idealized ''happy paths'', largely overlooking real-world tool failures. We introduce ToolMaze, a benchmark for dynamic path discovery and error recovery in TIR agents. To separate systematic replanning from blind trial-and-error, ToolMaze adopts a two-dimensional design: DAG-based topological complexity and a $2 \times 2$ taxonomy of tool perturbations (explicit/implicit, transient/permanent). Evaluations show that perturbations degrade performance across nearly all models, with the sharpest drops under implicit semantic failures. Driven by systemic over-trust in corrupted outputs, Perturbation Recovery Rate (PRR) plummets by around 37\% in these scenarios, while complex topologies trap agents in futile trial-and-error loops. Crucially, agentic fault-tolerance improves with model scale $3.66\times$ slower than basic task execution, highlighting dynamic replanning as a distinct bottleneck unaddressed by model scaling or prompting. Data and code are available at https://github.com/Zhudongsheng75/ToolMaze.

1 Introduction

Existing TIR benchmarks largely assume stable, truthful tools, overlooking explicit execution errors and implicit semantic corruption that require anomaly detection, backtracking, and systematic replanning. TOOLMAZE addresses this gap by evaluating dynamic path discovery and error recovery across DAG topological complexity and perturbation modes, showing that anomaly awareness and replanning are distinct capabilities.

Motivation: Existing TIR benchmarks follow a “happy path” assumption of stable, truthful environments, unlike failure-prone real-world tool execution.Real-world tools can produce errors such as 404, 429, and timeouts that block execution paths.
Motivation: Implicit failures return structurally valid but semantically corrupted outputs that agents may blindly propagate, causing cascading logic errors.One example is a negative stock count caused by delayed inventory updates.
Findings: Experiments show that agents often lack robust anomaly awareness, while dynamic replanning captures a capability not reflected by general task success alone.The benchmark is designed to expose reliability limitations under environmental variability and deceptive tool responses.
Motivation: Robust agents must shift from linear execution to dynamic path discovery by detecting anomalies, backtracking, and systematically replanning.This behavior resembles the deliberate, slow-thinking style of System 2 reasoning and is not measured by current benchmarks.
TOOLMAZE: TOOLMAZE evaluates dynamic path discovery and error recovery on a two-dimensional grid combining DAG-based Topological Complexity (C) with Perturbation Mode (P).The benchmark shifts tool-agent evaluation from static, single-trajectory execution to dynamic state-space exploration.
TOOLMAZE: Its scalable synthesis paradigm constructs DAG topologies before query naturalization, guaranteeing semantic coherence and exhaustive solution enumeration.This design supports systematic evaluation across topological complexity and perturbation modes.

2 Related Work

Prior work has advanced LLM tool use toward stateful, open-ended environments and begun evaluating robustness under evolving missions and disruptions. However, implicit semantic failures and DAG-structured recovery remain underexplored because existing work often uses shallow chains, narrow attack surfaces, or unstructured failures.

Foundational tool-use studies established LLM tool-use abilities, while newer paradigms target stateful, open-ended environments.
Multi-Mission Tool Bench and STT-Arena examine dynamic missions and replanning under spatio-temporal disruptions, respectively.
Existing benchmarks rarely isolate robustness and recovery under noise, hallucinations, and tool-response failures.
Prior work still underexplores implicit semantic failures and DAG-structured recovery, often centering on shallow chains, narrow attack surfaces, or unstructured failures.

3 The TOOLMAZE Framework

TOOLMAZE defines a two-dimensional benchmark over topological task complexity and perturbation mode to evaluate alternative-path discovery and fault-tolerant replanning. Its tool-first pipeline constructs and validates DAGs, exhaustively enumerates valid recovery paths, naturalizes tasks, injects controlled faults, and measures completion, recovery, and replanning efficiency.

Two-dimensional evaluation: TOOLMAZE evaluates agents on orthogonal axes: Topological Task Complexity (C), which controls alternative tool-call paths, and Perturbation Mode (P), which triggers exploration.The cross-product (C, P) defines the benchmark’s structured evaluation space.
Two-dimensional evaluation: The C-axis progresses from C1 linear execution to C2 1-to-N substitution and C3 many-to-many multi-path recovery.C1 has no alternatives, while C2 and C3 create increasingly broad spaces of valid recovery paths.
Two-dimensional evaluation: The P-axis includes a Non-Perturbed baseline and four modes combining explicit versus implicit errors with transient versus permanent persistence.The four modes are P1 Explicit-Transient, P2 Explicit-Permanent, P3 Implicit-Transient, and P4 Implicit-Permanent.
Benchmark construction: The tool-first pipeline assembles and validates DAGs, enumerates all valid topological recovery paths, and reverse-validates natural-language queries against their source dependencies.Validation enforces acyclicity, intended topology, semantic coherence, and consistency between generated queries and tool dependencies.
Perturbation engine: The Perturbation Engine deterministically returns configured synthetic failures and applies group-level activation rules so faults affect the selected alternative regardless of the chosen valid path.Transient faults affect only the initial invocation, whereas permanent faults make the targeted tool unavailable or corrupted.
Evaluation metrics: Robustness is measured through overall completion (TSR), recovery capability (PRR), and replanning efficiency (RC) across evaluation trajectories.The framework distinguishes foundational tool-use proficiency from recovery strategies such as retrying transient faults, switching paths for permanent faults, and graceful termination without alternatives.

4 Experiments

ToolMaze evaluates tool-integrated agents on 2,000 sandboxed instances spanning four topological complexities and four perturbation modes. Experiments show that perturbations sharply impair recovery, complexity worsens replanning, prompting helps only partially, and fault tolerance scales substantially more slowly than unperturbed task completion.

Dataset: 2,000 instances expand 400 synthesized base tasks across four perturbation modes and a Non-Perturbed baseline, using 270 manually constructed tools.Tasks are evaluated across topological complexity levels C1–C4.
Primary results: Almost all models suffer substantial TSR and PRR drops, with higher RC, when moving from Non-Perturbed execution to perturbation modes P1–P4.Even Claude-Sonnet-4-6 reaches 77.00% TSR in the unperturbed setting yet degrades substantially under perturbations.
Prompting: +1.5% to +20.8% improvements from the failure-aware prompt show consistent gains over the standard prompt, but only partial mitigation of perturbation failures.Perturbation TSR remains substantially below Non-Perturbed performance despite explicit failure warnings and recovery strategies.
Effect of task complexity: C2 yields the strongest resilience, while performance deteriorates progressively at C3 and C4 as dependency chains lengthen and the search space expands.C1 has zero structural redundancy and creates single points of failure; C2 enables rerouting around failed tools.
Perturbation severity: PRR declines monotonically while RC rises from P1 to P4, indicating that deceptive persistent errors trigger unsuccessful recovery and unnecessary tool calls.The inverse PRR–RC relationship reflects difficulty resolving implicit semantic errors and inefficient recovery planning.
Scaling: 17.85 pp versus 4.88 pp per parameter-count decade: TSR(NP) grows far faster with model scale than PRR.The comparison is based on log-linear fits across six open-weight models, with both metrics improving but at divergent rates.
Implicit–explicit trust gap: 38.12% versus 81.44% average PRR for P2 versus P1 leaves less room for further degradation when permanent failures become implicit under P4.The implicit–explicit PRR gap measures PRR(P1) − PRR(P3) for transient errors and PRR(P2) − PRR(P4) for permanent errors under the failure-aware prompt.

5 Conclusion

TOOLMAZE introduces a DAG-based benchmark for evaluating LLM agents’ fault-tolerance and dynamic recovery beyond idealized “happy path” settings. Its findings expose weak anomaly awareness, severe recovery degradation under implicit semantic failures, and trial-and-error loops under deep topological complexity.

Benchmark contribution: TOOLMAZE is a DAG-based benchmark designed to systematically evaluate LLM agents’ fault-tolerance and dynamic recovery.It challenges the prevalent “happy path” evaluation fallacy.
Key findings: Current models exhibit a systemic lack of anomaly awareness, driven by over-trust in corrupted outputs.This over-trust is identified as the mechanism underlying recovery failures.
Key findings: 37.15%: recovery rates under implicit semantic failures (P3/P4) plummet compared to explicit errors.The passage attributes this degradation to over-trust in corrupted outputs.
Key findings: Deep topological complexity traps agents in futile trial-and-error loops.This finding indicates that difficult graph structures impede effective dynamic recovery.
Key findings: 3.66×: agentic fault-tolerance improves more slowly than basic task execution.The supplied conclusion reports this scaling gap as a crucial finding about agentic fault-tolerance.

Limitations

ToolMaze rigorously evaluates dynamic replanning but limits realism through controlled DAG topologies and a foundational 2 × 2 failure taxonomy. Future work should extend evaluation toward open-domain workflows and compounded multi-hop failures.

Evaluation in Controlled Topologies: ToolMaze prioritizes procedurally generated DAG topologies over completely open-ended web environments to provide exact recovery-path ground truth and penalize inefficient trial-and-error.Its reversevalidation pipeline preserves semantic realism within the benchmark, while future work could target more unstructured, open-domain agentic workflows.
Extensibility of the Failure Taxonomy: Future work should model cascading failures and malicious adversarial injections as highly complex, multi-hop failure scenarios relevant to advancing agentic security.A silent error in one API can trigger a chain reaction, motivating extensions beyond the foundational matrix.

A Perturbation Classes

This section presents the defined perturbation types used in ToolMaze, with their classification provided in Table 3.

The paper presents its defined perturbation types in Table 3.

B Detailed Dataset Statistics

The dataset combines a reproducible corpus of simulated tools and alternative groups for multi-path evaluation with diverse, minimally duplicated tasks. Its 270 tools and 126 alternative groups support topology construction, while low within-subset similarity confirms high semantic variance.

Tool corpus and topology structure: 270 simulated tools are organized by functional role and application domain, alongside 126 alternative groups for constructing multi-path topologies.The alternative groups underpin topology conditions C2–C4.
Tool corpus and topology structure: Every tool is a hand-crafted deterministic simulation of a real-world API, mapping valid inputs to predefined outputs through static lookup tables.This design ensures bit-exact reproducibility while retaining realistic schemas, parameter constraints, and error-handling conventions.
Task diversity: 400 base tasks have non-mutually exclusive domain footprints because complex tasks can chain APIs across different sectors.For example, a task may retrieve a flight schedule and then record the expense.
Task diversity: ≤0.06 intra-category mean Jaccard similarity across 4,950 task pairs confirms high semantic variance and minimal template duplication.The comparison is computed within each 100-task subset.

C Prompt Templates

This section presents prompt configurations for baseline tool use, failure-aware evaluation, task-description generation, template generation, and implicit-perturbation generation. The failure-aware configuration explicitly anticipates tool failures and specifies recovery strategies, unlike the standard baseline.

C.1 Evaluation Prompt: The standard tool-use prompt is the baseline for instructing agents to invoke tools in response to user queries.It does not hint at possible tool failures or recovery strategies.
C.1 Evaluation Prompt: The failure-aware prompt informs agents about potential tool-execution failures and outlines corresponding recovery strategies.It is used for the P1–P4 evaluation configuration.
C.2 Task Description Generation Prompt: Table 7 provides the prompt for generating task descriptions from existing templates.This prompt supports task-description generation rather than evaluation-time tool invocation.
C.3 Template Generation Prompts: Tables 8–17 provide task-template-generation prompts for C1, C2, C3, and C4.C1 uses Tables 8–9, C2 uses Tables 10–12, C3 uses Tables 13–15, and C4 uses Tables 16–17.
C.4 Implicit Failure Generation Prompt: Tables 18–19 provide prompts for generating implicit perturbations for P3 and P4.These prompts target implicit failure generation.
C.4 Implicit Failure Generation Prompt: The appendix includes a table of perturbation classes alongside the implicit-failure-generation materials.Table 3 is identified as the perturbation-classes table.

D Full Results

This section presents the full evaluation results across perturbation modes and all models tested on C1–C4, TSR (NP), and P1–P4.

Full Results: Tables 20–22 report perturbation-mode results and full results for all evaluated models across C1–C4, TSR (NP), and P1–P4.Table 20 covers perturbation modes, while Tables 21 and 22 contain the full model results.

E Case Studies

The 16 case studies span all combinations of complexity levels C1–C4 and perturbation types P1–P4, contrasting successful and failed executions on identical task instances. Across these examples, recovery requires retrying transient failures, halting after permanent failures, detecting implicit corruption, and rerouting through alternatives when available.

Case-study design: The benchmark presents 16 representative case studies covering every combination of complexity level C1–C4 and perturbation type P1–P4.Each case contrasts a successful model with a failed model on the same task instance.
Case-study design: Each figure pairs the natural-language query, tool-call DAG, and perturbed victim response with successful and failed execution traces.The success panel shows correct perturbation handling, while the failure panel shows unsuccessful recovery.
Explicit failures: Explicit-transient failures are recovered by retrying, whereas explicit-permanent failures require stopping or abandoning the failed branch.Successful traces retry tools such as convert_datetime, adjust_temperature, and get_weatherapi_alert_card_native, or reroute after permanent errors.
Implicit failures: Implicit-transient failures expose models that accept corrupted outputs, while successful models detect inconsistencies and re-query for clean data.The failing traces propagate corrupted datetime, sensor, or weather results downstream without verification.
Dynamic rerouting: As complexity increases, successful recovery increasingly depends on selecting alternative paths, while failed models remain stuck, omit shared downstream tools, or complete no valid path.Examples range from C2 IoT rerouting to C3 weather-branch recovery and C4 finance-and-crypto alternative sourcing.