PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2610.08901v1cs.AI

TL;DR

Uncertainty estimation for multi-agent reasoning must account for how heterogeneous signals and reliability evolve across interaction rounds. SAUCE uses a filtering-style sequential update to combine round-level agreement and generation uncertainty. Across protocols and benchmarks, it outperforms log-likelihood and MAS-specific estimators on ranking and calibration.

  • Problem

    Parallel MAS uncertainty estimation must reconcile heterogeneous agent-level signals that fluctuate across rounds, because reliability depends on interaction dynamics rather than only the final output.

    Source: §1 · p. 2

  • Method

    SAUCE estimates uncertainty through a filtering-style sequential update over a latent system belief, weighting round-level agreement by generation uncertainty.

    Source: §1 · p. 2

  • Results

    SAUCE consistently outperforms log-likelihood baselines and recent MAS-specific estimators on ranking and calibration across Debate and DyLAN, and remains stable in longer debates where last-round confidence scores collapse.

    Source: §5.2 · p. 8, §5.4 · p. 9, §7 · p. 10

  • Takeaways & Limitations

    The results suggest interaction dynamics are a useful primitive for reasoning about the reliability of multi-agent systems.

    Source: §7 · p. 10

    SAUCE targets parallel reasoning systems with comparable per-round answers, limiting direct applicability to heterogeneous-role, tool-using, or open-ended planning systems.

    Source: §7 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Parallel multi-agent reasoning systems need uncertainty estimates that account for heterogeneous signals and interaction changes across rounds. SAUCE models these dynamics with sequential inference and reports advantages over existing uncertainty estimators.

1 Introduction

  • Reliable uncertainty estimation for parallel MAS must combine heterogeneous agent-level signals while tracking how they change across rounds.Sampling-based and Bayesian extensions can be costly across agents and rounds, while practical signal-based methods face heterogeneous, fluctuating signals.Source: §1 · p. 1
  • Two trajectories can yield the same final answer yet differ in reliability, motivating estimates based on interaction dynamics rather than a static final output.Stable convergence is presented as more trustworthy than oscillating outputs.Source: Figure 1 · p. 2, §1 · p. 2
  • SAUCE treats each round as noisy evidence about an evolving system belief, weighting agreement by generation uncertainty in a filtering-style update.The estimator is training-free and uses signals from the MAS inference trace without extra sampling or access to model weights or hidden states.Source: §1 · p. 2
  • SAUCE outperforms log-likelihood baselines and MAS-specific estimators across the Debate and DyLAN protocols.The paper also frames its contributions as a system-dynamics perspective, sequential consensus aggregation, and a lightweight estimator.Source: §1 · p. 2

2 Preliminaries

The paper represents parallel reasoning as a multi-round trajectory and defines uncertainty as a score derived from that trajectory. It motivates sequential updates because static summaries discard the temporal order of evidence.

2.1 Multi-Agent Reasoning Trajectory

  • A parallel reasoning MAS has agents produce responses at each round from the shared input and prior interaction history, with a final prediction typically aggregated from round-T answers.Debate and DyLAN are representative protocols of this form.Source: §2.1 · p. 3

2.2 Sequential Uncertainty Estimation for MAS

  • Trajectory-level uncertainty estimates uncertainty for a final prediction from the input and reasoning trajectory, with larger scores indicating lower confidence.The uncertainty state is updated from round-level evidence, and the trajectory is mapped to a final score.Source: §2.2 · p. 3
  • Static summaries lose temporal order: trajectories with identical average signals but different dynamics may have different reliability, motivating progressive updates as evidence arrives.Agents may reinforce, revise, or contradict one another over rounds.Source: §2.2 · p. 3
  • SAUCE formulates uncertainty estimation as sequential inference, integrating round-level signals into the uncertainty state.The framework is presented as a filtering-style update over interaction rounds.Source: §2.2 · p. 3

3 Method

SAUCE extracts agreement and generation-uncertainty signals from each round, then updates a confidence estimate across the interaction. It uses the trajectory of that estimate to score uncertainty, with clearer separation between correct and incorrect outputs than direct agreement averaging.

3.1 Round-Level Signals from Agent Outputs

  • Each round supplies modal-answer share M_t as cross-agent agreement and average token-level predictive entropy R_t as generation uncertainty.Lower agreement or higher entropy signals greater uncertainty; SAUCE uses both to assess the round’s evidence.Source: §3.1 · p. 4

