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

AI summary

Overview

Research area: Multi-agent systems (MAS) built on large language models, specifically uncertainty quantification (UQ) and reliability monitoring.

Technical level: Intermediate. The core idea — adding inherited upstream risk to each agent's own confidence — is intuitive, but the paper's derivation relies on probabilistic event decomposition, directed acyclic graphs, and two explicit conditional-independence assumptions.

Scope: The paper proposes a training-free, topology-agnostic layer that assigns a propagation-aware uncertainty score to every intermediate output in an LLM multi-agent execution, evaluated across three MAS topologies, three benchmarks, and four base models.

What This Paper Is About

In an LLM multi-agent system, an error made by one agent can be read as valid context by the next agent, then carried forward and even amplified. Standard uncertainty methods judge each generation in isolation, so a downstream agent can look locally confident while being wrong because its inputs were already contaminated. The paper's goal is to estimate, for every step in the execution, the marginal probability that the output is incorrect, accounting both for the agent's own local uncertainty and for uncertainty inherited from upstream messages.

Key Contributions

1. A propagation-aware UQ formulation for MAS. The paper represents an MAS execution as a directed acyclic execution graph, where each node is one agent output and each edge means "this output conditioned on that upstream message," allowing recurrent communication to be unrolled into a DAG over the realized trace.

2. A recursive uncertainty rule with an acceptance/critique mechanism. Each edge is modeled as either acceptance or critique of the parent's information, giving a contamination term and a correction term. The resulting recurrence is r_v = 1 − (1 − u_v) · Π_{p∈Pa(v)} (1 − α_pv · r_p), combining local uncertainty u_v with a self-reported acceptance score α̂_pv.

3. Online, single-pass computation with provable properties. The rule is computed in one topological forward pass with O(|V| + |E|) time complexity, so uncertainty is available as each output is generated rather than after the trajectory finishes. The paper proves boundedness, uncertainty attenuation (a downstream agent can be less uncertain than its parent), and linear scalability.

4. Empirical validation across topologies, models, and datasets. PropUQ-MAS is layered on top of two local UQ baselines (verbalized self-evaluation and Maximum Sequence Probability) and tested on sequential, hierarchical, and decentralized MAS structures.

Main Findings

• Final-answer UQ improves in most settings. Table 1 shows median relative gains of +7.32% in AUROC and +41.36% in PRR across datasets, model families, and MAS topologies. The largest single improvements appear when the local baseline is weak: for hierarchical MAS on MedQA with Qwen3-4B and MSP, AUROC rises from 0.628 to 0.760.

• Intermediate-step UQ improves as well. In the decentralized MAS setting, where each intermediate agent output is a complete candidate solution checkable against ground truth, PropUQ-MAS achieves average relative gains of +6.10% in AUROC and +47.58% in PRR. The authors omit Agent 1 (no incoming messages, so r_v = u_v) and Agent 4 (its output is the final answer, already covered in Table 1).

• The PRR gains are much larger than the AUROC gains. The paper frames this as the practical payoff: high-risk intermediate steps can be prioritized for rejection or intervention before they influence later agents.

• The improvements are not universal. A few entries in Table 1 regress. On hierarchical GSM8K with Qwen3-4B and MSP, AUROC falls from 0.564 to 0.541 and PRR from 0.100 to 0.094; with Gemma-3-12B and MSP, AUROC falls from 0.535 to 0.498.

• LLM-judged intermediate reasoning steps also improve. On 300 randomly sampled MedQA instances under sequential MAS with Qwen3-8B and GPT-5.5 as judge, the Critic's AUROC goes from 0.7516 to 0.7872 and PRR from 0.4264 to 0.5779; the Refiner's AUROC goes from 0.6709 to 0.7886 and PRR from 0.3869 to 0.5012. On 50 randomly selected examples, human annotations agreed with the GPT-5.5 judgments in 92.0% of cases.

• Self-reported acceptance weights carry real signal. Ablating α̂ (setting all edge weights to 1) consistently hurts across all three topologies with Qwen3-8B on both AUROC and PRR (Table 4) — for example, decentralized MedQA PRR drops from 0.626 to 0.612.

• The self-reported score tracks actual error inheritance. Binning incorrect-parent edges by the child's reported adoption score, the empirical error-inheritance rate rises monotonically from 0.050 in the lowest bin to 0.973 in the highest, aggregated over three datasets and four models.

• The method scales with MAS size. Varying sequential chain length and hierarchical expert-layer width on GSM8K and MBPP-Plus, PropUQ-MAS consistently beats the local verbalized baseline at every tested scale.

