PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yaokun Liu, Yifan Liu, Daniel Yue Zhang, Ruichen Yao, Zelin Li, Dong Wang

arXiv:2608.22130v1cs.MAcs.CL

TL;DR

MAS reliability can be compromised when erroneous intermediate messages are inherited and amplified, while existing UQ largely targets isolated outputs or single-agent reasoning. PROPUQ-MAS models execution as a communication graph and recursively combines local and upstream uncertainty for step-wise tracking. Experiments report consistent MAS UQ improvements, including +6.10% AUROC and +47.58% PRR on average.

  • Problem

    Existing UQ methods mainly assess isolated responses or single-agent reasoning and do not capture uncertainty propagation through MAS communication dependencies.

  • Method

    PROPUQ-MAS unfolds MAS execution into a communication-structured DAG and recursively combines local uncertainty with uncertainty inherited from upstream messages.

  • Results

    +6.10% AUROC and +47.58% PRR are the average relative gains reported for PROPUQ-MAS across extensive MAS experiments.

  • Takeaways & Limitations

    PROPUQ-MAS provides training-free, single-pass node-wise reliability tracking for intermediate and final outputs across reasoning and code-generation MAS tasks.

  • Takeaways & Limitations

    The propagation rule assumes edge-wise conditional independence and local-propagation independence, which may fail when messages jointly affect reasoning or acceptance behavior.

Abstract

from arXiv · show

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.

1 Introduction

MAS improve complex-task flexibility through specialized-agent collaboration, but inter-agent dependencies create system-wide error propagation risks. PROPUQ-MAS addresses this gap by tracking uncertainty over execution graphs and combining local with inherited risk.

  • MAS coordinate role-specialized agents across multi-step workflows to solve complex tasks.Their communication and collaboration support demanding applications such as autonomous software engineering and multi-step web navigation.
  • Intermediate errors can be accepted as valid context by downstream agents and propagated or amplified through communication.
  • Propagation-aware UQ should be step-wise, online-computable, and topology-agnostic for monitoring risky intermediate states and supporting intervention or attribution.
  • Existing UQ methods estimate local uncertainty for isolated outputs or single-agent reasoning trajectories rather than step-wise propagation in MAS.Signals include token probabilities, self-evaluation, semantic consistency, situation-aware step weights, and sequential decision uncertainty.
  • PROPUQ-MAS unfolds MAS trajectories into directed acyclic graphs and recursively combines each node’s local uncertainty with inherited upstream uncertainty.The framework is topology-agnostic and computes propagation in a single forward pass.
  • +6.10% AUROC and +47.58% PRR are the reported average relative gains from PROPUQ-MAS in extensive MAS experiments.

2 Related Work

Prior UQ methods provide local reliability signals for individual generations or single-agent trajectories, while MAS-specific methods do not explicitly model communication-mediated uncertainty propagation. PROPUQ-MAS instead supports real-time, node-wise UQ over arbitrary interaction topologies.

  • Existing LLM UQ methods estimate individual-generation reliability using likelihoods, self-evaluation, or sampling-based semantic consistency.These local signals are used as the uncertainty of each MAS node.
  • Single-agent trajectory UQ methods model sequential uncertainty but do not directly transfer to MAS structures with multi-parent or multi-recipient communication.
  • MAS-level UQ remains under-explored, and existing studies do not explicitly model uncertainty propagation across agents during execution.MATU instead measures consistency across multiple sampled MAS executions for trajectory-level assessment.
  • PROPUQ-MAS computes node-wise UQ in a single MAS forward pass, enabling real-time monitoring of intermediate outputs without training.This contrasts with post-hoc approaches requiring repeated executions.

3 Methodology

The methodology represents realized MAS execution as a DAG and decomposes node uncertainty into local generation risk and propagated contamination from parent messages. A recursive online rule then tracks uncertainty in topological order, with stated efficiency and propagation properties.

  • 3.1 Problem Setup: An arbitrary MAS execution is unfolded into a DAG whose nodes are outputs and whose edges indicate conditioning on earlier outputs.Multiple parents represent conditioning on several upstream messages, including in temporally unrolled feedback patterns.
  • 3.1 Problem Setup: Propagation-aware uncertainty is defined as each node’s marginal error probability in the MAS execution graph.
  • 3.2 Uncertainty Propagation in MAS: Each node’s uncertainty combines intrinsic local generation uncertainty with cascading uncertainty inherited through inter-agent communication.The inherited component is represented recursively from parent uncertainties.
  • 3.2.1 Error Event Decomposition: Local uncertainty captures an agent’s inherent reasoning or generation failure independently of parent-input correctness.It can be estimated with off-the-shelf single-agent UQ methods such as self-evaluation, token probabilities, and self-consistency.
  • 3.2.1 Error Event Decomposition: Each communication edge models acceptance or critique of an erroneous parent output, with αpv and βpv denoting the corresponding probabilities.Online execution uses a self-reported acceptance score ˆαpv as a plug-in estimate of transmission strength.
  • 3.2.1 Error Event Decomposition: Contamination occurs when an erroneous parent is accepted, whereas correction occurs when that parent is critiqued.The correction event is not itself an error-generating event.
  • 3.3 Online Inference and Key Properties: Algorithm 1 processes nodes in topological order, estimating local uncertainty and self-reported ˆαpv before updating node-wise reliability online.
  • 3.2.2 Recursive Uncertainty Propagation: The recursive rule updates node uncertainty by combining local uncertainty with propagated parent risks using marginal parent uncertainties and edge-level acceptance probabilities.The factorization requires edge-wise conditional independence and local-propagation independence because the exact joint distribution is unavailable online.

