Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation
Authors: Xinyi Ling, Ye Liu, Reza Averly, Xia Ning
Organizations: Department of Computer Science and Engineering, The Ohio State University · Department of Biomedical Informatics, The Ohio State University · Translational Data Analytics Institute, The Ohio State University
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 Conversation Uncertainty-aware Planning 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.
Figures & tables
Figure 1: Problem Formulation
Figure 2: The overview of CUP framework.
Dataset
#Conv.
#Attr.
Avg. Words per Conv.
Candidate Pool Size
Beauty
772
8
481.2
3,392
Fashion
826
8
403.1
4,034
Home
372
9
199.3
1,180
Inspired
98
6
279.3
17,731
Table 1: Dataset statistics. #Conv. is the number of conversations. #Attr. is the number of attributes associated with candidates.
Model
Method
Beauty
Fashion
Home
Inspired
SR(%)
avgT
SR(%)
avgT
SR(%)
avgT
SR(%)
avgT
SBERT
11.14
4.82
15.86
4.79
18.82
4.73
11.22
4.85
Qwen3-4B
Direct Prompting
37.05
4.18
37.65
4.13
41.92
4.05
32.65
4.22
CoT
38.47
4.11
39.23
4.05
48.39
3.88
45.92
4.01
LLM-planning
44.30
4.72
41.53
4.70
51.34
4.65
48.98
4.73
UoT
51.68
4.67
49.52
4.80
59.68
4.69
59.18
4.70
Table 2: Overall Performance
Figure 3: Ablation results on four datasets.
Variant
Beauty
Fashion
Home
Inspired
CUP -Random
53.4
50.6
57.3
52.0
CUP -1Step
65.2
65.6
70.4
76.5
CUP -NoEIG
72.7
74.5
75.0
81.6
CUP
82.1
83.4
84.1
89.8
Table 3: Multi-step search vs. uncertainty signal.
Figure 4: Dominance ratio of the target candidate.
Figure 5: Uncertainty Decrease Ratio.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 6: Case study of CUP framework.
Method
Beauty
Fashion
Home
Inspired
Prompt-MCTS ( Yu et al., 2023 )
49.5
48.2
58.6
55.1
INTENT-SIM ( Zhang and Choi, 2025 )
47.5
48.6
50.8
48.0
CUP (ours)
82.1
83.4
84.1
89.8
Appendix
Table 4: Head-to-head comparison against two additional training-free baselines on Qwen3-4B ( T=5 ). Success rate (%).
Initialization of b0
Beauty
Fashion
Home
Inspired
Cosine similarity (default, Eq. 1 )
82.1
83.4
84.1
89.8
Uniform
79.3
80.1
79.2
89.8
Appendix
Table 5: Belief-initialization ablation on Qwen3-4B. Success rate (%).
Recent advances in large language models (LLMs) have enabled their use as conversational recommender systems (CRS), demonstrating strong recommendation accuracy and natural dialogue. However, guiding multi-turn interactions to elicit user preferences effectively remains challenging. Existing approaches either use separate reinforcement learning agents with templated interactions or optimize for interactivity judged by another LLM, without measuring how much useful information is actually gained. We propose a new approach that quantifies the effectiveness of each interaction by the reduction in the assistant's uncertainty, measured via entropy over recommendations. We apply this entropy reduction as a reward---without relying on ground-truth recommendations, which are often unavailable in real-world scenarios---to fine-tune the LLM, enabling strategic interaction generation. Empirical results with supervised fine-tuning (SFT) and direct preference optimization (DPO) on the INSPIRED and ReDial datasets show that our method improves both recommendation quality and conversational efficiency.
Large Language Models (LLMs) excel at static reasoning tasks, yet their performance often degrades in interactive scenarios where information must be actively acquired through questioning. A key challenge lies in selecting questions that reduce uncertainty while incorporating responses that may be ambiguous or only partially informative. To address this, we propose Conversation-Aware Bayesian Experimental Design (CA-BED), an inference-time probabilistic dialog planning framework that integrates Bayesian Experimental Design with LLM-based likelihood estimation to optimize question selection over multiple conversational turns. CA-BED maintains a belief distribution over hypotheses, anticipates possible answers, and propagates expected information gain through a simulated conversation tree. Across two structured entity-deduction benchmarks, CA-BED yields an average 21.8% improvement in success rates over direct prompting, with comparable gains relative to alternative information-seeking methods. It achieves these gains with an average increase of only 1.8 conversational turns compared to direct prompting.
Turn-taking is a fundamental mechanism that governs when interlocutors speak and listen. Although Spoken Dialogue Systems (SDS) exploit a range of linguistic, acoustic, and non-verbal cues, they produce ill-timed responses in unscripted interaction. A central challenge is anticipating Transition Relevance Places (TRPs), or opportunities, not obligations, for a listener to take the floor. Human listeners do not wait for turn endings; as an utterance unfolds, they use expectations about its developing meaning to anticipate TRPs and decide whether to take the floor. We examine whether these evolving expectations can be modeled through semantic uncertainty -- an LLM-derived measure of how strongly a turn so far constrains what may plausibly come next. To do so, we sample possible continuations of an ongoing turn and use changes in semantic dispersion to identify TRPs within turns. We evaluate this account on a dataset with TRP labels derived from real-time listener responses, rather than retrospective annotation. Our approach substantially outperforms prompt-based and fine-tuned text-only baselines, providing empirical support for the view that evolving semantic constraints inform perceived turn-taking opportunities in unscripted interaction.
Muhammad Umair, Jan P. de Ruiter
Department of Computer Science Tufts University Medford, Massachusetts, USA