What Structurally Breaks an Agent? Auditing Difficulty in Stateful Tool-Use Workflows

Shereen Anand, Ju Wang, Yali DuarXiv 2026 · arXiv

This paper introduces a diagnostic "stress test" for AI agents to determine exactly why they fail in complex, multi-step tool-use tasks. By using a synthetic environment with mathematically controlled difficulty, the authors show that an agent's failure is often less about "reasoning" and more about specific structural bottlenecks like memory limits or inefficient search strategies.

TL;DR

The authors developed a synthetic, executable "instrument" that isolates whether an agent fails due to scheduling complexity, memory retention, or the number of available choices. Their audit reveals that these difficulty factors are often mathematically coupled, and that an agent's success depends heavily on its internal representation (e.g., using a cache vs. a precomputed plan) rather than just its general "intelligence."

What Problem Does This Paper Address?

Current benchmarks for AI agents typically provide an aggregate score—did the agent finish the task or not? However, a single score doesn't tell you why the agent failed. Did it lose track of a variable (state retention)? Did it perform actions in the wrong order (scheduling)? Or was it simply overwhelmed by too many possible tools to call (candidate selection)?

Existing work has looked at task complexity, but often treats these variables as independent. This paper argues that we need a more granular, "audited" approach to understand the structural breaking points of agents in stateful workflows—tasks where the environment changes with every action.

Methods

The researchers built a synthetic task generator where every task requires exactly eight operations ($N=8$). By keeping the "work" constant, they could independently vary four operational controls:

  • Dependency Depth ($d$): The length of the longest chain of prerequisites.
  • Candidate Count ($b$): The number of choices available for each tool call.
  • Active State Width ($w$): The number of "registers" (variables) the agent must track.
  • Feedback Condition: Whether the agent receives a "snapshot" of the current state or must reconstruct it from its own history.

To calibrate this instrument, they didn't just test Large Language Models (LLMs). They used programmed reference controllers—simple algorithms with deliberate, known weaknesses (e.g., a controller that can only remember two variables at a time). This allowed them to verify that the instrument correctly diagnoses specific deficits.

Datasets

Rather than a static dataset, the paper introduces an executable task family.

  • Primary Study: 49,152 generated tasks and 393,216 rollouts using reference controllers.
  • Follow-on Ablations: Nearly 300,000 additional rollouts testing specific strategies like retries, indexing, and different memory retention policies.
  • Exploratory LLM Pilot: Small-scale tests using a Copilot-routed model (identified as GPT-6 Luna) and a local, quantized Qwen2.5-0.5B model.

Key Insights and Ideas

  • Structural Couplings: You can't just increase "depth" without affecting other things. The authors' audit (see Table 1 below) shows that increasing depth at a fixed amount of work naturally reduces the number of valid ways to complete a task.
Exact structural audit showing how depth affects scheduling freedom
  • Representation is Everything: A task that "breaks" an agent might be solved instantly if the agent changes how it thinks. For example, a "branching deficit" (failing when there are many candidates) is often just a "serial scan" deficit. If an agent uses an indexed lookup instead of scanning candidates one by one, the number of candidates ceases to matter.
  • The Memory-Feedback Tradeoff: Providing state snapshots acts as a "perfect memory" external to the agent. If an agent with a tiny internal cache suddenly succeeds when snapshots are provided, you've successfully isolated a retention deficit.
  • Mathematical Success Ceilings: In some conditions (like "hidden resampling" where values change unpredictably), there is a hard mathematical limit on success that no amount of reasoning can overcome. This helps researchers distinguish between an agent's "stupidity" and a task's inherent impossibility.

Key Results

The reference controllers produced distinct "failure profiles" that matched the authors' analytic predictions (see Table 3).

Success rates of different programmed controllers

As shown in Figure 1, specific resource limits lead to predictable performance drops:

  • Cache-limited agents (blue/red lines) fail sharply as the number of variables to track (Active state width) increases, unless snapshots are provided.
  • Scan-limited agents (brown line) fail as the number of candidates per operation increases.
  • Random schedulers (diamond line) fail almost immediately as dependency depth increases beyond the simplest case.
Figure 1: Marginal profiles in the chains family, averaging all other controls equally. Points are simulation results, not fitted curves. The width panel averages snapshot and history conditions, so its roughly 50% cache floor hides the near-complete failure of the history-only condition at width eight. Full curves for both families are supplied.

In exploratory LLM tests, the small 0.5B local model failed every single task, highlighting a "floor effect" where the model was simply not capable enough to engage with the interface. The larger Copilot-routed model showed more promise but was still sensitive to feedback conditions.

Limitations and Future Work

The authors are careful to note that their tasks are "small and mechanical." They lack natural language instructions, tool discovery, or the ambiguity of real-world user goals. Furthermore, the exploratory LLM results are too small to support general claims about specific model providers.

Future work should involve:

  1. Scaling up: Testing larger, frontier models with more complex, realistic transfer tasks.
  2. Reasoning Budgets: Investigating how "thinking time" or token budgets interact with these structural bottlenecks.
  3. Harness Standardization: Freezing the interaction protocols to allow for fair cross-provider comparisons.

Summary updated

Abstract

An aggregate task score does not distinguish failures of scheduling, state retention, and candidate selection. We develop a small executable instrument that varies dependency depth, candidate count, active state width, and access to current-state snapshots while holding the number of required operations fixed. Two dependency-graph families show that increasing depth at fixed work changes both scheduling freedom and the number of reachable completion states, so these controls are coupled, and we quantify the coupling. The primary study contains 49,152 generated tasks and 393,216 reference-controller rollouts. A separately frozen follow-on design adds 295,936 rollouts covering retention strategy, snapshot cadence, hidden state resampling, recovery, query locality, candidate indexing, and relabeling. Residue caches and precomputed plans solve tasks that defeat limited raw-value caches, and indexed selection removes the serial-scan branching deficit. Hidden resampling imposes an exact success ceiling that additional state tracking cannot overcome. The contribution is an executable diagnostic instrument, analytic calibration, and an audit of its assumptions. A small local CPU study with a 0.5B model completed no workflows, and a 16-episode Copilot-routed fractional factorial is descriptive only. Neither supports general capability claims.
BibTeX
@misc{anand2026what,
  author = {Shereen Anand and Ju Wang and Yali Du},
  title = {{What Structurally Breaks an Agent? Auditing Difficulty in Stateful Tool-Use Workflows}},
  year = {2026},
  eprint = {2611.03227},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.03227},
}
Figure