Understanding and Estimating Uncertainty Flow in Multi-Agent Systems

Multi-agent systems solve tasks by exchanging messages, and each message changes what remains uncertain about the final outcome, indicating uncertainty as the floor on how well failure can be predicted at that point. Predicting failure is therefore an uncertainty estimation problem over the whole communication record. Though recent studies show that errors and hallucinations propagated in the communication could cause the whole system to fail, they mainly focus on the final outputs, instead of capturing the inherent consensus that happens in a multi-agent system. To address these limitations, we first develop a theoretical framework of how uncertainty about the outcome evolves through communication. By applying standard martingale identities to the filtration generated by the messages, we assign each message a resolution without assuming any dependence structure among agents, and show that the same identities hold for the features observed by an estimator. Motivated by our theoretical findings, we propose CUE, a supervised probe on backbone hidden states that estimates correctness and its uncertainty after every message and attributes the resolved uncertainty to rounds. We evaluate CUE on whether a multi-agent system's final answer is correct, across 4 benchmarks, 3 multi-agent orchestrations, and 2 LLM families, against 7 baselines. CUE achieves the highest AUROC in most of the configurations on both Llama and Qwen.