Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems

Tunyu Zhang; Zihao Zhao; Yusong Zhao; Haizhou Shi; Zhuohang Li; Haoxian Chen; Hao Wang; Dimitris N. Metaxas

cs.AIOct 6, 2026

Sequential Probabilistic Uncertainty Estimation for Parallel Multi-Agent Reasoning Systems

Authors: Tunyu Zhang, Zihao Zhao, Yusong Zhao, Haizhou Shi, Zhuohang Li, Haoxian Chen, Hao Wang, Dimitris N. Metaxas

Organizations: Rutgers University · University of Illinois Urbana-Champaign · Vanderbilt University · Columbia University

Abstract

LLM-based multi-agent systems (MAS) have attracted growing attention for improving reasoning through interaction among multiple agents. In this work, we focus on parallel multi-agent reasoning systems, where several agents solve the same problem over multiple rounds and aggregate their outputs into a final answer. Despite their strong reasoning performance, uncertainty estimation for such systems remains underexplored: the reliability of a MAS depends not only on individual generations, but also on how agents interact and evolve across rounds. We propose SAUCE (Sequential Agent Uncertainty through Consensus Evolution), a lightweight, training-free uncertainty estimator that formulates MAS uncertainty as sequential inference over a latent system-level belief. SAUCE aggregates round-level agreement and generation-uncertainty signals through a filtering-style update. Across five backbones, five benchmarks, and two MAS protocols, SAUCE improves misclassification detection, selective prediction, and calibration over a broad set of uncertainty estimation baselines, including standard log-likelihood-based methods and MAS-specific estimators.

Figures & tables

Figure 1 : Overview. (A) Two MAS trajectories can reach the same final answer but differ greatly in reliability: a stable run whose outputs converge across rounds (top) is more trustworthy than an unstable run whose outputs oscillate (bottom). A static view that only considers the final output cannot distinguish them, motivating uncertainty estimation from interaction dynamics. (B) SAUCE models multi-round interaction as a sequence of round-level observations $(M_{t},R_{t})$ , where agreement is weighted by generation uncertainty, and performs a filtering-style update over a latent system-level belief. The resulting trajectory summary defines the SAUCE uncertainty score $u({\bm{x}},\tau)$ (Eqn. 11 ).

Figure 2 : Round-level

\mu_{t}

on Llama-3.1-8B / MATH-500. Both classes grow more confident with each round, but correct trajectories converge to a consistently higher consensus. Shading shows

\pm 1

standard deviation across trajectories.

Panel of Figure 3 — Figure 3 : Distribution of (a) the baseline agreement signal $\bar{M}_{t}$ and (b) SAUCE’s posterior-mean estimate $\mu_{t}$ (each averaged over rounds) for correct vs. incorrect MAS outputs (MMLU-Pro, Gemini-2.5-FL, DyLAN). SAUCE sharpens the separation between classes (AUROC $0.579\!\to\!0.805$ ). Densities are normalized independently in each panel.

Figure 4 : Probabilistic view of SAUCE. A latent system belief $s_{t}$ evolves across rounds and emits a noisy observation $o_{t}$ formed from the agents’ outputs. SAUCE’s per-round estimate is the posterior expectation $\mathbb{E}[s_{t}\mid o_{1:t}]\!=\!\mu_{t}$ .

Method	MATH-500				MMLU-Pro				BBH				Avg
	Debate		DyLAN		Debate		DyLAN		Debate		DyLAN		Avg
	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC
Qwen3-4B
PE	64.89	83.45	64.58	82.70	59.54	73.63	63.53	74.92	68.90	87.13	59.13	83.79	63.43	80.94
LL	65.93	83.14	66.36	84.08	68.39	78.49	69.88	79.27	69.56	87.62	60.61	83.82	66.79	82.74
UDPO	57.29	79.14	72.50	84.10	58.22	66.43	67.95	73.43	59.18	84.38	64.97	88.00	63.35	79.25

Table 1 : Misclassification detection (AUROC

\uparrow

) and selective prediction (AUARC

\uparrow

) on open-source models. Boldface and underlining denote the best and second-best performance.

Method	Olympiad				MMLU-Pro				BBEH-mini				Avg
	Debate		DyLAN		Debate		DyLAN		Debate		DyLAN		Avg
	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC	ROC	ARC
Gemini-2.5-Flash-Lite
PE	65.51	66.86	66.35	65.23	48.71	73.35	70.22	89.09	49.98	19.13	41.73	16.06	57.08	54.95
LL	68.67	68.13	67.42	66.67	64.90	82.82	72.18	90.05	46.71	18.50	39.41	15.46	59.88	56.94
UDPO	63.08	48.89	81.58	71.05	54.59	77.52	57.83	82.71	59.23	25.12	75.41	27.29	65.29	55.43

Table 2 : Misclassification detection and selective prediction on closed-source models. Metrics and notation follow Table 1 . Boldface and underlining denote the best and second-best performance.

