PlanU: Large Language Model Reasoning through Planning under Uncertainty

• URL: http://arxiv.org/abs/2510.18442v2
• Date: Wed, 05 Nov 2025 02:40:29 GMT
• Title: PlanU: Large Language Model Reasoning through Planning under Uncertainty
• Authors: Ziwei Deng, Mian Deng, Chenjing Liang, Zeming Gao, Chennan Ma, Chenxing Lin, Haipeng Zhang, Songzhu Mei, Siqi Shen, Cheng Wang,
• Abstract summary: Large Language Models (LLMs) are increasingly being explored across a range of reasoning tasks.<n>LLMs sometimes struggle with reasoning tasks under uncertainty that are relatively easy for humans.<n>We introduce PlanU, an LLM-based planning method that captures uncertainty within Monte Carlo Tree Search.
• Score: 18.52550377318156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large Language Models (LLMs) are increasingly being explored across a range of reasoning tasks. However, LLMs sometimes struggle with reasoning tasks under uncertainty that are relatively easy for humans, such as planning actions in stochastic environments. The adoption of LLMs for reasoning is impeded by uncertainty challenges, such as LLM uncertainty and environmental uncertainty. LLM uncertainty arises from the stochastic sampling process inherent to LLMs. Most LLM-based Decision-Making (LDM) approaches address LLM uncertainty through multiple reasoning chains or search trees. However, these approaches overlook environmental uncertainty, which leads to poor performance in environments with stochastic state transitions. Some recent LDM approaches deal with uncertainty by forecasting the probability of unknown variables. However, they are not designed for multi-step reasoning tasks that require interaction with the environment. To address uncertainty in LLM decision-making, we introduce PlanU, an LLM-based planning method that captures uncertainty within Monte Carlo Tree Search (MCTS). PlanU models the return of each node in the MCTS as a quantile distribution, which uses a set of quantiles to represent the return distribution. To balance exploration and exploitation during tree search, PlanU introduces an Upper Confidence Bounds with Curiosity (UCC) score which estimates the uncertainty of MCTS nodes. Through extensive experiments, we demonstrate the effectiveness of PlanU in LLM-based reasoning tasks under uncertainty.

Related papers

• No Global Plan in Chain-of-Thought: Uncover the Latent Planning Horizon of LLMs [65.783709850324]
  This work stems from prior complementary observations on the dynamics of Chain-of-Thought (CoT): Large Language Models (LLMs)<n>LLMs are shown latent planning of subsequent reasoning prior to CoT emergence, thereby diminishing the significance of explicit CoT.<n>We investigate the latent planning strength of LLMs, through our probing method, Tele-Lens, applying to hidden states across diverse task domains.
  arXiv  Detail & Related papers  (2026-02-02T13:46:56Z)
• Towards Reliable LLM-based Robot Planning via Combined Uncertainty Estimation [68.106428321492]
  Large language models (LLMs) demonstrate advanced reasoning abilities, enabling robots to understand natural language instructions and generate high-level plans with appropriate grounding.<n>LLMs hallucinations present a significant challenge, often leading to overconfident yet potentially misaligned or unsafe plans.<n>We present Combined Uncertainty estimation for Reliable Embodied planning (CURE), which decomposes the uncertainty into epistemic and intrinsic uncertainty, each estimated separately.
  arXiv  Detail & Related papers  (2025-10-09T10:26:58Z)
• Beyond Prompt-Induced Lies: Investigating LLM Deception on Benign Prompts [79.1081247754018]
  Large Language Models (LLMs) are widely deployed in reasoning, planning, and decision-making tasks.<n>We propose a framework based on Contact Searching Questions(CSQ) to quantify the likelihood of deception.
  arXiv  Detail & Related papers  (2025-08-08T14:46:35Z)
• WakenLLM: Evaluating Reasoning Potential and Stability in LLMs via Fine-Grained Benchmarking [34.350505059394536]
  Large Language Models (LLMs) frequently output the label Unknown in reasoning tasks.<n>We introduce WakenLLM, a framework that quantifies the portion of Unknown output attributable to model incapacity.
  arXiv  Detail & Related papers  (2025-07-22T03:21:48Z)
