Shanghai AI Lab's ToolMaze Exposes How AI Agents Collapse When Tools Fail
Researchers introduce ToolMaze, a benchmark revealing that LLM agents systematically fail to recover from tool errors — and that scaling models barely helps
Takeaways
- New benchmark: Researchers introduce ToolMaze, the first benchmark to systematically evaluate LLM agent fault-tolerance using DAG-based task complexity and a 2x2 tool failure taxonomy.
- Silent failures are the hardest: Implicit semantic failures (structurally valid but wrong outputs) cause Perturbation Recovery Rate to drop ~37% compared to explicit errors, driven by agent over-trust in corrupted data.
- Scaling barely helps: Fault-tolerance improves 3.66x slower than basic task completion per order-of-magnitude increase in model size — it's a distinct capability, not a scaling byproduct.
- Leaderboard: Gemini-3.1-Pro-Preview leads (52.95 composite score), followed by GPT-5.5 (49.96), Claude-Sonnet-4-6 (46.14), and DeepSeek-V4-Pro (45.09) with failure-aware prompting.
- Prompting helps but isn't enough: Failure-aware prompts improve performance by up to +20.8%, but perturbed TSR remains far below the clean baseline across all models.
- Open source: Dataset and code are available at github.com/Zhudongsheng75/ToolMaze.
LLM agents are increasingly deployed to orchestrate real-world workflows: booking flights, querying financial APIs, managing calendars. But virtually every benchmark used to evaluate these agents tests them under ideal conditions , tools always respond correctly, pipelines never break. A team from Shanghai AI Laboratory, East China Normal University, and Baidu has now published a paper introducing ToolMaze, a benchmark designed to stress-test what happens when things actually go wrong.
The gap nobody was measuring
Real-world tool execution is rarely a seamless linear pipeline , it forms a complex, failure-prone dependency graph. Agents encounter two broad classes of failure: explicit failures like HTTP 404 or timeout errors that clearly block execution, and far more dangerous implicit failures , structurally valid but semantically wrong outputs, such as a negative stock count caused by a delayed inventory update. Without autonomous anomaly detection, agents blindly propagate these poisoned values, triggering cascading logic errors.
Prevailing benchmarks evaluate tool-integrated reasoning under a "happy path" fallacy, implicitly assuming perfectly stable and truthful environments. ToolMaze is built to break that assumption in a controlled, measurable way.

A two-axis design that actually isolates the problem
The core insight behind ToolMaze is that robustness evaluation needs two independent dimensions to be meaningful. Every task in the benchmark sits at a coordinate on a grid defined by Topological Complexity (C) and Perturbation Mode (P).
The complexity axis defines four levels of DAG (Directed Acyclic Graph , a dependency graph with no cycles) structure:
- C1 (linear): a single execution path with no alternatives , any failure is a dead end.
- C2 (1-to-N): one failing tool can be swapped for a functionally equivalent substitute.