# GraphTracer: Graph-Guided Failure Tracing in LLM Agents for Robust Multi-Turn Deep Search

arXiv: https://arxiv.org/abs/2510.10581 · HTML: https://mlsanity.com/paper/2510.10581/

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2025.

## Built on by (most cited first, 23 of 23)

- [Seeing the Whole Elephant: A Benchmark for Failure Attribution in LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2604.22708/) (2026)
- [DoVer: Intervention-Driven Auto Debugging for LLM Multi-Agent Systems](https://mlsanity.com/paper/2512.06749/) (2025)
- [Rethinking Failure Attribution in Multi-Agent Systems: A Multi-Perspective Benchmark and Evaluation](https://mlsanity.com/paper/2603.25001/) (2026)
- [From Flat Logs to Causal Graphs: Hierarchical Failure Attribution for LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2602.23701/) (2026)
- [CausalFlow: Causal Attribution and Counterfactual Repair for LLM Agent Failures](https://mlsanity.com/paper/2605.25338/) (2026)
- [AutoSaddler: Automatic Harness Optimization with Durable Updates from Agent Execution Traces](https://mlsanity.com/paper/2608.23041/) (2026)
- [FALAT: Tracing Failures in LLM Agent Trajectories via Dependency-Guided Search](https://mlsanity.com/paper/2606.00765/) (2026)
- [SoK: Trust-Authorization Mismatch in LLM Agent Interactions](https://mlsanity.com/paper/2512.06914/) (2025)
- [Tracing Agentic Failure from the Flow of Success](https://mlsanity.com/paper/2607.12747/) (2026)
- [TRAJDEBUG: Tracing Error Lifecycle to Identify Critical Failures in Long-Horizon Agent Trajectories](https://mlsanity.com/paper/2608.06346/) (2026)
- [Beyond Individual Intelligence: Surveying Collaboration, Failure Attribution, and Self-Evolution in LLM-based Multi-Agent Systems](https://mlsanity.com/paper/2605.14892/) (2026)
- [MemTrace: Tracing and Attributing Errors in Large Language Model Memory Systems](https://mlsanity.com/paper/2605.28732/) (2026)
- [VerifyMAS: Hypothesis Verification for Failure Attribution in LLM Multi-Agent Systems](https://mlsanity.com/paper/2605.17467/) (2026)
- [When Only the Final Text Survives: Implicit Execution Tracing for Multi-Agent Auditing](https://mlsanity.com/paper/2603.17445/) (2026)
- [CASPIAN: Online Detection and Attribution of Cascade Attacks in LLM Multi-Agent Systems via Cross-Channel Causal Monitoring](https://mlsanity.com/paper/2605.19240/) (2026)
- [Confidence Laundering in Agent Systems: Why Uncertainty Needs a Latent Carrier](https://mlsanity.com/paper/2606.20662/) (2026)
- [Learning to Recommend Multi-Agent Subgraphs from Calling Trees](https://mlsanity.com/paper/2601.22209/) (2026)
- [ReconMIL: Synergizing Latent Space Reconstruction with Bi-Stream Mamba for Whole Slide Image Analysis](https://mlsanity.com/paper/2603.19925/) (2026)
- [Agent System Operations: Categorization, Challenges, and Future Directions](https://mlsanity.com/paper/2606.01581/) (2026)
- [Diagnosis-Driven Automatic Repair for Agentic Workflow via Symbolic Inference](https://mlsanity.com/paper/2607.02882/) (2026)
- [Beyond LLM-Based Reasoning: Lightweight GNNs for Agent Failure Attribution](https://mlsanity.com/paper/2608.18575/) (2026)
- [Localizing Emergent Failures in Agentic AI: Recovering Minimal Repair Families via Counterfactual Replay](https://mlsanity.com/paper/2608.29228/) (2026)
- [Can Failed Trajectories Reveal Where Agents Go Wrong? Agentic Failure Attribution Without Step-Level Labels](https://mlsanity.com/paper/2610.13105/) (2026)

## Abstract (arXiv)

Multi-agent systems powered by Large Language Models excel at complex tasks through coordinated collaboration, yet they face high failure rates in multi-turn deep search scenarios. Existing temporal attribution methods struggle to accurately diagnose root causes, particularly when errors propagate across multiple agents. Attempts to automate failure attribution by analyzing action sequences remain ineffective due to their inability to account for information dependencies that span agents. This paper identifies two core challenges: textit(i) distinguishing symptoms from root causes in multi-agent error propagation, and textit(ii) tracing information dependencies beyond temporal order. To address these issues, we introduce GraphTracer, a framework that redefines failure attribution through information flow analysis. GraphTracer constructs Information Dependency Graphs (IDGs) to explicitly capture how agents reference and build on prior outputs. It localizes root causes by tracing through these dependency structures instead of relying on temporal sequences. GraphTracer also uses graph-aware synthetic data generation to target critical nodes, creating realistic failure scenarios. Evaluations on the Who&When benchmark and integration into production systems demonstrate that GraphTracer-8B achieves up to 18.18% higher attribution accuracy compared to state-of-the-art models and enables 4.8% to 14.2% performance improvements in deployed multi-agent frameworks, establishing a robust solution for multi-agent system debugging.