4 Empirical Evaluations

PROPUQ-MAS is evaluated across diverse MAS benchmarks, models, topologies, and intermediate or final outputs. It consistently improves uncertainty estimation and supports online monitoring of propagation-related risks.

  • Evaluation Setup: The evaluation spans GSM8K, MedQA, and MBPP-Plus across math, science, and code-generation tasks.Experiments use Qwen3 models at multiple scales and Gemma-3-12b-it for cross-family evaluation.
  • Evaluation Setup: The study tests sequential, hierarchical, and decentralized MAS interaction topologies, typically with four agents.These structures assess whether propagation-aware uncertainty generalizes across different communication patterns.
  • Final-Output UQ: +7.32% median AUROC and +41.36% median PRR are achieved for final-output UQ across datasets, model families, and MAS topologies.The gains are especially clear when local uncertainty estimates are weak or noisy.
  • Verifiable Intermediate Steps: +6.10% average AUROC and +47.58% average PRR are achieved for intermediate-agent UQ in decentralized MAS.These results indicate that propagated risk identifies unreliable intermediate outputs as well as final answers.
  • Structural Generalization: PROPUQ-MAS consistently improves over local verbalized UQ across tested sequential chain lengths and hierarchical expert-layer widths.The results support tracking uncertainty over longer chains and aggregating risks from larger parent sets.
  • Ablation Study: Using self-reported acceptance scores improves AUROC and PRR over uniform edge weights across three MAS topologies with Qwen3-8B.The ablation supports using acceptance as a correction-sensitive transmission weight for propagated risk.
  • Edge-Weight Validation: Error-inheritance rates increase monotonically from 0.050 to 0.973 across self-reported adoption-score bins for incorrect-parent cases.This supports the score as an online proxy for error-conditioned acceptance strength without additional training or inference passes.

5 Conclusion

PROPUQ-MAS models multi-agent execution as a communication-structured graph and combines local uncertainty with uncertainty inherited from upstream messages. The framework supports node-wise UQ across MAS settings, including a hierarchical GSM8K case where it captures propagated risk.

  • PROPUQ-MAS models MAS execution as a communication-structured graph and estimates node-wise reliability by combining local and inherited uncertainty.Its recursive rule tracks uncertainty in a single topological forward pass without additional training.
  • The framework reports improvements over single-agent UQ baselines for final-answer and intermediate-step uncertainty estimation across topologies and backbone models.
  • In a hierarchical GSM8K case, the summarizer follows erroneous agents despite low local uncertainty, whereas PROPUQ-MAS captures the propagated risk.The example’s final prediction is 47.25, compared with the gold answer 189.

Limitations

The paper identifies limitations involving transmission-parameter estimation, independence assumptions, and dependence on local uncertainty quality. These constraints reflect trade-offs between probabilistic fidelity, tractable computation, and online practicality.

  • The implementation uses a self-reported plug-in estimate for the latent error-conditioned transmission parameter, which may be imperfectly calibrated.The estimate is treated as an online proxy rather than a direct observation of the true parameter.
  • The propagation rule assumes edge-wise conditional independence and local-propagation independence to obtain a tractable factorization.These assumptions may be violated when upstream messages jointly affect downstream reasoning or misleading context changes multiple behaviors simultaneously.
  • PROPUQ-MAS depends on the quality of the local uncertainty estimator at each node.Stronger calibrated estimators may require labeled calibration data and be less practical for online execution.
  • The framework uses lightweight, single-pass MSP and verbalized uncertainty to support real-time inference.This choice complements propagation modeling but does not remove the framework’s dependence on local UQ quality.

B.4 Proof of Proposition 3: Linear Scalability

The recurrence can be evaluated in topological order because each node’s parents are processed first. Its per-node cost is linear in in-degree, and total time and space overhead scale linearly with the execution graph.

  • Topological ordering ensures that every node’s parent uncertainties are computed before evaluating its recursive uncertainty mapping.
  • Each node’s recurrence requires a single pass over its immediate parent set, with local time complexity O(|Pa(v)|).
  • Finding the topological order and tracking uncertainties across the full MAS trajectory have execution costs bounded linearly by graph size.
  • Auxiliary uncertainty storage is O(|V|), while graph adjacency lists and edge parameters require O(|V|+|E|) space.The resulting time and space overheads scale linearly with MAS execution scale.

