Paper deep dive
PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems
Yaokun Liu, Yifan Liu, Daniel Yue Zhang, Ruichen Yao, Zelin Li, Dong Wang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 8/25/2026, 6:15:10 AM
Summary
The paper introduces PropUQ-MAS, a framework for propagation-aware uncertainty quantification in LLM-based multi-agent systems (MAS). It models MAS execution as a directed acyclic graph (DAG) and estimates node-wise reliability by combining local agent uncertainty with propagated uncertainty from upstream agents. The method uses a recursive propagation rule based on acceptance/critique modes to update uncertainty scores in a single forward pass, demonstrating significant improvements in AUROC and PRR across various MAS topologies and datasets.
Entities (13)
Relation Signals (10)
PropUQ-MAS → improves → PRR
confidence 95% · average relative gains of ... +47.58% in PRR
PropUQ-MAS → improves → AUROC
confidence 95% · PropUQ-MAS consistently improves UQ in MAS, with average relative gains of +6.10% in AUROC
PropUQ-MAS → appliedto → Gemma 3 12B
confidence 90% · We evaluate PropUQ-MAS on... gemma-3-12b-it
PropUQ-MAS → appliedto → Qwen3-4B
confidence 90% · We evaluate PropUQ-MAS on... Qwen3-4B
PropUQ-MAS → evaluatedon → GSM8K
confidence 90% · We evaluate PropUQ-MAS across three benchmarks... GSM8K
PropUQ-MAS → evaluatedon → MedQA
confidence 90% · We evaluate PropUQ-MAS across three benchmarks... MedQA
PropUQ-MAS → evaluatedon → MBPP-Plus
confidence 90% · We evaluate PropUQ-MAS across three benchmarks... MBPP-Plus
PropUQ-MAS → uses → Maximum Sequence Probability
confidence 85% · we select two representative local uncertainty estimators... Maximum Sequence Probability (MSP)
PropUQ-MAS → uses →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2608.22130v1
- Canonical: https://arxiv.org/abs/2608.22130v1
Trouble viewing inline? Open PDF directly →
Full Text
80,326 characters extracted from source content.
Expand or collapse full text
PropUQ-MAS: Propagation-Aware Uncertainty Quantification for LLM Multi-Agent Systems Yaokun Liu Yifan Liu Daniel Yue Zhang Affiliation: Scale AIyaokunl2, yifan40, ryao8, zelin3, dwang24@illinois.eduyue.zhang@scale.com Ruichen Yao Affiliation: University of Illinois Urbana-Champaign Zelin Li Affiliation: University of Illinois Urbana-Champaign Dong Wang Affiliation: University of Illinois Urbana-Champaign Abstract 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%+6.10\% in AUROC and +47.58%+47.58\% in PRR.1 **footnotetext: Equal contribution.11footnotetext: Code is released at https://github.com/yaokunliu/PropUQ-MAS.git. 1 Introduction Large language model (LLM)-based multi-agent systems (MAS) have emerged as a powerful paradigm for solving complex tasks by orchestrating role-specialized agents across multi-step workflows 25; 15; 10. Through inter-agent communication and strategic collaboration, MAS exhibit superior flexibility in demanding domains such as autonomous software engineering and multi-step web navigation 18. However, the same inter-agent dependencies that enable such flexibility can also shift the reliability bottleneck from individual agent failures to system-wide error propagation. Unlike isolated agents whose errors stem primarily from intrinsic limitations (e.g., hallucinations), MAS reliability is a collective property governed by interaction dynamics: An erroneous intermediate message from an upstream agent may be interpreted as a valid context by downstream agents, incorporated into subsequent reasoning, and propagated or even amplified through inter-agent communication 2; 11. Figure 1: Local UQ misses propagated risk, while PropUQ-MAS tracks propagation-aware uncertainty over the MAS execution graph. To mitigate the cascading risks, we argue that MAS requires a step-wise propagation-aware uncertainty quantification (UQ) framework, which estimates the marginal failure risks of each intermediate output during the MAS execution trajectory. Such a framework can serve as a diagnostic signal for MAS by supporting real-time monitoring of risky intermediate states, adaptive intervention before errors accumulate, and post-hoc attribution of failure-contributing steps 21; 29. These target applications require the UQ framework to be topology-agnostic and online-computable: it should handle diverse MAS structures and update uncertainty as each intermediate output is generated, without waiting for the full trajectory to complete. However, existing UQ frameworks are not designed to track step-wise uncertainty propagation in MAS. As illustrated in Figure 1, traditional LLM UQ methods estimate local uncertainty for isolated single-turn outputs using signals such as token probabilities 8; 7, self-evaluation 22; 12, or semantic consistency 19; 14. Recent agentic UQ methods extend local uncertainty estimation from single responses to multi-step reasoning trajectories 32; 6. These methods assume a sequential single-agent trajectory, whereas MAS introduces more diverse communication topologies. These differences introduce MAS-specific UQ challenges that are not addressed by agentic UQ, yet MAS-specific UQ remains largely under-explored. More recently, MATU 3 estimates trajectory-level uncertainty by the consistency of multiple sampled executions. This post-mortem design neither models uncertainty propagation nor supports real-time node-wise UQ for online monitoring. To this end, we propose PropUQ-MAS, a propagation-aware MAS UQ framework for step-wise reliability estimation. By unfolding MAS trajectories into a directed acyclic graph, PropUQ-MAS bypasses structural constraints to deliver a topology-agnostic framework. Building on this graph view, we derive a recursive propagation rule with a probabilistic interpretation: each node’s uncertainty is updated by combining its local uncertainty with propagated uncertainty inherited from upstream agents. The inherited component explicitly modulates the uncertainty propagation strength over communication channels, formalizing the likelihood of error contamination across different agent behaviors, including acceptance and critique. This establishes a tractable propagation rule that quantifies uncertainty seamlessly in a single forward pass. Extensive experiments demonstrate that PropUQ-MAS consistently improves step-wise UQ in MAS, with average relative gains of +6.10%+6.10\% in AUROC and +47.58%+47.58\% in PRR, while showing strong generalization and interpretability. 2 Related Work 2.1 LLM Uncertainty Quantification Existing LLM UQ methods estimate the reliability of an individual generation using token-level likelihoods 8; 7; 23, verbalized confidence or self-evaluation 12; 22; 26, and sampling-based semantic consistency 14; 19. These methods provide useful local reliability signals, which we use as the local uncertainty of each node. However, they treat each generation as an isolated prediction target and do not model how errors can be inherited through later interactions. As a result, a downstream output may appear locally confident while still being unreliable due to a contaminated upstream context. Recent agentic UQ methods further extend local uncertainty estimation to multi-step single-agent trajectories, either by learning situation-aware step weights or decomposing sequential decision uncertainty 32; 6. Although these methods model uncertainty over sequential trajectories, they cannot directly transfer to complex MAS topologies, such as hierarchical structures with multi-parent or multi-recipient communication. In contrast, PropUQ-MAS models uncertainty propagation over execution graphs and applies to arbitrary interaction topologies. 2.2 MAS Uncertainty Quantification Recent work shows that MAS reliability depends on communication dynamics 2; 11; 29; 13, motivating step-wise reliability monitoring. However, MAS-level UQ remains largely under-explored, and existing studies do not explicitly model how uncertainty propagates across agents during execution. MATU estimates trajectory-level uncertainty by measuring consistency across multiple sampled MAS executions 3. While useful for holistic reliability assessment, such a post-hoc design requires repeated executions and does not explicitly model how uncertainty is transmitted through inter-agent communication, making it less suitable for real-time node-wise monitoring. In contrast, PropUQ-MAS is a real-time, training-free propagation layer that computes node-wise UQ in a single MAS forward pass, enabling online monitoring of intermediate outputs. 3 Methodology 3.1 Problem Setup The execution trajectory of a multi-agent system with arbitrary topology can be represented as a directed acyclic execution graph (DAG) =(,ℰ)G=(V,E). Each node v=(i,t)∈v=(i,t) denotes an output (e.g., an intermediate message, tool-use result, or final response) produced by agent i at step t. Each directed edge (p,v)∈ℰ(p,v) indicates that the generation of node v conditions on the information from node p. The parent set of v is denoted as Pa(v)=p:(p,v)∈ℰPa(v)=\p:(p,v) \. For MAS with feedback or repeated communication, we unroll the observed execution in temporal order: each new agent output becomes a separate node, and edges point from earlier outputs used as context to the later output they condition. Thus, even recurrent communication patterns form a DAG over the realized execution trace. Unlike a single-agent trajectory, which usually follows one temporal chain, an MAS execution graph allows a node to have multiple parents when an agent conditions on several upstream messages. In this paper, our goal is to quantify propagation-aware uncertainty as a reliability signal for each intermediate output in the MAS execution graph. For each node v, let Ev∈0,1E_v∈\0,1\ denote its error event, where Ev=1E_v=1 indicates the output is incorrect. The propagation-aware uncertainty of node v is then defined as the marginal error probability: rv:=Pr(Ev=1),∀v∈.r_v:= (E_v=1), ∀ v . 3.2 Uncertainty Propagation in MAS In MAS execution, node uncertainty does not arise only from local agent generation, but can also be inherited from upstream agents through inter-agent communication. We therefore focus on the propagated component of node-wise uncertainty, which depends on the accumulated uncertainties of parent nodes as a recursive mapping ℱF: rv=ℱ(rpp∈Pa(v)),r_v=F (\r_p\_p (v) ), where rpr_p represents the accumulated uncertainty from parent node p. 3.2.1 Error Event Decomposition To instantiate the recursive mapping ℱF, we introduce an event-level decomposition over the execution graph G, separating errors caused by local agent generation from errors transmitted through incoming interactions. For each node v, we decouple its uncertainty into a local component and a cascading component inherited from parent nodes through inter-agent interactions. Local Errors. The local error event is denoted by Iv∈0,1I_v∈\0,1\, where Iv=1I_v=1 represents that node v produces an incorrect output by the inherent reasoning or generation flaws of agent i at step t, isolated from the correctness of its parent inputs. We define the local uncertainty of node v as: uv:=Pr(Iv=1),u_v:= (I_v=1 ), where uv∈[0,1]u_v∈[0,1] can be estimated by off-the-shelf single-agent uncertainty quantification methods, including verbalized self-evaluation 22; 12, token-level predictive probabilities 8; 7, and sampling-based self-consistency 19; 14. Propagated Errors. To formalize error propagation in an MAS, we treat each edge (p,v)(p,v) as a potential channel of error transmission. For each edge (p,v)∈ℰ(p,v) , node v processes information from parent node p in one of two mutually exclusive modes: acceptance (AA) or critique (CC). Let Mpv∈A,CM_pv∈\A,C\ denote this edge-level mode. Conditioned on parent error Ep=1E_p=1, we define: αpv:=Pr(Mpv=A∣Ep=1),βpv:=Pr(Mpv=C∣Ep=1),s.t. αpv+βpv=1, gathered _pv:= (M_pv=A E_p=1),\\ _pv:= (M_pv=C E_p=1),\\ .t. _pv+ _pv=1, gathered where αpv,βpv∈[0,1] _pv, _pv∈[0,1] denote the probabilities that node v accepts or critiques an erroneous output from parent node p, respectively. In online execution, the true error-conditioned parameter αpv _pv is not directly observable as EpE_p is unknown. We therefore instantiate αpv _pv with a self-reported acceptance score α^pv α_pv, which serves as a plug-in estimate of the edge-level transmission strength. More implementation details are provided in Appendix A. Based on these two interaction modes, we define two edge-level events that characterize how errors are transmitted or blocked along an interaction edge. The contamination event ZpvZ_pv occurs when the parent node p is erroneous and v accepts its information. The correction event YpvY_pv occurs when parent node p is erroneous and v critique it: Zpv:=Ep=1,Mpv=A,Ypv:=Ep=1,Mpv=C. gatheredZ_pv:=1\E_p=1,\,M_pv=A\,\\ Y_pv:=1\E_p=1,\,M_pv=C\. gathered Given rp=Pr(Ep=1)r_p= (E_p=1), the corresponding contamination and correction probabilities are: Pr(Zpv=1)=αpvrp,Pr(Ypv=1)=βpvrp. (Z_pv=1)= _pvr_p, (Y_pv=1)= _pvr_p. Structurally, the overall error event EvE_v at node v occurs if and only if the agent either suffers from a local reasoning failure or is contaminated by at least one erroneous parent: Ev=Iv∨(⋁p∈Pa(v)Zpv).E_v=I_v ( _p (v)Z_pv ). (1) The correction event YpvY_pv does not appear in EvE_v because it is not an error-generating event. 3.2.2 Recursive Uncertainty Propagation The event decomposition in Eq. (1) directly implies that node v is correct if and only if it does not suffer from a local error and none of its incoming edges transmit contamination: Pr(Ev=0)=Pr(Iv=0,⋀p∈Pa(v)Zpv=0). (E_v=0)= (I_v=0, _p (v)Z_pv=0 ). However, computing this joint probability exactly would require the joint distribution over local errors and incoming contamination events, which is not available during online MAS execution. We therefore introduce a propagation layer that only requires marginal parent uncertainties and edge-level acceptance probabilities, leading to the following conditional independence assumptions. Assumption 1 (Edge-wise conditional independence). At node v, the incoming contamination events are represented by their marginal probabilities and treated as independent: Pr(⋀p∈Pa(v)Zpv=0)=∏p∈Pa(v)Pr(Zpv=0). ( _p (v)Z_pv=0 )= _p (v) (Z_pv=0). Assumption 2 (Local-propagation independence). The local error event IvI_v is independent of the incoming contamination events Zpvp∈Pa(v)\Z_pv\_p (v) for each node v. Under Assumptions 1 and 2, the joint probability factorizes as: Pr(Ev=0)=Pr(Iv=0)∏p∈Pa(v)Pr(Zpv=0). (E_v=0)= (I_v=0) _p (v) (Z_pv=0). Therefore, we obtain the node-wise uncertainty recurrence: rv=1−(1−uv)∏p∈Pa(v)(1−αpvrp).r_v=1-(1-u_v) _p (v)(1- _pvr_p). (2) A formal derivation of Eq. (2) is provided in Appendix B.1. Eq. (2) gives the node-wise uncertainty propagation rule for MAS execution graphs. This recurrence updates the uncertainty of each agent at each step by combining its local uncertainty with the propagated risks. Algorithm 1 Propagation-aware MAS UQ 0: Execution graph =(,ℰ)G=(V,E). 0: Propagated uncertainties rvv∈\r_v\_v . 1: Obtain a topological ordering of G. 2: for each node v in topological order do 3: Estimate local uncertainty uvu_v using a single-agent UQ method. 4: for each parent p∈Pa(v)p (v) do 5: Estimate α^pv α_pv by model self-reporting. 6: end for 7: if Pa(v)=∅Pa(v)= then 8: rv←uvr_v← u_v. 9: else 10: rv←1−(1−uv)∏p∈Pa(v)(1−α^pvrp)r_v← 1-(1-u_v) _p (v)(1- α_pvr_p). 11: end if 12: end for 13: return rvv∈\r_v\_v . 3.3 Online Inference and Key Properties As illustrated in Algorithm 1, PropUQ-MAS instantiates the recursive propagation rule as an online reliability tracking procedure over the MAS execution graph. Since arbitrary MAS interaction structures can be unfolded into a DAG-structured execution trace, the same procedure applies across different MAS topologies. Given uvv∈\u_v\_v and α^pv(p,v)∈ℰ\ α_pv\_(p,v) , node-wise uncertainties are evaluated on-the-fly using Eq. (2). Crucially, since the uncertainty recurrence depends solely on immediate predecessors, rvr_v can be computed in a streaming fashion during MAS execution without requiring full trajectory completion. These propagated uncertainties serve as real-time reliability signals directly attached to each agent’s intermediate messages at each step, which empower proactive downstream control policies, such as dynamic localized replanning, routing low-confidence steps to external verifiers, or executing early stopping to terminate unpromising paths for reliable MAS. Properties of PropUQ-MAS. Beyond online computability and topology-agnostic applicability, Eq. (2) also satisfies several desirable provable properties demonstrating its probabilistic validity, non-accumulative under critique, and computational efficiency, which support its use as a propagation-aware UQ layer. Detailed proofs are provided in Appendix B. Proposition 1 (Boundedness). For any node v∈v , if uv,rp,αpv∈[0,1]u_v,r_p, _pv∈[0,1] for all p∈Pa(v)p (v), then the propagated uncertainty is bounded: 0≤rv≤1.0≤ r_v≤ 1. In particular, if Pa(v)=∅Pa(v)= , the uncertainty reduces to the boundary condition rv=uvr_v=u_v. Proposition 2 (Uncertainty Attenuation). Let Rv=maxp∈Pa(v)rpR_v= _p (v)r_p denote the maximum uncertainty among all parent nodes. If uv<Rvu_v<R_v and 1−∏p∈Pa(v)(1−αpvrp)<Rv−uv1−uv,1- _p (v)(1- _pvr_p)< R_v-u_v1-u_v, then rv<Rvr_v<R_v. Therefore, the propagation rule exhibits non-monotonicity, meaning a downstream agent can have lower uncertainty than its parent through low local uncertainty or rigorous critique (i.e., small αpv _pv). Proposition 3 (Linear Scalability). For any MAS execution graph =(,ℰ)G=(V,E), the node-wise uncertainties rvv∈\r_v\_v can be computed exactly in a single topological forward pass. The total time complexity scales linearly with the graph size: (||+|ℰ|).O(|V|+|E|). Consequently, the linear complexity guarantees that Eq. (2) is computationally efficient, enabling real-time UQ with minimal overhead across arbitrary and dynamic MAS topologies. 4 Empirical Evaluations Tasks and Datasets. We evaluate PropUQ-MAS across three benchmarks spanning two reasoning-intensive domains: (i) Math and Science Reasoning, including GSM8K 4 and MedQA 28; and (i) Code Generation, including MBPP-Plus 17. Detailed descriptions of each benchmark are provided in Appendix C.1. Base Models. We evaluate PropUQ-MAS on open-source instruction-tuned models from two families: Qwen3-4B, Qwen3-8B, and Qwen3-14B from the Qwen3 family (27), and gemma-3-12b-it (9). Qwen3 models test robustness across model scales, while Gemma-3 evaluates cross-family generalization. MAS Structures. To evaluate whether PropUQ-MAS generalizes across different interaction topologies, we consider three representative MAS structures: sequential (30; 31), hierarchical (33; 35), and decentralized (5; 16). Unless otherwise specified, each MAS contains four agents following the common practice of LLM-MAS studies (24; 1). This scale provides a controlled yet non-trivial setting, offering sufficient structural expressivity to map each topology while maintaining computational tractability. The evaluated MAS interaction topologies are illustrated in Figure 2, with detailed structure descriptions provided in Appendix C.2. Figure 2: Illustration of the three evaluated MAS interaction topologies. Table 1: Final-output uncertainty estimation across MAS topologies. PropUQ-MAS is applied on top of each local UQ baseline; shaded cells indicate relative changes over the corresponding baseline, where green/red denotes gains/drops and darker colors indicate larger absolute changes. Dataset Metric Qwen3-4B Qwen3-8B Gemma-3-12B MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ Sequential MAS GSM8K AUROC 0.578 0.617 0.466 0.501 0.605 0.625 0.505 0.680 0.471 0.517 0.581 0.651 PRR 0.160 0.238 -0.073 -0.068 0.224 0.257 -0.028 0.340 0.005 0.102 0.156 0.250 MBPP+ AUROC 0.679 0.722 0.577 0.607 0.583 0.648 0.562 0.577 0.544 0.583 0.684 0.742 PRR 0.340 0.378 0.090 0.173 0.155 0.282 0.064 0.120 0.079 0.128 0.277 0.465 MedQA AUROC 0.649 0.742 0.428 0.607 0.754 0.842 0.600 0.791 0.635 0.668 0.627 0.674 PRR 0.254 0.410 -0.167 0.236 0.496 0.624 0.217 0.482 0.232 0.240 0.237 0.322 Hierarchical MAS GSM8K AUROC 0.564 0.541 0.535 0.597 0.664 0.717 0.516 0.577 0.535 0.498 0.549 0.606 PRR 0.100 0.094 0.082 0.222 0.321 0.446 -0.001 0.153 0.063 0.060 0.080 0.204 MBPP+ AUROC 0.688 0.718 0.632 0.661 0.619 0.719 0.580 0.630 0.630 0.674 0.682 0.730 PRR 0.335 0.432 0.201 0.289 0.172 0.401 0.081 0.245 0.204 0.207 0.382 0.423 MedQA AUROC 0.628 0.760 0.621 0.705 0.658 0.711 0.604 0.722 0.567 0.604 0.660 0.669 PRR 0.238 0.417 0.216 0.296 0.277 0.349 0.223 0.362 0.115 0.184 0.358 0.351 Decentralized MAS GSM8K AUROC 0.657 0.704 0.544 0.574 0.728 0.768 0.486 0.563 0.563 0.567 0.634 0.665 PRR 0.311 0.428 0.128 0.185 0.445 0.534 -0.004 0.181 0.128 0.162 0.271 0.294 MBPP+ AUROC 0.695 0.710 0.588 0.604 0.701 0.726 0.511 0.583 0.557 0.645 0.670 0.720 PRR 0.382 0.426 0.140 0.210 0.332 0.367 0.014 0.117 0.096 0.262 0.342 0.393 MedQA AUROC 0.749 0.824 0.693 0.731 0.812 0.821 0.718 0.854 0.599 0.636 0.576 0.611 PRR 0.416 0.563 0.355 0.337 0.539 0.568 0.429 0.626 0.155 0.208 0.160 0.200 Evaluation Metrics. We evaluate uncertainty quality using AUROC and prediction rejection ratio (PRR). For each node output, we convert its correctness annotation into a binary error label, setting the error label to 1 if the output is incorrect and 0 otherwise. AUROC measures the ranking quality of uncertainty scores, testing whether incorrect outputs receive higher uncertainty than correct ones. In contrast, PRR evaluates the usefulness of uncertainty for selective prediction: outputs are rejected from most to least uncertain, and a better estimator should remove errors earlier, leading to higher retained accuracy. Thus, AUROC measures threshold-free error ranking, while PRR measures decision-level utility under uncertainty-based rejection. Detailed definitions are provided in Appendix C.3. Higher AUROC and PRR indicate better uncertainty estimation. Baselines. To assess compatibility with different single-agent UQ methods, we select two representative local uncertainty estimators for LLMs: verbalized self-evaluation (Verb.) 22 and Maximum Sequence Probability (MSP) 23 for token-level predictive probability. Each estimator is evaluated as a standalone baseline and is also used to provide the local uncertainty uvu_v for PropUQ-MAS. Because PropUQ-MAS operates with a single MAS forward pass, we treat sampling-based UQ methods that require multiple sampled executions as complementary rather than local UQ baselines. We nevertheless compare with concurrent sampling-based methods, including MATU 3 and UProp 6, in Appendix D.3. Implementation Details. All main experiments are run on NVIDIA GH200 120GB GPUs. Unless otherwise specified, generation uses temperature 0.6, top-p 0.95, and repetition penalty 1.05. The maximum generation length is set to 8192 tokens for math and science reasoning tasks and 32768 tokens for code-generation tasks. Table 2: Intermediate-agent uncertainty estimation under decentralized MAS. PropUQ cells are shaded by relative change over each baseline: green/red indicates gains/drops, and darker colors indicate larger absolute changes. Dataset Agent Metric Qwen3-4B Qwen3-8B Gemma-3-12B MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ GSM8K Agent 2 AUROC 0.667 0.695 0.586 0.622 0.754 0.769 0.544 0.601 0.589 0.591 0.640 0.664 PRR 0.372 0.421 0.144 0.224 0.499 0.528 0.056 0.201 0.185 0.184 0.248 0.284 Agent 3 AUROC 0.668 0.692 0.549 0.601 0.724 0.760 0.556 0.625 0.561 0.566 0.629 0.663 PRR 0.369 0.421 0.120 0.221 0.416 0.509 0.084 0.245 0.125 0.151 0.257 0.276 MBPP+ Agent 2 AUROC 0.692 0.734 0.569 0.590 0.690 0.729 0.490 0.546 0.687 0.642 0.666 0.691 PRR 0.368 0.454 0.126 0.169 0.325 0.373 -0.026 0.098 0.355 0.353 0.361 0.395 Agent 3 AUROC 0.743 0.761 0.627 0.630 0.699 0.698 0.566 0.602 0.639 0.665 0.663 0.705 PRR 0.415 0.484 0.253 0.252 0.349 0.355 0.158 0.190 0.241 0.290 0.339 0.395 MedQA Agent 2 AUROC 0.770 0.799 0.715 0.752 0.796 0.810 0.667 0.816 0.656 0.667 0.622 0.625 PRR 0.481 0.513 0.408 0.423 0.477 0.509 0.338 0.509 0.284 0.298 0.297 0.290 Agent 3 AUROC 0.781 0.812 0.629 0.701 0.776 0.822 0.695 0.824 0.581 0.634 0.553 0.610 PRR 0.479 0.554 0.239 0.285 0.459 0.539 0.390 0.562 0.174 0.212 0.169 0.196 Table 3: Intermediate-agent uncertainty estimation under sequential MAS on MedQA with Qwen3-8B, using GPT-5.5 judgments. Agent UQ Method AUROC PRR Critic Verb. 0.7516 0.4264 +PropUQ 0.7872 0.5779 Refiner Verb. 0.6709 0.3869 +PropUQ 0.7886 0.5012 4.1 Final-Output UQ Performance We first evaluate whether PropUQ-MAS improves uncertainty estimation for the final answer produced by a MAS. For each instance, we compare the uncertainty score of the final output produced by a standalone local UQ baseline with the propagated uncertainty score computed by PropUQ-MAS. This comparison tests whether modeling uncertainty propagation better detects final-answer errors. Table 1 shows that PropUQ-MAS improves final-output UQ in most settings, with median relative gains of +7.32%+7.32\% in AUROC and +41.36%+41.36\% in PRR across datasets, model families, and MAS topologies. The gains are especially clear when the local UQ baseline is weak or noisy, suggesting that final-agent confidence alone can miss errors inherited from upstream agents. By incorporating parent uncertainty and edge-level acceptance, PropUQ-MAS captures this interaction-induced risk and yields more informative final-answer uncertainty. The results hold across model families and scales, suggesting that PropUQ-MAS works as a training-free, model-agnostic propagation layer rather than a model-specific calibration method. The overall performance gain supports the importance of explicitly modeling uncertainty propagation in MAS reliability assessment. Additional results on Qwen3-14B are provided in Appendix D. 4.2 Intermediate-Step UQ Performance We further evaluate whether PropUQ-MAS provides reliable uncertainty signals for intermediate MAS outputs, rather than only for the final answer. This experiment tests a key requirement of MAS reliability assessment: the capacity to pinpoint early-stage failures that precipitate final system errors. 4.2.1 Verifiable Intermediate Steps We first conduct quantitative analysis within the decentralized MAS setting, where each intermediate agent output is a complete candidate solution and can be checked against the ground-truth label. This configuration enables a direct intermediate-step evaluation of uncertainty scores. We compare PropUQ-MAS with local UQ baselines to measure the benefit of modeling interaction-aware propagation at each step. Table 2 reports intermediate-agent UQ results, with node-averaged results in Appendix Table 7. We omit Agent 1 because it has no incoming messages, so its propagated uncertainty is identical to its local uncertainty, i.e., rv=uvr_v=u_v. We also omit Agent 4 in the intermediate-agent table because its output corresponds to the final MAS answer, whose results are already reported in Table 1. Across the evaluated intermediate agents, PropUQ-MAS achieves average relative gains of +6.10%+6.10\% in AUROC and +47.58%+47.58\% in PRR, showing that modeling propagated risk helps identify unreliable intermediate outputs, not only unreliable final answers. The PRR gains indicate that high-risk intermediate steps can be prioritized for rejection or intervention before they affect later agents. Figure 3: Structural scale generalization results measured by AUROC. We evaluate the robustness of uncertainty propagation across varying sequential chain lengths and hierarchical expert-layer widths. 4.2.2 LLM-Judged Reasoning Steps For intermediate reasoning steps without direct ground-truth labels, we conduct an LLM-judged evaluation on 300 randomly sampled MedQA instances under the sequential MAS setting using Qwen3-8B. We use GPT-5.5 as an LLM judge (34) to annotate Critic and Refiner outputs as erroneous when they contain substantive medical or reasoning errors likely to mislead downstream agents; the judge prompt is provided in Appendix E.4. We exclude the Planner because it is a source node with no upstream inputs and therefore does not involve uncertainty propagation. For hierarchical MAS, the summarizer is the only node that aggregates upstream uncertainty, and its output is the final answer already evaluated in Table 1. The expert agents are source nodes, leaving no additional propagated intermediate node for evaluation. Table 3 shows consistent improvements from PropUQ-MAS for both intermediate agents. On 50 randomly selected examples, human annotations agree with the GPT-5.5 judgments in 92.0%92.0\% of cases, supporting the reliability of the judge-derived labels. These results show that propagation-aware UQ extends beyond complete candidate answers to intermediate reasoning states. Overall, these results support PropUQ-MAS as an online reliability monitor for MAS execution. By attaching propagated uncertainty to intermediate steps, it can identify early-stage errors and support interventions such as localized replanning, external verification, additional critique, or early stopping before these errors affect the final answer. Additional results on Qwen3-14B are provided in Appendix D. Table 4: Ablation on self-reported acceptance weights using Qwen3-8B. The w/o α α variant fixes all edge weights to one, while w/ α α uses self-reported acceptance scores. Bold marks the better value in each pair. Dataset Metric Sequential Hierarchical Decentralized w/o α α w/ α α w/o α α w/ α α w/o α α w/ α α GSM8K AUROC 0.672 0.680 0.569 0.577 0.519 0.563 PRR 0.331 0.340 0.148 0.153 0.142 0.181 MBPP+ AUROC 0.573 0.577 0.615 0.630 0.576 0.583 PRR 0.114 0.120 0.239 0.245 0.093 0.117 MedQA AUROC 0.785 0.791 0.719 0.722 0.848 0.854 PRR 0.476 0.482 0.345 0.362 0.612 0.626 4.3 MAS Scale Analysis We further examine whether PropUQ-MAS remains effective as MAS scale changes. Following prior work on MAS scaling 20, we vary two factors that directly affect uncertainty propagation: the chain length in sequential systems and the number of parent inputs in hierarchical systems. Each agent acts as both a critic and a solver, keeping agent behavior comparable across scales while preserving reasoning capability. Prompts are provided in Appendix E. Figure 3 reports AUROC results on GSM8K and MBPP-Plus, with additional PRR results in Appendix D. PropUQ-MAS consistently improves over the local verbalized UQ baseline across all tested sequential lengths and hierarchical widths. These results indicate that the propagation rule can track uncertainty over longer chains and aggregate risks from larger parent sets, supporting its scalability under different MAS sizes. 4.4 Ablation Study We conduct an ablation study to examine whether self-reported acceptance scores provide useful edge-level signals for uncertainty propagation. The ablated variant, w/o α α, sets all edge weights to 1, uniformly propagating parent uncertainty regardless of downstream acceptance or critique. The full model, w/ α α, uses the self-reported acceptance score as the plug-in transmission weight for each edge. Table 4 shows that w/ α α consistently improves over w/o α α on both AUROC and PRR across three MAS topologies with Qwen3-8B, indicating that self-reported α α provides useful interaction signals beyond uniform uncertainty propagation. The results support the correction-sensitive design of PropUQ-MAS, where accepted upstream risks contribute more than critiqued ones. 4.5 Validation of Self-Reported Edge Weights The error-conditioned edge parameter αpv=Pr(Mpv=A∣Ep=1) _pv= (M_pv=A E_p=1) is not directly accessible during online execution, as it depends on the correctness of the parent output. We therefore examine whether the self-reported proxy α^pv α_pv preserves the relative strength of error acceptance. Under the decentralized MAS topology, we conduct an edge-level analysis across three datasets and four models. Specifically, we isolate execution edges whose parent is incorrect (Ep=1E_p=1), bin them by the child node’s self-reported adoption score α^pv α_pv, and measure the error-inheritance rate, i.e., how often the child duplicates the parent’s error. Figure 4 shows a monotonic alignment between the self-reported score and the empirical error-inheritance rate, increasing from 0.0500.050 in the lowest bin to 0.9730.973 in the highest. This monotonicity demonstrates that the self-reported α^pv α_pv serves as a reliable proxy for error-conditioned acceptance strength. Crucially, it provides this signal online without additional training or inference passes. More generally, the PropUQ-MAS propagation recurrence in Eq. (2) is agnostic to the specific choice of edge-weight estimator. When labeled calibration data are available, the self-reported α^pv αpv can therefore be replaced by calibrated or learned estimators that more accurately approximate the error-conditioned edge parameter αpv _pv. Figure 4: Child error-inheritance rate across adoption-score bins for incorrect-parent cases, aggregated over three datasets and four models. Case Study from GSM8K under Hierarchical MAS Question. A team of 4 painters worked on a mansion for 3/83/8 of a day every day for 3 weeks. How many hours of work did each painter put in? Gold Answer: 189 Final Prediction: 47.25 (incorrect) Math Agent. Answer: compute 3 weeks as 21 days and 3/83/8 of a day as 9 hours, giving 21×9=18921× 9=189 hours. Then divide by 4 painters, concluding 189/4=47.25189/4=47.25 hours per painter. Local uncertainty: 0.20 Propagation-aware uncertainty: 0.20 Acceptance by Summarizer: 0.90 Science Agent. Answer: treat 21×3/8=63/821× 3/8=63/8 days as total team time, divide by 4 painters to get 63/3263/32 days per painter, and convert to hours: (63/32)×24=47.25(63/32)× 24=47.25. Local uncertainty: 0.30 Propagation-aware uncertainty: 0.30 Acceptance by Summarizer: 0.90 Code Agent. Answer: each painter works 3/83/8 of a day, i.e., (3/8)×24=9(3/8)× 24=9 hours per day. Over 3 weeks, this is 21 days, so each painter works 9×21=1899× 21=189 hours. Local uncertainty: 0.05 Propagation-aware uncertainty: 0.05 Acceptance by Summarizer: 0.30 Summarizer. I follow the Math and Science agents: first compute 21 days and 9 hours per day, giving 189 hours. Since there are 4 painters, divide by 4 and output 47.25. The Code Agent’s answer 189 is treated as total team hours rather than per-painter hours. Local uncertainty: 0.10 Propagation-aware uncertainty: 0.469 Figure 5: Case study from GSM8K under the hierarchical MAS topology. The summarizer follows erroneous agents with low local uncertainty, while PropUQ-MAS captures the propagated risk. 4.6 Case Study Figure 5 presents a GSM8K case under the hierarchical MAS topology. The summarizer is locally confident but follows two erroneous upstream agents while assigning low acceptance to the correct one, leading to an incorrect final answer. This illustrates a common MAS failure mode: local confidence can underestimate risk when downstream agents selectively rely on unreliable upstream information. By combining parent uncertainty with edge-level acceptance, PropUQ-MAS assigns higher propagation-aware uncertainty to the final output, making the propagated error more detectable. A complementary sequential MAS case study is provided in Appendix D.5. 5 Conclusion We introduce PropUQ-MAS, a propagation-aware uncertainty quantification framework for LLM-based multi-agent systems. Unlike standard UQ methods that estimate the reliability of isolated responses, PropUQ-MAS models MAS execution as a communication-structured graph and estimates node-wise reliability by combining intrinsic local uncertainty with cascading uncertainty inherited from upstream messages. Its recursive propagation rule enables efficient uncertainty tracking in a single topological forward pass without additional training. Experiments across reasoning and code-generation tasks show consistent improvements over single-agent UQ baselines for both final-answer and intermediate-step UQ, with gains across topologies and backbone models. Acknowledgments This research is supported in part by the National Science Foundation under Grant No. CNS-2427070, IIS-2331069, IIS-2202481, IIS-2130263, CNS-2131622. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation here on. Limitations Despite its empirical effectiveness, PropUQ-MAS has several limitations. First, the theoretical propagation rule uses the latent error-conditioned transmission parameter αpv _pv, while our implementation instantiates it with a self-reported plug-in estimate α^pv α_pv. Since the parent error event is unobserved during online execution, this self-reported score may be imperfectly calibrated as a probability. We therefore view α^pv α_pv as an online proxy for edge-level transmission strength rather than a direct observation of the true error-conditioned parameter. Future work could replace this proxy with calibrated, verifier-based, or learned transmission estimators. Second, our propagation rule relies on 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 when misleading context simultaneously increases local generation error and acceptance behavior, such as under severe prompt injection or context overload. Despite these approximations, the factorized rule enables efficient single-pass uncertainty estimation and empirically improves over local UQ baselines across tasks, models, and MAS topologies. Future work could relax these assumptions by modeling correlations among local errors, acceptance behavior, and propagated uncertainty. Third, PropUQ-MAS depends on the quality of the local UQ estimator at each node. While the framework is agnostic to the specific local UQ estimator and can readily incorporate calibrated alternatives, such as temperature scaling or isotonic regression, these methods typically require labeled calibration data and may be less practical for online MAS execution. We therefore use lightweight, single-pass MSP and verbalized uncertainty to support real-time inference. Incorporating stronger local UQ estimators is complementary to our propagation framework and may further improve propagation-aware uncertainty estimation. References Bajaj et al. (2026) T. S. Bajaj, N. Singh, K. Anand, and E. Singh Position: safety and fairness in agentic ai depend on interaction topology, not on model scale or alignment. arXiv preprint arXiv:2605.01147. Cited by: §4. Cemri et al. (2026) M. Cemri, M. Z. Pan, S. Yang, L. A. Agrawal, B. Chopra, R. Tiwari, K. Keutzer, A. G. Parameswaran, D. Klein, K. Ramchandran, M. A. Zaharia, J. E. Gonzalez, and I. Stoica Why do multi-agent llm systems fail?. Advances in Neural Information Processing Systems 38. Cited by: §1, §2.2. Chen et al. (2026) T. Chen, H. Yao, J. Chen, E. E. Papalexakis, and H. Wei Every response counts: quantifying uncertainty of llm-based multi-agent systems through tensor decomposition. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 16204–16218. Cited by: §D.3, §1, §2.2, §4. Cobbe et al. (2021) K. Cobbe, V. Kosaraju, M. Bavarian, M. Chen, H. Jun, L. Kaiser, M. Plappert, J. Tworek, J. Hilton, R. Nakano, C. Hesse, and J. Schulman Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Cited by: §C.1, §4. Du et al. (2024) Y. Du, S. Li, A. Torralba, J. B. Tenenbaum, and I. Mordatch Improving factuality and reasoning in language models through multiagent debate. In Forty-first international conference on machine learning, Cited by: §C.2, §4. Duan et al. (2025) J. Duan, J. Diffenderfer, S. Madireddy, T. Chen, B. Kailkhura, and K. Xu Uprop: investigating the uncertainty propagation of llms in multi-step agentic decision-making. arXiv preprint arXiv:2506.17419. Cited by: §D.3, §1, §2.1, §4. Fadeeva et al. (2024) E. Fadeeva, A. Rubashevskii, A. Shelmanov, S. Petrakov, H. Li, H. Mubarak, E. Tsymbalov, G. Kuzmin, A. Panchenko, T. Baldwin, P. Nakov, and M. Panov Fact-checking the output of large language models via token-level uncertainty quantification. In Findings of the Association for Computational Linguistics: ACL 2024, p. 9367–9385. Cited by: §1, §2.1, §3.2.1. Fomicheva et al. (2020) M. Fomicheva, S. Sun, L. Yankovskaya, F. Blain, F. Guzmán, M. Fishel, N. Aletras, V. Chaudhary, and L. Specia Unsupervised quality estimation for neural machine translation. Transactions of the Association for Computational Linguistics 8, p. 539–555. Cited by: §1, §2.1, §3.2.1. Gemma Team (2025) Gemma Team Gemma 3 technical report. arXiv preprint arXiv:2503.19786. Cited by: §4. Hong et al. (2024) S. Hong, M. Zhuge, J. Chen, X. Zheng, Y. Cheng, J. Wang, C. Zhang, Z. Wang, S. K. S. Yau, Z. Lin, L. Zhou, C. Ran, L. Xiao, C. Wu, and J. Schmidhuber MetaGPT: meta programming for a multi-agent collaborative framework. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1. Hu et al. (2025) J. Hu, Y. Dong, S. Ao, Z. Li, B. Wang, L. Singh, G. Cheng, S. D. Ramchurn, and X. Huang Position: towards a responsible llm-empowered multi-agent systems. arXiv preprint arXiv:2502.01714. Cited by: §1, §2.2. Kadavath et al. (2022) S. Kadavath, T. Conerly, A. Askell, T. Henighan, D. Drain, E. Perez, N. Schiefer, Z. Hatfield-Dodds, N. DasSarma, E. Tran-Johnson, S. Johnston, S. E. Showk, A. Jones, N. Elhage, T. Hume, A. Chen, Y. Bai, S. Bowman, S. Fort, D. Ganguli, D. Hernandez, J. Jacobson, J. Kernion, S. Kravec, L. Lovitt, K. Ndousse, C. Olsson, S. Ringer, D. Amodei, T. Brown, J. Clark, N. Joseph, B. Mann, S. McCandlish, C. Olah, and J. Kaplan Language models (mostly) know what they know. arXiv preprint arXiv:2207.05221. Cited by: §1, §2.1, §3.2.1. Kirchhof et al. (2025) M. Kirchhof, G. Kasneci, and E. Kasneci Position: uncertainty quantification needs reassessment for large language model agents. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025 - Position Paper Track, Cited by: §2.2. Kuhn et al. (2023) L. Kuhn, Y. Gal, and S. Farquhar Semantic uncertainty: linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023, Cited by: §1, §2.1, §3.2.1. Li et al. (2023) G. Li, H. A. A. K. Hammoud, H. Itani, D. Khizbullin, and B. Ghanem CAMEL: communicative agents for ”mind” exploration of large language model society. In Thirty-seventh Conference on Neural Information Processing Systems, External Links: Link Cited by: §1. Liang et al. (2024) T. Liang, Z. He, W. Jiao, X. Wang, Y. Wang, R. Wang, Y. Yang, S. Shi, and Z. Tu Encouraging divergent thinking in large language models through multi-agent debate. In Proceedings of the 2024 conference on empirical methods in natural language processing, p. 17889–17904. Cited by: §C.2, §4. Liu et al. (2023) J. Liu, C. S. Xia, Y. Wang, and L. Zhang Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation. Advances in neural information processing systems 36, p. 21558–21572. Cited by: §C.1, §4. Liu et al. (2024) X. Liu, H. Yu, H. Zhang, Y. Xu, X. Lei, H. Lai, Y. Gu, H. Ding, K. Men, K. Yang, S. Zhang, X. Deng, A. Zeng, Z. Du, C. Zhang, S. Shen, T. Zhang, Y. Su, H. Sun, M. Huang, Y. Dong, and J. Tang AgentBench: evaluating LLMs as agents. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1. Manakul et al. (2023) P. Manakul, A. Liusie, and M. Gales Selfcheckgpt: zero-resource black-box hallucination detection for generative large language models. In Proceedings of the 2023 conference on empirical methods in natural language processing, p. 9004–9017. Cited by: §1, §2.1, §3.2.1. Qian et al. (2025) C. Qian, Z. Xie, Y. Wang, W. Liu, K. Zhu, H. Xia, Y. Dang, Z. Du, W. Chen, C. Yang, Z. Liu, and M. Sun Scaling large language model-based multi-agent collaboration. In International Conference on Learning Representations, Vol. 2025, p. 41488–41505. Cited by: §4.3. Shinn et al. (2023) N. Shinn, F. Cassano, A. Gopinath, K. R. Narasimhan, and S. Yao Reflexion: language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, External Links: Link Cited by: §1. Tian et al. (2023) K. Tian, E. Mitchell, A. Zhou, A. Sharma, R. Rafailov, H. Yao, C. Finn, and C. D. Manning Just ask for calibration: strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, p. 5433–5442. Cited by: §1, §2.1, §3.2.1, §4. Vashurin et al. (2025) R. Vashurin, E. Fadeeva, A. Vazhentsev, L. Rvanova, D. Vasilev, A. Tsvigun, S. Petrakov, R. Xing, A. B. Sadallah, K. Grishchenkov, A. Panchenko, T. Baldwin, P. Nakov, M. Panov, and A. Shelmanov Benchmarking uncertainty quantification methods for large language models with lm-polygraph. Transactions of the Association for Computational Linguistics 13, p. 220–248. Cited by: §2.1, §4. Wang et al. (2025) J. Wang, J. Wang, B. Athiwaratkun, C. Zhang, and J. Y. Zou Mixture-of-agents enhances large language model capabilities. In International Conference on Learning Representations, Vol. 2025, p. 33944–33963. Cited by: §4. Wu et al. (2024) Q. Wu, G. Bansal, J. Zhang, Y. Wu, B. Li, E. Zhu, L. Jiang, X. Zhang, S. Zhang, J. Liu, A. H. Awadallah, R. W. White, D. Burger, and C. Wang AutoGen: enabling next-gen LLM applications via multi-agent conversations. In First Conference on Language Modeling, External Links: Link Cited by: §1. Xiong et al. (2024) M. Xiong, Z. Hu, X. Lu, Y. Li, J. Fu, J. He, and B. Hooi Can llms express their uncertainty? an empirical evaluation of confidence elicitation in llms. In International Conference on Learning Representations, Vol. 2024, p. 23650–23678. Cited by: §2.1. Yang et al. (2025a) A. Yang, A. Li, B. Yang, B. Zhang, B. Hui, B. Zheng, B. Yu, C. Gao, C. Huang, C. Lv, C. Zheng, D. Liu, F. Zhou, F. Huang, F. Hu, H. Ge, H. Wei, H. Lin, J. Tang, J. Yang, J. Tu, J. Zhang, J. Yang, J. Yang, J. Zhou, J. Zhou, J. Lin, K. Dang, K. Bao, K. Yang, L. Yu, L. Deng, M. Li, M. Xue, M. Li, P. Zhang, P. Wang, Q. Zhu, R. Men, R. Gao, S. Liu, S. Luo, T. Li, T. Tang, W. Yin, X. Ren, X. Wang, X. Zhang, X. Ren, Y. Fan, Y. Su, Y. Zhang, Y. Zhang, Y. Wan, Y. Liu, Z. Wang, Z. Cui, Z. Zhang, Z. Zhou, and Z. Qiu Qwen3 technical report. arXiv preprint arXiv:2505.09388. Cited by: §4. Yang et al. (2025b) H. Yang, H. Chen, H. Guo, Y. Chen, C. Lin, S. Hu, J. Hu, X. Wu, and X. Wang Llm-medqa: enhancing medical question answering through case studies in large language models. In 2025 International Joint Conference on Neural Networks (IJCNN), p. 1–8. Cited by: §C.1, §4. Zhang et al. (2025) S. Zhang, M. Yin, J. Zhang, J. Liu, Z. Han, J. Zhang, B. Li, C. Wang, H. Wang, Y. Chen, and Q. Wu Which agent causes task failures and when? on automated failure attribution of LLM multi-agent systems. In Forty-second International Conference on Machine Learning, External Links: Link Cited by: §1, §2.2. Zhang et al. (2024) Y. Zhang, R. Sun, Y. Chen, T. Pfister, R. Zhang, and S. Ö. Arık Chain of agents: large language models collaborating on long-context tasks. Advances in Neural Information Processing Systems 37, p. 132208–132237. Cited by: §C.2, §4. Zhao et al. (2025a) J. Zhao, H. Xie, Y. Lei, X. Song, Z. Shi, L. Li, S. Liu, and H. Zhang Connecting the dots: a chain-of-collaboration prompting framework for llm agents. arXiv preprint arXiv:2505.10936. Cited by: §C.2, §4. Zhao et al. (2025b) Q. Zhao, D. Li, Y. Liu, W. Cheng, Y. Sun, M. Oishi, T. Osaki, K. Matsuda, H. Yao, C. Zhao, H. Chen, and X. Zhao Uncertainty propagation on LLM agent. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), W. Che, J. Nabende, E. Shutova, and M. T. Pilehvar (Eds.), Vienna, Austria, p. 6064–6073. External Links: Link, Document, ISBN 979-8-89176-251-0 Cited by: §1, §2.1. Zhao et al. (2026) W. Zhao, M. Yuksekgonul, S. Wu, and J. Zou Sirius: self-improving multi-agent systems via bootstrapped reasoning. Advances in Neural Information Processing Systems 38, p. 124475–124504. Cited by: §C.2, §4. Zheng et al. (2023) L. Zheng, W. Chiang, Y. Sheng, S. Zhuang, Z. Wu, Y. Zhuang, Z. Lin, Z. Li, D. Li, E. P. Xing, H. Zhang, J. E. Gonzalez, and I. Stoica Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems 36, p. 46595–46623. Cited by: §4.2.2. Zhuge et al. (2024) M. Zhuge, W. Wang, L. Kirsch, F. Faccio, D. Khizbullin, and J. Schmidhuber Language agents as optimizable graphs. arXiv preprint arXiv:2402.16823. Cited by: §C.2, §4. Appendix A Acceptance Probability Elicitation We instantiate the edge-level transmission parameter αpv _pv using a training-free self-reporting procedure. In the probabilistic formulation, αpv _pv denotes the error-conditioned acceptance probability, i.e., the probability that node v accepts information from parent node p when the parent output is erroneous. During online MAS execution, this true error-conditioned quantity is not directly observable, since the parent error variable EpE_p is unknown. We therefore use a self-reported adoption score as a plug-in estimate of the edge-level transmission strength. Specifically, after node v is generated, the corresponding agent is prompted to report an adoption score α^pv∈[0,1] α_pv∈[0,1] for each parent p∈Pa(v)p (v). The score indicates the degree to which the current output relies on the information from parent p, rather than critiquing, revising, or rejecting it. Let spvs_pv denote the reported adoption score. We set α^pv=spv,β^pv=1−α^pv. α_pv=s_pv, β_pv=1- α_pv. In the online recurrence, α^pv α_pv is used as the empirical edge weight in Eq. (2), serving as a proxy for the latent transmission parameter αpv _pv. This procedure introduces no additional training and can be applied to arbitrary MAS topologies. Since the elicited score is a self-reported proxy rather than a direct observation of the error-conditioned probability, its calibration may be imperfect. Nevertheless, the mathematical properties in Section 3.3, such as boundedness, attenuation, and linear scalability, only require edge weights in [0,1][0,1] and therefore also hold for the plug-in weights used during online inference. The prompt template is shown in Figure 10. Appendix B Detailed Proofs and Derivations This appendix provides the formal derivation of the uncertainty recurrence presented in Eq. (2), followed by detailed proofs of the key properties outlined in Section 3.3. B.1 Derivation of the Uncertainty Recurrence We derive the node-wise uncertainty recurrence in Eq. (2). Recall from the structural error composition in Eq. (1) that the overall error event EvE_v at node v is defined as: Ev=Iv∨(⋁p∈Pa(v)Zpv).E_v=I_v ( _p (v)Z_pv ). Applying De Morgan’s laws, the complement event, representing a successful and error-free output at node v, occurs if and only if the agent avoids both local intrinsic reasoning failures and cascading external contamination: Ev=0⇔Iv=0andZpv=0,∀p∈Pa(v).E_v=0 I_v=0 Z_pv=0, ∀ p (v). Expressing this structural relationship in terms of joint probability yields: Pr(Ev=0)=Pr(Iv=0∧⋀p∈Pa(v)Zpv=0). (E_v=0)= (I_v=0\ \ _p (v)Z_pv=0 ). By invoking Assumption 2 (Local-Propagation Independence), the local error event IvI_v is conditionally independent of the incoming edge-level propagation events. This conditional independence allows us to factorize the joint probability as follows: Pr(Ev=0)=Pr(Iv=0)⋅Pr(⋀p∈Pa(v)Zpv=0). (E_v=0)= (I_v=0)· ( _p (v)Z_pv=0 ). Next, by applying Assumption 1 (Edge-Wise Conditional Independence), the contamination events are mutually independent across distinct incoming edges. This tracking condition reduces the joint probability of the intersection to a product of marginal probabilities: Pr(⋀p∈Pa(v)Zpv=0)=∏p∈Pa(v)Pr(Zpv=0). ( _p (v)Z_pv=0 )= _p (v) (Z_pv=0). Combining these two factorizations yields the fully decoupled expression for the success probability: Pr(Ev=0)=Pr(Iv=0)∏p∈Pa(v)Pr(Zpv=0). (E_v=0)= (I_v=0) _p (v) (Z_pv=0). (3) By definition, the success probability of isolated local reasoning is Pr(Iv=0)=1−uv (I_v=0)=1-u_v. For each edge-level contamination event ZpvZ_pv, its marginal probability can be expanded by conditioning on the parent error state EpE_p: Pr(Zpv=1) (Z_pv=1) =Pr(Ep=1∧Mpv=A) = (E_p=1\ \ M_pv=A) =Pr(Mpv=A∣Ep=1)Pr(Ep=1) = (M_pv=A E_p=1) (E_p=1) =αpvrp, = _pvr_p, which directly implies Pr(Zpv=0)=1−αpvrp (Z_pv=0)=1- _pvr_p. Substituting these probability terms back into Eq. (3), we obtain: Pr(Ev=0)=(1−uv)∏p∈Pa(v)(1−αpvrp). (E_v=0)=(1-u_v) _p (v)(1- _pvr_p). Finally, utilizing the fundamental complement relation for total node uncertainty, rv=Pr(Ev=1)=1−Pr(Ev=0)r_v= (E_v=1)=1- (E_v=0), we arrive at the exact closure: rv=1−(1−uv)∏p∈Pa(v)(1−αpvrp),r_v=1-(1-u_v) _p (v)(1- _pvr_p), which completes the proof of Eq. (2). Boundary Condition for Source Nodes. By mathematical convention, for any source node v with no predecessors (i.e., Pa(v)=∅Pa(v)= ), the empty product evaluates to 11. Under this condition, the recurrence naturally simplifies to rv=uvr_v=u_v, preserving structural consistency across arbitrary graph entries. B.2 Proof of Proposition 1 (Boundedness) We verify that the local uncertainty recurrence relation preserves the algebraic constraints of a valid probability measure. Given the assumption that uv,rp,αpv∈[0,1]u_v,r_p, _pv∈[0,1] for all p∈Pa(v)p (v), it follows that 0≤αpvrp≤10≤ _pvr_p≤ 1 for each incoming dependency edge (p,v)∈ℰ(p,v) . This directly implies: 0≤1−αpvrp≤1.0≤ 1- _pvr_p≤ 1. Since the unit interval [0,1][0,1] is structurally closed under finite multiplication, the joint product over the parent configuration satisfies: 0≤∏p∈Pa(v)(1−αpvrp)≤1.0≤ _p (v)(1- _pvr_p)≤ 1. Multiplying this product by the bounded local success probability 1−uv∈[0,1]1-u_v∈[0,1] preserves the interval containment: 0≤(1−uv)∏p∈Pa(v)(1−αpvrp)≤1.0≤(1-u_v) _p (v)(1- _pvr_p)≤ 1. Finally, substituting this term back into the complementation formula of Eq. (2) yields: rv=1−(1−uv)∏p∈Pa(v)(1−αpvrp)⟹0≤rv≤1.r_v=1-(1-u_v) _p (v)(1- _pvr_p) 0≤ r_v≤ 1. In the boundary case where Pa(v)=∅Pa(v)= , the empty product evaluates to 11, and the expression smoothly collapses to rv=1−(1−uv)=uvr_v=1-(1-u_v)=u_v, ensuring perfect alignment with the boundary condition. This proves Proposition 1. B.3 Proof of Proposition 2: Uncertainty Attenuation Consider a non-source node v such that Pa(v)≠∅Pa(v)≠ , and let Rv=maxp∈Pa(v)rpR_v= _p (v)r_p denote the maximum uncertainty among its parent nodes. To facilitate the algebraic analysis, we define the aggregate incoming contamination probability as: Bv:=1−∏p∈Pa(v)(1−αpvrp).B_v:=1- _p (v)(1- _pvr_p). By rearranging the terms of the core recurrence relation in Eq. (2), the node-wise uncertainty rvr_v can be equivalently expressed as a linear combination of local uncertainty and external contamination: rv=uv+(1−uv)Bv.r_v=u_v+(1-u_v)B_v. (4) By hypothesis, we assume that the node possesses a lower local risk than its parents, uv<Rvu_v<R_v, and that its aggregate contamination is bounded by: Bv<Rv−uv1−uv.B_v< R_v-u_v1-u_v. (5) Since Rv≤1R_v≤ 1, the condition uv<Rvu_v<R_v guarantees that uv<1u_v<1, which ensures that the denominator (1−uv)(1-u_v) is strictly positive. Consequently, we can multiply both sides of the inequality in Eq. (5) by (1−uv)(1-u_v) without reversing the inequality sign: (1−uv)Bv<Rv−uv.(1-u_v)B_v<R_v-u_v. Adding uvu_v to both sides yields: uv+(1−uv)Bv<Rv.u_v+(1-u_v)B_v<R_v. Finally, substituting the rewritten recurrence relation from Eq. (4) into the left-hand side of the inequality directly produces: rv<Rv.r_v<R_v. This demonstrates that a downstream node can achieve a lower uncertainty score than its predecessors, formally establishing that risk does not monotonically accumulate along the MAS execution trajectory. This completes the proof of Proposition 2. Table 5: Qwen3-14B final-output uncertainty estimation across MAS topologies. PropUQ cells are shaded by relative change over each baseline: green/red indicates gains/drops, and darker colors indicate larger absolute changes. Dataset Metric Qwen3-14B MSP +PropUQ Verb. +PropUQ Sequential MAS GSM8K AUROC 0.715 0.677 0.580 0.651 PRR 0.403 0.374 0.159 0.271 MBPP+ AUROC 0.690 0.655 0.544 0.569 PRR 0.291 0.321 -0.005 0.111 MedQA AUROC 0.734 0.835 0.588 0.756 PRR 0.378 0.601 0.178 0.393 Hierarchical MAS GSM8K AUROC 0.649 0.723 0.543 0.557 PRR 0.237 0.375 0.076 0.105 MBPP+ AUROC 0.674 0.734 0.611 0.647 PRR 0.278 0.399 0.221 0.255 MedQA AUROC 0.662 0.737 0.681 0.664 PRR 0.239 0.403 0.249 0.237 Decentralized MAS GSM8K AUROC 0.608 0.659 0.586 0.612 PRR 0.200 0.307 0.154 0.181 MBPP+ AUROC 0.710 0.732 0.575 0.608 PRR 0.350 0.381 0.128 0.174 MedQA AUROC 0.753 0.813 0.684 0.686 PRR 0.401 0.535 0.372 0.346 Table 6: Qwen3-14B intermediate-agent uncertainty estimation under decentralized MAS. PropUQ cells are shaded by relative change over each baseline: green/red indicates gains/drops, and darker colors indicate larger absolute changes. Dataset Agent Metric Qwen3-14B MSP +PropUQ Verb. +PropUQ GSM8K Agent 2 AUROC 0.645 0.656 0.564 0.593 PRR 0.272 0.309 0.100 0.125 Agent 3 AUROC 0.673 0.689 0.516 0.556 PRR 0.305 0.352 0.037 0.064 MBPP+ Agent 2 AUROC 0.698 0.742 0.584 0.593 PRR 0.343 0.371 0.157 0.171 Agent 3 AUROC 0.751 0.764 0.621 0.620 PRR 0.434 0.438 0.206 0.226 MedQA Agent 2 AUROC 0.812 0.837 0.674 0.711 PRR 0.548 0.581 0.370 0.376 Agent 3 AUROC 0.789 0.834 0.719 0.765 PRR 0.509 0.568 0.452 0.435 B.4 Proof of Proposition 3: Linear Scalability By construction, the MAS execution trajectory is represented as a directed acyclic graph (DAG) =(,ℰ)G=(V,E), which inherently admits a topological sorting of its vertices, denoted by the sequence v1,v2,…,v||v_1,v_2,…,v_|V|. For any directed dependency edge (p,v)∈ℰ(p,v) , the predecessor p strictly precedes the successor v within this sequence. This structural dependency guarantees that evaluating the recursive mapping in Eq. (2) sequentially according to the topological order always ensures that all requisite parent uncertainties rp:p∈Pa(v)\r_p:p (v)\ are fully computed prior to visiting node v. The local calculation for an individual node v requires a single pass over its immediate parent set Pa(v)Pa(v): rv=1−(1−uv)∏p∈Pa(v)(1−αpvrp).r_v=1-(1-u_v) _p (v)(1- _pvr_p). The computational overhead for evaluating this node-wise recurrence scales linearly with its in-degree, yielding a local time complexity of (|Pa(v)|)O(|Pa(v)|). Summing these individual operational costs across the entire vertex set V leverages a fundamental graph-theoretic identity: ∑v∈(|Pa(v)|)=(∑v∈|Pa(v)|)=(|ℰ|). _v O(|Pa(v)|)=O ( _v |Pa(v)| )=O(|E|). Given that finding or verifying the topological ordering via standard algorithms (e.g., Kahn’s algorithm or Depth-First Search) incurs an execution cost of (||+|ℰ|)O(|V|+|E|), the cumulative computational time for tracking uncertainties across the entire MAS trajectory is tightly bounded by: (||+|ℰ|).O(|V|+|E|). Furthermore, the auxiliary space complexity is (||)O(|V|) to store the scalar uncertainty values rvv∈\r_v\_v , plus (||+|ℰ|)O(|V|+|E|) to maintain the underlying graph adjacency lists and edge-level interaction parameters. Consequently, both the time and space overheads scale linearly with the scale of MAS execution, completing the proof of Proposition 3. Appendix C Supplementary Experimental Setup C.1 Benchmark Descriptions GSM8K. GSM8K (4) contains 8.5K grade-school math word problems designed to evaluate multi-step numerical reasoning. Each problem requires translating a natural-language question into a sequence of arithmetic operations and producing a final numeric answer. MedQA. MedQA (28) consists of medical licensing exam questions that test biomedical knowledge, clinical reasoning, and diagnostic decision-making. The benchmark requires models to integrate textual context with domain-specific medical knowledge under a multiple-choice setting. MBPP-Plus. MBPP-Plus (17) extends the original MBPP benchmark with additional test cases and stricter execution-based evaluation. Each problem asks the model to generate a self-contained Python function that satisfies a functional specification. Table 7: Mean uncertainty estimation under decentralized MAS. We report AUROC and PRR averaged over Agents 2–4; superscripts show relative changes for PropUQ, with green/red indicating gains/drops. Dataset Metric Qwen3-4B Qwen3-8B Gemma-3-12B MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ MSP +PropUQ Verb. +PropUQ GSM8K AUROC 0.664 0.697+5.0% 0.560 0.599+7.0% 0.735 0.766+4.1% 0.529 0.596+12.8% 0.571 0.575+0.6% 0.634 0.664+4.7% PRR 0.351 0.423+20.7% 0.131 0.210+60.7% 0.453 0.524+15.5% 0.045 0.209+361.0% 0.146 0.166+13.5% 0.259 0.285+10.1% MBPP+ AUROC 0.710 0.735+3.5% 0.595 0.608+2.2% 0.697 0.718+3.0% 0.522 0.577+10.5% 0.628 0.651+3.7% 0.666 0.705+5.9% PRR 0.388 0.455+17.1% 0.173 0.210+21.6% 0.335 0.365+8.8% 0.049 0.135+177.4% 0.231 0.302+30.8% 0.347 0.394+13.5% MedQA AUROC 0.767 0.812+5.9% 0.679 0.728+7.2% 0.795 0.818+2.9% 0.693 0.831+19.9% 0.612 0.646+5.5% 0.584 0.615+5.4% PRR 0.459 0.543+18.5% 0.334 0.348+4.3% 0.492 0.539+9.6% 0.386 0.566+46.7% 0.204 0.239+17.1% 0.209 0.229+9.6% Table 8: Comparison with MATU and UProp on MedQA using Qwen3-8B. Time is in seconds per example, and UProp applies only to sequential MAS. Bold marks the best uncertainty metric within each topology. Metric Sampling-Based MSP Verb. MATU UProp w/o +PropUQ w/o +PropUQ Sequential MAS AUROC 0.718 0.650 0.754 0.842 0.600 0.791 PRR 0.373 0.330 0.496 0.624 0.217 0.482 Time/sample (s) 41.410 11.310 1.129 1.328 4.059 4.258 Hierarchical MAS AUROC 0.626 – 0.658 0.711 0.604 0.722 PRR 0.263 – 0.277 0.349 0.223 0.362 Time/sample (s) 56.040 – 1.536 1.735 5.522 5.721 Figure 6: Structural scale generalization results measured by PRR. We evaluate the robustness of uncertainty propagation across varying sequential chain lengths and hierarchical expert-layer widths. C.2 MAS Structure Details We provide additional details for the three MAS interaction structures used in our experiments. Sequential MAS. In the sequential MAS, we adopt a chain-of-agents design (30; 31) with four role-specialized agents: planner, critic, refiner, and solver. The planner first receives the input question, and each downstream agent processes the reasoning output of its immediate predecessor. Hierarchical MAS. In the hierarchical MAS, we follow a domain-specialized design (33; 35), where code, math, and science agents independently reason from different domain perspectives, and a summarizer agent aggregates their intermediate responses to produce the final answer. Decentralized MAS. In the decentralized MAS, agents have no predefined roles and communicate through a peer-to-peer mesh (5; 16). Each agent can condition on the input question and messages from the other agents, allowing us to evaluate uncertainty propagation under dense, role-free interactions. C.3 Evaluation Metrics Let rv∈[0,1]r_v∈[0,1] be the uncertainty score and ev∈0,1e_v∈\0,1\ be the ground-truth error indicator (ev=1e_v=1 for incorrect outputs) for node v∈evalv _eval. AUROC. AUROC quantifies the probability that an incorrect node is ranked higher than a correct one. Let =v:ev=1P=\v:e_v=1\ and =v:ev=0N=\v:e_v=0\: AUROC= = 1||||∑v∈∑w∈[(rv>rw) 1|P||N| _v _w [1(r_v>r_w) +12(rv=rw)]. + 121(r_v=r_w) ]. Prediction Rejection Ratio (PRR). PRR evaluates uncertainty-informed selective prediction. By sorting nodes in descending order of rvr_v, we compute the Area Under the Accuracy-Rejection Curve (AURC), denoted as AUCuqAUC_uq. To ensure a metric independent of the base accuracy, PRR normalizes this area against random and oracle baselines: PRR=AUCuq−AUCrandAUCoracle−AUCrand.PRR= AUC_uq-AUC_randAUC_oracle-AUC_rand. Higher AUROC and PRR scores signify superior discriminative power and practical utility for error filtering. Appendix D Additional Experiment Results D.1 Final-output Results on Qwen3-14B. Table 5 reports additional final-output UQ results using Qwen3-14B. The experiments follow the same datasets, MAS topologies, metrics, and local UQ baselines used in the main evaluation in Section 4.1. The results show that PropUQ-MAS remains effective at a larger Qwen3 scale, providing further evidence that the proposed propagation rule is not limited to smaller base models. D.2 Additional Intermediate-Step Results Table 6 further reports the intermediate-step UQ results on Qwen3-14B under the decentralized MAS setting. Following the main intermediate-step evaluation in Section 4.2, we report results for intermediate agents whose outputs can be directly judged against the ground-truth answer. PropUQ-MAS improves AUROC and PRR in most settings for both MSP and verbalized uncertainty baselines, indicating that the propagation rule also provides effective intermediate-step reliability signals at the larger Qwen3 scale. Appendix Table 7 further summarizes the averaged intermediate-step results over Agents 2–4. The improvements are consistent across datasets, model families, and local UQ baselines: PropUQ-MAS improves AUROC in all reported settings and improves PRR in nearly all settings, with especially large PRR gains for verbalized uncertainty. These averaged results confirm that propagation-aware UQ provides stable intermediate-step reliability gains, rather than improvements limited to a single agent or dataset. D.3 Comparison with Sampling-Based Baselines We compare PropUQ-MAS with two concurrent sampling-based UQ baselines, MATU (3) and UProp (6), on MedQA using Qwen3-8B under sequential and hierarchical MAS. UProp is designed for single-agent trajectories and can therefore be adapted only to the sequential setting. At the time of our experiments, official implementations were unavailable; we therefore implemented both baselines following their original papers. Table 8 shows that PropUQ-MAS achieves the strongest uncertainty estimation in both topologies: it outperforms MATU and UProp on sequential MAS, and both propagated variants outperform MATU on hierarchical MAS. Moreover, PropUQ-MAS is substantially more efficient than sampling-based baselines, as it introduces only a lightweight propagation layer during standard MAS execution. These results confirm that PropUQ-MAS effectively provides robust, online reliability signals with minimal computational overhead. D.4 PRR results for scale generalization Figure 6 reports the PRR results for the scale generalization analysis in Section 4.3. We vary the chain length in sequential MAS and the expert-layer width in hierarchical MAS. Across GSM8K and MBPP-Plus, PropUQ-MAS consistently improves over the verbalized uncertainty baseline, showing that the proposed propagation rule remains useful when the MAS trajectory becomes longer or when an aggregation node receives more parent inputs. These results complement the AUROC results in the main text and further support the scalability of PropUQ-MAS under both deeper and wider MAS structures. Additional Case Study from GSM8K under Sequential MAS Question. There are 36 penguins sunbathing. One-third swim away, and another one-third go inside a cave. How many penguins are still sunbathing? Gold Answer: 12 Final Prediction: 16 (incorrect) Planner. Plan: start with 36 penguins; compute one-third of 36 as 12 swimmers; compute another one-third of 36 as 12 cave-going penguins; subtract both groups from 36, giving 36−12−12=1236-12-12=12. Local uncertainty: 0.15 Propagation-aware uncertainty: 0.15 ↓ Planner to Critic: acceptance = 0.60 Critic. I think the plan may be incomplete: “another one-third” could refer to one-third of the remaining 24 penguins rather than one-third of the original 36. Under this interpretation, 24/3=824/3=8, leading to 24−8=1624-8=16. Local uncertainty: 0.75 Propagation-aware uncertainty: 0.773 ↓ Critic to Refiner: acceptance = 0.95 Refiner. Refined plan: start with 36; subtract 12 swimmers to get 24 remaining; then take one-third of the 24 as 8 cave-going penguins; therefore 24−8=1624-8=16. Local uncertainty: 0.20 Propagation-aware uncertainty: 0.787 ↓ Refiner to Final Solver: acceptance = 0.90 Final Solver. I follow the Refiner’s plan: after 12 penguins swim away, 24 remain; taking one-third of 24 gives 8, so the final answer is 24−8=1624-8=16. The steps seem internally consistent, so my local uncertainty is low. Local uncertainty: 0.10 Propagation-aware uncertainty: 0.738 Figure 7: Additional sequential MAS case study from GSM8K. The planner initially gives a correct plan, but the critic introduces an incorrect interpretation that is strongly adopted by later agents. Although the final solver has low local uncertainty, PropUQ-MAS assigns high propagation-aware uncertainty by tracking the accepted upstream risk. D.5 Sequential MAS Case Study Figure 7 presents a GSM8K case under the sequential MAS topology. While the hierarchical case in Section 4.6 illustrates selective aggregation over multiple upstream branches, this example focuses on a different failure mode: an error introduced at one intermediate step can be successively adopted and carried forward along a reasoning chain. In this example, the planner first produces a correct plan. The critic then introduces an alternative but incorrect interpretation of the problem, which is strongly adopted by the refiner. The final solver follows the refined plan and outputs an incorrect answer despite having low local uncertainty. This shows that a downstream agent may appear reliable from its own local perspective while still inheriting an earlier reasoning error. PropUQ-MAS identifies this failure by propagating uncertainty along the accepted dependencies in the sequential chain. As the incorrect interpretation is repeatedly accepted by later agents, the final output receives high propagation-aware uncertainty. This complementary case demonstrates that PropUQ-MAS can capture not only selective risk aggregation in hierarchical MAS, but also chain-wise risk transmission in sequential MAS. Appendix E Prompt Templates This appendix provides the prompt templates used in our experiments. E.1 MAS Agent Response Prompts Figure 8 and Figure 9 show the role-specific prompts used for sequential and hierarchical MAS execution. Sequential MAS Role Prompts Shared input: ## Input Question: QUESTION Planner Agent: You are a Planner Agent. Given the input question, design a concise step-by-step plan for solving it. Do not produce the final answer. ## Output Format: Planner Agent’s Output: [Your plan here] Critic Agent: You are a Critic Agent. You are given the input question and the Planner Agent’s plan. Evaluate whether the plan is correct and complete, and provide helpful feedback. ## Plan from Planner Agent: PLANNER_OUTPUT ## Output Format: Critic Agent’s Output: Original Plan: [Copy the provided plan here] Feedback: [Your feedback here] Refiner Agent: You are a Refiner Agent. You are given the input question, the Planner Agent’s plan, and the Critic Agent’s feedback. Produce an improved step-by-step plan. ## Original Plan and Critic Feedback: PLANNER_AND_CRITIC_OUTPUT ## Output Format: Refiner Agent’s Output: [Your refined plan here] Solver Agent: You are the final Solver Agent in a sequential MAS: Planner → Critic → Refiner → Solver. You are given the input question and the Refiner Agent’s plan. The plan may contain irrelevant or incorrect content; ignore it if it is not useful. ## Refined Plan: REFINER_OUTPUT Reason step by step and output the final answer inside YOUR_FINAL_ANSWER. Figure 8: Role-specific prompt template used for the sequential MAS. Hierarchical MAS Role Prompts Shared input: ## Input Question: QUESTION Math Agent: You are a math agent. Solve the input question from a mathematical reasoning perspective. Output the final answer inside YOUR_FINAL_ANSWER. Science Agent: You are a science agent. Solve the input question from a scientific reasoning perspective. Output the final answer inside YOUR_FINAL_ANSWER. Code Agent: You are a code agent. Solve the input question using programming or algorithmic reasoning when useful. Output the final answer inside YOUR_FINAL_ANSWER. Task Summarizer: You are a task summarizer. You are given the input question and the responses from the Math, Science, and Code agents. Synthesize their outputs and produce the final answer. ## Previous Agent Outputs: MATH_SCIENCE_CODE_OUTPUTS Output the final answer inside YOUR_FINAL_ANSWER. Figure 9: Role-specific prompt template used for the hierarchical MAS. Self-Reporting Prompt for α^pv α_pv Elicitation For each incoming agent, report message_adoption_weight as a number in [0,1]. • A higher value means your response largely accepts or reuses that agent’s message. • A lower value means your response critiques, revises, rejects, or only weakly relies on that message. ## Output one line for each directly connected incoming agent: <message_adoption agent="INCOMING_AGENT_NAME" score="FLOAT_0_TO_1"/> Figure 10: Prompt template used to elicit the self-reported acceptance score α^pv α_pv after an agent response is generated. E.2 Acceptance Probability Elicitation Prompt Figure 10 shows the prompt template used to elicit the self-reported acceptance score α^pv α_pv. This score serves as the plug-in estimate of the edge-level acceptance probability αpvα_pv in online inference. E.3 Prompt for Scale Generalization Analysis In the scale generalization analysis, we vary the number of agents while keeping their behavior comparable across scales. Each agent follows the same critic-solver instruction: it verifies incoming answers, provides feedback, and then produces its own answer. This controlled design allows us to change the MAS depth or width without introducing additional role-specific effects. Figure 11 shows the prompt used in this experiment. Critic-Solver Prompt for Scale Generalization Given the input question and answers from directly connected previous agents, independently verify each incoming answer, decide whether you agree, and identify what should be improved. If you disagree, provide an alternative solution. Then provide feedback and your own answer. ANSWER_FORMAT_INSTRUCTION ## Output Format ## Feedback - Agent X: [State whether you agree, what is correct, and what should be improved] Figure 11: Prompt template used in the scale generalization analysis, where each agent acts as both critic and solver. E.4 LLM-as-a-Judge Prompt for Intermediate-Step Evaluation For the intermediate-step evaluation in the sequential MAS, GPT-5.5 judges whether each Critic or Refiner output contains a substantive medical or reasoning error. Figure 12 shows the prompt template. LLM-as-a-Judge Prompt for Intermediate-Step Evaluation System Message You are a strict but fair expert judge for medical question answering. Return exactly one valid JSON object and no additional text. /no_think User Message Evaluate the specified intermediate MAS node using the task, reference answer, and preceding node outputs below. Assess the target node itself rather than inferring its quality solely from the final MAS prediction. ### Task Question: TASK_QUESTION Gold answer option: GOLD_ANSWER_OPTION Final MAS prediction: FINAL_MAS_PREDICTION ### Previous Intermediate Context PREVIOUS_INTERMEDIATE_CONTEXT ### Target Node Role: NODE_ROLE Output: NODE_OUTPUT ### Role-Specific Criterion ROLE_SPECIFIC_JUDGING_INSTRUCTION ### Label Definitions • "helpful": medically valid and useful, without a substantive error. • "mixed": useful but incomplete, ambiguous, or affected by a limited issue. • "harmful": contains a substantive medical or reasoning error likely to mislead downstream agents. Set "node_error" to true if and only if the label is "harmful"; otherwise, set it to false. Return exactly one JSON object with only "label", "node_error", and "rationale". Do not include Markdown fences or any other text. /no_think Role-Specific Criteria Critic: Determine whether the Critic gives a medically valid critique of the preceding plan. It should identify genuine issues or appropriately confirm correct reasoning without introducing a substantive error. Refiner: Determine whether the Refiner produces a medically valid revised plan. It should preserve or improve the preceding reasoning without introducing a substantive error. Placeholder Definitions • TASK_QUESTION: complete multiple-choice medical question, including answer options. • GOLD_ANSWER_OPTION: reference answer option; FINAL_MAS_PREDICTION: final MAS answer. • PREVIOUS_INTERMEDIATE_CONTEXT: preceding outputs in execution order; use [none] when unavailable. • NODE_ROLE: target role (Critic or Refiner); NODE_OUTPUT: target output. • ROLE_SPECIFIC_JUDGING_INSTRUCTION: criterion for the target role. Figure 12: LLM-as-a-judge prompt for labeling Critic and Refiner outputs in the sequential MedQA evaluation.