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

Shereen Anand; Ju Wang; Yali Du

cs.LGNov 2, 2026

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

Authors: Shereen Anand, Ju Wang, Yali Du

Organizations: PES University, India · University College London, United Kingdom · King’s College London, United Kingdom

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.

Figures & tables

Family	$d$	Edges	Masks	Orders	Ready nodes
Chains	1	0	256	40320	4.02
Chains	2	4	81	2520	2.70
Chains	4	6	25	70	1.67
Chains	8	7	9	1	1.00
Barriers	1	0	256	40320	4.02
Barriers	2	16	31	576	2.13

Table 1. Exact structural audit at

N=8

. “Masks” counts reachable sets of completed operations; “orders” counts successful operation permutations. Ready nodes are averaged uniformly over nonterminal reachable completion masks, not over a controller’s trajectories.

Grid	Intervention and anchors	Configurations
Work	$N=4,8,16$ ; $d=2,4$ ; $w=4$ ; initial-only or every-step snapshots	192
Memory	$N=16,d=4$ ; fixed, next-use, residue, plan, and stale retention; initial-only or every-fourth snapshots	96
Observation	$N=8,d=4$ ; periods $0,1,2,4$ crossed with public updates or hidden independent resampling	256
Recovery	$N=8,d=4$ ; error allowances $0,2,8,56$ ; trials with replacement or elimination; both snapshot endpoints	256
Locality	$N=16,d=4$ ; balanced, clustered, or concentrated queries crossed with additive or static state	192
Selection	$N=8,d=4,w=4$ ; $b=2,4,8$ ; serial, fixed, redundant, and indexed selection; every-step snapshots	36

Table 2. Follow-on design. Both graph families appear in every grid. Unless stated otherwise,

b=4,8

and

w=4,8

. Grid-specific controller sets and the complete configuration manifest are supplied with the artifact.

Family	Controller	Success (%)	95% interval	Predicted (%)
Barriers	Exact	100.00	[100.00, 100.00]	100.00
Barriers	Cache-2	75.63	[75.51, 75.75]	75.56
Barriers	Cache-2 + Scan-4	51.06	[50.87, 51.27]	51.13
Barriers	Cache-4	87.89	[87.80, 88.00]	87.93
Barriers	Random schedule	25.00	[25.00, 25.00]	25.37
Barriers	Scan-1	33.52	[33.45, 33.61]	33.46

Table 3. Measured and instance-conditional predicted success. Intervals are paired seed-bootstrap bands. Degenerate bootstrap bands do not bound unseen rare events; Table 5 provides nondegenerate binomial intervals for the sparse scheduling condition.

Panel of Figure 1 — 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.

Family	Controller	Depth	Candidates	Width	History
Barriers	Exact	0.00	0.00	0.00	0.00
Barriers	Cache-2	0.02	-1.68	-49.43	-48.75
Barriers	Cache-2 + Scan-4	-0.10	-74.79	-33.32	-32.63
Barriers	Cache-4	-0.08	-0.89	-48.42	-24.21
Barriers	Random schedule	-100.00	0.00	0.00	0.00
Barriers	Scan-1	0.07	-100.00	-0.23	0.00

Table 4. High-minus-low main contrasts in percentage points. Depth: 8 minus 1; candidates: 8 minus 2; width: 8 minus 1; history: history minus snapshot. Each averages all remaining levels equally within its family. The supplement reports the corresponding paired intervals.

Family	$d$	Observed (%)	Wilson interval	Exact (%)
Chains	1	100.00	[98.52, 100.00]	100.0000
Chains	2	3.91	[2.14, 7.04]	6.2500
Chains	4	0.00	[0.00, 1.48]	0.1736
Chains	8	0.00	[0.00, 1.48]	0.0025
Barriers	1	100.00	[98.52, 100.00]	100.0000
Barriers	2	0.00	[0.00, 1.48]	1.4286

