From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
Authors: Zhengzhao Ma, Boxi Cao, Yaojie Lu, Hongyu Lin, Xianpei Han, Le Sun
Organizations: Chinese Information Processing Laboratory, Institute of Software, Chinese Academy of Sciences · University of Chinese Academy of Sciences, Beijing, China
Reliable uncertainty quantification (UQ) is essential for deploying large language model (LLM) agents in complex interactive environments. Existing UQ methods largely rely on local signals, such as token probabilities, predictive entropy, or per-step confidence, and therefore overlook the long-range dependencies through which errors accumulate across an execution trajectory. As a result, they may fail to identify agent failures whose causes originate several reasoning or interaction steps before the final answer. We propose RUPA (Relational Uncertainty Propagation for Agents), a trajectory-level UQ framework for LLM agents. RUPA represents an execution history as a directed trajectory graph in which reasoning states, tool interactions, and environment feedback are nodes connected by temporal and semantic dependency edges. It then propagates uncertainty over this graph to capture how execution risk accumulates and transfers across interaction steps. The propagated signal is combined with trajectory-level behavioral features and goal-alignment information to produce a confidence estimate for the full agent trajectory. We evaluate RUPA on representative agent benchmarks, including τ-2, Terminal-Bench-2, and GAIA, using 6 open-source LLMs spanning multiple model families. Experimental results show that RUPA consistently outperforms existing UQ methods by providing more accurate uncertainty estimates, enabling earlier failure detection, and improving uncertainty-guided agent execution across diverse agent tasks. These results demonstrate that explicitly modeling relational dependency is crucial to reliable UQ for long-horizon LLM agents, providing a practical foundation for trustworthy agent execution.
Figures & tables
Figure 1: Overview of RUPA. The agent trajectory is converted into a directed dependency graph, uncertainty is propagated over historical states, and the propagated risk is combined with local uncertainty to estimate trajectory-level uncertainty.
Domain
Random
Seq. Prob.
Verbalize
Airline
0.441
0.205
0.485
Retail
0.472
0.301
0.523
Table 1: Preliminary AUROC evaluation of traditional UQ methods on τ2 agent tasks.
Figure 2: Structural analysis of failure-indicative signals in failed agent trajectories.
Model
Method
Average
τ -2
Terminal-Bench
GAIA
AUROC
AUPRC
F1
AUROC
AUPRC
F1
AUROC
AUPRC
F1
AUROC
AUPRC
F1
Qwen3.5-27B
Entropy
0.559
0.543
0.538
0.573
0.623
0.438
0.508
0.679
0.705
0.595
0.326
0.470
Seq-prob
0.566
0.612
0.582
0.547
0.636
0.509
0.541
0.682
0.667
0.611
0.517
0.571
SAUP
0.595
0.561
0.630
0.630
0.681
0.595
0.491
0.611
0.763
0.665
0.390
0.533
Tracer
0.608
0.559
0.641
0.634
0.678
0.649
0.511
0.605
0.730
0.680
0.394
0.545
Uprop
0.588
0.623
0.645
0.628
0.691
0.677
0.530
0.668
0.671
0.606
0.511
0.587
Table 2: Uncertainty quantification performance across agent benchmarks. The best result for each model is shown in bold .
Figure 3: Prefix-based early failure detection on GAIA and Terminal-Bench with MiniMax-M2.7. Curves report AUROC and AUPRC when each method observes only a fixed percentage or a fixed number of steps from the trajectory prefix.
Figure 4: Entropy-matched analysis of trajectory-graph confidence signals.
Method
AUROC
AUPRC
F1
Full RUPA
0.718
0.805
0.755
w/o graph modeling
0.678
0.642
0.675
w/o propagation
0.689
0.657
0.694
w/o 50% graph edges
0.705
0.654
0.739
w/ random graph
0.681
0.643
0.691
Table 4: Ablation study of RUPA on 3 agent task benchmarks.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Default
Visible Window
5
weight decay δ
0.80
momentum decay γ
0.75
Graph propagation weight ηg
0.70
momentum weight ηm
0.30
History weight λh
1.0
Appendix
Table 5: Default hyperparameter settings used in RUPA.
Edge type
relation strength
Sequential
0.35
Latest
0.75
Repetition
0.95
Feedback
0.85
Progression
0.65
Parallel
0.45
Appendix
Table 6: Type-specific edge strength used in RUPA.
Figure 5: Parameter sensitivity analysis of RUPA on GAIA with MiniMax-M2.7. Each subplot shows AUROC as a function of one hyperparameter while keeping the remaining settings fixed. The dashed gray line indicates the default values of hyperparameters, or the corresponding default edge weight used in the main experiments.
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.
Yaokun Liu, Yifan Liu, Daniel Yue Zhang +3
University of Illinois Urbana-Champaign · Scale AI
Uncertainty quantification (UQ) methods for language models are typically evaluated on single-turn outputs, where uncertainty is attached to one generated answer. For LLM agents, however, the unit of observation is an interactive trajectory, where the model can ask clarifying questions, call tools, update state, and make intermediate decisions whose errors propagate to the final outcome. We study whether three common families of single-turn UQ methods transfer to this setting. Across five LLMs and four multi-turn tool-use datasets from BFCL-v4 and τ2-bench, we evaluate white-box scorers based on action-token probabilities, black-box consistency scorers based on resampled trajectories, and reflexive scorers based on model self-assessment of the trajectory. We find that transfer is often useful but uneven. Token-probability scores are highly sensitive to the choice of aggregator used across turns, reflexive scores provide the strongest low-cost baseline in most evaluated settings, and black-box self-consistency is often the strongest UQ family, with trajectory-equivalence and action-set consistency typically ranking highest among its variants. These results suggest that UQ methods developed for single generations should be revalidated at the trajectory level, with careful attention to the consistency measurement, aggregator choice, and computational budget.
Agents have attracted considerably increasing attention due to the power of executing both Reasoning and Acting (ReAct) in open and dynamic environments. The ReAct process typically exhibits a multi-turn trajectory in which one drives Large Language Models (LLMs) to generate both reasoning chains and task-specific actions in an interleaved manner. However, agents often suffer from significant uncertainty, where identical tasks yield divergent trajectories; trajectories with higher uncertainty often produce incomprehensible behaviors, severely undermining agent credibility. This work conjectures that such trajectory-level uncertainty frequently stems from cumulative turn-level reasoning uncertainty induced by LLMs; the latter often exhibits a collection of branches of divergent reasoning chains and their resulting actions. Built upon this, we present the Graph-based Reasoning UncErtainty in Trajectories (GRUET) method for the uncertainty quantification of ReAct, comprising turn-level reasoning uncertainty quantification and trajectory-level uncertainty aggregation; the former precisely quantifies reasoning uncertainty via modeling the reasoning space spanned by potential reasoning branches as a graph and then approximating the reasoning space complexity with graph complexity, while the latter employs simple aggregation strategies for quantifying the overall trajectory credibility. Empirical evaluations across nine LLMs and five benchmarks validate the effectiveness of our proposed GRUET in terms of selective generation performance, measured by AUROC, AUPRC, and AUARC.
Shuang Liang, Xin-Yu Hu, Shao-Qun Zhang
National Key Laboratory for Novel Software Technology, Nanjing University, China. · School of Intelligent Science and Technology, Nanjing University, China.