Every Response Counts: Quantifying Uncertainty of LLM-based Multi-Agent Systems through Tensor Decomposition

Tiejin Chen; Huaiyuan Yao; Jia Chen; Evangelos E. Papalexakis; Hua Wei

cs.LGApr 9, 2026

Every Response Counts: Quantifying Uncertainty of LLM-based Multi-Agent Systems through Tensor Decomposition

Authors: Tiejin Chen, Huaiyuan Yao, Jia Chen, Evangelos E. Papalexakis, Hua Wei

Organizations: Arizona State University · University of California, Riverside

Abstract

While Large Language Model-based Multi-Agent Systems (MAS) consistently outperform single-agent systems on complex tasks, their intricate interactions introduce critical reliability challenges arising from communication dynamics and role dependencies. Existing Uncertainty Quantification methods, typically designed for single-turn outputs, fail to address the unique complexities of the MAS. Specifically, these methods struggle with three distinct challenges: the cascading uncertainty in multi-step reasoning, the variability of inter-agent communication paths, and the diversity of communication topologies. To bridge this gap, we introduce MATU, a novel framework that quantifies uncertainty through tensor decomposition. MATU moves beyond analyzing final text outputs by representing entire reasoning trajectories as embedding matrices and organizing multiple execution runs into a higher-order tensor. By applying tensor decomposition, we disentangle and quantify distinct sources of uncertainty, offering a comprehensive reliability measure that is generalizable across different agent structures. We provide comprehensive experiments to show that MATU effectively estimates holistic and robust uncertainty across diverse tasks and communication topologies.

Figures & tables

Figure 1: The overall pipeline of MATU . As shown in the figure, MATU could be applied to multi-agent systems with different communication topologies. We first collect trajectories for a fixed system and task, and then obtain embedding matrices for each trajectory. Then, we form a ragged tensor by stacking all embedding matrices and obtain the reconstructed tensor by conducting CP-2 decomposition. Finally, we use the reconstruction losses from reconstructed tensors with different ranks as the final uncertainty.

Table 2

Methods	GPT-4o		Qwen2.5-7B		Llama3.1-8B
Methods	AUROC	AUARC	AUROC	AUARC	AUROC	AUARC
Dataset: MATH
Eigv(Agre)-final	0.6359	0.6133	0.6506	0.8212	0.6340	0.6059
Eigv(Agre)-Whole	0.6308	0.6115	0.6314	0.8081	0.6215	0.5953
P(true)	0.6226	0.6070	0.6602	0.8291	0.6581	0.6225
SAUP-Single	-	-	0.6261	0.7982	0.6339	0.6008

Table 3: Comparison of our methods with different baselines on various datasets and LLMs on AnyMac Wang et al. (2025) , highlighted with best performance.

Panel of Figure 2 — Figure 2: Results for ablation study and sensitivity study. The results show that our design for MATU and our choices of the hyperparameter are well-suited.

Figure 3: Comparison of MATU and baselines on llama3 and the Humaneval dataset. The results show that MATU can have better results even with tool integration, showing the robustness of MATU .

Method	AUROC ( $\uparrow$ )
SAUP-Single	0.5930
SAUP-Multiple	0.6201
Eigv(Agre)-final	0.6355
MATU	0.6770

Table 4: Uncertainty quantification performance (AUROC) under strict distribution shift (Math prompts on MMLU dataset) using Qwen2.5-7B.

Figure 4: Comparison of backbone selection results. A higher accuracy demonstrates a better selection strategy. The results show that MATU has a superior performance improvement on accuracy, indicating that MATU offers a more robust uncertainty value.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Case Info	Agent Reasoning Trajectories (Key Steps Only)	Uncertainty Quantification
Problem: Find the distance between intersections of $y=x^{2}$ and $x+y=1$ . True Answer: $\sqrt{10}$ System Accuracy: 100% (10/10 runs correct)	Trajectory Type A: Direct & Concise $\bullet$ Determine intersection coordinates $\to$ Calculate distance Assessment: Ideal path, minimal token generation.	SAUP (Baseline): 0.88 (High) Issue: High cumulative entropy from verbose steps. Eigv-Whole (Baseline): 0.35 (Medium) Issue: Long contexts dilute NLI entailment accuracy. MATU (Ours): 0.05 (Low) Result: Correctly aligns semantic intent across diverse paths.
	Trajectory Type B: Self-Correction $\bullet$ Determine coordinates $\to$ Correct y-axis calculation error $\to$ Get correct coordinates $\to$ Calculate distance Assessment: Agent successfully recovers from an error.
	Trajectory Type C: Verbose (High Step Count) $\bullet$ Determine coordinates $\to$ Get coordinates $\to$ … (intermediate steps) … $\to$ Calculate distance Assessment: Logically identical to Type A, but higher step count increases cumulative entropy.

Appendix

Table 5: Case Study on Mathematical Reasoning. Despite diverse communication patterns, all agents consistently reach the correct solution (

\sqrt{10}

). Baselines like SAUP fail due to sensitivity to trajectory length (step count), and Eigv-Whole struggles with long-context entailment. MATU effectively disentangles surface-level variations from semantic stability, correctly assigning low uncertainty.

Uncertainty Quantification

Uncertainty quantification estimates how reliable predictions and scientific inferences are, and how uncertainty propagates into decisions.

See all 651 papers

PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems
Aug 22, 2026Yaokun Liu, Yifan Liu, Daniel Yue Zhang +3Multi-Agent LLM Systems LLM Uncertainty Estimation
University of Illinois Urbana-Champaign · Scale AI
Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems
Oct 6, 2026Tunyu Zhang, Zihao Zhao, Yusong Zhao +5LLM Uncertainty Estimation Multi-Agent LLM Systems
Rutgers University · University of Illinois Urbana-Champaign · Vanderbilt University +1
Semantic Uncertainty-Guided Orchestration in Hierarchical Multi-Agent Systems
Aug 11, 2026John Knowlton, Aritra Guha, Risto MiikkulainenSemantic Uncertainty Estimation Multi-Agent Orchestration
The University of Texas at Austin, USA · AT&T Chief Data Office, USA · Cognizant AI Lab, USA

Aug 22, 2026J/K move · Enter open · S save

PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems

Yaokun Liu, Yifan Liu, Daniel Yue Zhang, Ruichen Yao+2

University of Illinois Urbana-Champaign · Scale AI

Multi-Agent LLM Systems LLM Uncertainty Estimation Uncertainty Propagation

Open paper AskPDF arXiv

LLM-based multi-agent systems (MAS) solve complex tasks through communication among role-specialized agents. However, inter-agent dependencies introduce reliability risks beyond isolated agent failures. For instance, errors in intermediate messages could be inherited and amplified by downstream agents. Existing uncertainty quantification (UQ) methods mainly target isolated responses or single-agent reasoning, and therefore fail to capture uncertainty propagation in MAS. To this end, we propose PropUQ-MAS, an error propagation-aware UQ framework that represents MAS execution as a communication-structured graph and estimates each step's reliability by combining local uncertainty with uncertainty inherited from upstream messages. Extensive experiments demonstrate that PropUQ-MAS consistently improves UQ in MAS, with average relative gains of +6.10% in AUROC and +47.58% in PRR.

Abstract

Uncertainty Quantification

Explore similar work

PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems

Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems

Semantic Uncertainty-Guided Orchestration in Hierarchical Multi-Agent Systems