Figure 5 : Brier score after Platt scaling (5-fold cross-validation) on MMLU-Pro under the Debate protocol, across all five backbones. SAUCE attains the lowest Brier-Platt score on four of the five backbones.

Figure 6 : Per-round behavior on a 15-round Qwen3-4B Debate run on MMLU-Pro, grouped by final-answer correctness. Left : SAUCE posterior mean

\mu_{t}

; the correct/incorrect gap persists through round 15. Middle : Average per-agent log-likelihood at round

t

; both classes become increasingly token-confident and the gap vanishes. Right : AUROC against final-consensus correctness as a function of debate length

T

; SAUCE plateaus while LL degrades toward chance (dashed line).

Method	AUROC	Brier-Platt
Last round, $1{-}M_{t}$	58.4	21.3
(a) Round-mean of $M_{t}$	68.6	20.0
(b) Static joint with $R_{t}$	68.4	20.9
(c) SAUCE (Ours)	77.1	19.2

Table 3 : Component-wise ablation on Qwen3-4B / MMLU-Pro / Debate. Row (b) is the static joint of

M_{t}

and

R_{t}

; row (c) is the full sequential update with

\bar{\mu}

readout. AUROC

\uparrow

and Brier-Platt

\downarrow

Appendix figures & tables11 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Format	Open-source size	Closed-source size
MATH-500	Free-form math	$500$	–
MMLU-Pro	Multiple-choice	$12{,}032$	$5{,}000$ (subset)
BBH	MCQ / short string	$1{,}250$	–
OlympiadBench	Free-form math	–	$674$
BBEH-mini	MCQ / short string	–	$\approx\!460$

Appendix

Table 4 : Benchmark formats and evaluation sizes used in the main results. “–” denotes a benchmark not used for that model class.

MAS protocol	$\lambda$	$q$	$\sigma_{0}^{2}$	$\mu_{0}$
Debate	$0.95$	$0.10$	$0.25$	$0.0$
DyLAN	$0.70$	$0.001$	$0.25$	$0.0$

Appendix

Table 5 : SAUCE hyperparameter defaults transferred across all cells.

Method	MATH-500	MMLU-Pro
mean $(R_{t})$ – no filter	77.00	64.93
Learned $\lambda_{\theta}({\bm{h}}_{t})$	82.85	75.18
Const. $\lambda^{*}$ (ours)	82.94	74.76

Appendix

Table 6 : Learned vs. constant transition coefficient on Qwen3-4B / Debate (AUROC

\uparrow

\times 100

). The two filter variants achieve similar AUROC on both datasets; both improve substantially over the no-filter baseline.

Figure 7 : Per-axis sensitivity of SAUCE’s four hyperparameters at the calibration cell (Qwen3-4B / MMLU-Pro). Top row: Debate, selected values

(\lambda,q,\sigma_{0}^{2},\mu_{0})=(0.95,0.10,0.25,0.0)

. Bottom row: DyLAN, selected values

(0.70,0.001,0.25,0.0)

. In each panel, one hyperparameter is swept while the other three are held at their per-protocol selected value (marked by ★ and a dotted vertical line).

Method	MATH-500		MMLU-Pro		BBH		Avg
Method	Debate	DyLAN	Debate	DyLAN	Debate	DyLAN	Avg
Qwen3-4B
PE	16.92	17.06	22.44	21.64	15.23	16.48	18.30
LL	17.12	16.97	22.46	21.65	15.41	16.55	18.36
UDPO	17.16	15.13	21.40	19.84	15.54	15.85	17.49
MATU	17.86	17.94	22.38	22.34	16.32	16.16	18.83

Appendix

Table 7 : Calibration quality on open-source models, measured by Brier score after Platt scaling with 5-fold cross-validation (

\downarrow

\times 100

). Bold denotes the lowest score per (model, protocol, dataset) cell, and per-backbone Avg.

Method	OlympiadBench		MMLU-Pro		BBEH-mini		Avg
Method	Debate	DyLAN	Debate	DyLAN	Debate	DyLAN	Avg
Gemini-2.5-Flash-Lite
PE	22.35	21.87	18.70	14.84	17.21	15.05	18.34
LL	22.47	22.18	14.83	13.53	17.18	15.56	17.63
UDPO	21.60	16.63	18.47	15.93	16.80	14.21	17.27
MATU	22.02	23.45	18.62	15.93	17.06	14.56	18.61

Appendix

Table 8 : Calibration quality on closed-source models, measured by Brier score after Platt scaling with 5-fold cross-validation (

\downarrow

\times 100

). Notation follows Table 7 .

