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

1. Problem Statement

Current benchmarks for Tool-Integrated Reasoning (TIR) in Large Language Models (LLMs) predominantly evaluate agents under "happy path" conditions, implicitly assuming that tool environments are perfectly stable and truthful. This overlooks the reality of real-world tool execution, which often involves complex, failure-prone dependency graphs. Agents frequently encounter two distinct types of failures:

• Explicit Failures: Machine-readable exceptions (e.g., HTTP 404, 429, timeouts) that clearly block execution.
• Implicit Failures: Structurally valid but semantically corrupted responses (e.g., negative stock counts due to delayed updates) that require autonomous anomaly detection to identify.

Existing evaluation methods fail to distinguish between systematic replanning and blind trial-and-error, often introducing perturbations randomly rather than at pre-specified nodes. Consequently, there is a lack of rigorous metrics to measure an agent's ability to detect anomalies, backtrack, and dynamically replan when obstructed.

2. Methodology: The TOOLMAZE Framework

The authors introduce TOOLMAZE, a benchmark designed to shift evaluation from static, single-trajectory execution to dynamic state-space exploration. The framework is built upon a two-dimensional evaluation grid defined by orthogonal axes: Topological Complexity (C) and Perturbation Mode (P).

2.1 Tool Corpus and Task Generation

• Corpus: A curated set of 270 tools across six domains (Financial, Travel, Office, Shopping, IoT, General), categorized as Source, Processor, or Action tools.
• DAG-Based Construction: Tasks are generated as Directed Acyclic Graphs (DAGs) where nodes represent tool calls and edges represent data-flow dependencies. This ensures semantic coherence and allows for the exhaustive enumeration of valid recovery paths (ground truth).
• Naturalization: DAGs are converted into context-rich natural language queries via a two-stage pipeline, with reverse validation to ensure the generated query strictly matches the underlying tool dependencies.

2.2 The C × P Evaluation Matrix

• Axis 1: Topological Complexity (C): Tasks are structured into four levels of increasing complexity:
  • C1 (Linear): Single path, no alternatives.
  • C2 (1-to-N): Introduces functionally equivalent substitutes requiring single-step substitution.
  • C3 (Many-to-Many): Creates a combinatorial space of valid recovery paths across interacting sub-graphs.
  • C4 (Integrated Multi-branch): Combines multiple C2 and C3 patterns, requiring reasoning over multiple branching nodes.
• Axis 2: Perturbation Mode (P): A 2 × 2 taxonomy crossing error manifestation (Explicit vs. Implicit) and temporal persistence (Transient vs. Permanent):
  • P1: Explicit-Transient (e.g., temporary timeout).
  • P2: Explicit-Permanent (e.g., tool removed).
  • P3: Implicit-Transient (e.g., temporary semantic corruption).
  • P4: Implicit-Permanent (e.g., persistent semantic corruption).
• Perturbation Engine: A runtime engine injects deterministic, pre-specified synthetic responses (errors or corrupted data) at specific tool nodes. This ensures identical fault conditions across all evaluated models.

2.3 Evaluation Metrics

Beyond standard Task Success Rate (TSR), TOOLMAZE introduces metrics to isolate recovery capabilities:

• Perturbation Recovery Rate (PRR): The conditional probability of resolving an encountered perturbation (via retry, alternative path, or graceful abort).
• Recovery Cost (RC): A penalty metric quantifying inefficiency by measuring unnecessary tool calls during recovery compared to the theoretical minimum.

3. Key Contributions

1. Novel Two-Dimensional Benchmark: TOOLMAZE is the first benchmark to systematically evaluate dynamic path discovery and error recovery using orthogonal axes of DAG complexity and perturbation modes.
2. High-Quality, Scalable Synthesis Paradigm: The authors design a data synthesis pipeline that constructs DAG topologies before query naturalization. This guarantees semantic coherence and enables the exhaustive enumeration of ground-truth recovery paths.
3. Comprehensive Empirical Analysis: Through experiments on state-of-the-art open-weight and proprietary models, the study provides a granular analysis of agent robustness, revealing specific failure modes and scaling behaviors.

4. Experimental Results

The evaluation covered a range of models (e.g., GPT-5.5, Claude-Sonnet-4-6, Gemini-3.1-Pro-Preview, Qwen series, GLM-5.1) under both standard and failure-aware prompts.

• Performance Degradation: Almost all models exhibited substantial performance drops when transitioning from non-perturbed baselines to perturbation modes. Even frontier models with high baseline success rates suffered sharp declines in TSR, PRR, and increases in RC under perturbations.
• Implicit vs. Explicit: The sharpest performance drops occurred under implicit semantic failures (P3/P4). Models exhibited a significant "trust gap," with Perturbation Recovery Rates plummeting by approximately 37% in implicit scenarios compared to explicit ones. This indicates a systemic over-trust in corrupted outputs.
• Complexity Impact: Resilience was highest at C2 (where alternatives exist) but deteriorated as complexity scaled to C3 and C4. Agents struggled with longer dependency chains and combinatorially expanded search spaces, often getting trapped in futile trial-and-error loops.
• Scaling Disparity: A critical finding is that agentic fault-tolerance improves with model scale at a rate 3.66× slower than basic task execution. While Task Success Rate (TSR) grows significantly with parameter count, Perturbation Recovery Rate (PRR) shows minimal gains, suggesting dynamic replanning is a distinct capability not naturally solved by scaling alone.
• Prompting Limitations: While failure-aware prompts (explicitly warning of potential failures) improved performance, the gains were partial. Models still lacked robust dynamic replanning capabilities even with explicit guidance.

5. Significance and Claims

The paper claims that TOOLMAZE challenges the prevalent "happy path" evaluation fallacy in the field. Its primary significance lies in demonstrating that robustness does not naturally emerge from general instruction-following proficiency or model scaling.

The authors argue that current LLM agents lack intrinsic anomaly awareness and that dynamic replanning represents a distinct, foundational capability that requires targeted training signals rather than just larger models or superficial prompting. The benchmark underscores the urgent need to shift evaluation paradigms from linear execution toward deliberate, "System 2-style" autonomous anomaly detection and replanning to build genuinely resilient agents.

The work is limited to controlled, procedurally generated DAG topologies to ensure mathematical ground truth, acknowledging that future work could extend these principles to more unstructured, open-domain workflows.