Most Tool-Integrated Reasoning (TIR) benchmarks assume tools work perfectly—no exceptions, no incorrect outputs, no timeouts. Real-world tool-using LLM agents encounter failures constantly, yet we lack systematic ways to measure their recovery. This leaves practitioners blind to the brittle behavior that causes agents to collapse when a single API call fails.

ToolMaze introduces a benchmark that combines DAG-structured task topologies with a controlled failure injection framework. Tasks are defined as directed acyclic graphs of tool calls, with nodes representing tool invocations and edges representing dependencies. The benchmark varies topological complexity (branching, sequential chains, fan-out) and injects anomalies drawn from a 2x2 taxonomy: type (execution failure vs. malformed observation) crossed with persistence (permanent vs. transient). An LLM agent must parse environment feedback, distinguish a real failure from a recoverable one, and replan a valid alternative DAG path—not just retry the same node—to test systematic dynamic replanning rather than blind trial-and-error. The environment tracks whether the agent’s new plan actually resolves the failure or just skirts around it without learning.

GPT-4o achieves 85% task success on the no-failure baseline but falls to 31% when any tool anomaly occurs. The drop is not uniform: under permanent execution failures the success rate dips below 20%, while transient malformed observations cause less severe but still significant degradation. Failure analysis reveals three root causes: planning rigidity where agents repeatedly call failed tools without altering the plan, hallucinated tool invocations (calling tools that don’t exist or with wrong parameters), and broken state tracking where the agent loses memory of which sub-task already succeeded and replans from incorrect assumptions. The DAG structure matters too—complex graphs with multiple branching paths exacerbate these failures, showing that current LLMs lack robust graph-based backtracking.

Today’s agent pipelines are dangerously optimistic. You need an error-handling middleware that intercepts tool outputs, tags them with persistent failure flags, and presents an explicit state summary (completed nodes, failed nodes, remaining dependencies) back to the LLM in each turn. Integrate a replanning instruction that forces the model to first state why the last call failed, then propose an alternative next node from the DAG that respects the current state. Constrain retries: if a tool fails permanently, remove it from the model’s available tool set for the remainder of the task. This hardens the agent against hallucinated retries and forces genuine route rediscovery.

ToolMaze uses synthetic DAGs and scripted failures; it does not yet capture real-world semantic tool errors, partial successes, or interactions where tool outputs are subtly corrupted, and evaluation is limited to single-agent settings without multi-agent fallback.