PlanU: Large Language Model Reasoning through Planning under Uncertainty

Ziwei Deng (Xiamen University) · Mian Deng (Xiamen Universitiy) · Chenjing Liang (Xiamen University) · Zeming Gao (Xiamen University) · Chennan Ma (Alibaba Group) · Chenxing Lin (Xiamen University) · Haipeng Zhang (ShanghaiTech University) · Songzhu Mei (National University of Defense Technology) · Siqi Shen (Xiamen University) · Cheng Wang (Huawei Technologies Ltd.)

curiosity scoredecision-making approachesenvironmental uncertainty exploration-exploitation balancellm uncertaintymonte carlo tree search multi-step reasoningmultiple reasoning chainsprobability forecastingquantile distributionreasoning taskssearch treesstochastic environments uncertainty estimationupper confidence bounds

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.