Skip to content

AgentTrace: Causal Graph Tracing for Root Cause Analysis in Deployed Multi-Agent Systems

🕒 Published (v1): 2026-03-16 00:46 UTC · Source: Arxiv · Venue: ICLR 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

AgentTrace is a post-hoc root cause analysis framework for deployed multi-agent LLM systems that reconstructs causal graphs from execution logs, traces backward from error nodes via BFS, and ranks candidate root causes using interpretable positional and structural features—without LLM inference at debug time. On 550 synthetic failure scenarios across 10 domains, it achieves 94.9% Hit@1 and 0.97 MRR at 0.12s latency, versus 68.5% Hit@1 for GPT-4 at 8.3s.

Problem

When multi-agent LLM workflows fail in production, cascading effects mean the error manifests far downstream from its origin. Manual log inspection is slow, and existing approaches (LLM self-debugging, distributed tracing for microservices) either require expensive inference calls or ignore the semantic structure of inter-agent message passing. No dedicated, lightweight RCA tool existed for this specific architecture class.

Method

AgentTrace operates in four stages:

  1. Causal graph construction: Parses execution logs into a DAG \(G=(V,E)\) with three edge types—sequential (same-agent consecutive actions), communication (message-send → message-receive across agents), and data dependency (producer → consumer via variable reference tracking).

  2. Backward BFS tracing: From the error node \(v_{\text{error}}\), performs breadth-first backward traversal up to depth \(d=10\) to collect the candidate set \(C\) of ancestor nodes.

  3. Node ranking: Scores each candidate via a weighted sum: $\(\text{score}(v) = \sum_{i \in \{p,s,c,f,e\}} w_i \cdot F_i(v)\)$ Five feature groups: Position (\(w_p=0.70\)), Structure (\(w_s=0.20\)), Content (\(w_c=0.05\)), Flow (\(w_f=0.03\)), Confidence (\(w_e=0.02\)). A total of 17 features; weights determined by grid search on 50 held-out validation scenarios.

  4. No LLM at inference: All features are computed from log metadata and graph topology; LLM inference is used only in baselines.

Key Contributions

  • Formal causal graph model for multi-agent execution traces with three semantically typed edge classes
  • Backward BFS tracing algorithm with configurable depth for candidate set construction
  • A 17-feature, 5-group interpretable scoring function with grid-searched group weights
  • A 550-scenario benchmark spanning 10 domains with systematically injected bugs (5 types) and verified ground-truth root cause annotations
  • Empirical demonstration that positional features alone (Hit@1 = 87.3%) explain most of the signal, with structure adding +5.1 pp

Results

  • AgentTrace: Hit@1 = 94.9%, Hit@3 = 98.4%, MRR = 0.97 (overall, \(n=550\))
  • GPT-4 baseline: Hit@1 = 68.5%, MRR = 0.74; Cohen's \(h=0.77\) vs. AgentTrace (large effect, \(p < 10^{-10}\))
  • Heuristic baselines: Last Node 12.7%, Random 9.1%, First Node 3.6% Hit@1
  • Robustness: Hit@1 ranges 93.6–95.8% across bug types, 93.9–95.5% across trace lengths (8–15 steps), 92.7–96.1% across bug positions
  • Best domain: Legal Document Analysis 100% Hit@1; worst: Financial Trading 90.0%
  • Runtime: 0.12s mean vs. 8.3s for GPT-4 (69Ă— speedup); scales as \(T \approx 12.5n + 5\) ms

Limitations

  • Benchmark is entirely synthetic (550 scenarios); no validation on real production traces
  • Each scenario has exactly one root cause; real failures frequently involve multiple concurrent contributing factors
  • Assumes complete, accurate execution logging—not guaranteed in production
  • Position-feature dominance may reflect a benchmark construction artifact (60% of bugs injected at early steps 2–3)
  • Failure cases include 12/28 with multiple plausible root causes and 8/28 where late-stage bugs caused over-prioritization of early steps

Relevance to Harnesses / Meta-Harnesses

AgentTrace directly addresses a critical operational gap for any multi-agent harness: when an orchestrated pipeline fails, pinpointing where in the agent graph the fault originated is a prerequisite for automated recovery, self-healing, or informed human intervention. A meta-harness that manages multiple sub-agents could integrate AgentTrace as a diagnostic sidecar—consuming the same execution logs already emitted by agent orchestrators (AutoGen, MetaGPT) to trigger targeted reruns from the identified root cause rather than full pipeline restarts. The framework's design—log-driven, LLM-free at runtime, sub-second—makes it suitable for embedding inside a harness's monitoring loop without adding significant latency or cost to the primary execution path.