3.2 Sequential Uncertainty Update

  • SAUCE propagates its confidence estimate and stability weight across rounds, then combines the estimate with current agreement using a reliability-dependent weight.The propagation uses λ for temporal coupling and q for additional interaction uncertainty; noisier rounds receive less weight and preserve more of the propagated state.Source: §3.2 · p. 4
  • The per-record uncertainty score negates the temporal average of µ_t, so it reflects the full deliberation trajectory rather than only the terminal round.Figure 2 reports that confidence rises across rounds for both classes, while correct trajectories converge to higher consensus.Source: §3.2 · pp. 4–5, Figure 2 · p. 4
  • AUROC 0.579→0.805: SAUCE’s round-averaged posterior mean separates correct from incorrect outputs more clearly than baseline agreement on MMLU-Pro / Gemini-2.5-FL / DyLAN.The figure compares the baseline agreement signal with SAUCE’s posterior-mean estimate, each averaged over rounds.Source: Figure 3 · p. 5, §3.2 · p. 5

4 Theoretical Analysis

SAUCE frames multi-agent interaction as sequential inference over a latent system belief, treating round-level signals from agent outputs as noisy observations. Under a linear-Gaussian instantiation, its recursion corresponds to posterior inference over that belief.

4.1 Sequential Inference over Latent System Beliefs

  • Agent outputs at each round provide noisy observations of a latent system belief, and Bayesian filtering updates the belief as observations accumulate.The latent belief represents the system’s underlying belief about the correctness of its current solution.Source: §4.1 · p. 5, §4 · p. 5, Figure 4 · p. 5

4.2 Linear-Gaussian Instantiation and Posterior Variance Update

  • The linear-Gaussian instantiation assumes the latent belief evolves with temporal dependence λ and process noise q.The authors describe constant λ as a deliberate simplification, empirically justified through ablations in Appendix C.1.Source: §4.2 · p. 6
  • The SAUCE recursion is the exact posterior update for the linear-Gaussian model when agreement M_t is the observation and generation uncertainty R_t is observation-noise variance.µ_t is the posterior mean of the latent belief, and v_t is its posterior variance.Source: §4.2 · p. 6
  • The running estimate µ_t summarizes how the system’s belief evolves across the trajectory rather than relying on the terminal round alone.Source: §4.2 · p. 6

5 Experiments

The experiments test uncertainty estimation across multiple models, benchmarks, and multi-agent protocols, evaluating detection, selective prediction, and calibration. SAUCE leads across most ranking and coverage comparisons, with robustness in longer debates and an ablation supporting the sequential update.

5.1 Experimental Setup

  • Experiments span five backbones, five reasoning suites, Debate and DyLAN, four training-free baselines, and AUROC, AUARC, and calibrated Brier-score evaluation.Runs use three agents and up to three rounds; SAUCE hyperparameters are tuned on one calibration cell per architecture and reused across other model–dataset combinations.Source: §5.1 · pp. 6–7

5.2 Uncertainty Estimation for Multi-Agent Systems

  • SAUCE leads the large majority of AUROC and AUARC cells and every per-backbone average across protocols and backbones; PE and LL often near or below chance, while UDPO and MATU lead only isolated cells.The advantage holds across both Debate and DyLAN; SAUCE also transfers to closed-source models using top-k token log-probabilities.Source: Table 1 · p. 7, Table 2 · p. 7, §5.2 · p. 8

5.3 Uncertainty Estimation for Calibration

  • SAUCE has the lowest Brier-Platt score on four of five backbones for MMLU-Pro Debate; on Gemini-FL it is within 0.5 pp of LL, the strongest baseline.Its calibrated probabilities remain spread across the probability range and close to empirical accuracy; a two-parameter Platt transform yields per-trajectory confidence for downstream gating.Source: Figure 5 · p. 8, §5.3 · p. 8

5.4 Robustness in Long Debates

  • In 15-round Qwen3-4B Debate, SAUCE preserves a correct–incorrect gap and its AUROC plateaus after round 3, while last-round LL loses separation and degrades toward chance.Both classes become increasingly token-confident, causing LL scores to concentrate as the debate proceeds.Source: Figure 6 · p. 8, §5.4 · p. 9

