Beyond LLM-Based Reasoning: Lightweight GNNs for Agent Failure Attribution

Ting-Wei Li; Yuanchen Bei; Xiao Lin; Hanghang Tong

Source-linked AI summary

Beyond LLM-Based Reasoning: Lightweight GNNs for Agent Failure Attribution

Ting-Wei Li, Yuanchen Bei, Xiao Lin, Hanghang Tong

arXiv:2608.18575v1Aug 19, 2026cs.CL

TL;DR

Agent failure attribution in multi-agent LLM systems is difficult and existing LLM-based solutions are costly. AFANet instead uses lightweight graph modeling of interaction trajectories, achieving competitive or superior performance with minimal computational cost and robustness across architectures. The findings suggest structured interaction modeling can suffice for effective attribution.

Problem
Agent failure attribution must identify faulty agents and error types in failed multi-agent trajectories, while existing LLM-based approaches face substantial computational and architectural overhead.
Method
AFANet represents multi-agent conversations as heterogeneous graphs using turn-level semantic signals and temporal and intra-agent structural relationships.
Results
AFANet achieves competitive or superior performance to LLM-based methods with minimal computational cost, while remaining robust across GNN architectures and benefiting from inexpensive test-time adaptation.
Takeaways & Limitations
Structured modeling of agent interactions can provide effective failure attribution without heavy generative LLM reasoning.
Takeaways & Limitations
Generalization across substantially different multi-agent settings remains challenging under distribution shift.

Abstract

from arXiv · show

Large language model (LLM)-based multi-agent systems (MAS) often exhibit complex failure modes, which frequently cause agents to produce incorrect outcomes. This motivates the task of Agent Failure Attribution: given a failed multi-agent trajectory, identify the faulty agents and their corresponding error types. Existing approaches predominantly rely on LLMs to perform failure attribution, either through direct prompting, fine-tuning on synthetic data or complex agentic pipelines. While effective, these methods incur substantial computational overhead due to long-context processing, expensive post-training and handcrafted workflows. Moreover, empirical evidence shows that even state-of-the-art models achieve limited accuracy on existing benchmarks, suggesting that scaling model size alone is insufficient. In this work, we revisit this task and question the necessity of such expensive generative solutions. We introduce AFANet, a lightweight graph-based framework that models interaction trajectories through step-level semantic signals and agent-level relationships. We show that with significantly fewer parameters and near-zero inference cost, AFANet (i) matches or outperforms LLM-based baselines, including fine-tuned models on in-domain benchmarks, (ii) maintains robust performance across different GNN architectures and (iii) can be further improved with inexpensive test-time adaptation on the OOD benchmark. Our results suggest that effective agent failure attribution does not require heavy LLM reasoning and a lightweight, structured approach can achieve strong performance.

1 Introduction

The introduction frames Agent Failure Attribution as necessary because errors can propagate across interacting agents, while existing LLM-based solutions impose substantial computational costs. It proposes AFANet, a lightweight GNN that uses turn-level semantics and agent-level structure to attribute failures efficiently.

Problem setting: Errors introduced by one agent can propagate through subsequent interactions and produce incorrect multi-agent outcomes, motivating Agent Failure Attribution.AFA identifies faulty agents and their error types in failed multi-agent trajectories.
Main claim: AFANet can achieve similar or better performance against LLMs while incurring significantly lower training and inference cost.The comparison includes base Qwen-2.5-7B/14B-Instruct models and their SFT and subsequent GRPO variants.
Limitations of prior work: Existing methods formulate failure attribution as generative reasoning through prompting, synthetic-data fine-tuning, or multi-stage agentic pipelines.These approaches improve performance but incur substantial computational overhead.
AFANet: AFANet replaces expensive LLM reasoning with a lightweight GNN that models interaction trajectories using step-level semantic signals and agent-level relationships.Its graph message passing integrates turn-level semantics with temporal and intra-agent dependencies.
AFANet: AFANet represents failed multi-agent trajectories as conversation graphs containing turn-level textual features and temporal or agent-level connections.The resulting graph is passed to AFANet for agent-failure prediction.

2 Preliminaries

