🤖 machine learning

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

This paper introduces MATU, a novel framework that leverages tensor decomposition to quantify uncertainty in Large Language Model-based Multi-Agent Systems by analyzing entire reasoning trajectories and disentangling distinct sources of uncertainty arising from complex communication dynamics and topologies.

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

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you hire a team of expert AI assistants to solve a really hard problem, like diagnosing a rare disease or writing a complex piece of software. You don't just ask one AI; you ask a whole group to talk to each other, debate, and build a solution together. This is called a Multi-Agent System (MAS).

While these teams are incredibly powerful, they have a big flaw: they can be unreliable. Sometimes, one agent makes a tiny mistake early on, and the whole team blindly follows that mistake down a rabbit hole, confidently producing a wrong answer.

The paper you shared introduces a new tool called MATU to solve this. Think of MATU as a "Team Trust Meter" that doesn't just look at the final answer, but watches the entire conversation to see how shaky the team's logic really is.

Here is how it works, broken down with simple analogies:

1. The Problem: Why Old Methods Fail

Imagine you are a teacher grading a group project.

Old Method: You only read the final essay the group submitted. If the essay looks good, you give them an A. But you missed the fact that two students were arguing the whole time, or that one student copied the wrong facts from the internet.
The Issue with AI: Current AI safety tools do the same thing. They look at the final sentence the AI says. They don't see the messy, confusing, or contradictory steps the AI took to get there. In a team of AIs, if Agent A whispers a wrong idea to Agent B, and Agent B builds a whole house on that wrong idea, the final house might look pretty, but the foundation is rotten.

2. The Solution: MATU (The "Team Trust Meter")

The authors created MATU to fix this. Instead of just reading the final essay, MATU acts like a super-observant film director who records every single take of the movie.

Here is the step-by-step process using a creative analogy:

Step A: The "Rehearsal" (Collecting Trajectories)

Imagine you ask the AI team to solve a math problem. You don't just ask them once. You ask them 10 times (like 10 different rehearsals).

In Rehearsal 1, they might argue for 5 minutes, then agree.
In Rehearsal 2, they might skip the argument and jump straight to the answer.
In Rehearsal 3, they might get confused and go in circles.

MATU collects all these different "rehearsals" (called trajectories).

Step B: The "Translation" (Embedding)

The AI team speaks in words, numbers, and code. MATU translates every single sentence and action into a universal language of meaning (mathematical vectors).

Analogy: Imagine translating every word the team says into a specific color. "Add 2" becomes Blue. "Divide by 0" becomes Red. Even if they say it differently ("Let's sum these" vs. "Add them up"), they both turn Blue. This lets MATU compare apples to apples, even if the words are different.

Step C: The "3D Puzzle" (Tensor Decomposition)

This is the magic part. MATU stacks all these rehearsals into a giant, 3D block (a Tensor).

Dimension 1: The different team members.
Dimension 2: The steps in the conversation.
Dimension 3: The different rehearsals.

Now, MATU tries to compress this 3D block into a simpler, smaller version (like squishing a sponge).

If the team is reliable: Their conversations are consistent. They all follow a similar pattern. When MATU squishes the block, it fits perfectly. The "reconstruction error" (how much information is lost) is low. Result: High Trust.
If the team is unreliable: Their conversations are chaotic. One rehearsal goes left, another goes right. When MATU tries to squish this messy block, it falls apart. The "reconstruction error" is high. Result: Low Trust (High Uncertainty).

3. Why This is a Big Deal

The paper shows that MATU is better than previous methods because:

It sees the whole movie, not just the ending: It catches errors that happen in the middle of the process.
It handles different team structures: Whether the AI team is a circle, a line, or a chaotic free-for-all, MATU can measure their trust.
It works even when they use tools: If the AI team uses calculators or code interpreters, MATU still works.

The Real-World Impact

Why do we care?

Medical Safety: If an AI team diagnoses a patient, MATU can tell the doctor, "Hey, this team is very unsure. Their internal logic is all over the place. Don't trust this diagnosis."
Better AI Selection: If you have 5 different AI teams working on a problem, MATU can pick the one that is most confident and consistent, saving you from bad answers.

Summary

In short, MATU is a new way to check if a team of AI robots is "thinking clearly." Instead of just checking their final answer, it watches their entire messy conversation, translates it into a mathematical puzzle, and sees if the pieces fit together. If the puzzle is broken, the system knows the answer is likely wrong, even if the final sentence looks perfect.

1. Problem Statement

While Large Language Model (LLM)-based Multi-Agent Systems (MAS) outperform single-agent systems on complex tasks, they introduce unique reliability challenges due to intricate communication dynamics and role dependencies. Existing Uncertainty Quantification (UQ) methods, designed primarily for single-turn or single-agent outputs, fail to address three specific complexities inherent to MAS:

Cascading Uncertainty in Multi-Step Reasoning: Errors in early steps propagate through the reasoning chain. Existing methods often focus only on the final output or struggle to process long, concatenated reasoning trajectories using Natural Language Inference (NLI) models due to context limits.
Variability of Inter-Agent Communication Paths: For the same query, agents may collaborate through different interaction sequences across runs. Standard semantic diversity metrics are blind to this path-level variability.
Diversity of Communication Topologies: MAS can be structured in static (e.g., star, chain) or dynamic topologies. UQ methods validated on single models often fail to generalize across these varying structural configurations.

