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

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 4 Jun 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [Tool learning and function calling](https://mlsanity.com/agents/tool-learning-and-function-calling/)

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

- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [ToolLLM: Facilitating Large Language Models to Master 16000+ Real-world APIs](https://mlsanity.com/paper/2307.16789/) (2023)
- [τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains](https://mlsanity.com/paper/2406.12045/) (2024)
- [DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence](https://mlsanity.com/paper/2606.19348/) (2026)
- [API-Bank: A Comprehensive Benchmark for Tool-Augmented LLMs](https://mlsanity.com/paper/2304.08244/) (2023)
- [GLM-5: from Vibe Coding to Agentic Engineering](https://mlsanity.com/paper/2602.15763/) (2026)
- [Identifying the Risks of LM Agents with an LM-Emulated Sandbox](https://mlsanity.com/paper/2309.15817/) (2023)
- [ToolQA: A Dataset for LLM Question Answering with External Tools](https://mlsanity.com/paper/2306.13304/) (2023)
- [Survey on Evaluation of LLM-based Agents](https://mlsanity.com/paper/2503.16416/) (2025)
- [Evaluation and Benchmarking of LLM Agents: A Survey](https://mlsanity.com/paper/2507.21504/) (2025)
- [GuardAgent: Safeguard LLM Agents by a Guard Agent via Knowledge-Enabled Reasoning](https://mlsanity.com/paper/2406.09187/) (2024)
- [Measuring what Matters: Construct Validity in Large Language Model Benchmarks](https://mlsanity.com/paper/2511.04703/) (2025)
- [Vending-Bench: A Benchmark for Long-Term Coherence of Autonomous Agents](https://mlsanity.com/paper/2502.15840/) (2025)
- [From Allies to Adversaries: Manipulating LLM Tool-Calling through Adversarial Injection](https://mlsanity.com/paper/2412.10198/) (2024)
- [ReliabilityBench: Evaluating LLM Agent Reliability Under Production-Like Stress Conditions](https://mlsanity.com/paper/2601.06112/) (2026)
- [ToolFlow: Boosting LLM Tool-Calling Through Natural and Coherent Dialogue Synthesis](https://mlsanity.com/paper/2410.18447/) (2024)
- [ToolTweak: An Attack on Tool Selection in LLM-based Agents](https://mlsanity.com/paper/2510.02554/) (2025)
- [PALADIN: Self-Correcting Language Model Agents to Cure Tool-Failure Cases](https://mlsanity.com/paper/2509.25238/) (2025)
- [Beyond ReAct: A Planner-Centric Framework for Complex Tool-Augmented LLM Reasoning](https://mlsanity.com/paper/2511.10037/) (2025)
- [Multi-Mission Tool Bench: Assessing the Robustness of LLM based Agents through Related and Dynamic Missions](https://mlsanity.com/paper/2504.02623/) (2025)
- [Mimicking the Familiar: Dynamic Command Generation for Information Theft Attacks in LLM Tool-Learning System](https://mlsanity.com/paper/2502.11358/) (2025)
- [Robust Tool Use via Fission-GRPO: Learning to Recover from Execution Errors](https://mlsanity.com/paper/2601.15625/) (2026)
- [Auditing Automated Evaluation, Error Propagation, and Runtime Mitigation in Tool-Using Language Agents](https://mlsanity.com/paper/2604.16706/) (2026)
- [STT-Arena: A More Realistic Environment for Tool-Using with Spatio-Temporal Dynamics](https://mlsanity.com/paper/2605.18548/) (2026)
- [More Vulnerable than You Think: On the Stability of Tool-Integrated LLM Agents](https://mlsanity.com/paper/2506.21967/) (2025)

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

- [Model or Harness? An Interaction-Centric Taxonomy for Localizing Agent Failures](https://mlsanity.com/paper/2607.28802/) (2026)
- [AgentCheck: A Reproduce-Intervene-Mitigate Workbench for LLM Agents over MCP](https://mlsanity.com/paper/2607.11098/) (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)
- [Retry, Switch, or Abstain? Learning Strategy-Aware Tool-Use Policies via Controlled Error Injection](https://mlsanity.com/paper/2608.11977/) (2026)
- [Outcome Monitors: Recovery Affordances for Silent Tool Failures](https://mlsanity.com/paper/2608.19303/) (2026)
- [Cost-Utility Alignment in LLM Agent Trajectories:Profiling,Attribution,Diagnosis,Adaptation,and Evaluation](https://mlsanity.com/paper/2608.26195/) (2026)
- [MemToC: Benchmarking Memory-Tool Conflict Resolution in Large Language Models](https://mlsanity.com/paper/2608.26295/) (2026)
- [Engineering Reliable Commit Gates for Agentic AI: Cost-Aware Verification Portfolios under Common-Mode Data Failures](https://mlsanity.com/paper/2609.10969/) (2026)
- [OctoNest: Adaptive Cross-Device Execution through Stateful Control](https://mlsanity.com/paper/2606.20487/) (2026)
- [ATLAS: Dual-Horizon Diagnostic Evaluation for Industrial Tool-Use Agents](https://mlsanity.com/paper/2608.30685/) (2026)
- [Stale Does Not Mean Unsafe: Guard Precision for Tool-Using LLM Agents under Infrastructure State Races](https://mlsanity.com/paper/2609.29522/) (2026)
- [Same Winners, Different Success Rates: Evaluating How LLM Agents Recover from Failures](https://mlsanity.com/paper/2609.34215/) (2026)
- [One Readout, Many Repairs: Diffusion-Guided Hierarchical Search for Tool-Agent Repair](https://mlsanity.com/paper/2609.34879/) (2026)
- [From Migration to Calibration: Aligning Agents with Deployment Requirements](https://mlsanity.com/paper/2609.35149/) (2026)
- [Quantization Effects on Tool-Failure Recovery Vary Across Prompts and Evaluation Designs](https://mlsanity.com/paper/2610.07781/) (2026)
- [Loud Failures, Quiet Failures: Fault Detection and Recovery in Tool-Using Language Model Agents](https://mlsanity.com/paper/2610.10062/) (2026)
- [State Representation Shapes Long-Horizon Agent Learning and Transfer: An Empirical Study](https://mlsanity.com/paper/2610.15407/) (2026)

## Abstract (arXiv)

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 × 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× 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.