Method	Qwen3-4B			GPT-5.4-mini
Method	MATH-500	MMLU-Pro	BBH	OlympiadBench	MMLU-Pro	BBEH-mini
EWMA	66.80	68.43	69.56	81.63	66.95	53.46
Slope	37.79	38.76	40.75	32.36	39.56	57.25
Switches	61.76	60.59	61.47	71.08	57.58	52.43
TTC	66.47	68.29	68.29	79.97	66.31	56.94
Mean $1{-}M_{t}$	66.60	68.56	69.72	82.33	67.08	55.95

Appendix

Table 9 : Simpler trajectory summaries under Debate (AUROC

\uparrow

\times 100

). Boldface and underlining denote the best and second-best performance. Evaluation sizes and score definitions follow Appendix C.4 .

Method	Qwen3-4B			GPT-5.4-mini
Method	MATH-500	MMLU-Pro	BBH	OlympiadBench	MMLU-Pro	BBEH-mini
Original	68.59	76.42	72.86	83.83	69.53	49.96
Reversed	68.30	71.68	74.26	82.29	65.21	49.72
Shuffled	68.41	72.45	73.84	82.99	66.22	49.12
$\Delta$	$+0.19$	$+3.97$	$-1.41$	$+0.84$	$+3.31$	$+0.24$

Appendix

Table 10 : Temporal-order ablation under Debate (AUROC

\uparrow

\times 100

). Shuffled averages three seeds;

\Delta

is original minus the better alternative. Best and second-best scores are bold and underlined.

Statistic	Qwen3-4B			GPT-5.4-mini
Statistic	MATH-500	MMLU-Pro	BBH	OlympiadBench	MMLU-Pro	BBEH-mini
SAUCE	68.59	76.42	72.86	83.83	69.53	49.96
95% CI	62.6–74.7	75.6–77.3	69.4–76.3	80.7–87.1	67.4–71.5	43.8–56.3
vs. PE	0.011	$\mathbf{<0.001}$	0.019	$\mathbf{<0.001}$	$\mathbf{<0.001}$	0.121
vs. LL	0.020	$\mathbf{<0.001}$	0.034	$\mathbf{<0.001}$	$\mathbf{<0.001}$	0.002
vs. UDPO	$\mathbf{<0.001}$	$\mathbf{<0.001}$	$\mathbf{<0.001}$	$\mathbf{<0.001}$	$\mathbf{<0.001}$	1.000

Appendix

Table 11 : Paired-bootstrap comparisons under Debate. The first two rows report SAUCE’s AUROC (

\times 100

) and 95% interval; subsequent rows give its tail fraction against each baseline. Bold indicates

p<0.05

;

<0.001

denotes zero tail counts in 1,000 resamples.

Method	Qwen3-4B		GPT-5.4-mini
Method	MATH-500	BBH	OlympiadBench	BBEH-mini
PE	67.04 $\pm$ 1.64	69.83 $\pm$ 0.99	53.65 $\pm$ 1.92	46.11 $\pm$ 1.31
LL	67.67 $\pm$ 1.22	71.57 $\pm$ 1.59	70.17 $\pm$ 0.68	43.34 $\pm$ 2.54
SAUCE (Ours)	72.26 $\pm$ 2.29	72.58 $\pm$ 1.76	82.79 $\pm$ 0.87	49.01 $\pm$ 1.51
Runs	5	5	6	5
$n$ per run	500	1,250	673–674	460

Appendix

Table 12 : Repeated Debate rollouts (AUROC

\uparrow

, mean

\pm

sample standard deviation,

\times 100

). Boldface and underlining denote the best and second-best means.

Switches	$n$	Accuracy (%)	Mean confidence
0	8,004	76.9	0.915
1	1,595	49.5	0.758
2	486	44.4	0.676
3+	611	38.8	0.622

Appendix

Table 13 : Answer-switch analysis among final-unanimous trajectories on Qwen3-4B / Debate / MMLU-Pro (

n=10{,}696

). Switches count changes in individual agents’ answers.

Explore similar work

PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems
Aug 22, 2026Yaokun Liu, Yifan Liu, Daniel Yue Zhang +3Uncertainty Quantification Large Language Model Uncertainty
University of Illinois Urbana-Champaign · Scale AI
Runtime Uncertainty Monitoring for LLM-Based Multi-Agent Systems Using Bayesian Networks
Jul 28, 2026Bart Custers, Koorosh AslansefatLarge Language Model Uncertainty Multi-Agent Large Language Model Systems
University of Hull, Hull HU6 7RX, UK
The Bystander Effect in Multi-Agent Reasoning: Quantifying Cognitive Loafing in Collaborative Interactions
May 11, 2026Dahlia Shehata, Ming LiMulti-Agent Reasoning Collaboration
University of Waterloo Canada

Aug 22, 2026, cs.MAJ/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

Uncertainty Quantification Large Language Model Uncertainty Uncertainty

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

Explore similar work

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

Runtime Uncertainty Monitoring for LLM-Based Multi-Agent Systems Using Bayesian Networks

The Bystander Effect in Multi-Agent Reasoning: Quantifying Cognitive Loafing in Collaborative Interactions