The core problem is the lack of a framework that can holistically quantify uncertainty by capturing the variability in reasoning trajectories, communication paths, and system topologies simultaneously.

2. Methodology: MATU Framework

The authors propose MATU (Multi-Agent Tensor Uncertainty), a novel framework that quantifies uncertainty by representing the entire system behavior as a higher-order tensor and applying tensor decomposition.

Key Technical Steps:

Embedding for Multi-Step Reasoning:
- Instead of analyzing raw text, MATU encodes every intermediate step of an agent's reasoning (including tool calls) into a shared latent space using pre-trained embedding models (e.g., Qwen3-embedding).
- For a specific run $j$ and agent $k$ , the sequence of steps is converted into an embedding matrix $E^{(j,k)} \in \mathbb{R}^{T_{j,k} \times d}$ , where $T_{j,k}$ is the variable number of steps and $d$ is the embedding dimension. This decouples semantic comparability from surface form and length.
Tensor Representation (Ragged Tensor):
- To handle the variability in trajectory lengths and communication patterns across $N$ runs and $K$ agents, MATU constructs a ragged tensor $\mathcal{X}$ .
- Unlike standard tensors requiring fixed dimensions, this structure allows $T_{j,k}$ to vary, aggregating multiple execution runs into a single mathematical object that preserves communication diversity.
Tensor Decomposition (PARAFAC2/CP-2):
- MATU applies PARAFAC2 (CP-2) decomposition, a method specifically designed for irregular tensor structures.
- The decomposition seeks a low-rank approximation of the ragged tensor: $\mathcal{X} \approx \sum_{r=1}^R \lambda_r \mathbf{u}^{(1)}_r \otimes \mathbf{u}^{(2)}_r \otimes \mathbf{u}^{(3)}_r$ .
- Uncertainty Metric: The framework calculates the reconstruction loss ( $L_R = \|\mathcal{X} - \hat{\mathcal{X}}_R\|$ ) for different ranks $R$ .
- Logic: If the system is reliable, trajectories should follow a consistent, low-rank structure (low reconstruction error). High reconstruction error indicates that trajectories are inconsistent and cannot be explained by a few latent factors, implying high uncertainty.
- The final uncertainty score $U$ is the sum of reconstruction losses across all examined ranks.

3. Key Contributions

Systematic Definition: Provides the first systematic definition of UQ for LLM-based MAS, identifying unique uncertainty sources from tool usage, multi-step reasoning, and inter-agent communication.
Novel Framework (MATU): Introduces a tensor decomposition-based approach that integrates uncertainty signals at both the response level (semantic consistency) and the run level (structural consistency), enabling holistic estimation.
Generalizability: The use of ragged tensors and CP-2 decomposition allows the method to generalize across diverse communication topologies (static and dynamic) without requiring structural re-engineering.
Interpretability: The latent factors from decomposition can be mapped to specific reasoning failures, offering interpretability beyond a simple scalar score.

4. Experimental Results

The authors evaluated MATU across four datasets (MATH, MoreHopQA, MMLU, HumanEval) using various LLMs (GPT-4o, Qwen2.5, Llama3.1) and MAS frameworks (Camel, AutoGen, AnyMac).

Static vs. Dynamic Designs: MATU consistently outperformed baselines (Eigv(Agre), P(true), SAUP) in both static (Camel, AutoGen) and dynamic (AnyMac) systems. It showed particular strength in dynamic environments where interaction sequences vary significantly between runs.
Tool Integration: On the HumanEval benchmark (requiring code generation and tool use), MATU demonstrated superior robustness compared to baselines.
Out-of-Distribution (OOD) Detection: MATU effectively distinguished between in-distribution and OOD data (e.g., applying math prompts to general knowledge tasks), achieving an AUROC of 0.6770, significantly outperforming SAUP (0.6201).
Downstream Utility: In a backbone selection task (choosing the best model response from a pool), MATU-guided selection yielded higher accuracy than random selection or other uncertainty metrics, proving its practical utility for deployment.
Ablation Studies:
- Direct tensor decomposition on embeddings outperformed distance-based metrics (Cosine Similarity, EMD).
- Embedding dimensions of 256 provided optimal performance.
- Smaller embedding models (Qwen-0.6B) offered a near-optimal balance between efficiency and accuracy.

5. Significance

This work addresses a critical gap in the reliability of AI systems. As MAS become more prevalent in high-stakes domains (healthcare, scientific discovery), the ability to quantify system-level uncertainty is paramount.

Beyond Single-Agent Logic: MATU moves the field beyond treating agents as isolated units, acknowledging that uncertainty in MAS is a property of the interaction and trajectory, not just the final answer.
Scalability and Adaptability: By leveraging tensor decomposition, the method scales to complex, dynamic topologies without needing retraining or specific architectural adjustments.
Safety and Trust: The ability to detect fragile consensus and OOD failures provides a mechanism to mitigate risks, such as preventing a cascading error in a medical diagnosis pipeline.

In summary, MATU transforms the problem of multi-agent uncertainty from a semantic similarity task into a structural analysis task, offering a robust, generalizable, and interpretable solution for the next generation of collaborative AI systems.