The paper models a multi-agent system as agents generating a stepwise interaction trajectory for a query, with a verifier determining task success or failure. Agent Failure Attribution then predicts which agent–error-type pairs contributed to a failed trajectory.

System and trajectory formulation: A multi-agent system contains M LLM-based agents and produces a trajectory T of selected agents and generated content for query q.At step t, agent a_it ∈ A is selected and generates content x_t ∈ X.
System and trajectory formulation: An outcome verifier maps each trajectory and query to o ∈ {0, 1}, denoting task failure or success, respectively.The verifier is defined as o = g(T, q).
Agent Failure Attribution: For a failed trajectory, AFA predicts a subset of agent–error labels Y ⊆ A × E, where each pair identifies an agent and an error type contributing to failure.The predefined error set E contains K error types, and AFA is formulated as multi-way classification for each agent.

3 Methodology

AFANet attributes agent failures by representing multi-agent conversations as heterogeneous turn-level graphs that combine semantic, deviation, and statistical signals. It propagates information through flexible GNN layers, pools turn representations to agents, and jointly predicts fault status and error types.

Graph construction: AFANet models each multi-agent conversation as a heterogeneous graph whose turn-level nodes connect temporal progression with intra-agent dependencies.The graph captures both sequential structure and long-range consistency among turns produced by the same agent.
Turn representations: Each turn combines deviation features from TF-IDF and truncated-SVD representations, statistical features, and dense semantic embeddings from pretrained sentence encoders.The resulting feature dimension is d = ddev + dstat + ddense.
AFANet architecture: AFANet projects turn features into a hidden space, applies residual message passing with L GNN layers, and supports GCN, GAT, or GraphSAGE architectures.Agent representations concatenate mean-pooled and max-pooled turn representations before prediction.
AFANet architecture: The prediction head maps each pooled agent representation to K +1 classes, covering the clean class and distinct error types.Class 0 denotes no error, while classes 1, . . . , K −1 represent different error types.
Learning and inference: AFANet jointly optimizes weighted agent-level fault detection and error-type classification, then decodes predictions using threshold-based or ranking-based inference.Thresholds are selected on validation data to maximize agent-level and error-level metrics.

4 Experiment

Experiments show that AFANet matches or outperforms LLM-based baselines while requiring substantially fewer computational resources. Its performance remains robust across GNN architectures, benefits from both relational and feature components, and can be improved through lightweight test-time adaptation under distribution shift.

Main results: AFANet achieves competitive or superior average performance against pretrained, post-trained, and proprietary LLM baselines across in-domain and OOD datasets.It is particularly effective on pair-level attribution, the most challenging setting requiring both faulty-agent and error-type identification.
Efficiency: AFANet substantially reduces training time, inference time, trainable parameters, and preprocessing cost compared with LLM-based counterparts.Preprocessing consists of conversation-graph construction across the train, validation, and test splits.
Backbone sensitivity: AFANet maintains relatively stable performance across GNN architectures and layer configurations, indicating architectural robustness.The reference model uses a 2-layer GCN with both edge types.
Ablation: Removing all edges, either edge type, deviation/statistical features, or the GNN module degrades performance, showing that structure and feature components provide complementary signals.Deviation/statistical features are especially important for pair-level metrics, while temporal and same-agent edges capture complementary interaction patterns and behavioral consistency.
Generalization study: Lightweight entropy-minimization test-time adaptation is evaluated to improve AFANet’s OOD performance without retraining or additional supervision.The study considers Agent-level, Pair-level, and Faulty-agent pair-level adaptation objectives on Who&When.

5 Related Work

Prior agent failure attribution work uses direct LLM prompting, synthetic-data finetuning, or increasingly structured agentic frameworks. These approaches improve trajectory analysis but incur inference, training, or workflow complexity.

Direct prompting: Direct-prompting methods analyze long interaction trajectories with pretrained LLMs, but require costly inference and carefully designed prompts.These approaches frame failure attribution as a reasoning task over execution logs.
Finetuning-based methods: Finetuning-based methods train specialized attribution models on synthetic faulty trajectories generated through error injection, counterfactual replay, or graph-guided synthesis.They subsequently use supervised fine-tuning and reinforcement learning, introducing significant training-cost overhead.
Agentic systems: Agentic systems combine sophisticated prompting, structured representations, and memory mechanisms to capture inter-agent dependencies and reuse observed failure patterns.Representations include causal graphs, hierarchical context models, and complex patterns.

