> AgentTrace: Why Structural Graph Features Beat LLMs for Multi-Agent Failure Attribution
Structural causal graph features find root causes in multi-agent LLM failures at 35ms and zero cost, outperforming six LLM prompting strategies even with ground-truth hints. 100% of real traces exhibit chain topology.
// TABLE_OF_CONTENTS
AgentTrace: Structural Root Cause Analysis¶
Core Methodology¶
AgentTrace formalizes multi-agent traces as Multi-Agent Structural Causal Models (MA-SCM): DAGs where nodes are typed agent decisions and edges encode information flows. Root cause ranking uses backward BFS from the error node, scored by structural position features, causal mediation via topological DP in O(V+E), and Halpern-Pearl actual causality with min-cut approximation.
Proposition 1 (Structural Responsibility Degeneracy): On chain topologies, every intermediate node is a cut vertex, so HP responsibility scores are uniform — formal causal reasoning cannot discriminate without functional equations.
Key Results¶
| Method | Agent-Level Accuracy | Cost | Latency |
|---|---|---|---|
| AgentTrace (structural) | 39-54% | $0 | 35ms |
| DeepSeek-V3 + ground truth hint | 43% | API | ~8s |
| Best LLM prompting (6 strategies) | 23% | API | ~2s |
Even with ground truth access, LLMs cannot reliably identify which agent caused the failure.
Chain Topology Universality¶
A census of 297 real traces across five data sources found 100% exhibit chain or near-chain topology. This reflects how current multi-agent systems are architecturally structured (planner → researcher → coder → reviewer → executor).
The Cost-Accuracy Dead Zone¶
A 24,000-graph experiment revealed: adding partial LLM enhancement (~1,500 tokens) hurts performance versus pure structural methods. The choice is binary — either $0 structural scoring or full LLM pipelines consuming 15K+ tokens.
Dataset-Dependent Method Selection¶
| Dataset | Best Method | Accuracy | Why |
|---|---|---|---|
| AgentRx | Linear scorer | 54.0% | High content diversity |
| MAST | Causal scorer | 42.4% | Agent role asymmetry |
| Who&When | Linear+Semantic | 39.0% | Long conversations |
No single scorer dominates. Best method depends on trace structure properties.
Practical Implications¶
- Build causal graphs at instrumentation time, not retroactively via LLM
- Profile trace topology before choosing a scorer
- Avoid the dead zone: either $0 structural or full 15K+ token LLM pipelines
- 35ms at zero cost makes real-time attribution feasible in CI/CD for agent testing