GraphTracer: Graph-Guided Failure Tracing in LLM Agents for Robust
  Multi-Turn Deep Search
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: (i) distinguishing symptoms from root causes in multi-agent
error propagation, and (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.
68efc102d22df134b7f5ca27
Heng Zhang
68efc102d22df134b7f5ca28
Yuling Shi
claimed_verified
2025-10-15T16:55:17.600Z
645b0c3ec35da9c7afd95421
https://cdn-avatars.huggingface.co/v1/production/uploads/645b0c3ec35da9c7afd95421/vYBrCDagHsXAo6J2p-uG0.jpeg
Yuling
user
YerbaPage
68efc102d22df134b7f5ca29
Xiaodong Gu
68efc102d22df134b7f5ca2a
Haochen You
68efc102d22df134b7f5ca2b
Zijian Zhang
68efc102d22df134b7f5ca2c
Lubin Gan
68efc102d22df134b7f5ca2d
Yilei Yuan
68efc102d22df134b7f5ca2e
Jin Huang
GraphTracer: Graph-Guided Failure Tracing in LLM Agents for Robust
  Multi-Turn Deep Search
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: (i) distinguishing symptoms from root causes in multi-agent
error propagation, and (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.
GraphTracer addresses multi-agent system failure attribution by constructing Information Dependency Graphs to trace information flow and improve debugging accuracy.
multi-agent systems Large Language Models deep search scenarios temporal attribution information dependencies GraphTracer Information Dependency Graphs failure attribution synthetic data generation Who&When benchmark