6 Conclusion

The paper shows that strong agent failure attribution does not require heavy generative approaches. AFANet uses lightweight graph-based modeling of interaction trajectories to achieve competitive or superior results at minimal computational cost.

6 Conclusion: AFANet models interaction trajectories with step-level signals and agent-level structure.This is the framework’s lightweight graph-based approach.
6 Conclusion: AFANet achieves competitive or superior results against LLM-based methods.The conclusion attributes these results to structured modeling rather than heavy generative approaches.
6 Conclusion: The findings indicate that structured agent-interaction modeling can support effective failure attribution with minimal computational cost.This conclusion directly challenges the necessity of expensive generative solutions.

A Graph construction

The graph construction represents conversation turns with normalized TF-IDF features reduced to compact dense embeddings, then augments them with behavioral, semantic, numerical, positional, length, and structural statistics. These features capture deviations, consistency, alignment, and participation patterns at the turn and agent levels.

TF-IDF and dimensionality reduction: Each conversation is converted into row-wise ℓ2-normalized turn-level TF-IDF representations over a local vocabulary built from lowercased, tokenized turns.The resulting matrix is XTF-IDF ∈RT ×|V|, with T turns and |V| vocabulary terms.
TF-IDF and dimensionality reduction: Truncated SVD produces compact r-dimensional representations for each turn, with r = 16 in the implementation.The retained rank r controls the dense feature dimensionality.
Behavioral and semantic features: Behavioral features measure sequential, self, consensus, cross-agent, and internal-agent deviations or consistency using cosine-based comparisons.These comparisons relate each turn to the preceding turn, the same agent’s history, the conversation centroid, other agents, and same-agent turns.
Behavioral and semantic features: Additional semantic and lightweight numerical features capture same-agent temporal consistency, vocabulary stability, problem alignment, numeric-token presence, and word-length statistics.Problem alignment compares a turn with the initial problem statement, while vocabulary stability compares token overlap within the same agent’s remaining turns.
Position, length, and structural features: Position, length, and structural features encode normalized turn position, boundary indicators, agent-authored turn fractions, token lengths, participation ratios, and participation-position spread.The construction includes binary first/last-turn indicators and conversation-level z-normalized length.

B Dataset Details

The section specifies that both datasets are MIT-licensed and summarizes the dataset size statistics used in the experiments.

Licensing: Both datasets are released under MIT licenses.The passage states that the two datasets share this licensing arrangement.
Dataset statistics: The experiments use dataset size statistics summarized in Table 6.The provided table is identified as reporting dataset size statistics used in the experiments.
Dataset statistics: Table 6 presents the dataset size statistics for the experimental datasets.The table caption identifies its contents but provides no individual values in the supplied passage.

C Error Types

The paper adopts a 14-type taxonomy for agent failure attribution from prior work. The listed failures span specification issues, inter-agent misalignment, and task verification failures.

C Error Types: The taxonomy contains 14 agent failure types, adopted from prior work.This taxonomy structures the failure-attribution task around predefined error categories.
C Error Types: Specification issues include task or role specification deviation, redundant steps, removed conversation history, and removed termination conditions.These are labeled FM-1.1 through FM-1.5.
C Error Types: Inter-agent misalignment includes repeating handled tasks, ambiguous requests, goal deviation, hidden information, ignored agents, and inconsistent reasoning.These are labeled FM-2.1 through FM-2.6; the passage also introduces task verification failures with premature termination as FM-3.1.

D Test-Time Adaptation for AFANet

AFANet’s test-time adaptation minimizes three entropy-based objectives for agent-level, pair-level, and selected faulty-agent pair predictions. It updates only LayerNorm affine parameters for 30 Adam steps on the unlabeled OOD batch, using the final checkpoint for evaluation.