Table 5. Random-scheduler calibration using one representative cell per depth and family, with 256 distinct seeds. Other candidate, width, and observation conditions repeat the same scheduling draws and do not increase this effective trial count. Wilson 95% binomial intervals retain uncertainty at zero observed successes.

$b$	Controller	Success (%)	Checks/call	Build entries	Lookups
4	Exact	100.00	2.49	0	0.00
4	Indexed	100.00	0.00	32	8.00
4	Scan-1	0.59	1.00	0	0.00
4	Sham-check-4	0.59	4.00	0	0.00
4	Fixed-check-4	100.00	4.00	0	0.00
8	Exact	100.00	4.52	0	0.00

Table 6. Selection ablation with full snapshots. Checks per call are the aggregate comparison count divided by execution calls. Build entries charge candidate-table preparation separately; lookup calls are separate operations, not equivalent CPU-time units. Early termination changes total comparisons, so only the fixed and redundant controls match comparison counts per decision.

Intervention	Level	Success	Mean completed	$n$
Depth	1	2/3	5.67	3
Depth	8	3/3	8.00	3
Branching	2	2/3	7.33	3
Branching	8	3/3	8.00	3
Register width	1	2/3	7.33	3
Register width	8	2/3	6.33	3

Table 7. Exploratory Copilot-routed GPT-6 Luna pilot. Mean completed operations are out of eight. Each cell has three task seeds; no inferential claims are warranted.

Factor	Success difference	Operation difference	$n$ per level
Depth (8 vs. 2)	-25.0 pp	-1.50	8
Branching (8 vs. 2)	+50.0 pp	+1.50	8
Register width (8 vs. 1)	+25.0 pp	+2.50	8
Snapshot vs. history	+50.0 pp	+2.00	8

Table 8. Descriptive high-minus-low contrasts in the 16-episode Copilot-routed fractional factorial. Eight episodes contribute to each factor level; each of only two task seeds spans four conditions per level. Main effects may be aliased with three-factor interactions.

Contrast	Low success	High success	Difference (95% interval)
family (barriers $-$ chains)	0/128 (0.000)	0/128 (0.000)	+0.0 pp (+0.0, +0.0)
depth (8 $-$ 2)	0/128 (0.000)	0/128 (0.000)	+0.0 pp (+0.0, +0.0)
branching (8 $-$ 2)	0/128 (0.000)	0/128 (0.000)	+0.0 pp (+0.0, +0.0)
width (8 $-$ 1)	0/128 (0.000)	0/128 (0.000)	+0.0 pp (+0.0, +0.0)
observation (snapshot $-$ history)	0/128 (0.000)	0/128 (0.000)	+0.0 pp (+0.0, +0.0)

Table 9. Exploratory local-model factorial. Each level contains 128 tasks. Differences are paired by task seed and averaged over the other factors; intervals resample the eight seed clusters.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Condition	Controller	Success (%)	Low	High	Calls
n16_p0	Cache-2	0.00	0.00	0.00	3.38
n16_p0	Exact	100.00	100.00	100.00	16.00
n16_p0	Random schedule	0.00	0.00	0.00	1.69
n16_p0	Scan-4	50.05	50.00	50.15	9.44
n16_p1	Cache-2	100.00	100.00	100.00	16.00
n16_p1	Exact	100.00	100.00	100.00	16.00

Appendix

Table 11

Condition	Controller	Success (%)	Low	High	Calls
p0	Next-use-2	0.05	0.00	0.15	5.05
p0	Cache-2	0.00	0.00	0.00	2.98
p0	Cache-4	50.00	50.00	50.00	9.66
p0	Residue-8	100.00	100.00	100.00	16.00
p0	Precomputed plan	100.00	100.00	100.00	16.00
p0	Stale-8	0.00	0.00	0.00	4.20

Appendix

Table 12

