PaperlayerView exact revision on arXiv

Source-linked AI summary

From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

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

arXiv:2608.16002v1cs.CLcs.AI

TL;DR

Long-horizon LLM agents need uncertainty estimates that capture dependencies across execution trajectories, not just local step confidence. RUPA models trajectories as relational graphs and propagates uncertainty, consistently improving estimation quality, earlier failure detection, and uncertainty-guided execution across benchmarks and models.

  • Problem

    Existing agent UQ methods largely model execution steps independently or as linear sequences, leaving relational dependencies and trajectory-level uncertainty insufficiently characterized.

  • Method

    RUPA represents agent executions as directed dependency graphs and propagates uncertainty along temporal and semantic relations to estimate trajectory-level execution risk.

  • Results

    0.718 average AUROC versus 0.694 for the strongest baseline, with RUPA consistently improving uncertainty estimation, early failure detection, and uncertainty-guided execution across benchmarks and models.

  • Takeaways & Limitations

    Explicitly modeling relational dependencies supports more reliable uncertainty quantification for long-horizon LLM agent execution.

  • Takeaways & Limitations

    Prior agent UQ methods predominantly use linear trajectory representations, leaving execution-step dependency structure largely unexplored.

Abstract

from arXiv · show

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.

1 Introduction

RUPA frames uncertainty as a trajectory-level property shaped by relational dependencies among agent execution events, rather than independent stepwise confidence. It represents trajectories as directed relational graphs and propagates uncertainty to improve estimation, failure detection, and uncertainty-guided execution across diverse benchmarks and models.

  • Motivation: LLM agents pursue complex objectives through multi-step reasoning, tool use, and interaction with external environments.These capabilities span software engineering, web automation, scientific discovery, and complex decision-making tasks.
  • Problem: Existing UQ methods struggle with long-horizon agent execution because they primarily target isolated predictions or short-context generation.Agent-oriented methods also commonly model trajectories as linear sequences and aggregate uncertainty by temporal distance or semantic similarity.
  • Method: RUPA models execution as a directed relational graph whose nodes represent reasoning states, tool invocations, user interactions, and environment observations.The framework treats uncertainty as evolving through dependencies among execution events rather than as independent confidence estimates.
  • Results: RUPA consistently improves uncertainty estimation quality, early failure detection, and uncertainty-guided agent execution over existing UQ methods.The evaluation covers 3 representative agent benchmarks and 6 open-source LLMs ranging from 26B to 230B parameters.
  • Contributions: RUPA identifies relational dependencies between execution steps as a key source of uncertainty evolution and performs relation-aware uncertainty propagation to estimate execution risk.This graph-based formulation addresses limitations of methods that model trajectories as independent predictions or linear sequences.

2 Related Works

Prior LLM uncertainty quantification methods include probability-based, verbalized, and sampling-based approaches, but are mainly designed for single-turn prediction. Agent-level methods extend uncertainty estimation to full trajectories, yet largely model trajectories linearly and therefore overlook relational dependencies governing risk propagation.

  • LLM Uncertainty Quantification: LLM UQ methods are categorized into probability-based, verbalized, and sampling-based approaches for estimating prediction reliability.Probability-based methods use output-distribution signals, while verbalized methods elicit explicit confidence scores.
  • LLM Uncertainty Quantification: Despite strong performance, existing UQ methods primarily target single-turn prediction and cannot effectively characterize uncertainty across long-horizon reasoning and interaction trajectories.This limitation motivates uncertainty estimation at the trajectory level rather than only at individual predictions.
  • Agent Uncertainty Quantification: Agent UQ estimates the probability that an entire execution trajectory successfully accomplishes its target task, with methods including SAUP, Tracer, and UProp.These approaches extend traditional uncertainty estimation from individual responses to complete agent trajectories.
  • Agent Uncertainty Quantification: Existing agent UQ methods predominantly represent trajectories as linear sequences, leaving dependencies among reasoning steps unexplored and hindering accurate modeling of risk accumulation and propagation.Prior work improves uncertainty estimation by using execution history, but the relational structure within that history remains insufficiently modeled.

3 Empirical Analysis of Agent Uncertainty