Test-Time Adaptation: AFANet defines separate entropy-minimization losses at the agent and pair levels.Agent-level adaptation uses faulty-agent logits a_i with p_i = σ(a_i), while pair-level adaptation represents clean and error-type classes in s_i ∈ R^{K+1}.
Test-Time Adaptation: Faulty-agent pair-level minimization estimates k faulty agents and selects the top-k agents by faulty-agent logits a_i.The selected agents are used to form the adaptation objective for faulty-agent pair predictions.
Test-Time Adaptation: Only LayerNorm affine parameters are updated while all other AFANet parameters remain frozen.The three losses are minimized jointly during test-time adaptation.
Test-Time Adaptation: 30 Adam gradient steps with learning rate 1e−3 are applied over the entire unlabeled OOD batch.No OOD labels are used, and the final checkpoint is used for evaluation.

E Limitation • · F Impact Statement

AFANet shows some robustness under distribution shift, but generalization to substantially different multi-agent settings and failures requiring deeper semantics or long-horizon reasoning remains challenging. The paper identifies customized graph propagation and hybrid graph–LLM reasoning as future directions, while highlighting no societal consequence requiring emphasis.

E Limitation •: AFANet’s OOD generalization remains challenging across substantially different multi-agent settings.The framework demonstrates certain robustness under distribution shift, but this does not extend reliably to substantially different settings.
E Limitation •: Future work could design customized message passing operators to better capture failure propagation patterns.The proposed direction targets graph operators specialized to how failures propagate through multi-agent interactions.
E Limitation •: Adaptive graph propagation mechanisms are another proposed route for improving cross-setting generalization.The paper specifically suggests adapting graph propagation to better model failure propagation patterns.
E Limitation •: Lightweight structural modeling may be insufficient for failures requiring deeper semantic understanding.The limitation applies to failures beyond the studied attribution scenarios’ structural requirements.
E Limitation •: Failures requiring long-horizon reasoning remain a limitation of the lightweight approach.The paper identifies deeper semantics and long-horizon reasoning as capabilities that some failures may still require.
E Limitation •: Combining graph-based modeling with LLM reasoning is proposed to jointly leverage structural consistency and semantic inference.This hybrid direction is intended to address the lightweight framework’s limited reasoning capability.
F Impact Statement: The paper discusses advances in Large Language Model and Graph Machine Learning research.This statement frames the work’s broader research areas without identifying a specific impact claim.
F Impact Statement: The authors note potential societal consequences but identify none requiring emphasis.The impact statement explicitly says that no potential societal consequence must be highlighted.

NeurIPS Paper Checklist

The checklist indicates that the paper’s stated contributions are supported by the introduction and experiments, while emphasizing reproducibility, statistical reporting, compute disclosure, and societal-impact discussion. It also outlines expectations for clearly stated limitations, assumptions, and access to code and data.

Claims: The paper answers [Yes] on claims alignment, stating that its four main contributions are supported by the introduction or experiment sections.The abstract and introduction should accurately state contributions, assumptions, limitations, and expected generalization.
Limitations and assumptions: The checklist expects authors to discuss limitations, strong assumptions, and robustness to violations of those assumptions.It encourages a separate “Limitations” section and clarification of assumptions such as independence, noiselessness, model well-specification, and local asymptotic validity.
Experimental reproducibility: Experiments should be reproducible through clear algorithm or architecture descriptions and an available path to reproduce or verify results.For closed-source models, researchers should still have some access path for reproduction or verification.
Open access to data and code: Code and data instructions should specify the exact command, environment, data-access and preparation steps, and scripts needed to reproduce experimental results.The checklist permits [No] for open access in some cases, provided the contribution does not centrally depend on an open-source benchmark.
Statistical significance and compute: Results supporting the paper’s main claims should include error bars, confidence intervals, or statistical significance tests with clearly identified sources of variability.The checklist also asks authors to report worker types, resources, per-run compute, total compute, and additional project compute.
Broader impacts: The paper should address potential positive and negative societal impacts, including malicious uses, fairness concerns, and risks from released models or scraped datasets.High-risk models should include safeguards such as usage restrictions, access controls, or safety filters.