5.5 Contribution of the Sequential Update

  • The static combination of agreement and generation uncertainty performs close to the agreement-only round mean, whereas the full sequential update yields a clear gain.The ablation indicates that the improvement comes from the sequential update rather than a static combination of the two signals.Source: Table 3 · p. 9, §5.5 · p. 9

6 Related Work

Prior uncertainty methods address single LLMs or limited aspects of multi-agent systems, while SAUCE treats uncertainty in parallel reasoning systems as inference over interaction trajectories.

Uncertainty Estimation for LLMs

  • Single-LLM uncertainty methods include sampling-based, Bayesian, and internal-signal approaches, but do not directly model how multi-agent interactions evolve across rounds.Sampling-based and Bayesian methods become costly when repeated across agents and rounds, while internal signals fluctuate and differ across agents.Source: §6 · p. 9

Parallel Multi-Agent Reasoning Systems

  • Parallel multi-agent work studies system-level signals and specialized uncertainty methods, whereas SAUCE updates uncertainty online from standard rollout signals within a single trajectory.Examples include general agent uncertainty frameworks, debate-collapse optimization, and MATU’s estimates from repeated MAS runs.Source: §6 · p. 9

7 Conclusion

The paper concludes that SAUCE’s sequential inference over multi-round interactions performs across protocols and benchmarks, including longer debates. Its direct applicability is limited to parallel reasoning systems with comparable per-round answers and simple agreement and uncertainty signals.

7 Conclusion

  • Across Debate and DyLAN benchmarks, SAUCE’s filtering-style update consistently outperforms log-likelihood baselines and recent MAS-specific estimators on ranking and calibration, and remains stable in longer debates.The conclusion identifies interaction dynamics as a useful primitive for reasoning about MAS reliability and suggests uncertainty-aware orchestration and adaptive control as future directions.Source: §7 · p. 10
  • SAUCE assumes comparable per-round answers, limiting direct applicability to heterogeneous roles, tool use, or open-ended planning where round-level consensus is not naturally defined.Its current instantiation uses modal-answer share and token-level predictive entropy; more principled alternatives remain future work.Source: §7 · p. 10

Appendix

  • The appendices cover the algorithm and implementation, additional empirical studies, and proofs and derivations supporting the paper’s theoretical claims.The empirical studies include calibration grids, hyperparameter sensitivity, trajectory summaries, and temporal-order analyses.Source: Appendix · p. 15

A Algorithm

  • SAUCE is presented as a single-pass procedure that extracts round-level signals and applies a propagation–update recursion using standard rollout quantities, without additional forward passes.Its hyperparameters are shared across model–dataset cells within each protocol.Source: A Algorithm · p. 15

B.1 Metrics

  • The implementation appendix defines AUROC as ranking correct against incorrect trajectories, AUARC through rejection by uncertainty, and Brier score after Platt scaling with five-fold cross-validation.The three metrics are reported as percentages.Source: §B.1 · p. 16

B.2 Benchmarks

The appendix describes benchmark and hyperparameter choices, then tests transition flexibility and parameter sensitivity. The learned transition offers little AUROC difference from a constant coefficient, while sensitivity varies across parameters.

B.2 Benchmarks

  • Open-source evaluation uses MATH-500, MMLU-Pro, and BBH; stronger closed-source models use harder math and instruction sets plus a shared 5,000-item MMLU-Pro subset.The harder variants address limited correct/incorrect variation on the original tasks, while the shared subset controls API cost.Source: §B.2 · p. 16, Table 4 · p. 17

C Additional Experiments

  • The appendix adds studies of transition coefficients, hyperparameter sensitivity, calibration, trajectory summaries and order, statistical variability, and unanimous-final-agreement trajectories.Source: C Additional Experiments · p. 17

C.1 Constant vs. Context-Dependent Transition Coefficient

  • The learned and constant transitions differed by 0.09 AUROC points on MATH-500 and 0.42 on MMLU-Pro; both beat the no-filter baseline.The constant coefficient remains training-free and avoids the learned alternative’s engineering overhead.Source: Table 6 · p. 18, §C.1 · p. 18

C.2 Hyperparameter Sensitivity

  • In Debate, AUROC drops by roughly three points as λ decreases from 0.95 to 0.1; initial mean and variance also show sensitivity across their swept ranges.Figure 7 sweeps one parameter at a time around each protocol’s selected tuple.Source: Figure 7 · p. 18, §C.2 · pp. 18–19

