Source-linked AI summary
From Flat Logs to Causal Graphs: Hierarchical Failure Attribution for LLM-based Multi-Agent Systems
Yawen Wang, Wenjie Wu, Junjie Wang, Qing Wang
TL;DR
LLM-based MASs are fragile, and existing attribution methods struggle to recover causal responsibility from flat, complex execution logs. CHIEF builds a hierarchical causal graph, uses virtual-oracle-guided backtracking and counterfactual screening, and outperforms eight baselines on agent- and step-level accuracy. Its evaluation remains limited to the Who&When benchmark and assumes a single decisive root cause.
Problem
Existing failure-attribution methods treat complex MAS trajectories as flat sequences, limiting their ability to disentangle causal links and responsibility.
Method
CHIEF reconstructs trajectories into a hierarchical causal graph, then applies virtual-oracle-guided backtracking and progressive counterfactual screening.
Results
CHIEF outperforms eight baselines on both agent- and step-level accuracy on the Who&When benchmark.
Takeaways & Limitations
The results highlight causal structure as important for failure attribution in lengthy and unstructured MAS logs.
Takeaways & Limitations
CHIEF is evaluated only on Who&When and assumes a single decisive root cause, leaving cumulative error propagation for future validation.
Abstract
from arXiv · showhide
LLM-powered Multi-Agent Systems (MAS) have demonstrated remarkable capabilities in complex domains but suffer from inherent fragility and opaque failure mechanisms. Existing failure attribution methods, whether relying on direct prompting, costly replays, or supervised fine-tuning, typically treat execution logs as flat sequences. This linear perspective fails to disentangle the intricate causal links inherent to MAS, leading to weak observability and ambiguous responsibility boundaries. To address these challenges, we propose CHIEF, a novel framework that transforms chaotic trajectories into a structured hierarchical causal graph. It then employs hierarchical oracle-guided backtracking to efficiently prune the search space via sybthesized virtual oracles. Finally, it implements counterfactual attribution via a progressive causal screening strategy to rigorously distinguish true root causes from propagated symptoms. Experiments on Who&When benchmark show that CHIEF outperforms eight strong and state-of-the-art baselines on both agent- and step-level accuracy. Ablation studies further confirm the critical role of each proposed module.
1 Introduction
LLM-based MASs are capable but fragile, while existing failure-attribution methods struggle with lengthy, structurally complex logs. CHIEF addresses this by reconstructing trajectories into causal graphs and combining virtual-oracle backtracking with counterfactual attribution.
- LLM-based MASs achieve strong capabilities but can exhibit failure rates up to 86.7% as errors propagate through opaque dependencies.
- Existing attribution methods use direct prompting, repeated trajectory replays, or fine-tuning, but flat-log treatment obscures causal structure and responsibility.
- CHIEF reconstructs chaotic MAS trajectories as hierarchical causal graphs, decomposing tasks and parsing agent behavior into Observation-Thought-Action-Result structures.
- Hierarchical oracle-guided backtracking verifies subtasks with synthesized virtual oracles and prunes the search top-down to locate failure steps.
- Counterfactual attribution progressively screens causal scope, dependency type, and reversibility to distinguish root causes from propagated symptoms.
- 77.59% agent-level and 29.31% step-level accuracy were achieved on the hand-crafted subset, while the algorithm-generated subset reached 76.80% and 52.00%.These results were reported alongside comparisons against eight baselines and ablations of the proposed modules.
2 Related Work
Related work includes hand-crafted and automated MAS construction, alongside failure-attribution methods based on LLM judging, hierarchy, replay, and training. CHIEF instead uses a hierarchical causal graph for one-pass attribution without costly replays or additional training.
- MAS frameworks include hand-crafted systems with predefined procedures and automated systems that optimize agent roles and topologies.
- Agent and tool orchestration introduces fragility because errors propagate through opaque dependencies, motivating automated failure attribution.
- LLM-as-a-Judge methods can yield under 10% accuracy on lengthy logs, while hierarchical consensus methods may confuse visible symptoms with hidden root causes.
- Spectrum-based FAMAS uses repeated replays for statistical attribution, incurring high costs on long trajectories.
- CHIEF reconstructs a hierarchical causal graph to support efficient one-pass reasoning without costly replays or additional training.
3 Problem Formulation
Failure attribution identifies the agent-step pair responsible for a failed MAS trajectory. The formulation defines decisive errors counterfactually and selects the earliest such error as the root cause.
- The MAS follows a turn-based protocol in which one active agent acts at each timestep, producing a trajectory with a binary success or failure outcome.
- Failure attribution seeks the specific agent-step pair that caused a failed trajectory.
- A decisive error is an agent action whose counterfactual correction changes the trajectory outcome from failure to success.
- A trajectory may contain multiple decisive errors because errors propagate through execution.
- The root cause is defined as the earliest decisive error in the temporal sequence.
4 Method
CHIEF converts flat MAS trajectories into a hierarchical causal graph, then uses oracle-guided backtracking and counterfactual screening to identify root causes rather than propagated symptoms.
- Overview: CHIEF structures failure attribution into graph construction, hierarchical oracle-guided backtracking, and counterfactual attribution.The three phases parse trajectories, identify candidates top-down, and distinguish root causes from propagated symptoms.
- Hierarchical Causal Graph Construction: The Hierarchical Causal Graph models latent execution topology through subtasks, agents, and dependency edges.It represents environmental feedback, planning, execution, agent interactions, and data/control dependencies that are obscured in flat logs.
- Hierarchical Causal Graph Construction: Subtasks are generated with RAG-based task decomposition and refined through trajectory-aligned reflection to match the raw execution flow.Reflection iteratively corrects mismatched subtasks, reducing divergence between the generated plan and the observed trajectory.
- Hierarchical Causal Graph Construction: Agent nodes encode Observation-Thought-Action-Result attributes extracted from raw trajectories by an LLM-based parser.Each agent node represents an atomic agent instance within a subtask.
- Hierarchical Oracle-Guided Backtracking: Virtual oracles define each subtask’s goal, preconditions, key evidence, and acceptance criteria for execution verification.Their generation uses the task instruction, preceding oracles, the remaining trajectory, and retrieved task-decomposition examples.
- Hierarchical Oracle-Guided Backtracking: Top-down backtracking narrows failures from subtasks to agents and steps using semantic evaluation against oracle constraints.The evaluator compares subtask outputs, agent OTAR tuples, and step execution details to identify candidates at progressively finer granularity.
- Counterfactual Attribution: Counterfactual causal screening tests whether a localized error originates locally or propagates from upstream dependencies.When upstream causes exist, CHIEF excludes the observed step and continues through planning-control and data-flow attribution.
5 Experiment Setup
The evaluation uses the Who&When benchmark and compares CHIEF with eight representative approaches under standard agent- and step-level accuracy protocols.
- Dataset: Who&When contains 184 failure logs drawn from algorithm-generated and hand-crafted subsets.The benchmark includes 126 algorithm-generated logs and 58 hand-crafted logs from general-purpose task sources.
- Baselines: CHIEF is compared against eight representative approaches spanning random selection, LLM prompting, fine-tuning, and related paradigms.Prompting baselines include direct, sequential, binary-search, and ECHO-style strategies; fine-tuning baselines include AgenTracer and GraphTracer.
- Metrics: Evaluation reports agent-level accuracy for identifying the responsible agent and step-level accuracy for identifying the exact root-cause step.Results are averaged over three independent runs using a strict top-1 criterion.
- Implementation: CHIEF is implemented in Python 3.11 with DeepSeek-V3.2 (thinking) as the default base LLM.Baselines use official implementations and default configurations where available, with reported results used when reproduction was hindered.
6 Results
CHIEF achieves strong attribution accuracy and cost efficiency across benchmark settings, while ablations show that its graph, oracle-guided search, and counterfactual modules contribute complementary capabilities.
- Main Results: CHIEF surpasses eight baselines across nearly all reported metrics, including direct prompting, hierarchical-context, replay-based, and fine-tuning approaches.FAMAS is the stated exception for hand-crafted-subset step-level accuracy.
- Robustness: CHIEF remains superior under matched settings without ground truth, except for FAMAS’s step-level accuracy, with virtual oracles supplying intermediate supervision.Access to ground truth benefits all methods, but CHIEF remains comparatively stable.
- Cost Efficiency: CHIEF uses 2.5 ∼3× more tokens than direct prompting but 6 ∼8× fewer than spectrum-based FAMAS, while avoiding replay and fine-tuning pipelines.The method performs one-pass causal graph reasoning and has comparable token costs to ECHO.
- Base LLM Impact: Performance varies with the base LLM’s instruction-following and reasoning capabilities, with DeepSeek-V3.2 achieving the highest performance across settings.Gemini-3 leads among closed-source models except for Claude 4.5 on algorithm-generated-subset step accuracy.
- Ablation Study: The full CHIEF configuration outperforms ablations because M1 supplies structure, M2 narrows search, and M3 verifies causes counterfactually.M1 alone yields mixed results on the hand-crafted subset, while either M2 or M3 recovers performance.
7 Conclusion
CHIEF reconstructs flat MAS logs as hierarchical causal graphs and combines virtual-oracle backtracking with counterfactual reasoning for failure attribution. On Who&When, it outperforms eight baselines at both agent and step levels, highlighting the importance of causal structure in lengthy, unstructured logs.
- CHIEF reconstructs flat logs into hierarchical causal graphs and uses virtual-oracle backtracking with counterfactual reasoning for attribution.
- CHIEF outperforms eight baselines on both agent- and step-level accuracy on the Who&When benchmark.
Limitations
CHIEF’s effectiveness depends on accurate hierarchical causal graphs and virtual oracles, while its evaluation and single-root-cause focus remain limited in scope.
- Limitations: CHIEF relies on the fidelity of its hierarchical causal graph and virtual oracles.Hallucinated edges can propagate inaccuracies to the final diagnosis.
- Limitations: Evaluation is limited to the Who&When benchmark, the sole public dataset available.The authors identify broader-system validation as future work.
- Limitations: CHIEF identifies a single decisive root cause, leaving cumulative error propagation for future verification.The benchmark assumes failure results from one decisive cause rather than several minor deviations.
A Details for RAG-based Task Decomposition
The RAG component retrieves semantically similar exemplars and inserts them into prompts as decomposition prototypes to encourage verifiable subtask stages.
- A Details for RAG-based Task Decomposition: The RAG component retrieves similar exemplars and injects them into prompts as decomposition prototypes.The prototypes are intended to encourage verifiable subtask stages.
- A Details for RAG-based Task Decomposition: The knowledge base combines 165 GAIA instances with explicit steps and 33 AssistantBench instances containing implicit sub-goals and verification trails.GAIA entries provide decomposition templates, while AssistantBench entries provide decomposition guidelines.
- A Details for RAG-based Task Decomposition: Retrieval uses cosine similarity over embeddings and inserts two exemplars at both retrieval and final-prompt stages.The number of exemplars is fixed at two for each stage.
- A Details for RAG-based Task Decomposition: GAIA entries concatenate questions with reasoning steps, while AssistantBench entries combine task descriptions with detailed explanations.This normalized plain-text format creates a unified retrievable knowledge base.
B Prompt for OTAR Parsing
The appendix describes prompts that parse execution traces, construct hierarchical dependencies, synthesize virtual-oracle criteria, and progressively localize faults.
- B Prompt for OTAR Parsing: OTAR parsing converts each agent’s trace within predefined subtasks into Observation, Thought, Action, and Result tuples.The prompt requires exact subtask-name matching, active-agent identification, and detailed behavioral breakdowns.
- B Prompt for OTAR Parsing: The knowledge-base construction description and formatting are illustrated in Figure 3.The figure is associated with the OTAR-parsing prompt subsection.
- B Prompt for OTAR Parsing: Retrieved exemplars are injected into the OTAR prompt to support consistent, parseable annotations.The examples include task descriptions and explanation text used as prompt context.
- B Prompt for OTAR Parsing: The OTAR prompt uses a constrained template with sectional directives to standardize annotations across subtasks.Figure 7 provides the prompt template for this parsing process.
- C Prompt for Edge Construction: Subtask and agent edge construction defines edge types and counterfactual patterns for dependencies, collaboration, and error propagation.These prompts model logical progression between subtasks and interactions among agents.
- D Prompt for Oracle Synthesis: Virtual-oracle synthesis uses prior oracle constraints and later unprocessed trajectories to create internally consistent subtask verification criteria.Sequential generation and global self-checking provide intermediate supervision for hierarchical backtracking.
- E Prompt for Hierarchical Backtracking: Hierarchical backtracking evaluates subtasks, agents, and steps sequentially to narrow candidate error nodes.It leverages the causal graph and virtual oracles for coarse-to-fine fault localization.
F Details for Counterfactual Attribution
Counterfactual attribution combines local, planning-control, data-flow, and deviation-aware strategies, with examples distinguishing planner from executor responsibility in cyclic failures.
- Planning-Control Attribution: Planning-control attribution distinguishes cyclic failures caused by persistent planning errors from those caused by abnormal execution.The two examples assign responsibility differently despite both exhibiting cyclic behavior.
- Counterfactual Attribution: The appendix includes an example of hierarchical causal graph structure and prompts for task decomposition and edge construction.The listed figures cover graph construction, subtask-agent edges, step edges, oracle synthesis, backtracking, and counterfactual attribution.
- Planning-Control Attribution: A planner that persists with a failed approach despite repeated failure signals is assigned responsibility for the root cause.In the example, fixation on the deprecated version produces subsequent loops and an incorrect answer.
- Planning-Control Attribution: An executor that ignores repeatedly reasserted constraints is assigned responsibility when planning remains valid and adapts appropriately.The example contrasts reasonable planner strategy shifts with persistent executor misinterpretation.
- Counterfactual Attribution: Counterfactual attribution first tests local origins, then examines planning control and data flow, and finally filters transient deviations.The four strategies are Local Attribution, Planning-Control Attribution, Data-Flow Attribution, and Deviation-Aware Attribution.
- Counterfactual Attribution: The counterfactual-attribution prompt is presented alongside prompts for oracle synthesis and hierarchical backtracking.These prompts correspond to successive stages of the attribution pipeline.