# From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents

arXiv: https://arxiv.org/abs/2608.16002 · HTML: https://mlsanity.com/paper/2608.16002/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use.
- Builds on 36 of its 41 references that are in the map.
- First posted on arXiv 17 Aug 2026.

## Placed in

- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 30 of 36)

- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Toolformer: Language Models Can Teach Themselves to Use Tools](https://mlsanity.com/paper/2302.04761/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [WebArena: A Realistic Web Environment for Building Autonomous Agents](https://mlsanity.com/paper/2307.13854/) (2023)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [GAIA: a benchmark for General AI Assistants](https://mlsanity.com/paper/2311.12983/) (2023)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models](https://mlsanity.com/paper/2303.08896/) (2023)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [A Survey of Uncertainty in Deep Neural Networks](https://mlsanity.com/paper/2107.03342/) (2021)
- [τ2-Bench: Evaluating Conversational Agents in a Dual-Control Environment](https://mlsanity.com/paper/2506.07982/) (2025)
- [Terminal-Bench: Benchmarking Agents on Hard, Realistic Tasks in Command Line Interfaces](https://mlsanity.com/paper/2601.11868/) (2026)
- [How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering](https://mlsanity.com/paper/2012.00955/) (2020)
- [Semantic Entropy Probes: Robust and Cheap Hallucination Detection in LLMs](https://mlsanity.com/paper/2406.15927/) (2024)
- [A Survey of Large Language Models in Medicine: Progress, Application, and Challenge](https://mlsanity.com/paper/2311.05112/) (2023)
- [Beyond Binary Rewards: Training LMs to Reason About Their Uncertainty](https://mlsanity.com/paper/2507.16806/) (2025)
- [On Verbalized Confidence Scores for LLMs](https://mlsanity.com/paper/2412.14737/) (2024)
- [Reasoning Models Better Express Their Confidence](https://mlsanity.com/paper/2505.14489/) (2025)
- [Confidence Is All You Need: Few-Shot RL Fine-Tuning of Language Models](https://mlsanity.com/paper/2506.06395/) (2025)
- [UProp: Investigating the Uncertainty Propagation of LLMs in Multi-Step Agentic Decision-Making](https://mlsanity.com/paper/2506.17419/) (2025)
- [Adaptive Retrieval Without Self-Knowledge? Bringing Uncertainty Back Home](https://mlsanity.com/paper/2501.12835/) (2025)
- [Towards Uncertainty-Aware Language Agent](https://mlsanity.com/paper/2401.14016/) (2024)
- [Position: Uncertainty Quantification Needs Reassessment for Large-language Model Agents](https://mlsanity.com/paper/2505.22655/) (2025)
- [Rowen: Adaptive Retrieval-Augmented Generation for Hallucination Mitigation in LLMs](https://mlsanity.com/paper/2402.10612/) (2024)
- [Do LLMs estimate uncertainty well in instruction-following?](https://mlsanity.com/paper/2410.14582/) (2024)
- [Uncertainty Quantification in LLM Agents: Foundations, Emerging Challenges, and Opportunities](https://mlsanity.com/paper/2602.05073/) (2026)
- [Decoupling Reasoning and Confidence: Resurrecting Calibration in Reinforcement Learning from Verifiable Rewards](https://mlsanity.com/paper/2603.09117/) (2026)
- [Confidence Estimation for LLMs in Multi-turn Interactions](https://mlsanity.com/paper/2601.02179/) (2026)
- [TRACER: Trajectory Risk Aggregation for Critical Episodes in Agentic Reasoning](https://mlsanity.com/paper/2602.11409/) (2026)

## Built on by (most cited first, 1 of 1)

- [Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents](https://mlsanity.com/paper/2610.07948/) (2026)

## Abstract (arXiv)

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.