• Case study shows the failure mode it targets. In a GSM8K hierarchical example, the Math and Science agents produce 47.25 (gold answer 189) with local uncertainties of 0.20 and 0.30, the Code Agent produces the correct 189 with local uncertainty 0.05, and the Summarizer accepts the two wrong answers at 0.90 each and the correct one at 0.30. The Summarizer's local uncertainty is 0.10, but its propagation-aware uncertainty is 0.469 — the error becomes detectable.

Methodology in Plain English

The researchers treat a multi-agent run as a flowchart. Each box is one agent output; each arrow means the later output used the earlier one as context. Because arrows only point forward in time — even when agents talk back and forth — the flowchart can always be written as a DAG.

For each box, they ask two separate questions. First, how likely is this agent to fail on its own, ignoring its inputs? That is the local uncertainty, borrowed directly from existing single-agent methods such as token probabilities or asking the model to evaluate itself. Second, how much bad information did it inherit from the boxes feeding into it? For each incoming arrow, the agent is asked how much it adopted that parent's content rather than critiquing or revising it. If the parent was wrong and the agent accepted it, contamination occurs; if the agent critiqued it, the error is blocked.

Combining the two questions under two simplifying assumptions — that incoming contamination events can be treated independently, and that local errors are independent of inherited ones — gives a clean product formula: the node is correct only if the agent avoided a local error and none of its incoming edges transmitted contamination. Subtract from one and you have the recurrence. Because each node only needs its immediate predecessors, scores can be computed in a streaming fashion during execution. Everything is training-free: the approach adds a reporting prompt and a small arithmetic update on top of whatever UQ method is already in use.

Experiments cover GSM8K and MedQA (math and science reasoning) and MBPP-Plus (code generation), run on Qwen3-4B, Qwen3-8B, and Qwen3-14B, plus gemma-3-12b-it for cross-family generalization. Three MAS structures are tested, each with four agents. Quality is measured with AUROC (does higher uncertainty rank incorrect outputs higher?) and PRR (does rejecting the most uncertain outputs remove errors earlier?). All main runs use NVIDIA GH200 120GB GPUs, temperature 0.6, top-p 0.95, repetition penalty 1.05, with maximum generation lengths of 8192 tokens for reasoning tasks and 32768 for code.

Why This Matters

Research impact. The paper reframes MAS reliability as a collective, interaction-driven property rather than a sum of individual agent failures. It also positions itself against MATU, which estimates trajectory-level uncertainty from consistency across multiple sampled executions — a post-hoc design that the authors argue does not model propagation and cannot support real-time, node-wise monitoring.

Real-world applications:

• Autonomous software engineering, where a mistaken design or API assumption from one agent propagates through later implementation and review steps.
• Multi-step web navigation, where an early misread of a page can be inherited by every subsequent action.
• Clinical question answering (the MedQA setting), where an erroneous intermediate claim could mislead a downstream summarizer into a wrong final recommendation.
• Online monitoring and control of agent pipelines — routing low-confidence steps to external verifiers, triggering localized replanning, adding extra critique, or stopping unpromising paths early.

Industry relevance. The method is training-free, model-agnostic, and runs in a single forward pass with linear overhead, which matters for production agentic deployments where re-running a task multiple times for sampling-based UQ is too expensive. It also requires only marginal parent uncertainties and edge-level scores, so it can be retrofitted onto existing multi-agent frameworks without retraining.

Future Directions

• Replacing the self-reported proxy with calibrated estimators. The true edge parameter α_pv is conditioned on an unobservable parent error event, so the paper uses a self-reported score as a plug-in. The authors suggest verifier-based or learned transmission estimators when labeled calibration data exist.

• Relaxing the independence assumptions. Edge-wise conditional independence and local-propagation independence may break down when upstream messages jointly affect downstream reasoning, or when misleading context simultaneously raises local error and acceptance — for example under severe prompt injection or context overload.

• Strengthening local UQ without losing online feasibility. The framework is agnostic to the local estimator, but calibrated alternatives like temperature scaling or isotonic regression need labeled data, which conflicts with real-time execution.

• Beyond UQ: closing the loop. The paper frames propagated uncertainty as an input to intervention policies (replanning, verification, early stopping) but does not evaluate whether acting on these signals actually improves MAS outcomes.

Target Audience

Researchers and engineers working on LLM multi-agent systems, agent reliability and monitoring, or uncertainty quantification for language models. It is most useful to readers who already know what AUROC measures and are comfortable with basic probabilistic notation, but the central idea — inherited uncertainty matters as much as local confidence — is accessible to practitioners building or debugging agent pipelines. Readers looking for a drop-in, training-free monitoring layer will find the algorithmic description and ablation results immediately actionable; readers interested in the formal properties can find the proofs in the paper's appendices.

Authors’ 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.