Empirical analysis shows that conventional local-confidence UQ fails on long-horizon agent tasks because failures arise from relational dependencies distributed across trajectories. High-risk steps and structural failure signals appear throughout execution, motivating trajectory-level graph-based uncertainty modeling.

  • Traditional uncertainty estimation fails on long-horizon agent tasks: Traditional sequence probability and verbalized confidence perform poorly for trajectory-level failure prediction on representative τ-2 Airline and Retail tasks.The preliminary study uses Qwen3.5-27B and compares these two conventional UQ methods.
  • Traditional uncertainty estimation fails on long-horizon agent tasks: 0.205 AUROC is achieved by sequence probability on Airline, compared with 0.485 for verbalized confidence.Both values are close to random guessing, and similar observations hold on Retail.
  • Failure signals are distributed over relational trajectory dependencies: High-risk steps are distributed throughout trajectories rather than concentrated near final answers, indicating that failures can originate in intermediate reasoning or interaction steps.The analysis identifies each failed trajectory’s highest-anomaly execution step and examines its position and dependency relations.
  • Failure signals are distributed over relational trajectory dependencies: 0.981 average repetition and 0.883 average stagnation scores characterize failure steps, alongside frequent feedback-conflict and correction/retry relations.These patterns associate execution failures with relational and structural dependencies among trajectories.
  • Implication: The findings show that agent-execution uncertainty is trajectory-dependent, making linear sequence representations insufficient for characterizing risk evolution.This evidence motivates the paper’s graph-based uncertainty propagation framework.

4 Methods

RUPA models each agent execution prefix as a relational trajectory graph and propagates uncertainty through dependency edges rather than relying only on temporal order. It combines local and structurally accumulated uncertainty, including long-range momentum and goal alignment, to estimate step- and trajectory-level risk.

  • Trajectory graph construction: RUPA converts each execution trajectory into a directed dependency graph and propagates execution risk across reasoning, tool-use, and environment-interaction events.The framework is explicitly trajectory-aware and relational, targeting uncertainty accumulation across interaction steps.
  • Trajectory graph construction: Edges encode sequential, latest, repetition, progression, parallel, feedback, and goal-alignment relations, extending uncertainty modeling beyond simple temporal ordering.Edge types are determined using embedding distance and matching cues; goal alignment links the current reasoning step to the original task objective.
  • Uncertainty initialization: Each graph node receives local uncertainty from predictive entropy for assistant nodes or observable interaction signals for environment nodes.Environment signals include execution failures, empty tool responses, and conflicting environment feedback.
  • Relational uncertainty propagation: Propagation weights reflect relation reliability, relation strength, and temporal distance, while goal-alignment edges use a similarity-based alignment score instead of an edge weight.Structurally important dependencies receive greater influence, whereas obsolete execution states are gradually discounted.
  • Relational uncertainty propagation: RUPA aggregates dependency-related historical uncertainty with exponentially decayed uncertainty momentum, allowing early failures to influence later reasoning despite current confidence.The resulting step-level score is propagated forward, and complete trajectories aggregate step scores into a trajectory-level estimate where larger values indicate higher failure probability.

5 Experiments

RUPA is evaluated across three representative agent benchmarks and six open-source LLMs, consistently achieving the strongest uncertainty-estimation performance. Its trajectory-level relational modeling supports earlier failure detection, improved uncertainty-guided execution, and gains beyond local confidence signals.

  • Experimental Setup: RUPA is evaluated on τ-2, Terminal-Bench-2, and GAIA across conversational decision making, terminal-based software engineering, and open-domain problem solving.The experiments use six open-source LLMs spanning multiple model families and scales.
  • Baseline Comparisons: 0.656 average AUROC is achieved by RUPA on Qwen3.5-27B, compared with 0.559 for Entropy.On GPT-OSS-120B, RUPA achieves 0.577 AUROC versus 0.492 for Entropy, illustrating the weakness of traditional entropy-based UQ in long-horizon environments.
  • Baseline Comparisons: 0.645 average AUROC is achieved by RUPA on Qwen3.6-35B, improving over Tracer’s 0.629.The passage attributes this gap to RUPA’s ability to model relational structure-based risk propagation beyond sequential execution information.
  • Overall UQ Performance: Across six evaluated models, RUPA achieves the highest average AUROC, AUPRC, and F1 score while consistently outperforming prior agent UQ approaches.Average AUROC improves from 0.608 to 0.656 on Qwen3.5-27B, from 0.629 to 0.645 on Qwen3.6-35B, from 0.761 to 0.780 on Gemma4-26B, from 0.842 to 0.861 on Gemma4-31B, and from 0.694 to 0.718 on MiniMax-M2.7.
  • Early Failure Detection: RUPA consistently achieves higher uncertainty-estimation performance from partial trajectory prefixes, enabling earlier failure detection before execution is complete.The prefix analysis retains a fixed percentage or number of reasoning/action steps and estimates uncertainty using only the available partial trajectory.
  • Uncertainty-Guided Execution: RUPA’s uncertainty-guided action selection improves agent execution on Terminal-Bench-2 and GAIA by choosing among sampled candidate actions using predicted uncertainty.The strategy selects the action associated with the lowest predicted uncertainty score; the cited passage reports that Table 3 shows RUPA consistently achieves the strongest result, but the supplied text truncates the exact values.
  • Ablation Study: 0.718 to 0.678 AUROC and 0.805 to 0.642 AUPRC result when graph modeling is removed, showing that relational graph modeling substantially contributes to RUPA’s performance.Replacing the relational graph with a random topology causes a similar degradation, indicating that meaningful dependency structures, rather than graph features alone, drive the gains.