• Embodied Agent Interface: Benchmarking LLMs for Embodied Decision Making [85.24399869971236]
  We aim to evaluate Large Language Models (LLMs) for embodied decision making.<n>Existing evaluations tend to rely solely on a final success rate.<n>We propose a generalized interface (Embodied Agent Interface) that supports the formalization of various types of tasks.
  arXiv  Detail & Related papers  (2024-10-09T17:59:00Z)
• Unlocking the Power of LLM Uncertainty for Active In-Context Example Selection [6.813733517894384]
  Uncertainty Tripartite Testing Paradigm (Unc-TTP) is a novel method for classifying Large Language Models (LLMs) uncertainty.<n>Unc-TTP performs three rounds of sampling under varying label injection interference, enumerating all possible outcomes.<n>Our experiments show that uncertainty examples selected via Unc-TTP are more informative than certainty examples.
  arXiv  Detail & Related papers  (2024-08-17T11:33:23Z)
• Q*: Improving Multi-step Reasoning for LLMs with Deliberative Planning [53.6472920229013]
  Large Language Models (LLMs) have demonstrated impressive capability in many natural language tasks. LLMs are prone to produce errors, hallucinations and inconsistent statements when performing multi-step reasoning. We introduce Q*, a framework for guiding LLMs decoding process with deliberative planning.
  arXiv  Detail & Related papers  (2024-06-20T13:08:09Z)
• Evaluating Uncertainty-based Failure Detection for Closed-Loop LLM Planners [10.746821861109176]
  Large Language Models (LLMs) have witnessed remarkable performance as zero-shot task planners for robotic tasks.<n>However, the open-loop nature of previous works makes LLM-based planning error-prone and fragile.<n>In this work, we introduce a framework for closed-loop LLM-based planning called KnowLoop, backed by an uncertainty-based MLLMs failure detector.
  arXiv  Detail & Related papers  (2024-06-01T12:52:06Z)
• Uncertainty Estimation and Quantification for LLMs: A Simple Supervised Approach [6.209293868095268]
  We study the problem of uncertainty estimation and calibration for LLMs. We propose a supervised approach that leverages labeled datasets to estimate the uncertainty in LLMs' responses. Our method is easy to implement and adaptable to different levels of model accessibility including black box, grey box, and white box.
  arXiv  Detail & Related papers  (2024-04-24T17:10:35Z)
• Uncertainty Quantification for In-Context Learning of Large Language Models [52.891205009620364]
  In-context learning has emerged as a groundbreaking ability of Large Language Models (LLMs) We propose a novel formulation and corresponding estimation method to quantify both types of uncertainties. The proposed method offers an unsupervised way to understand the prediction of in-context learning in a plug-and-play fashion.
  arXiv  Detail & Related papers  (2024-02-15T18:46:24Z)
• Benchmarking LLMs via Uncertainty Quantification [91.72588235407379]
  The proliferation of open-source Large Language Models (LLMs) has highlighted the urgent need for comprehensive evaluation methods. We introduce a new benchmarking approach for LLMs that integrates uncertainty quantification. Our findings reveal that: I) LLMs with higher accuracy may exhibit lower certainty; II) Larger-scale LLMs may display greater uncertainty compared to their smaller counterparts; and III) Instruction-finetuning tends to increase the uncertainty of LLMs.
  arXiv  Detail & Related papers  (2024-01-23T14:29:17Z)
• Decomposing Uncertainty for Large Language Models through Input Clarification Ensembling [69.83976050879318]
  In large language models (LLMs), identifying sources of uncertainty is an important step toward improving reliability, trustworthiness, and interpretability. In this paper, we introduce an uncertainty decomposition framework for LLMs, called input clarification ensembling. Our approach generates a set of clarifications for the input, feeds them into an LLM, and ensembles the corresponding predictions.
  arXiv  Detail & Related papers  (2023-11-15T05:58:35Z)
• Tree of Uncertain Thoughts Reasoning for Large Language Models [19.926757833392212]
  We introduce the Tree of Uncertain Thoughts (TouT) - a reasoning framework tailored for Large Language Models (LLMs) Our TouT effectively leverages Monte Carlo Dropout to quantify uncertainty scores associated with LLMs' diverse local responses at these intermediate steps. We substantiate our approach with rigorous experiments on two demanding planning tasks: Game of 24 and Mini Crosswords.
  arXiv  Detail & Related papers  (2023-09-14T13:14:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.