Condition	Controller	Success (%)	Low	High	Calls
p0_shock0	Cache-2	0.29	0.05	0.59	2.85
p0_shock0	Exact	100.00	100.00	100.00	8.00
p0_shock0	Scan-4	50.68	50.34	51.12	5.18
p0_shock0	Uniform	0.00	0.00	0.00	1.25
p0_shock1	Cache-2	0.00	0.00	0.00	2.25
p0_shock1	Exact	0.00	0.00	0.00	2.25

Appendix

Table 13

Condition	Controller	Success (%)	Low	High	Calls
r0_p0	Cache-2 + eliminate	0.29	0.05	0.59	2.85
r0_p0	Scan-1 + eliminate	0.29	0.10	0.54	1.64
r0_p0	Uniform	0.00	0.00	0.00	1.25
r0_p0	Eliminate	0.00	0.00	0.00	1.25
r0_p1	Cache-2 + eliminate	100.00	100.00	100.00	8.00
r0_p1	Scan-1 + eliminate	0.29	0.10	0.54	1.64

Appendix

Table 14

Condition	Controller	Success (%)	Low	High	Calls
balanced_additive	Next-use-2	0.05	0.00	0.15	5.05
balanced_additive	Cache-2	0.00	0.00	0.00	2.98
balanced_additive	Exact	100.00	100.00	100.00	16.00
balanced_additive	Stale-8	0.00	0.00	0.00	4.20
balanced_static	Next-use-2	0.05	0.00	0.15	5.05
balanced_static	Cache-2	0.00	0.00	0.00	3.04

Appendix

Table 15

Condition	Controller	Success (%)	Low	High	Calls
b2	Exact	100.00	100.00	100.00	8.00
b2	Indexed	100.00	100.00	100.00	8.00
b2	Scan-1	100.00	100.00	100.00	8.00
b2	Sham-check-4	100.00	100.00	100.00	8.00
b2	Scan-2	100.00	100.00	100.00	8.00
b2	Fixed-check-4	100.00	100.00	100.00	8.00

Appendix

Table 16

Condition	Controller	Success (%)	Low	High	Calls
reverse0_p0	Cache-2	0.29	0.05	0.59	2.85
reverse0_p0	Exact	100.00	100.00	100.00	8.00
reverse0_p0	Random schedule	0.00	0.00	0.00	1.29
reverse0_p0	Scan-4	50.68	50.34	51.12	5.18
reverse0_p1	Cache-2	100.00	100.00	100.00	8.00
reverse0_p1	Exact	100.00	100.00	100.00	8.00

Appendix

Table 17

Agent Failure Analysis

Agent failure analysis studies how and why AI agents make errors, traces causes through execution, and helps detect or prevent recurrence.

See all 157 papers

Aug 20, 2026

One Success Isn't Reliability: Thinkingbox, a Sandbox and Benchmark for Agents in Stateful Business Workflows

Recent agent benchmarks increasingly ground evaluation in executable environments, from code repair to web navigation, app APIs, and function calling. Yet completing consequential work beyond code requires more than producing a plausible response or valid tool call: agents must gather missing information over multiple turns, follow domain policies, coordinate dependent tools, and realize the correct persistent state transition without collateral effects. In this paper, we introduce Thinkingbox, a sandbox for tool-agent-user interaction that provides isolated MCP-compatible tool sessions, complete execution traces, and outcome evaluation over terminal backend state. Built on this sandbox, Thinkingbox-bench contains 507 policy-conditioned workflows across business scenarios, including retail, hospitality, auto insurance, neobank internal IT, and consulting IT/HR support. Each attempt is evaluated by task-specific executable checks that accept valid trajectories while rejecting wrong, missing, or extra effects; designated tasks additionally check required properties of the final response. Our experiments reveal that even the strongest proprietary and open-weight models show steep reliability drops: Claude Opus 5 falls from 66.50% pass@1 to 47.53% pass^20, and Kimi-K3 from 57.37% pass@1 to 17.60% pass^20. Moreover, many failed trials terminate cleanly after valid state-changing actions, so response- or tool-call-level signals poorly proxy end-to-end completion. Thinkingbox-bench reveals a large gap between occasionally finding a successful trajectory and reliably completing stateful business tasks. We release Thinkingbox, Thinkingbox-Bench, and Thinkingbox-integrated reinforcement learning framework.

