# UProp: Investigating the Uncertainty Propagation of LLMs in Multi-Step Agentic Decision-Making

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

## Key facts

- Cited by 42 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 31 of its 41 references that are in the map.
- First posted on arXiv 20 Jun 2025.

## 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 31)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Qwen2.5 Technical Report](https://mlsanity.com/paper/2412.15115/) (2024)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [A Survey of Large Language Models](https://mlsanity.com/paper/2303.18223/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [AgentBench: Evaluating LLMs as Agents](https://mlsanity.com/paper/2308.03688/) (2023)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [A Survey of Uncertainty in Deep Neural Networks](https://mlsanity.com/paper/2107.03342/) (2021)
- [INSIDE: LLMs' Internal States Retain the Power of Hallucination Detection](https://mlsanity.com/paper/2402.03744/) (2024)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [A Survey of Embodied AI: From Simulators to Research Tasks](https://mlsanity.com/paper/2103.04918/) (2021)
- [Unsupervised Quality Estimation for Neural Machine Translation](https://mlsanity.com/paper/2005.10608/) (2020)
- [ART: Automatic multi-step reasoning and tool-use for large language models](https://mlsanity.com/paper/2303.09014/) (2023)
- [Aligning Cyber Space with Physical World: A Comprehensive Survey on Embodied AI](https://mlsanity.com/paper/2407.06886/) (2024)
- [Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities](https://mlsanity.com/paper/2405.20003/) (2024)
- [Shifting Attention to Relevance: Towards the Predictive Uncertainty Quantification of Free-Form Large Language Models](https://mlsanity.com/paper/2307.01379/) (2023)
- [Large Language Models for Robotics: A Survey](https://mlsanity.com/paper/2311.07226/) (2023)
- [A Survey of Large Language Models in Medicine: Progress, Application, and Challenge](https://mlsanity.com/paper/2311.05112/) (2023)
- [GTBench: Uncovering the Strategic Reasoning Limitations of LLMs via Game-Theoretic Evaluations](https://mlsanity.com/paper/2402.12348/) (2024)
- [Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning](https://mlsanity.com/paper/2406.14283/) (2024)
- [Towards Mitigating Hallucination in Large Language Models via Self-Reflection](https://mlsanity.com/paper/2310.06271/) (2023)
- [ReST meets ReAct: Self-Improvement for Multi-Step Reasoning LLM Agent](https://mlsanity.com/paper/2312.10003/) (2023)
- [PV-Tuning: Beyond Straight-Through Estimation for Extreme LLM Compression](https://mlsanity.com/paper/2405.14852/) (2024)
- [Contextualized Sequence Likelihood: Enhanced Confidence Scores for Natural Language Generation](https://mlsanity.com/paper/2406.01806/) (2024)
- [SAUP: Situation Awareness Uncertainty Propagation on LLM Agent](https://mlsanity.com/paper/2412.01033/) (2024)

## Built on by (most cited first, 30 of 42)

- [Uncertainty Quantification in LLM Agents: Foundations, Emerging Challenges, and Opportunities](https://mlsanity.com/paper/2602.05073/) (2026)
- [Agentic Uncertainty Quantification](https://mlsanity.com/paper/2601.15703/) (2026)
- [Agentic Confidence Calibration](https://mlsanity.com/paper/2601.15778/) (2026)
- [TRACER: Trajectory Risk Aggregation for Critical Episodes in Agentic Reasoning](https://mlsanity.com/paper/2602.11409/) (2026)
- [Hidden Measurement Error in LLM Pipelines Distorts Annotation, Evaluation, and Benchmarking](https://mlsanity.com/paper/2604.11581/) (2026)
- [LEC: Linear Expectation Constraints for Selection-Conditioned Risk Control in Selective Prediction and Routing Systems](https://mlsanity.com/paper/2512.01556/) (2025)
- [Why Semantic Entropy Fails: Geometry-Aware and Calibrated Uncertainty for Policy Optimization](https://mlsanity.com/paper/2605.21801/) (2026)
- [Uncertainty Quantification for Retrieval-Augmented Reasoning](https://mlsanity.com/paper/2510.11483/) (2025)
- [Recurrent Confidence Chain: Temporal-Aware Uncertainty Quantification in Large Language Models](https://mlsanity.com/paper/2601.13368/) (2026)
- [Knowing What You Know Is Not Enough: Large Language Model Confidences Don't Align With Their Actions](https://mlsanity.com/paper/2511.13240/) (2025)
- [Exploring Agentic Tool-Calling Decisions via Uncertainty-Aligned Reinforcement Learning](https://mlsanity.com/paper/2606.06976/) (2026)
- [Optimizing What Policies Learn From: Recoverability-aware Rollout Intervention Learning](https://mlsanity.com/paper/2608.05080/) (2026)
- [Uncertainty Propagation in LLM-Based Systems](https://mlsanity.com/paper/2604.23505/) (2026)
- [Rewarding Beliefs, Not Actions: Consistency-Guided Credit Assignment for Long-Horizon Agents](https://mlsanity.com/paper/2605.20061/) (2026)
- [From Passive Metric to Active Signal: The Evolving Role of Uncertainty Quantification in Large Language Models](https://mlsanity.com/paper/2601.15690/) (2026)
- [QUIVER: A Formal Framework for Quantifying Perturbation Propagation and Bifurcation in Compound AI Systems](https://mlsanity.com/paper/2605.23956/) (2026)
- [A Systematic Evaluation of Black-Box Uncertainty Estimation Methods for Large Language Models](https://mlsanity.com/paper/2606.19868/) (2026)
- [Bayesian Uncertainty Propagation for Agentic RAG Pipelines: A Proof-of-Concept Study on Multi-Hop Question Answering](https://mlsanity.com/paper/2607.00972/) (2026)
- [Last Step Matters: Early Uncertainty Cannot Predict Failure in Long-Horizon Agents](https://mlsanity.com/paper/2608.29685/) (2026)
- [IUQ: Interrogative Uncertainty Quantification for Long-Form Large Language Model Generation](https://mlsanity.com/paper/2604.15109/) (2026)
- [Confidence Laundering in Agent Systems: Why Uncertainty Needs a Latent Carrier](https://mlsanity.com/paper/2606.20662/) (2026)
- [Measuring Harness-Induced Belief Divergence in Multi-Step LLM Agents](https://mlsanity.com/paper/2607.04528/) (2026)
- [Beyond Single-Turn Confidence: Trajectory-Adapted Uncertainty Quantification for LLM Agents](https://mlsanity.com/paper/2608.11552/) (2026)
- [From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents](https://mlsanity.com/paper/2608.16002/) (2026)
- [Monitoring Web Agents Without Internal Signals: Observable Trajectories and Key-Step Supervision](https://mlsanity.com/paper/2609.02057/) (2026)
- [How to Speculate about Uncertainty in Agentic Coding? A Draft-Model Gate Method](https://mlsanity.com/paper/2609.05274/) (2026)
- [Directional Concentration Uncertainty: A representational approach to uncertainty quantification for generative models](https://mlsanity.com/paper/2602.13264/) (2026)
- [Proper Scoring Rules for Agentic Uncertainty Quantification](https://mlsanity.com/paper/2605.24756/) (2026)
- [Can We Trust LLM's Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework](https://mlsanity.com/paper/2607.08017/) (2026)
- [Runtime Uncertainty Monitoring for LLM-Based Multi-Agent Systems Using Bayesian Networks](https://mlsanity.com/paper/2607.25877/) (2026)

## Abstract (arXiv)

As Large Language Models (LLMs) are integrated into safety-critical applications involving sequential decision-making in the real world, it is essential to know when to trust LLM decisions. Existing LLM Uncertainty Quantification (UQ) methods are primarily designed for single-turn question-answering formats, resulting in multi-step decision-making scenarios, e.g., LLM agentic system, being underexplored. In this paper, we introduce a principled, information-theoretic framework that decomposes LLM sequential decision uncertainty into two parts: (i) internal uncertainty intrinsic to the current decision, which is focused on existing UQ methods, and (ii) extrinsic uncertainty, a Mutual-Information (MI) quantity describing how much uncertainty should be inherited from preceding decisions. We then propose UProp, an efficient and effective extrinsic uncertainty estimator that converts the direct estimation of MI to the estimation of Pointwise Mutual Information (PMI) over multiple Trajectory-Dependent Decision Processes (TDPs). UProp is evaluated over extensive multi-step decision-making benchmarks, e.g., AgentBench and HotpotQA, with state-of-the-art LLMs, e.g., GPT-4.1 and DeepSeek-V3. Experimental results demonstrate that UProp significantly outperforms existing single-turn UQ baselines equipped with thoughtful aggregation strategies. Moreover, we provide a comprehensive analysis of UProp, including sampling efficiency, potential applications, and intermediate uncertainty propagation, to demonstrate its effectiveness. Codes will be available at https://github.com/jinhaoduan/UProp.