C Supplementary Experimental Setup

The supplementary setup evaluates uncertainty across three MAS interaction structures and multiple benchmarks using node-level error indicators and AUROC and PRR metrics. Additional Qwen3-14B results show the method remains effective at larger scale.

  • The experiments use GSM8K, MedQA, and MBPP-Plus to cover mathematical reasoning, medical decision-making, and Python function generation.
  • The evaluated MAS structures are sequential, hierarchical, and decentralized, spanning chains, domain-specialized aggregation, and peer-to-peer interaction.
  • Uncertainty scores are evaluated against ground-truth node errors, where an incorrect output has error indicator e_v = 1.
  • AUROC measures ranking of incorrect versus correct nodes, while PRR evaluates uncertainty-informed selective prediction and is normalized against random and oracle baselines.
  • Qwen3-14B final-output results show PROPUQ-MAS remains effective at a larger model scale.The supplementary evaluation uses the same datasets, topologies, metrics, and local UQ baselines as the main evaluation.

D.2 Additional Intermediate-Step Results

Additional evaluations show that PROPUQ-MAS improves intermediate-step uncertainty estimation across larger models, agents, datasets, and local UQ baselines. It also outperforms sampling-based baselines across sequential and hierarchical MAS while adding limited computational overhead.

  • PROPUQ-MAS improves AUROC and PRR in most Qwen3-14B decentralized-MAS settings for both MSP and verbalized uncertainty baselines.These results indicate effective intermediate-step reliability signals at the larger Qwen3 scale.
  • PROPUQ-MAS improves AUROC in all averaged Agents 2–4 settings and PRR in nearly all settings across datasets, model families, and local UQ baselines.PRR gains are especially large for verbalized uncertainty, supporting stable intermediate-step improvements beyond one agent or dataset.
  • PROPUQ-MAS achieves the strongest uncertainty estimation in both sequential and hierarchical MAS topologies, outperforming MATU and UProp where applicable.UProp is adapted only to the sequential setting.
  • PROPUQ-MAS introduces only a lightweight propagation layer during standard MAS execution, making it more efficient than sampling-based baselines.The comparison uses MATU and UProp on MedQA with Qwen3-8B.

D.4 PRR results for scale generalization

Scale-generalization experiments vary sequential chain length and hierarchical expert-layer width. Across GSM8K and MBPP-Plus, PROPUQ-MAS consistently improves PRR over verbalized uncertainty as MAS structures become deeper or wider.

  • PROPUQ-MAS consistently improves PRR over verbalized uncertainty across GSM8K and MBPP-Plus when sequential chains become longer or hierarchical expert layers become wider.The analysis varies chain length and expert-layer width to test robustness across structural scales.
  • The results support scalability under both deeper sequential MAS structures and wider hierarchical MAS structures.They complement the AUROC results reported in the main text.

D.5 Sequential MAS Case Study

The sequential GSM8K case study shows how an incorrect intermediate interpretation can be adopted along a reasoning chain despite low downstream local uncertainty. PROPUQ-MAS detects this chain-wise risk by propagating uncertainty through accepted dependencies.

  • A critic introduces an incorrect interpretation after the planner produces a correct plan, and the refiner strongly adopts that interpretation.The final solver follows the refined plan and produces an incorrect answer despite low local uncertainty.
  • PROPUQ-MAS assigns high propagation-aware uncertainty to the final output as later agents repeatedly accept the incorrect interpretation.This identifies risk inherited through the sequential chain rather than relying only on the final solver’s local signal.
  • The case complements hierarchical selective-risk aggregation by demonstrating chain-wise risk transmission in sequential MAS.The two examples cover distinct propagation patterns across MAS topologies.

E Prompt Templates

The appendix documents role-specific MAS prompts, acceptance-score elicitation, scale-generalization instructions, and LLM-as-a-judge templates. It also includes a sequential GSM8K case with an incorrect final prediction.

  • E Prompt Templates: The appendix provides the prompt templates used in the experiments.
  • E.1 MAS Agent Response Prompts: Figures 8 and 9 show role-specific prompts for sequential and hierarchical MAS execution.
  • E.2 Acceptance Probability Elicitation: Figure 10’s self-reported acceptance score ˆαpv serves as the plug-in estimate of edge-level acceptance probability αpv during online inference.
  • E.3 Prompt for Scale Generalization Analysis: Scale generalization uses a shared critic-solver instruction in which each agent verifies incoming answers, provides feedback, and produces its own answer.This controls agent behavior while varying MAS depth or width.
  • E.4 LLM-as-a-Judge Prompt for Intermediate-Step Evaluation: GPT-5.5 judges whether sequential Critic or Refiner outputs contain substantive medical or reasoning errors.Figure 12 provides the corresponding judge prompt.
  • E.4 LLM-as-a-Judge Prompt for Intermediate-Step Evaluation: The sequential GSM8K case reports a gold answer of 12 and an incorrect final prediction of 16.The example is presented as an additional case study under sequential MAS.
Loading 2608.22130v1…