Zhuochun Li, Youngmin Ko, Ali Keramati +11

University of Pittsburgh · Northwestern University · University of California, Irvine +2

Business Process Automation AI Agent Benchmarks Tool-Using Agents LLM Agent Reliability Agent Benchmarks

Ask PDF

Apr 17, 2026

Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Multi-Agent Workflows

Long-horizon tool-using tasks sometimes benefit from revisiting earlier subtasks for recovery and exploration, but added multi-agent workflow flexibility can also introduce coordination overhead and substantial inference cost. We study complete cyclic subtask graphs, a deliberately maximally flexible multi-agent architecture in which executable subtask nodes are fully connected and a unified state-analysis-and-routing agent selects transitions using natural-language criteria. This makes unrestricted revisitation explicit and directly analyzable at the subtask level. We evaluate task-specific (Spec-Cyc) and benchmark-generic (Gen-Cyc) graphs on TextCraft, ALFWorld, and Finance-Agent, with ablations over planner/executor/router strength, tool exposure (generalist vs specialized),

n

-shot successful trajectory summaries, and fault-injected random subtask perturbations. The benchmarks expose three distinct regimes. ALFWorld highlights a setting where explicit revisitation supports recovery and exploration; TextCraft, a largely prerequisite-chain domain, often favors the efficiency of simpler forward execution; and Finance-Agent remains bottlenecked by retrieval, grounding, and evidence synthesis more than by workflow flexibility alone. Shared-win token comparisons further show that the added flexibility can be substantially more expensive than a single ReAct agent. Overall, we use complete cyclic subtask graphs as a maximally flexible experimental lens for measuring when multi-agent revisitation helps, when it mainly adds coordination cost, and when external task bottlenecks dominate.

Luay Gharzeddine, Samer Saab

1Dept of Computer Science, Lebanese American University. · 2*Dept of Electrical and Computer Engineering, Lebanese American University.

Multi-Agent Coordination Multi-Agent Orchestration LLM Agent Workflow Optimization AI Agent Benchmarks Tool-Using Agents Graph-Based Planning+1

Ask PDF

Sep 26, 2026

Dude, Where's My State? Execution Information Requirements for Stateful Agents

Long-running agents must preserve information that later steps depend on. We introduce the Execution Information Requirement (EIR), a lower bound on the information that must remain accessible for correct completion under specified task and access conditions. We develop LACUNA, a framework that generates tasks with known dependencies and varies information demand, retention, and recovery separately from the difficulty of individual operations. Across four models, restoring a missing result raises accuracy on affected recall steps to 100%, compared with 0% for equal-length irrelevant information. Sufficient storage alone does not ensure success: retention policies can discard required results, errors can propagate through later computations, and agents can stop before recovery is complete. We also introduce VESTIGE, which uses agent execution traces to construct semantic graphs and measure information demand for real tasks. Across 72,562 software-agent trajectories, VESTIGE reveals a steeper distance-related decline in solution-relevant rereading for failed runs (RR 0.951 per distance doubling), while adjusted peak demand alone is not associated with failure. Together, these contributions support evaluating whether agents preserve and recover the information their tasks require.

Nikita Mehrotra, Ashish Tiwari, Priyanshu Gupta +1

Software Engineering Agents Long-Horizon Agent Evaluation AI Agent Benchmarks State Tracking Agent Memory Management

Ask PDF

Abstract

Agent Failure Analysis

Explore similar work

One Success Isn't Reliability: Thinkingbox, a Sandbox and Benchmark for Agents in Stateful Business Workflows

Complete Cyclic Subtask Graphs for Tool-Using LLM Agents: Flexibility, Cost, and Bottlenecks in Multi-Agent Workflows

Dude, Where's My State? Execution Information Requirements for Stateful Agents