From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

Summary

Reliable uncertainty quantification (UQ) is essential for deploying large language model (LLM) agents in complex interactive environments. Existing UQ methods often rely on local signals, such as token probabilities or predictive entropy, overlooking long-range dependencies where errors accumulate across an execution trajectory. We propose RUPA, a trajectory-level UQ framework that represents an execution history as a directed trajectory graph, with nodes for reasoning states, tool interactions, and environment feedback, and edges for temporal and semantic dependencies. Uncertainty is propagated over this graph to capture how execution risk accumulates and transfers across steps, combined with trajectory-level behavioral features and goal alignment to produce a confidence estimate. Evaluated on τ-2, Terminal-Bench-2, and GAIA using 6 open-source LLMs, RUPA outperforms existing methods by providing more accurate uncertainty estimates, enabling earlier failure detection, and improving uncertainty-guided agent execution, demonstrating the importance of relational dependency modeling for reliable UQ in long-horizon agents.