B.3 Hyperparameter Configuration

  • Each protocol’s hyperparameters are jointly tuned on Qwen3-4B/MMLU-Pro, then transferred unchanged to every other model–dataset cell.Debate uses (0.95, 0.10, 0.25, 0.0); DyLAN uses (0.70, 0.001, 0.25, 0.0).Source: §B.3 · p. 17, Table 5 · p. 17, §C.2 · p. 18

C.3 Calibration on All Benchmarks

Across the full calibration grid, SAUCE has the best per-backbone average on every model and leads or nearly leads on most cells.

C.3 Calibration on All Benchmarks

  • SAUCE attains the best per-backbone average on every model and is leading or near-leading on most benchmark–protocol cells.Source: §C.3 · p. 19

C.4 Comparison with Simpler Trajectory Summary Methods

The appendix compares SAUCE with simpler trajectory summaries and tests whether chronological processing matters, then reports bootstrap and repeated-rollout analyses. Results generally favor SAUCE and original ordering, with task-specific exceptions and distinct sources of variability.

C.4 Comparison with Simpler Trajectory Summary Methods

  • SAUCE achieves the highest AUROC among listed summaries in five of six settings and beats EWMA in those same settings.GPT-5.4-mini on BBEH-mini is the exception: SAUCE is near chance and slope performs best.Source: §C.4 · p. 20
  • Original-order processing outperforms both alternatives in five of six settings; its MMLU-Pro AUROC margin over the better alternative is 3.97 points for Qwen3-4B and 3.31 for GPT-5.4-mini.The effect is smaller elsewhere, and reversal improves Qwen3-4B on BBH.Source: §C.4 · p. 20, Table 10 · p. 21

C.5 Statistical Significance

  • Bootstrap tail fractions were below 0.05 against PE, averaged LL, UDPO, and single-run MATU in five of six settings, but showed no EWMA advantage on GPT-5.4-mini/BBEH-mini.These prompt-level intervals hold the rollout fixed and do not measure variability across independently generated rollouts.Source: Table 11 · p. 21, §C.5 · pp. 21–22
  • Across four repeated-rollout settings, SAUCE had the highest mean AUROC, with sample standard deviations of 0.87–2.29 points; BBEH-mini remained near chance.The relative advantage on BBEH-mini should not be read as reliable discrimination.Source: §C.5 · pp. 21–22, Table 12 · p. 22

C.6 Trajectory Analysis under Unanimous Final Agreement

Among trajectories with identical final parsed answers, more agent-level answer changes coincide with lower accuracy and lower mean SAUCE confidence.

C.6 Trajectory Analysis under Unanimous Final Agreement

  • For final-unanimous trajectories, accuracy falls from 76.9% to 38.8% as agent-level switches rise from zero to three or more, while mean SAUCE confidence falls from 0.915 to 0.622.Final-round agreement is constant across groups; the passage describes an association, not a causal effect, and confidence is not a calibrated correctness probability.Source: §C.6 · p. 22

D Theoretical Analysis and Proofs

The appendix proves the linear-Gaussian SAUCE recursion, derives its innovations-form marginal-likelihood objective, and establishes that the objective is a tight evidence lower bound under the model.

D.1 Proof of Proposition 4.1

  • Induction establishes the SAUCE posterior recursion: the linear-Gaussian transition and observation yield Gaussian beliefs whose variance has a precision-addition form.The proof predicts from the previous-round belief, forms the joint state-observation distribution, and conditions on the new observation.Source: §D.1 · p. 23

D.2 Innovations Form of the Marginal Likelihood

  • The marginal likelihood factorizes into round-wise predictive terms, whose innovations form balances prediction error against predictive uncertainty.The squared error is penalized relative to predictive variance, while the log-variance term penalizes overconfidence.Source: §D.2 · pp. 23–24

D.3 Equivalence with the Evidence Lower Bound

  • The training objective is both the exact marginal likelihood and the tight evidence lower bound, so the failure of λθ(ht) to outperform a constant cannot be attributed to a loose variational bound.The Kalman smoother gives the exact posterior, making the KL term zero.Source: §D.3 · p. 24

Related papers

Loading 2610.08901v1…