Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation

Xinyi Ling, Ye Liu, Reza Averly, & Xia Ning · 2026

Read Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation by Xinyi Ling, Ye Liu, Reza Averly, & Xia Ning (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-03924.txt.

Introduction

Xinyi Ling and colleagues treated goal-oriented conversation as uncertainty-aware planning across multiple turns. Structured methods plan well but need fixed schemas, while language-model methods flex but lack long-horizon decisions. Their CUP framework lets a language model propose actions and a planner weigh their long-term effect on uncertainty. Tests on several conversational benchmarks showed higher success with fewer turns, plus faster information gathering and earlier confident commitment.

Catalog record

CREATORXinyi Ling, Ye Liu, Reza Averly, & Xia Ning
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31960
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.03924

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation Xinyi Ling, Ye Liu, Reza Averly, & Xia Ning Abstract Goal-oriented conversational systems require making sequential decisions under uncertainty about the user’s intent, where the algorithm must balance information acquisition and target commitment over multiple turns. Existing approaches address this challenge from different perspectives: structured methods enable multi-step planning but rely on predefined schemas, while LLM-based approaches support flexible interactions but lack long-horizon decision making, resulting in poor coordination between information acquisition and target commitment. To address this limitation, we formulate goal-oriented conversation as an uncertainty-aware sequential decision problem, where uncertainty serves as a guiding signal for multi-turn decision making. We propose a C onversation U ncertainty-aware P lanning framework ( CUP ) that integrates language models with structured planning: a language model proposes feasible actions, and a planner evaluates their long-term impact on uncertainty reduction. Experiments on multiple conversational benchmarks show that CUP consistently improves success rates while requiring fewer interaction turns. Further analysis demonstrates that uncertainty-aware planning contributes to more efficient information acquisition and earlier confident commitment. 1 Introduction Goal-oriented conversational systems aim to identify a user’s underlying intent through multi-turn interactions and commit an appropriate target, such as recommending an item or completing a task ( 5 ; 30 ; 25 ) . A central challenge lies in decision-making under uncertainty about the user’s intent: the system must balance acquiring additional information and committing to a possible target from candidate hypotheses. Asking more questions can reduce uncertainty but incur interaction cost, while committing too early risks incorrect outcomes ( 51 ; 22 ) . Effective systems must therefore consider the long-term impact of actions on uncertainty over the user’s intent. Existing approaches address this problem from different perspectives. Traditional structured methods model dialogue as a sequential decision-making process with explicit state and action spaces, enabling multi-step planning and long-horizon optimization ( 5 ; 44 ; 46 ) . However, they typically rely on predefined schemas ( 7 ) and limited domain knowledge ( 3 ) , which restrict their applicability in open-ended settings. More importantly, such structured formulations inherently impose rigid representations on the state and action space, limiting their ability to capture rich semantic information and adapt to diverse, free-form user inputs ( 4 ) . In contrast, with the rise of large language models (LLMs), LLM-based approaches have demonstrated strong performance across a wide range of conversational tasks ( 26 ; 50 ) . They leverage rich linguistic knowledge to enable flexible and generalizable interactions, but lack explicit mechanisms for optimizing over multi-turn interaction trajectories ( 41 ; 40 ; 49 ) . Consequently, their decision-making is often driven by local or heuristic strategies, without explicit reasoning about the long-term impact of actions. Despite these advances, traditional structured methods remain constrained by predefined schemas, while LLM-based approaches lack explicit mechanisms for multi-turn decision making, making it difficult for both to effectively coordinate information acquisition and target commitment over multiple turns. To address this limitation, we formulate goal-oriented conversation as an uncertainty-aware sequential decision problem, where an LLM is used to propose feasible actions while an uncertainty-guided planning module evaluates their long-term impact. Specifically, we propose a C onversation U ncertainty-aware P lanning ( CUP ) framework with three components: (1) a belief and uncertainty modeling module that maintains a distribution over candidate hypotheses and estimates the current uncertainty about the user’s intent; (2) an uncertainty-guided planning module that evaluates proposed actions based on their long-term impact; and (3) a language-grounded execution module that realizes the selected action in natural language and updates the belief state based on the user response. At each turn, the agent selects actions by considering their informativeness and long-term effects, enabling more effective multi-turn decision making. We evaluate our approach on four datasets across multiple model backbones. Experimental results show that our method consistently improves the success rate while requiring fewer interaction turns. Further analysis shows that uncertainty-aware planning leads to more efficient information acquisition and earlier confident decisions. Our contributions are as follows: (1) We identify uncertainty as a key signal in goal-oriented conversational decision making and investigate how it can guide multi-turn interaction. (2) We formulate goal-oriented conversation as an uncertainty-aware sequential decision problem and propose the CUP framework, which leverages expected information gain for long-horizon decision making. (3) We empirically demonstrate consistent improvements in both effectiveness and efficiency across multiple datasets and backbones. The code is available in https://anonymous.4open.science/r/CUP-1BD8 . 2 Related Work Uncertainty in Active Information Acquisition. Active information acquisition studies how an agent should sequentially gather observations or features to reduce its uncertainty in a downstream decision ( 16 ; 10 ; 19 ) . This problem has been studied across Bayesian experimental design ( 9 ) , sequential decision-making ( 21 ) , and active learning ( 35 ) . Goal-oriented conversation can be viewed as a sequential decision-making problem ( 8 ) in which each interaction turn can serve as an information-gathering step. Recent works in conversational information acquisition use Monte Carlo approximation ( 22 ) or probability-based uncertainty criteria ( 17 ) to guide decision making. However, existing approaches typically treat uncertainty as a myopic scoring function for the next action. In contrast, our method incorporates uncertainty directly into tree-search priors, allowing it to guide multi-step planning rather than only greedy one-step selection. Goal-Oriented Conversational Systems. Goal-oriented conversational systems aim to accomplish tasks through multi-turn interactions. Early approaches formulate conversation as a sequential decision process using slot-filling pipelines ( 29 ) , later extended to reinforcement learning ( 11 ; 39 ) and Markov decision process (MDP) frameworks for optimizing long-term task success ( 37 ; 42 ; 23 ; 43 ) . Attribute-based methods further improve information acquisition by progressively refining a candidate search space ( 52 ; 45 ; 47 ) , while recent work explores proactive conversation strategy and modular policy planners ( 12 ; 38 ; 13 ) . Despite modeling dialogue as a sequential process, many approaches rely on locally optimized policies and do not explicitly model long-horizon interaction trajectories, limiting coordination across turns ( 18 ; 2 ) . Our work addresses this gap through structured multi-step conversational planning. 3 Method 3.1 Problem Formulation Figure 1: Problem Formulation We model goal-oriented conversational planning as a partially observable sequential decision-making problem ( 43 ; 27 ) . Specifically, the agent maintains a belief state b_{t} over a candidate set C_{t} conditioned on the current conversation history h_{t} , as illustrated in Figure 1 . At each turn t , the agent first estimates the uncertainty over the current belief state b_{t} , and then selects an action a_{t} to interact with the user. With the user response r_{t} , the agent further updates the conversation history h_{t+1} , candidate set C_{t+1} and the belief state b_{t+1} for the next turn. This process forms an iterative decision loop, where uncertainty guides action selection , enabling the agent to balance information acquisition and target commitment over multiple turns. 3.2 CUP Overview Our proposed C onversation U ncertainty-aware P lanning framework ( CUP ) consists of three components, as illustrated in Figure 2 : (1) a belief and uncertainty modeling

Read the complete text