🤖 AI

From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

This paper introduces RUPA, a trajectory-level uncertainty quantification framework that models execution histories as directed graphs to propagate uncertainty across relational dependencies, thereby outperforming existing methods in detecting long-range error accumulation and improving the reliability of LLM agents in complex interactive environments.

Original authors: Zhengzhao Ma. Boxi Cao, Yaojie Lu, Hongyu Lin, Xianpei Han, Le Sun

Published 2026-08-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zhengzhao Ma. Boxi Cao, Yaojie Lu, Hongyu Lin, Xianpei Han, Le Sun

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the rapidly evolving world of artificial intelligence, a new generation of software has emerged that does more than just answer questions or write text. These systems, known as autonomous agents, are designed to act on their own. They can break a complex goal into smaller steps, use digital tools to gather information, and interact with computer environments to solve problems that require dozens or even hundreds of decisions. Think of them as digital employees capable of navigating the internet, writing code, or managing data without constant human supervision. However, as these agents take on more difficult tasks, a critical question arises: how can we know if they are about to make a mistake? Unlike a simple text generator that might produce a single wrong sentence, an agent's failure is often a slow process. A small error made early in a long chain of reasoning can ripple forward, distorting later steps and leading to a complete breakdown in the final result. For these systems to be trusted in the real world, developers need a way to measure the risk of failure as it happens, not just after the fact.

Researchers have long tried to build systems that can tell when a model is unsure. Traditional methods usually look at the immediate output of the computer, checking how confident the model seems about the very next word it is about to generate. This approach works well for short tasks, but it fails when the task stretches over a long timeline. The problem is that these methods treat each step as an isolated event, ignoring the history of how the agent got there. They miss the subtle connections between a decision made ten steps ago and the current action. If an agent misunderstands a user's request at the beginning, that initial confusion might not look like a mistake at the time, but it can cause the entire project to go off track later. Current tools are like a driver who only looks at the road directly in front of the car, missing the fact that a wrong turn was taken miles back that will eventually lead to a dead end.

To solve this, a team of researchers from the Chinese Academy of Sciences has developed a new framework called RUPA. Instead of viewing an agent's work as a simple list of steps, they map the entire process as a network of connected events. In this system, every action, tool use, and piece of feedback is a node in a graph, and the lines connecting them represent the logical relationships between them. The researchers found that errors often travel along these specific connections. By building this map, the system can trace how uncertainty grows and moves through the agent's history. It calculates a risk score for the current moment by looking not just at the immediate confidence of the model, but also at the reliability of the path that led to it. If an early step was shaky, the system recognizes that the current step is built on a weak foundation, even if the current step itself looks confident.

The team tested this approach on a wide variety of challenging tasks, including complex software engineering problems, terminal-based computing challenges, and open-ended problem-solving scenarios. They ran these tests using six different large language models, ranging from smaller to very large systems. The results showed that this new method was significantly better at spotting trouble than existing techniques. In one set of tests, the new system improved the ability to detect failures by a noticeable margin compared to the best previous methods. More importantly, it could identify potential failures much earlier in the process. While older methods often only realized something was wrong near the very end, this new approach could signal danger after just a few steps, giving the system a chance to correct its course before the task was ruined.

The researchers also demonstrated that this better understanding of risk could be used to make the agents work better. When the system was given the choice between several possible actions, it could use the risk scores to pick the safest option. In these trials, the agents guided by this new method completed more tasks successfully than those guided by traditional confidence measures. The study suggests that the key to reliable artificial intelligence is not just looking at the present moment, but understanding the structure of the journey. By mapping the relationships between every step an agent takes, we can see how small uncertainties accumulate into big problems. This approach provides a practical way to build agents that are not only capable but also trustworthy, capable of navigating complex environments without losing their way.

Technical Summary: Relational Uncertainty Propagation for LLM Agents (RUPA)

Problem Statement

Reliable uncertainty quantification (UQ) is a critical prerequisite for deploying Large Language Model (LLM) agents in complex, long-horizon interactive environments. While existing UQ methods effectively estimate confidence for isolated predictions or short-context generation, they struggle with autonomous agents that execute multi-step reasoning, tool use, and environmental interactions.

Current approaches predominantly rely on local signals, such as token probabilities, predictive entropy, or per-step confidence. These methods largely overlook long-range dependencies through which errors accumulate and propagate across an execution trajectory. Consequently, they often fail to identify agent failures whose root causes originate several reasoning or interaction steps prior to the final answer. Furthermore, existing agent-oriented UQ methods that do incorporate history typically model trajectories as linear sequences, failing to capture the inherently relational nature of dependencies between agent steps (e.g., how an early mistake influences subsequent tool use or how a feedback loop alters the reasoning path).

Methodology: RUPA Framework

The authors propose RUPA (Relational Uncertainty Propagation for Agents), a trajectory-level UQ framework that models agent execution as a structured dependency graph rather than a linear sequence. The methodology consists of three core components:

1. Relational Trajectory Graph Construction

RUPA converts an agent's execution history into a directed graph $G = (V, E)$ :

Nodes ( $V$ ): Represent execution events, including user instructions, assistant reasoning/actions, tool invocations, and environment observations.
Edges ( $E$ ): Capture logical dependencies between historical events and the current step. The framework identifies seven specific relation types:
- Sequential: Immediate preceding execution.
- Latest: Most recent environment/user instructions.
- Repetition: Actions with similar reasoning patterns or tool usage.
- Progression: Reasoning steps extending existing solutions.
- Parallel: Alternative reasoning branches under the same context.
- Feedback: Signals indicating execution failures or unstable outputs.
- Goal Alignment: Semantic dependency between current reasoning and the original task objective.

2. Relation-Aware Uncertainty Propagation

Unlike sequential aggregation, RUPA propagates uncertainty through the graph edges based on their structural importance:

Local Uncertainty ( $U_t$ ): Computed from predictive entropy for assistant nodes or observable interaction signals (e.g., execution failures, empty responses) for environment nodes.
Edge Weights ( $w_{i,t}$ ): Learned propagation weights determined by relation reliability, strength, and temporal distance. Structurally important dependencies exert greater influence, while obsolete states are discounted.
Goal Alignment Score ( $Q_{i,t}$ ): A specific score estimating the semantic alignment between the current step and the task objective.
Propagation Mechanism: The structural risk ( $G_t$ ) is calculated by aggregating uncertainty from neighboring historical nodes weighted by their edge weights. This is combined with an exponentially decayed uncertainty momentum ( $m_t$ ) to preserve long-range trends.
Final Estimation: The trajectory-level uncertainty ( $R_t$ ) is a weighted sum of the local uncertainty and the propagated historical uncertainty ( $H_t$ ):
$R_t = \lambda_u U_t + \lambda_h H_t$

3. Integration with Agent Execution

The propagated signal is combined with trajectory-level behavioral features and goal-alignment information to produce a confidence estimate for the full agent trajectory. This estimate can be used for risk detection, adaptive resampling, and decision optimization.

Key Contributions

Identification of Relational Dependencies: The work identifies that uncertainty in LLM agents is a trajectory-level property evolving over relational structures, revealing the limitations of methods that treat trajectories as independent predictions or linear sequences.
RUPA Framework: The proposal of a graph-based UQ framework that represents agent execution as a directed relational graph and performs relation-aware uncertainty propagation to estimate execution risk.
Empirical Validation: Extensive experiments across three benchmarks and six LLMs demonstrate that explicitly modeling structural dependencies is crucial for reliable UQ in long-horizon agents.

Experimental Results

The authors evaluated RUPA on three representative benchmarks: $\tau$ -2, Terminal-Bench-2, and GAIA, using six open-source LLMs ranging from 26B to 230B parameters (including Qwen3.5/3.6, Gemma4-26B, Gemma4-31B, GPT-OSS-120B, and MiniMax-M2.7).

Superior Uncertainty Estimation: RUPA consistently outperformed existing UQ methods (including Entropy, Sequence Probability, SAUP, Tracer, and UProp) across all model families. For instance, on the MiniMax-M2.7 model, RUPA improved the average AUROC from 0.694 (strongest baseline) to 0.718.
Early Failure Detection: In prefix-based evaluations, RUPA identified potential execution failures significantly earlier than existing methods. The advantage was most pronounced when only a small fraction of the trajectory was observed, indicating that propagated uncertainty signals emerge early in the execution process.
Downstream Performance Improvement: When used to guide agent execution (selecting actions with lower predicted uncertainty during multi-sample decoding), RUPA consistently improved task success rates. For example, on Terminal-Bench-2 with Qwen3.5-27B, accuracy improved from 0.105 (random selection) to 0.213 when guided by RUPA.
Complementary Information: Entropy-matched analysis showed that graph-based modeling provides uncertainty signals distinct from token-level confidence, particularly in low-entropy regions where traditional methods fail to distinguish between successful and failed trajectories.

Significance and Claims

The paper argues that explicitly modeling relational dependency is crucial for reliable uncertainty quantification in long-horizon LLM agents. The authors claim that RUPA provides a practical foundation for trustworthy agent execution by:

Capturing how execution risks accumulate and transfer across interaction steps, rather than treating steps as isolated events.
Enabling earlier detection of failures that originate from intermediate reasoning or interaction steps.
Improving the reliability of autonomous agents in diverse tasks, from software engineering to complex decision-making, by providing more accurate uncertainty estimates that can guide downstream strategies like self-correction and risk mitigation.

The work concludes that the failure of traditional UQ methods in agent settings is not merely a matter of data volume but a structural limitation in how execution history is represented, and that shifting from linear sequences to relational graphs is a necessary step toward robust autonomous agents.