6 Conclusion

The paper concludes that long-horizon agent uncertainty is relational, arising from dependencies among reasoning, tools, and feedback. RUPA models these dependencies as trajectory graphs, propagates accumulated failure risk, and outperforms existing methods while enabling earlier failure detection.

  • Agent execution uncertainty arises from dependencies among reasoning steps, tool interactions, and environment feedback rather than isolated predictions.
  • RUPA represents agent trajectories as dependency graphs and propagates uncertainty along meaningful execution relations to capture accumulating failure risks.
  • RUPA consistently outperforms conventional uncertainty quantification methods and recent agent-specific baselines.
  • RUPA enables earlier failure detection and consistently improves uncertainty-guided agent execution.

A Appendix · A.1 Implementation Details of RUPA

RUPA constructs trajectory graphs from observable prefix information using normalized textual states, deterministic matching and lexical cues, while weighting relation edges by reliability and relation strength. Its implementation avoids future outcomes and verifier labels during graph construction and specifies hyperparameters for sensitivity analysis.

  • A.1 Implementation Details of RUPA: RUPA normalizes each trajectory step by concatenating assistant messages, reasoning content, tool-call signatures, and available observations.The normalized representation is lowercased, stripped of punctuation, stop words, and numeric tokens before tokenization.
  • A.1 Implementation Details of RUPA: Tool calls are canonicalized as function-name–argument signatures before deterministic trajectory-edge construction.
  • A.1 Implementation Details of RUPA: Graph construction uses only observable prefix information, excluding future outcomes and final verifier labels.
  • A.1 Implementation Details of RUPA: RUPA computes token- and tool-use matching scores between historical and current assistant nodes using text-embedding distances.The implementation uses bge-m3; token overlap is an alternative when embedding models are unavailable.
  • A.1 Implementation Details of RUPA: Lexical cues identify progression, parallel, and feedback edges from continuation, alternative-branch, and instability-related language.Examples include “next” and “therefore,” “alternative” and “fallback,” and observations containing “error,” “exception,” or “timeout.”
  • A.1 Implementation Details of RUPA: For each relation edge type τ, RUPA computes edge weights from reliability and relation strength.The reliability coefficient is derived from unlabeled training trajectories using variation in normalized relation strength.
  • A.1 Implementation Details of RUPA: The relation-weighting formulation includes a temperature parameter governing the relation-type set T.
  • A.1 Implementation Details of RUPA: RUPA’s implementation specifies detailed hyperparameters and evaluates their effects through GAIA parameter-sensitivity analysis with MiniMax-M2.7.Figure 5 plots AUROC against one hyperparameter at a time while holding the remaining settings fixed and marks default settings with a dashed gray line.

A.2 Detailed Experiment Settings

Experiments use standardized benchmark splits, prompts, and execution settings, with baselines reproduced from official code or paper descriptions and RUPA calibrated without test labels. Repeated-sampling methods use controlled decoding and sampling settings, while RUPA’s graph parameters are fixed across model families and datasets.

  • Common Evaluation Protocol: All methods share benchmark splits, prompts, and Harbor-based trajectory execution, while repeated-sampling methods use temperature 0.7 and 3 samples per query unless otherwise stated.Final uncertainty scores follow each method’s original scoring rule.
  • Baseline Reproduction: Baseline reproduction follows official implementations when available, while SAUP and Uprop are independently reimplemented from their papers and reported scoring procedures.Tracer is reproduced using its released codebase.
  • RUPA Calibration: RUPA calibrates graph construction and uncertainty propagation on unlabeled training trajectories, fixing relation weights, temporal decay, and history window size across model families and datasets.Test labels are excluded from parameter selection and calibration.

A.3 Parameter Sensitivity Ablation Analysis

RUPA’s parameter-sensitivity ablation on MiniMax-M2.7 with the GAIA dataset shows stable failure-prediction performance across reasonable hyperparameter settings, with defaults generally near strong or near-optimal regions.

  • Parameter Sensitivity: The ablation evaluates how RUPA’s hyperparameters affect final failure-prediction performance on MiniMax-M2.7 using GAIA.Each one-parameter ablation keeps the other hyperparameters fixed to the main-experiment configuration.
  • Parameter Sensitivity: RUPA remains stable under small perturbations of hyperparameters such as graph decay and momentum weight.The analysis fixes other hyperparameters at the main-experiment settings while varying one parameter at a time.
  • Parameter Sensitivity: The default hyperparameters consistently lie near strong or near-optimal regions for most parameters.This suggests the edge-weight assignment strategy balances different structural signals sensibly.
Loading 2608.16002v1…