From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
Summary
The paper proposes RUPA, a framework that models LLM agent execution as a dependency graph to propagate uncertainty, improving failure detection and confidence estimation in long trajectories.
View Cached Full Text
Cached at: 08/19/26, 03:58 AM
Paper page - From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents
Source: https://huggingface.co/papers/2608.16002
Abstract
RUPA models agent execution as a dependency graph to propagate uncertainty across long trajectories, improving failure detection and confidence estimation for LLM agents.
Reliableuncertainty 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 (RelationalUncertainty Propagationfor Agents), atrajectory-level UQframework forLLM agents. RUPA represents an execution history as adirected trajectory graphin 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 modelingrelational dependencyis crucial to reliable UQ for long-horizonLLM agents, providing a practical foundation for trustworthy agent execution.
View arXiv pageView PDFGitHub1Add to collection
Get this paper in your agent:
hf papers read 2608\.16002
Don’t have the latest CLI?curl \-LsSf https://hf\.co/cli/install\.sh \| bash
Models citing this paper0
No model linking this paper
Cite arxiv.org/abs/2608.16002 in a model README.md to link it from this page.
Datasets citing this paper0
No dataset linking this paper
Cite arxiv.org/abs/2608.16002 in a dataset README.md to link it from this page.
Spaces citing this paper0
No Space linking this paper
Cite arxiv.org/abs/2608.16002 in a Space README.md to link it from this page.
Collections including this paper0
No Collection including this paper
Add this paper to acollectionto link it from this page.
Similar Articles
Beyond Single-Turn Confidence: Trajectory-Adapted Uncertainty Quantification for LLM Agents
This paper studies whether single-turn uncertainty quantification methods transfer to interactive LLM agent trajectories, evaluating white-box, black-box, and reflexive scorers across five LLMs and four tool-use datasets. Results show that transfer is uneven, with black-box self-consistency often strongest, and recommend revalidating UQ methods at the trajectory level.
Your Agent Has a Genome: Sequence-Level Behavioral Analysis and Runtime Governance of LLM-Powered Autonomous Agents
This paper introduces Base Sequence Analysis, a framework that encodes LLM agent runtime behavior into compact sequences, revealing high-risk patterns like the 'P-X-P' trigram and a verification deficit. It presents Governor, a runtime intervention system that improves task success by 6.2% and reduces token consumption by 44%.
Managing Uncertainty in LLM-Generated Procedural Knowledge for Virtual Laboratory Planning
This paper presents a prototype framework for managing uncertainty in LLM-generated procedural knowledge for virtual laboratory planning, using structured domain representations to repair uncertain procedural steps.
Uncertainty Decomposition for Clarification Seeking in LLM Agents
This paper proposes a prompt-based uncertainty decomposition method for LLM agents that separates action confidence from request uncertainty, enabling proactive clarification seeking in underspecified tasks. The method is evaluated on new clarification-augmented benchmarks across five LLM backbones, showing significant improvements.
Relational Priors as Convergence Pressure in LLM-Based Multi-Agent Systems
This paper studies how making inter-agent relation semantics explicit in LLM-based multi-agent systems acts as convergence pressure, increasing agreement but not reliably improving accuracy. The authors argue relational priors should be used diagnostically and task-specifically, not as a default add-on.