Source-linked AI summary
Adaptive Influence Graphs for Failure Attribution in Multi-Agent Systems
Yarden Bakish, Amir Dudai, Roy Ganz, Oren Nuriel, Elad Ben Avraham, Mor Shpigel Nacson, Ron Litman
TL;DR
Multi-agent failure attribution remains difficult because engineers must diagnose long, interleaved traces. The paper introduces Adaptive Influence Graphs, which adaptively construct and navigate evidence-grounded graphs, and reports improved attribution with a new state of the art on Who&When.
Problem
Failure diagnosis in increasingly complex multi-agent executions still largely requires engineers to inspect long, interleaved logs to identify the responsible agent and decisive error step.
Method
AIGs use a builder to adaptively construct a structured influence graph and a reader to navigate it while verifying graph claims against the original log.
Results
55.20% exact step accuracy on Algorithm-Generated Who&When establishes a new state of the art, improving over the previous best of 51.60%.
Takeaways & Limitations
The findings support that failure attribution depends on both the diagnosing model and how the trace is represented and traversed.
Takeaways & Limitations
Whether the representation ladder transfers to other multi-agent frameworks and task distributions remains open.
Abstract
from arXiv · showhide
Multi-agent LLM systems are increasingly deployed in real-world applications, where failures can be costly and difficult to localize. Despite growing efforts to automate failure attribution, diagnosing failed runs still largely relies on human engineers. Yet engineers rarely debug complex systems by reading raw logs end to end. Instead, observability tools organize traces around components, actions, and dependencies to support targeted navigation. We hypothesize that modern LLMs can benefit from the same paradigm. To test this hypothesis, we introduce Adaptive Influence Graphs (AIGs), a two-stage agentic framework that first transforms a failed trace into a structured graph and then navigates it to identify the critical error. Across multiple models, we show that richer trace representations consistently improve failure attribution, with adaptive graph construction and agent-directed traversal yielding the strongest results. AIGs establish a new state of the art on Who&When, the standard benchmark for multi-agent failure attribution. This affirms our hypothesis that attribution depends not only on the diagnosing model, but also on how the trace is represented and explored.
1 Introduction
The paper frames multi-agent failure attribution as both a reasoning and trace-interface problem. It introduces Adaptive Influence Graphs to adaptively structure failed traces and navigate them for critical-error identification.
- Motivation: Human engineers must inspect long, interleaved logs to identify the first error in increasingly complex multi-agent executions.The paper argues that automated diagnosis is needed for scalable development and deployment.
- Task: Failure attribution identifies the failure-responsible agent and decisive error step in a failed execution.
- Hypothesis: Attribution depends not only on the diagnosing model, but also on how the trace is represented and traversed.The same reader can misattribute a failure from a raw log but identify the critical step from a structured graph.
- Evaluation Design: The study compares raw logs, structured logs, influence graphs, and adaptive influence graphs while holding the reader fixed for the representation ladder.The adaptive graph uses an agentic builder, and a critic–refiner audits its structural and semantic consistency.
- Results: 55.20% exact step accuracy is achieved with adaptive graph construction and agent-directed traversal, compared with 46.40% on raw logs.The result surpasses the previous best reported result of 51.60% on the Algorithm-Generated partition.
- Contribution: AIGs are introduced as a two-stage agentic framework that constructs an influence graph and traverses it while verifying evidence against the original log.
2 Related Work
Prior work improves attribution either by changing the reasoning procedure or by restructuring traces with predefined representations. The paper positions AIGs against this fixed-interface pattern and draws inspiration from trace observability systems.
- Failure Attribution: Prior attribution methods primarily improve reasoning procedures applied to execution traces through multi-stage diagnosis and related inference strategies.
- Trace Restructuring: Another line of work restructures traces into canonical records, dependency representations, causal graphs, or learned feature sequences before attribution.
- Research Gap: Existing structured approaches generally use construction policies fixed in advance through predefined record types, node boundaries, or hierarchies.
- Trace Observability: Observability platforms present execution traces as hierarchical, filterable objects with nested spans, searchable attributes, and expandable trees.AIGs adapt this practice of targeted trace navigation to automated failure attribution.
3 Method
AIGs separate graph construction from graph reading: a builder creates a step-grounded representation, a critic–refiner checks it, and a reader navigates graph dependencies while consulting the original log.
- Problem Formulation: A failed trajectory is a sequence of agent actions and emitted log contents, and attribution predicts the agent and step that first derailed correct task solving.The evaluation measures exact agent accuracy and exact step accuracy.
- Pipeline: A builder constructs graph G from the query and trajectory, while a reader uses tools to produce an attribution over the agent and step.The stages are coupled because the reader can access referenced log entries on demand.
- Structured Logs: Structured logs group consecutive steps from the same agent into nodes while preserving the original evidence.This isolates the effect of making execution structure explicit without adding semantic abstraction.
- Influence Graphs: Influence Graphs enrich a fixed node partition with summaries, inputs, outputs, authorship, and sparse inheritance edges.Edges represent downstream reuse of earlier work and are omitted when unsupported causal links could mislead the reader.
- Adaptive Influence Graphs: Adaptive Influence Graphs jointly determine node boundaries, node roles, abstractions, and inheritance topology for each trace.An agentic builder interleaves trace inspection with graph construction using dedicated tool families.
- Graph Representation: Every graph node is grounded in one or more raw-log steps and assigned a type whose required fields define its representation.
- Validation: A critic–refiner loop checks connectivity, acyclicity, root and sink constraints, and semantic faithfulness to referenced log steps.The refiner applies minimal edits for at most R rounds or until no violations remain.
- Agentic Reading: The agentic reader starts from a candidate node, follows incoming inheritance edges backward, and shifts blame only when the raw log confirms the edge’s claimed downstream error.
4 Results
AIGs improve failure attribution across Who&When evaluations, with the strongest gains arising when adaptive graph construction is combined with agent-directed traversal. The method reaches state-of-the-art performance on the Algorithm-Generated partition, while results vary across partitions and models.
- Who&When Benchmark Results: 55.20% step accuracy on the Algorithm-Generated partition exceeds the previous best of 51.60% by 3.6 percentage points.AIGs also achieve 71.20% agent accuracy without ground-truth access at inference time.
- Who&When Benchmark Results: AIGs remain competitive across models, reaching 54.76% with GPT-5.6-sol, 53.97% with Sonnet-4, and 53.17% with DS-V3.2.All three results surpass the previous best, and matched-model advantages hold against CHIEF and RAFFLES.
- Who&When Benchmark Results: 29.31% step accuracy on the Hand-Crafted partition matches A2P and CHIEF for the highest result without ground-truth access.Agent accuracy is lower than CHIEF’s on this partition: 63.79% versus 72.41%.
- The Interface Ladder: 46.40% to 48.80% to 52.00% step accuracy shows progressively richer trace representations improve attribution before traversal is added.The ladder compares raw logs, structured logs, and Influence Graphs while holding Opus-5 fixed.
- The Interface Ladder: 55.20% step accuracy is achieved when agent-directed traversal reads the adaptive graph, compared with 50.40% when the same graph is flattened into one prompt.Traversal directs the reader toward relevant evidence and supports selective verification against the original log.
5 Analysis
The analysis shows that AIGs construct denser, longer-range representations and that readers use them to focus verification rather than replace it. These complementary builder and reader behaviors are especially helpful for later failures and relaxed localization.
- Where AIGs Improve Attribution: 40.5% exact accuracy on failures at step 5 or later rises from 10.8% with raw-log reading to 40.5% with AIGs.Among incorrect raw-log predictions, 76% still identify the correct agent, pointing to step localization as the main difficulty in that analysis.
- Where AIGs Improve Attribution: 55.20% exact, 64.00% within one step, 78.40% within two, and 84.00% within three are the AIG localization rates across tolerance windows.AIGs lead at every reported window.
- What the Builder Constructs: AIGs average 9.5 nodes and 13.5 edges versus 7.5 nodes and 9.0 edges for fixed Influence Graphs.Their most connected node averages 3.6 outgoing edges versus 1.8, indicating denser and more variable-granularity representations.
- What the Builder Constructs: AIG inheritance links span 3.6 steps on average and 5.6 steps at maximum, versus 3.1 and 4.2 for fixed Influence Graphs.The longer ranges connect upstream actions to multiple downstream consequences rather than merely restating local execution order.
- How the Reader Uses the Graph: 61.3% of executions inspect as their first raw step the step ultimately submitted, while 86.5% investigate multiple raw steps.Only 1.6% commit from the graph alone, so graph navigation focuses evidence gathering rather than replacing verification.
- How the Reader Uses the Graph: The builder exposes action-level and long-range influence structure, while the reader uses it for selective verification over the original log.The two stages therefore play complementary roles in the attribution process.
6 Conclusion
AIGs treat failure attribution as an interface-design problem: an agentic builder constructs a navigable graph, and a reader verifies and traverses it. Enriching trace representation and reading improves attribution and achieves state-of-the-art performance on Who&When.
- AIGs turn failed execution traces into Adaptive Influence Graphs that an independent reader navigates while checking claims against the underlying log.
- 55.20% step accuracy is achieved on the Algorithm-Generated Who&When partition, up from 46.40% with raw logs and establishing a new state of the art.
- The method retains its advantage across the tested model backbones.
- Explicit structure carries much of the gain: structured logs outperform raw transcripts, influence graphs improve further, and adaptive construction with dynamic navigation performs best.
- Failure attribution depends on both the diagnosing model and the interface through which it understands and explores the trace.
Limitations
The evaluation is centered on the Who&When benchmark, so transfer to other multi-agent frameworks and task distributions remains open. The method also incurs additional token cost from graph construction and critique-refinement.
- The representation ladder is evaluated on Who&When, and its transfer to other multi-agent frameworks and task distributions remains open.
- AIGs add a build stage and critic–refiner loop, costing more tokens than raw-log reading.
- The method is best suited to settings where a reliable diagnosis is worth the added overhead.
Ethical considerations
The work is diagnostic and uses publicly available benchmark traces without human subjects, personal data, or user-generated content. Its typed graph representation supports trace-grounded verification by assigning structured roles and step references to nodes.
- Ethical considerations: The study uses publicly available execution-trace data and involves no human subjects, personal data, or user-generated content beyond the benchmarks.
- Ethical considerations: The intended use is diagnostic: helping developers localize the agent and step responsible for a failed multi-agent run.
- Typed Nodes: Typed nodes distinguish workflow roles, with task and conclusion as endpoints and orchestrator and agent representing routing and execution turns.
- Typed Nodes: Every node carries step references, enabling graph fields to be checked against the raw execution trace.
C With-Ground-Truth Results
With ground-truth access during diagnosis, AIG performance does not consistently improve and observed drops remain within sampling noise. The reported table covers the Who&When benchmark and notes model-specific evaluation details.
- Ground-truth access does not consistently help AIGs; observed drops are at most four traces and fall within sampling noise at these sample sizes.
- Table 7 lists node types in the agentic graph, with every node carrying the raw-log steps it covers.
- Table 8 reports Who&When results with ground-truth access at inference time, using author-reported baseline numbers and noting that one Algorithm-Generated log was content-filtered.
D Representation Ablations Across Backbones
Across Opus-5, Sonnet-4, and DS-V3.2, richer trace representations produce the same performance ordering, with AIG strongest and raw transcripts weakest. The size of each gain varies by backbone, but no model reverses the ladder.
- AIGs are strongest, followed by Influence Graphs, structured logs, and raw transcripts across all three backbones.The ordering is consistent even though the magnitude of each step differs.
E IG Example
Influence Graphs and Adaptive Influence Graphs represent failed trajectories as navigable structures built from log steps, abstractions, and inheritance relations. IGs preserve a deterministic node partition, while AIGs compactly reorganize actions for query-specific traversal and verification.
- IG Example: Influence Graphs preserve the deterministic node partition while adding abstractions and inheritance edges over the chain.Each node includes what it did, its input, and its committed artifact alongside the raw content it abstracts.
- IG Example: Sonnet-4 and DS-V3.2 representation-ablation tables evaluate the Algorithm-Generated Who&When partition without ground-truth access.Their tables identify the AIG results in bold.
- IG Example: AIGs merge consecutive steps into action-level nodes and connect reused work across adjacent or separated actions tied to the failure.The resulting graph supports navigation, backtracking, and verification against cited log steps.
- IG Example: Figures 6 and 7 depict typed graph nodes carrying log-step abstractions and inheritance edges that record downstream reuse.The AIG representation is produced by the builder and consumed by the reader.