# PlanU: Large Language Model Reasoning through Planning under Uncertainty

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 2 of its 55 references that are in the map.
- First posted on arXiv 21 Oct 2025.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)

## Builds on (most cited first, 2 of 2)

- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [RoT: Enhancing Large Language Models with Reflection on Search Trees](https://mlsanity.com/paper/2404.05449/) (2024)

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

- [Streaming Hallucination Detection in Long Chain-of-Thought Reasoning](https://mlsanity.com/paper/2601.02170/) (2026)
- [Uncertainty Decomposition for Clarification Seeking in LLM Agents](https://mlsanity.com/paper/2606.19559/) (2026)
- [PO-PDDL: Learning Symbolic POMDPs from Visual Demonstrations for Robot Planning Under Uncertainty](https://mlsanity.com/paper/2606.15654/) (2026)
- [SGG-ReflAct: Sub-Goal Guided ReflAct with Structured Planning for Reliable Long-Horizon Reasoning](https://mlsanity.com/paper/2609.34548/) (2026)

## Abstract (arXiv)

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.