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

Ting-Wei Li, Yuanchen Bei, Xiao Lin, Hanghang TongarXiv 2026 · arXiv

TL;DR

Instead of using massive, computationally expensive Large Language Models (LLMs) to diagnose why a multi-agent system failed, why not use a graph? This paper introduces AFANet, a lightweight Graph Neural Network (GNN) with just 65K parameters that matches or outperforms state-of-the-art LLMs at Agent Failure Attribution (AFA). By focusing on structural interaction dynamics rather than heavy text generation, AFANet delivers up to a 70x training speedup and a 300x inference speedup.

What Problem Does This Paper Address?

Large language model-based multi-agent systems (MAS) are increasingly used to solve complex tasks through collaboration. However, they fail in complex ways: an error introduced by one agent can propagate through subsequent turns, leading to an incorrect final outcome.

Identifying the root cause—which agent messed up and what specific error type occurred—is known as Agent Failure Attribution (AFA). Currently, the standard approach is to feed the entire interaction log back into a powerful LLM (like GPT-4 or fine-tuned open-source models) to reason out the failure. This creates severe bottlenecks:

  1. Efficiency Bottleneck: Processing long conversation contexts repeatedly is incredibly slow and expensive.
  2. Architectural Complexity: Current pipelines rely on fragile, handcrafted multi-stage prompting workflows.
  3. Systematic Ineffectiveness: Surprisingly, even state-of-the-art reasoning models achieve limited accuracy on this task, sometimes barely beating random baselines.

The authors challenge this paradigm by asking a fundamental question: Is heavy LLM reasoning actually necessary for agent failure attribution?

Methods

The authors propose AFANet, a lightweight framework that treats failure attribution as a structural graph classification problem rather than a generative text problem.

Figure 2: Overall pipeline. Given a failed multi-agent system trajectory, we first transform it into a conversation graph with turn-level textual features and temporal/agent-level connections. The graph will then be passed through our proposed AFANet for agent failure prediction.

The method breaks down into three main steps:

  1. Conversation Graph Construction: Each turn in the multi-agent dialogue becomes a node. The framework connects these nodes with two types of edges:
  2. Temporal edges between consecutive turns to preserve the sequential flow.
  3. Intra-agent edges connecting all turns generated by the same agent to capture long-range behavioral consistency.
  4. Feature Engineering: Instead of relying solely on raw text, each node's features combine:
  5. Semantic features from a compact pretrained sentence encoder (Sentence-BERT).
  6. Statistical features like turn position, token length, and agent participation ratios.
  7. Deviation features computed via TF-IDF and truncated SVD, which explicitly measure how much an agent's current turn mathematically diverges from the rest of the conversation context (acting as an anomaly detector).
  8. GNN Processing & Pooling: Standard GNN layers (like GCN or GraphSAGE) propagate these features across the graph. Turn-level representations are then aggregated using a dual pooling strategy (mean and max pooling) to form agent-level representations, which a simple prediction head classifies into specific error types.

Datasets

The framework was evaluated on two key benchmarks:

  • AEGIS-Bench: Used as the in-domain dataset, featuring a pre-defined split of 7,146 training, 1,787 validation, and 600 test trajectories with complex multi-agent failure annotations.
  • Who&When: Used as an out-of-distribution (OOD) evaluation dataset consisting of 184 test conversations, where exactly one faulty agent is present per trajectory.

Key Insights and Ideas

  • Structure Trumps Heavy Reasoning: Multi-agent failures are often characterized by structural anomalies—sudden shifts in vocabulary, deviations from the conversation consensus, or internal inconsistencies. GNNs are inherently better suited to model these structural dynamics than autoregressive LLMs.
  • Extreme Parameter Efficiency: AFANet achieves its results with only 65,000 trainable parameters, compared to the 7 billion to 14 billion parameters of the LLM baselines it competes against.
  • Unsupervised Test-Time Adaptation (TTA): To handle distribution shifts when moving to out-of-distribution data (like the Who&When dataset), the authors introduced a lightweight test-time adaptation strategy based on entropy minimization. By encouraging the model to make more confident predictions at inference time, it boosts OOD performance without requiring any target labels.

Key Results

AFANet dramatically outperforms LLM baselines in efficiency while matching or exceeding them in accuracy, particularly on the challenging "Pair-level" metric (correctly identifying both the faulty agent and the exact error type simultaneously).

Figure 1: Attribution accuracy and efficiency comparison between our proposed AFANet and LLMs. AFANet can achieve similar or better performance against LLMs while incurring significantly lower training and inference cost. We consider the base models: Qwen-2.5-7B/14B-Instruct, denoted as 7B/14B, respectively. We also include their post-trained variants obtained through SFT (S) and subsequent GRPO training (G), denoted by 7B+S/14B+S and 7B+S+G/14B+S+G.
  • Efficacy: On AEGIS-Bench, AFANet achieved a Pair Micro-F1 score of 17.42%, outperforming a fine-tuned Qwen2.5-14B model (which scored 16.62% with SFT) and beating proprietary models like GPT-4 (7.44%) and Claude 3.5 Sonnet (7.68%).
  • Speedups: AFANet required only 1.1 hours to train on a single V100 GPU, compared to over 3 days for RL-tuned LLMs (a 70x speedup).
  • Inference Efficiency: At test time, AFANet processed the evaluation set in 1.16 seconds, compared to 367 seconds for a 14B LLM—representing a 300x speedup.

Limitations and Future Work

While highly effective, the authors note a couple of key limitations:

  • OOD Generalization: Generalizing across drastically different multi-agent architectures or entirely new domains remains difficult, though test-time adaptation helps mitigate this.
  • Limited Deep Semantic Reasoning: Purely structural and statistical modeling can miss subtle, deeply logical failures that require true semantic understanding of complex code or mathematical reasoning.

The authors suggest that the ultimate future direction lies in a hybrid approach: combining lightweight graph-based structural modeling with targeted LLM semantic inference to get the best of both worlds.

Summary updated

Abstract

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.
BibTeX
@misc{li2026beyond,
  author = {Ting-Wei Li and Yuanchen Bei and Xiao Lin and Hanghang Tong},
  title = {{Beyond LLM-Based Reasoning: Lightweight GNNs for Agent Failure Attribution}},
  year = {2026},
  eprint = {2608.18575},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.18575},
}
Figure