Paper deep dive
Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation
Xinyi Ling, Ye Liu, Reza Averly, Xia Ning
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 95%
Last extracted: 4/10/2026, 2:30:24 AM
Summary
The paper introduces the Conversation Uncertainty-aware Planning (CUP) framework, which treats goal-oriented conversation as a sequential decision-making problem. By integrating Large Language Models (LLMs) with Monte Carlo Tree Search (MCTS) and uncertainty estimation (via entropy and Expected Information Gain), CUP enables agents to balance information acquisition and target commitment over multiple turns, significantly improving success rates and interaction efficiency compared to existing methods.
Entities (5)
Relation Signals (3)
CUP → improves → Success Rate
confidence 95% · Experimental results show that our method consistently improves the success rate
CUP → integrates → LLM
confidence 95% · CUP framework (CUP) that integrates language models with structured planning
CUP → uses → MCTS
confidence 95% · We instantiate the planner using Monte Carlo Tree Search (MCTS)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 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.
Tags
Links
- Source: https://arxiv.org/abs/2604.03924v1
- Canonical: https://arxiv.org/abs/2604.03924v1
Trouble viewing inline? Open PDF directly →
Full Text
49,561 characters extracted from source content.
Expand or collapse full text
Preprint. Under review. Uncertainty as a Planning Signal: Multi-Turn Decision Making for Goal-Oriented Conversation Xinyi Ling 1∗ , Ye Liu 2∗ , Reza Averly 1 , & Xia Ning 1,2,3 1 Department of Computer Science and Engineering 2 Department of Biomedical Informatics 3 Translational Data Analytics Institute The Ohio State University ling.303, liu.12989, averly.1, ning.104@osu.edu Abstract Goal-oriented conversational systems require making sequential decisions under uncertainty about the user’s intent, where the algorithm must bal- ance 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 limita- tion, 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. Experi- ments on multiple conversational benchmarks show thatCUPconsistently 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 (Bordes et al., 2017; Peng et al., 2024; Liu et al., 2025). 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 (Zhang et al., 2025; Kobalczyk et al., 2025). 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 ac- tion spaces, enabling multi-step planning and long-horizon optimization (Bordes et al., 2017; Wu et al., 2019a; 2023). However, they typically rely on predefined schemas (Casanueva et al., 2020) and limited domain knowledge (Bisk et al., 2020), which restrict their applica- bility 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 (Bocklisch et al., 2017). ∗ Equal contribution 1 arXiv:2604.03924v1 [cs.CL] 5 Apr 2026 Preprint. Under review. In contrast, with the rise of large language models (LLMs), LLM-based approaches have demonstrated strong performance across a wide range of conversational tasks (Liu et al., 2024; Yi et al., 2025). They leverage rich linguistic knowledge to enable flexible and general- izable interactions, but lack explicit mechanisms for optimizing over multi-turn interaction trajectories (Wei et al., 2022; Wang et al., 2023; Yao et al., 2023). 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 Conversation Uncertainty-aware Planning (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 theCUPframework, 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 (He et al., 2016; Covert et al., 2023; Javdani et al., 2014). This problem has been studied across Bayesian experimental design (Choudhury et al., 2026), sequential decision-making (Kaelbling et al., 1998), and active learning (Settles, 2009). Goal-oriented conversation can be viewed as a sequential decision-making problem (Chopra & Shah, 2025) in which each interaction turn can serve as an information-gathering step. Recent works in conversational information acquisition use Monte Carlo approximation (Kobalczyk et al., 2025) or probability-based uncertainty criteria (Hu et al., 2024) 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 (Peng et al., 2017), later extended to reinforcement learning (Deng et al., 2021; Wang et al., 2025) and Markov decision process (MDP) frameworks for optimizing long-term task success (Sun & Zhang, 2018; Wen et al., 2017; Lei et al., 2020; Williams & Young, 2007). Attribute-based methods further improve information acquisition by progressively refining a candidate search space (Zhang et al., 2 Preprint. Under review. 2018; Wu et al., 2019b; Xu et al., 2021), while recent work explores proactive conversation strategy and modular policy planners (Deng et al., 2023; Tang et al., 2019; Deng et al., 2024). 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 (Jannach et al., 2021; Afchar et al., 2022). Our work addresses this gap through structured multi-step conversational planning. 3 Method 3.1 Problem Formulation Conversation Candidate Set Belief State Uncertainty Estimation Action Selection User Response Information Update 1 2 34 Figure 1: Problem Formulation We model goal-oriented conver- sational planning as a partially observable sequential decision- making problem (Williams & Young, 2007; Mrk ˇ si ́ c et al., 2017). Specifically, the agent maintains a belief stateb t over a candidate setC t conditioned on the current conversation historyh t , as illus- trated in Figure 1. At each turnt, the agent first estimates the uncer- tainty over the current belief state b t , and then selects an actiona t to interact with the user. With the user responser t , the agent further updates the conversation historyh t+1 , candidate setC t+1 and the belief stateb 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 Conversation Uncertainty-aware Planning framework (CUP) consists of three components, as illustrated in Figure 2: (1) a belief and uncertainty modeling module that maintains a belief state over candidates and estimates uncertainty; (2) an uncertainty-guided planning module that evaluates proposed actions based on their long-term impact; and (3) a language-grounded action execution module that realizes the selected action in natural language and updates the belief state based on the user response. 3.3 Belief & Uncertainty Modeling At each turn,CUPmaintains a belief stateb t over the candidate setC t , representing a probability distribution conditioned on the conversation historyh t . At initialization, the belief is computed based on the semantic similarity between each candidatec i ∈ C 0 and the initial conversation historyh 0 , which contain the user’s initial query or an ongoing conversation between the user and the agent, and is never empty. b 0 (c i ) = exp(sim(c i , h 0 )) ∑ c j ∈C 0 exp(sim(c j , h 0 )) .(1) Here,sim(·)denotes cosine similarity between the embeddings of the candidate and the conversation history, assigning higher probability to candidates that are more semanti- cally aligned with the user’s intent. After that, we quantify the uncertainty using the entropy (Seidenfeld, 1986) of the belief state b t : H(b t ) =− ∑ c i ∈C t b t (c i ) log b t (c i ).(2) Entropy measures how dispersed the belief state is over the candidate set. High entropy indicates that the belief is spread across many candidates and the agent is uncertain about 3 Preprint. Under review. (1) Belief & Uncertainty Modeling(2) Uncertainty-Guided Planning Conversation Candidate Set Belief State Expected Information Gain (EIG) Selected Action Actions with various possible responses (3) Language-Grounded Action Execution LLM Simulated Response Selected Action Language Utterance "...family- friendly like PG- rated movies, or more mature like PG-13 or R-rated?" "How about Zootopia (2016)? A fun animated movie with lovable characters which is great for family." Ask Commit Information Update Figure 2: The overview of CUP framework. the user’s intent, while low entropy indicates that the belief is concentrated on a few candidates. This makes entropy a principled and widely-used gauge (Namdari & Li, 2019; Hu et al., 2024) of uncertainty for guiding conversational planning. Commitment Trigger. The belief state triggers a commitment when H(b t ) log|C t | < εand max c i ∈C t b t (c i ) ≥ θ, indicating that the belief is sufficiently concentrated and confident. Commitment is also triggered when|C t |≤2 or the maximum turnTis reached. Otherwise, CUP will proceed to the next expected information gain calculation. Expected Information Gain. Subsequently, we construct an action setA t using an LLM (denoted asLLM) conditioned on the current conversation history h t and candidate set C t : A t =LLM(h t , C t ),(3) Each actiona t ∈A t is either (1) ask, which queries an attribute of the candidates with several provided options; (2) commit, which selects a candidatec ∗ ∈ C t to present to the user. We compute the expected information gain (EIG) (Lindley, 1956; Ryan, 2003) on each action a t ∈A t to measure the expected reduction in uncertainty after taking action a t : EIG(a t , b t ) =H(b t )− ∑ o∈O a t p(o | a t )H(b t | o),(4) whereO a t denotes the set of possible observation to actiona t , andH(b t | o)is the posterior entropy after observingo ∈O a t . The possible observationO a t are directly derived from the actiona t : for an ask action, they correspond to the provided options; for a commit action, they correspond to user acceptance or rejection. EIG scores are then converted into a probability distribution over actions, serving as a prior for planning: P(a t , b t ) = exp(EIG(a t , b t )) ∑ a ′ t ∈A t exp(EIG(a ′ t , b t )) .(5) A higherP(a t ,b t )indicates that the actiona t is expected to reduce uncertainty more given the current belief state , and is therefore prioritized during planning. 3.4 Uncertainty-Guided Planning Given the current belief stateb t ,CUPselects actions via lookahead planning over fu- ture interaction trajectories. We instantiate the planner using Monte Carlo Tree Search (MCTS) (Browne et al., 2012; Chopra & Shah, 2025), where uncertainty is used as a signal to guide multi-turn decision making. MCTS Planning.Starting fromb t , MCTS builds a search tree where each node represents a belief state and each edge represents an action outgoing from that belief state node, 4 Preprint. Under review. simulating future trajectories. Each actiona t ∈A t is evaluated using the following adapted scoring function (Silver et al., 2017): Score(a t , b t ) =V(a t , b t ) + c· P(a t , b t ) p N(b t ) 1 + N(b t , a t ) ,(6) The first termV(b t ,a t )is the estimated action value, and exploits currently estimated action values. While the second term encourages exploration of less-visited actions weighted by their EIG-based prior.P(a t ,b t )is the EIG-based prior from Eq. 5,N(b t )denotes the visit counts of the node corresponding to belief stateb t , andN(b t ,a t )denotes the edge counts corresponding to actiona t taken fromb t . The action value is defined as the expected cumulative reward over simulated trajectories: V(b t , a t ) =E " T ∑ t ′ =t γ t ′ −t R(a t ′ , b t ′ ) # ,(7) whereγ∈ (0, 1]is a discount factor that down-weights rewards from future turns and the reward R balances task success, interaction efficiency, and uncertainty reduction: R(a t , b t ) = 1[success]− λ + α· EIG(a t , b t )− β· 1[failure].(8) where1[success]and1[failure]indicate whether the commitment is accepted or rejected by the user, respectively, which are calculated only whena t is a commit action.λ>0 is a turn- level penalty factor that accumulates over turns and penalizes longer conversations.α>0 weights the uncertainty reduction signal (EIG), andβ>0 penalizes incorrect commitments. Action Selection.After planning, the best actiona ∗ t = arg max a t V(b t ,a t )is selected for ex- ecution and then passed to the execution module (Section 3.5) to produce the corresponding utterance. 3.5 Language-Grounded Action Execution The selected action a ∗ t is realized as a natural language utterance utt t by theLLM: utt t =LLM(a ∗ t , h t , C t , b t ),(9) whereh t denotes the conversation history,C t is the current candidate set, andb t is the corresponding belief state. More specifically, ifa ∗ t is an ask action, theLLMwill be employed to generate a question about a specific attribute, accompanied by a set of options, where utt t ←Question,O ptions. The options partition the candidate set, so that each possible user response eliminates a subset of inconsistent candidates and reduces uncertainty. If a ∗ t is a commit action,CUPselects the most probable candidatec ∗ = arg max c i ∈C t b t (c i ). Whenmax c i b t (c i ) ≥ θ , theLLMproduces a direct commitment. When the commit action is selected by the planning module, or|C t | ≤2, or the maximum turnTis reached,LLM is further used to perform semantic reasoning and generate a refined commitment by leveraging the conversation historyh t and current candidate setC t . Here, theLLMwill identify the candidate that best matches the user ’s expressed preferences asc ∗ , and generate utt t committing c ∗ to the user, denoted as utt t ←c ∗ . State Update. The utteranceutt t is then presented to the user simulator, which returns a responser t . The conversation history is updated ash t+1 = h t ∪utt t ,r t , and the candidate setC t+1 ⊆C t is pruned by removing candidates that contradictr t . The belief state is updated as: b t+1 (c i )∝ b t (c i )· sim(c i , h t+1 ) δ ,c i ∈C t+1 , 0,otherwise, (10) whereδ≥0 controls the influence of the updated dialogue history. Here,sim(·)measures the semantic similarity betweenc i andh t+1 . The update follows a Bayesian multiplicative logic, retaining the prior information inb t while reweighting each candidate with new information. Candidates contradicting the user response are filtered out. After applying the update,b t+1 is renormalized. The updated information seeds the next turn, and the interaction proceeds until a commitment is accepted by the user or the maximum turn budget is reached. 5 Preprint. Under review. 4 Experiments 4.1 Experimental Setup Table 1: Dataset statistics. #Conv. is the num- ber of conversations. #Attr. is the number of attributes associated with candidates. Dataset #Conv. #Attr. Avg. Words per Conv. Candidate Pool Size Beauty7728481.23,392 Fashion8268403.14,034 Home3729199.31,180 Inspired986279.317,731 Datasets.We evaluate our method on four widely-used conversational datasets: In- spired (Hayati et al., 2020), Beauty, Fashion, and Home (?). Inspired focuses on movie recommendation and the others cover var- ious e-commerce scenarios. Each dataset consists of multi-turn dialogues paired with a ground-truth target.Following prior work (Hu et al., 2024; Chopra & Shah, 2025), we construct, for each conversation, a candidate set with a ground-truth target and 299 distractor candidates retrieved by SBERT (Reimers & Gurevych, 2019) from the full dataset candidate pool. More statistics are illustrated in Table 1. Evaluation Metrics. We adopt two primary evaluation metrics (Hu et al., 2024; Chopra & Shah, 2025) that reflect the core objectives of conversational decision making, including (1) Success Rate (SR) measures whether the system successfully commits the ground-truth target within a limited number of turns, capturing the overall accuracy. (2) Average Turns (avgT) measures the number of interaction turns in the conversation, reflecting the efficiency of the method. Baselines. We compare our method against a comprehensive set of baselines spanning retrieval-based, LLM-based, and planning-based approaches. Specifically, we include: •Retrieval-based methods: SBERT (Reimers & Gurevych, 2019), performs semantic retrieval without conversational planning. •Heuristic LLM-based methods: Direct Prompting, directly generates responses by an LLM without explicit reasoning or multi-turn decision making. Chain-of-Thought (CoT) (Wei et al., 2022), improves local reasoning via chain-of-thought prompting but does not model long-horizon interaction. LLM planning, performs heuristic multi-step reasoning without explicit uncertainty modeling. • Uncertainty-aware planning methods: UoT (Hu et al., 2024), uses uncertainty over de- cision tree to guide question selection. ATD (Kobalczyk et al., 2025), select clarification questions to reduce task ambiguity by sample-based approximation. BED-LLM (Choud- hury et al., 2026), applies logit-based expected information gain for informative action selection. MISQ-HF (Chopra & Shah, 2025), combines uncertainty with cluster-based multi-step conversational planning. Implementation Details. We use Qwen3-4B (Yang et al., 2025), Mistral-7B-v0.3 (Jiang et al., 2024), and Llama-3.1-8B (Grattafiori et al., 2024) as backbone models, and Llama-3.2- 3B (Grattafiori et al., 2024) as the user simulator (Sekuli ́ c et al., 2024; Abbasiantaeb et al., 2024). For planning, we adopt a Monte Carlo Tree Search with search budgetK =50 and exploration constantc =1.4. The discount factor is set toγ =0.99, the information gain bonusα =0.2, the turn penaltyλ =0.1, and the failure penaltyβ =0.5. The entropy-based commitment thresholds of normalized entropy ratio and maximum belief probability are set toε =0.5 andθ =0.8, respectively. Belief updates use Bayesian multiplicative updates withδ =1.0 Embeddings are computed using SBERT (Reimers & Gurevych, 2019). All experiments are conducted with a maximum turn limit of T = 5. 4.2 Main Results Table 2 presents the overall performance, whereCUPconsistently achieves the best results across datasets and model backbones. We highlight three key observations from the results. 6 Preprint. Under review. Table 2: Overall Performance ModelMethod BeautyFashionHomeInspired SR(%)avgTSR(%)avgTSR(%)avgTSR(%)avgT SBERT11.144.8215.864.7918.824.7311.224.85 Qwen3-4B Direct Prompting37.054.1837.654.1341.924.0532.654.22 CoT38.474.1139.234.0548.393.8845.924.01 LLM-planning44.304.7241.534.7051.344.6548.984.73 UoT51.684.6749.524.8059.684.6959.184.70 ATD48.964.7048.434.6253.764.5858.164.68 BED-LLM55.574.4951.824.3865.054.3165.314.41 MISQ-HF63.214.3356.414.2069.894.1067.354.30 CUP (ours)82.12 4.1083.41 4.1684.14 3.6789.80 3.93 Mistral-7B-v0.3 Direct Prompting32.254.2033.904.1839.524.1127.554.23 CoT35.424.1738.144.0145.983.9336.734.09 LLM-planning43.014.8141.654.6952.694.6248.984.70 UoT53.114.7350.854.7759.134.7161.224.66 ATD49.224.6948.674.6254.304.5057.144.63 BED-LLM61.534.6250.244.4563.444.3466.334.58 MISQ-HF64.904.3059.324.1671.774.0674.494.28 CUP (ours)82.90 4.0683.77 4.1183.87 3.6291.84 4.01 Llama-3.1-8B Direct Prompting33.944.2235.234.2138.174.1528.574.16 CoT37.824.1038.624.1347.313.9440.823.99 LLM-planning44.434.7540.684.7349.194.7050.004.77 UoT57.904.6952.064.7360.484.6162.234.71 ATD49.094.6652.304.6056.994.5658.164.64 BED-LLM68.784.3859.324.4069.354.3571.434.39 MISQ-HF69.954.3163.444.1875.004.1277.554.32 CUP (ours)81.99 4.0682.20 4.0189.78 3.7592.86 3.86 Planning with uncertainty leads to more effective multi-turn decision making. Methods that treat each turn independently (e.g., Direct Prompting, CoT) perform poorly, as they lack mechanisms to anticipate future interactions, resulting in myopic decisions. While LLM-based planning introduces heuristic multi-step simulation, it lacks a principled signal and often produces inefficient interaction (e.g., on Beauty with Llama-3.1-8B, LLM-planning 4.75 vs. CoT 4.10). Uncertainty-aware methods (e.g., ATD, UoT, BED-LLM, MISQ-HF) improve performance by prioritizing actions that reduce ambiguity, but typically rely on one-step or heuristic signals. In contrast,CUPintegrates uncertainty into planning as a global decision signal, enabling evaluation of actions based on their long-term impact. This leads to consistently higher success rates, especially on challenging datasets such as Inspired (Qwen3-4B: 58.16% (ATD)→ 67.35% (MISQ-HF)→ 89.80% (CUP)). CUP’s gains vary across domains. Across all settings,CUPconsistently outperforms no- planning baselines (e.g., Direct Prompting), but the magnitude of improvement differs by domain. For example, gains over Direct Prompting are largest on Inspired (Llama-3.1-8B, +64.29%), while Fashion and Home exhibit smaller yet stable improvements (around 50%). This difference reflects the varying difficulty of multi-turn information acquisition: Inspired involves high ambiguity and semantic overlap among candidates, making it difficult to identify the target from context alone, consistent with its weaker performance of SBERT. These results indicate thatCUPis particularly beneficial in scenarios that require sustained information acquisition over multiple turns. Planning reduces sensitivity to backbone models. The performance gap between Qwen3- 4B and Llama-3.1-8B is relatively small underCUP(e.g., Beauty 82.12% vs. 81.99%), but more pronounced for LLM-based methods (Direct Prompting: 37.05% vs. 33.94%). This suggests that our designed planning mechanism reduces reliance on model capacity by guiding action selection. The consistent performance across backbones further indicates that CUP improves the decision process itself rather than depending on stronger LLMs. 7 Preprint. Under review. LLM-OnlyCUP-Random-HeuristicCUP-RandomCUP-HeuristicCUP Method 0 25 50 75 Success Rate (%) (a) Beauty Method 0 25 50 75 Success Rate (%) (b) Fashion Method 0 25 50 75 Success Rate (%) (c) Home Method 0 25 50 75 Success Rate (%) (d) Inspired Figure 3: Ablation results on four datasets. 4.3 Ablation Study To understand the contribution of each component, we conduct a factorized ablation study along two dimensions: (1) action selection (planning) and (2) commitment realization (execution). All variants share the same interaction budget and backbone (Qwen3-4B). Specifically, we consider the following configurations: • CUP-Heuristic: Retain the planning module but replace all LLM-based commitment with a heuristic top-1 candidate commitment. • CUP-Random: Removes structured planning by selecting actions uniformly at random, while retaining LLM-based commitment. • CUP-Random-Heuristic: Removes both planning and LLM-based commitment, serv- ing as a lower bound. •LLM-only: Directly generates commitment decisions using the LLM without explicit planning or structured action selection. Figure 3 presents the success rate across four datasets. The fullCUPmodel consistently achieves the best performance, indicating that uncertainty-aware planning and language- grounded commitment play complementary roles. Planning is the dominant factor, as variants with structured planning (CUP,CUP-Heuristic) consistently outperform those without it (CUP-Random,CUP-Random-Heuristic), while LLM-based commitment pro- vides additional but smaller gains. In contrast, the variant LLM-only performs poorly, highlighting that local decision strategies are insufficient for effective multi-turn interaction. 4.4 Dominance of Target Candidate 12345 Turn 70 80 Dominance Ratio (%) (a) Beauty 12345 Turn 70 80 Dominance Ratio (%) (b) Fashion 12345 Turn 75 80 85 Dominance Ratio (%) (c) Home 12345 Turn 60 70 80 90 Dominance Ratio (%) (d) Inspired Figure 4: Dominance ratio of the target candidate. To understand howCUPprogressively narrows the candidate search space, we analyze the dominance of the target candidate across interaction turns. Specifically, we define the dominance ratio as: DominanceRatio t = 1− Rank t (c ∗ )− 1 |C t | ,(11) whereRank t (·)denotes the position of a candidate in the ranking induced by the belief state at turnt, with 1 being the highest rank.|C t |represents the size of the current candidate set. This metric measures how prominent the target candidatec ∗ is within the remaining candidate set C t , where a value of 1.0 indicates that the target is ranked first. 8 Preprint. Under review. Action Search Planning Candidate Search Space Update TargetObservationAction Conversation History What kind of genre are you in the mood for? Drama, Comedy, Thriller, or Others I am looking for recommendation about movie trailers. ... I like action movies. ... I like black. Maybe English. What language of movie do you like? English, Asian language, or Others Cool. I will try! Do you like John Wick (2014)? It satifies your preference. Uncertainty over user intent decr ease Infomation Update 7 Action Execution AskCommit/ 5 Simulated Response 6 User Accepts or Max Turn Reached Conversation Candidates Belief 1 Action Search Planning 4 Actions Proposal 3 Uncertainty Estimation 2 8 Conversation Candidate Set Belief State Uncertainty Estimation Action Selection User Response Information Update (1) Belief & Uncertainty Modeling(2) Uncertainty-Guided Planning Conversation Candidate Set Belief State Expected Information Gain (EIG) Selected Action Actions with various possible responses CommitAsk Confidence Verification LLM-Refined Commitment Question + Options LLM-Ask (3) Language-Grounded Action Execution LLM Simulated Response Selected Action Language Utterance "...family- friendly like PG- rated movies, or more mature like PG-13 or R-rated?" "How about Zootopia (2016)? A fun animated movie with lovable characters which is great for family." Ask Commit Information Update 1 2 34 Conversation History So are you drawn to that creative and boundary- pushing era, or something light-hearted? # Content rating: G, PG, R, or others # I want movies that are mainly comedy, with some interest in action elements, especially superhero-style movies like Marvel... I'm looking for an R-rated movie which takes risks and pushes limits. I'm really feeling more recent vibe with new-generation movies that mix intense fights with a lot of comedy. When do you want them to have come out? from the 2010s, or before or early 2000s? # Year range: before 2000, 2000-2009, 2010- 2015, or others # Thanks for the suggestion, but I'm not quite there yet. How about Nostalgia (2018)? An mature, modern indie drama with a reflective, emotionally grounded recent tone. Target: Deadpool (2018) 73/300 11/53 6/11 3/6 Conversation History Are you looking for something tailored to men, or unisex that suitable for adults, or perhaps something designed specifically for women? # Gender: Men, Women, Unisex, or others # I'm looking for a stadium-compliant bag that strictly meets size requirements to find one within the allowed dimension..... I'm really drawn to the unisex style that's versatile and easy to use. I'm looking for something affordable in the $10–$25 range that offers good quality without being too pricey. What’s your budget? Unisex options can vary quite a bit in price. Are you flexible, or do you have a range in mind? # Price range: $10-$25, $25-50$, no preference, or others # Yessss! I was searching for something like this. How about Travelon Anti-theft Metro Stadium Mini Crossbody Cross Body Bag? For adults in general with reasonable pricec. Target: Travelon Anti-theft Metro Stadium Mini Crossbody Cross Body Bag 13/300 2/56 1/15 1/1 ✅ ❌ (a) A Success Case from Fashion. Conversation History So are you drawn to that creative and boundary- pushing era, or something light-hearted? # Content rating: G, PG, R, or others # I want movies that are mainly comedy, with some interest in action elements, especially superhero-style movies like Marvel... I'm looking for an R-rated movie which takes risks and pushes limits. I'm really feeling more recent vibe with new-generation movies that mix intense fights with a lot of comedy. When do you want them to have come out? from the 2010s, or before or early 2000s? # Year range: before 2000, 2000-2009, 2010- 2015, or others # Thanks for the suggestion, but I'm not quite there yet. How about Nostalgia (2018)? An mature, modern indie drama with a reflective, emotionally grounded recent tone. Target: Deadpool (2018) 73/300 11/53 6/11 3/6 ❌ (b) A Failure Case from Inspired. Figure 5: Case study of CUP framework. Figure 4 shows that the dominance ratio increases steadily during early turns (turn 1-3) across all datasets, indicating that the target rapidly rises in rank as informative interactions are performed. This trend reflects effective candidate discrimination, demonstrating the advantage of ourCUPframework. A slight decline in later turns (turn 4-5) is mainly due to early commitment on confident cases, leaving more ambiguous instances in subsequent turns. We also analyzed the uncertainty reduction over interaction turns, which can be found in Appendix B. 4.5 Case Study To better understand the mechanism of ourCUPframework, we illustrate two representative cases in Figure 5. In the success case (Figure 5a), the agent effectively reduces uncertainty through clarification questions, rapidly narrowing the candidate search space and enabling a correct commitment within three turns. This demonstrates that uncertainty-aware action selection can guide efficient information acquisition and support accurate decision making. In the failure case (Figure 5b), although the target candidate is progressively promoted in the ranking (e.g., 73/300→11/53→6/11→3/6), the remaining ambiguity is not fully resolved. As a result, the agent fails to confidently identify the correct target and makes an incorrect commitment. This suggests that sometimes improving overall ranking alone is insufficient for reliable decision making, and points to a promising direction for future work in placing greater emphasis on distinguishing among top-ranked candidates, where residual uncertainty is most critical. We will explore more effective strategies to better resolve ambiguity among top candidates in the following work. 5 Conclusion In this work, we study goal-oriented conversational decision making under uncertainty, emphasizing the need to coordinate information acquisition and target commitment over multiple turns. Existing approaches either rely on rigid structured formulations or flex- ible but myopic language models, limiting their ability to reason over long interaction trajectories. To address this, we formulate conversation as an uncertainty-aware sequential decision problem and proposeCUP, which integrates language models with structured planning by using uncertainty as a guiding signal. Experiments show thatCUPconsistently 9 Preprint. Under review. improves both effectiveness and efficiency across datasets and model backbones. Further analysis reveals that uncertainty-aware planning enables faster belief concentration and more efficient information acquisition, highlighting its value for multi-turn decision making in conversational systems. References Zahra Abbasiantaeb, Yifei Yuan, Evangelos Kanoulas, and Mohammad Aliannejadi. Let the llms talk: Simulating human-to-human conversational qa via zero-shot llm-to-llm interactions. In Proceedings of the 17th ACM International Conference on Web Search and Data Mining, p. 8–17, 2024. Darius Afchar, Alessandro B. Melchiorre, Markus Schedl, Romain Hennequin, Elena V. Epure, and Manuel Moussallam. Explainability in music recommender systems. AI Magazine, 43(2):190–208, June 2022. ISSN 0738-4602. doi: 10.1002/aaai.12056. URL https://doi.org/10.1002/aaai.12056. Yonatan Bisk, Ari Holtzman, Jesse Thomason, Jacob Andreas, Yoshua Bengio, Joyce Chai, Mirella Lapata, Angeliki Lazaridou, Jonathan May, Aleksandr Nisnevich, et al. Experience grounds language. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP), p. 8718–8735, 2020. Tom Bocklisch, Joey Faulkner, Nick Pawlowski, and Alan Nichol. Rasa: Open source language understanding and dialogue management. arXiv preprint arXiv:1712.05181, 2017. Antoine Bordes, Y-Lan Boureau, and Jason Weston. Learning end-to-end goal-oriented dia- log. In International Conference on Learning Representations, 2017. URLhttps://openreview. net/forum?id=S1Bb3D5g. Cameron Browne, Edward Powley, Daniel Whitehouse, et al. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 4(1):1–43, 2012. I ̃ nigo Casanueva, Tadas Tem ˇ cinas, Daniela Gerz, Matthew Henderson, and Ivan Vuli ́ c. Efficient intent detection with dual sentence encoders. In Proceedings of the 2nd workshop on natural language processing for conversational AI, p. 38–45, 2020. Harshita Chopra and Chirag Shah. Feedback-aware MCTS for goal-oriented information seeking. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=ustF8MMZDJ. Deepro Choudhury, Sinead Williamson, Adam Golinski, Ning Miao, Freddie Bickford Smith, Michael Kirchhof, Yizhe Zhang, and Tom Rainforth. BED-LLM: Intelligent information gathering with LLMs and bayesian experimental design. In The Fourteenth International Conference on Learning Representations, 2026. URLhttps://openreview.net/forum?id= qyylZMLYT8. Ian Connick Covert, Wei Qiu, Mingyu Lu, Na Yoon Kim, Nathan J White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. In International Conference on Machine Learning, p. 6424–6447. PMLR, 2023. Yang Deng, Yaliang Li, Fei Sun, Bolin Ding, and Wai Lam. Unified conversational rec- ommendation policy learning via graph-based reinforcement learning. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, p. 1431–1441, 2021. Yang Deng, Lizi Liao, Liang Chen, Hongru Wang, Wenqiang Lei, and Tat-Seng Chua. Prompting and evaluating large language models for proactive dialogues: Clarification, target-guided, and non-collaboration. In Findings of the Association for Computational Linguistics: EMNLP 2023, p. 10602–10621, 2023. 10 Preprint. Under review. Yang Deng, Wenxuan Zhang, Wai Lam, See-Kiong Ng, and Tat-Seng Chua. Plug-and- play policy planner for large language model powered dialogue agents. In The Twelfth International Conference on Learning Representations, 2024. URLhttps://openreview.net/ forum?id=MCNqgUFTHI. Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024. Shirley Anugrah Hayati, Dongyeop Kang, Qingxiaoyang Zhu, Weiyan Shi, and Zhou Yu. Inspired: Toward sociable recommendation dialog systems. In Proceedings of the 2020 conference on empirical methods in natural language processing (EMNLP), p. 8142–8152, 2020. He He, Paul Mineiro, and Nikos Karampatziakis. Active information acquisition, 2016. URL https://arxiv.org/abs/1602.02181. Zhiyuan Hu, Chumin Liu, Xidong Feng, Yilun Zhao, See-Kiong Ng, Anh Tuan Luu, Junxian He, Pang Wei Koh, and Bryan Hooi. Uncertainty of thoughts: Uncertainty-aware planning enhances information seeking in LLMs. In The Thirty-eighth Annual Conference on Neural In- formation Processing Systems, 2024. URL https://openreview.net/forum?id=CVpuVe1N22. Dietmar Jannach, Ahtsham Manzoor, Wanling Cai, and Li Chen. A survey on conversational recommender systems. ACM Computing Surveys, 54(5):1–36, 2021. Shervin Javdani, Yuxin Chen, Amin Karbasi, Andreas Krause, Drew Bagnell, and Siddhartha Srinivasa. Near optimal bayesian active learning for decision making. In Artificial Intelligence and Statistics, p. 430–438. PMLR, 2014. Albert Jiang, Alexandre Sablayrolles, Alexis Tacnet, Antoine Roux, Arthur Mensch, Audrey Herblin-Stoop, Baptiste Bout, Baudouin de Monicault, Blanche Savary, Bam4d, Caroline Feldman, Devendra Singh Chaplot, Diego de las Casas, Eleonore Arcelin, Emma Bou Hanna, Etienne Metzger, Gianna Lengyel, Guillaume Bour, Guillaume Lample, Harizo Rajaona, Jean-Malo Delignon, Jia Li, Justus Murke, Louis Martin, Louis Ternon, Lucile Saulnier, L ́ elio Renard Lavaud, Margaret Jennings, Marie Pellat, Marie Torelli, Marie-Anne Lachaux, Nicolas Schuhl, Patrick von Platen, Pierre Stock, Sandeep Subramanian, Sophia Yang, Szymon Antoniak, Teven Le Scao, Thibaut Lavril, Timoth ́ e Lacroix, Th ́ eophile Gervet, Thomas Wang, Valera Nemychnikova, William El Sayed, and William Marshall. Mistral-7B-Instruct-v0.3.https://huggingface.co/mistralai/Mistral-7B-Instruct-v0. 3, 2024. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99–134, 1998. Kasia Kobalczyk, Nicol ́ as Astorga, Tennison Liu, and Mihaela van der Schaar. Active task disambiguation with LLMs. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=JAMxRSXLFz. Wenqiang Lei, Xiangnan He, Yisong Miao, Qingyun Wu, Richang Hong, Min-Yen Kan, and Tat-Seng Chua. Estimation-action-reflection: Towards deep interaction between conversational and recommender systems. In Proceedings of the 13th international conference on web search and data mining, p. 304–312, 2020. Dennis V. Lindley. On a measure of the information provided by an experiment. Annals of Mathematical Statistics, 27(4):986–1005, 1956. Ollie Liu, Deqing Fu, Dani Yogatama, and Willie Neiswanger. DeLLMa: Decision making under uncertainty with large language models. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=Acvo2RGSCy. Zihan Liu, Wei Ping, Rajarshi Roy, Peng Xu, Chankyu Lee, Mohammad Shoeybi, and Bryan Catanzaro. Chatqa: Surpassing gpt-4 on conversational qa and rag. Advances in Neural Information Processing Systems, 37:15416–15459, 2024. 11 Preprint. Under review. Nikola Mrk ˇ si ́ c, Diarmuid O S ́ eaghdha, Tsung-Hsien Wen, Blaise Thomson, and Steve Young. Neural belief tracker: Data-driven dialogue state tracking. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 1777–1788, 2017. Alireza Namdari and Zhaojun Li. A review of entropy measures for uncertainty quantifica- tion of stochastic processes. Advances in Mechanical Engineering, 11(6):1687814019857350, 2019. Baolin Peng, Xiujun Li, Lihong Li, Jianfeng Gao, Asli Celikyilmaz, Sungjin Lee, and Kam- Fai Wong. Composite task-completion dialogue policy learning via hierarchical deep reinforcement learning. In Proceedings of the 2017 conference on empirical methods in natural language processing, p. 2231–2240, 2017. Bo Peng, Xinyi Ling, Ziru Chen, Huan Sun, and Xia Ning. ecellm: Generalizing large language models for e-commerce from large-scale, high-quality instruction data. In International Conference on Machine Learning, p. 40215–40257. PMLR, 2024. Nils Reimers and Iryna Gurevych. Sentence-bert: Sentence embeddings using siamese bert-networks. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP- IJCNLP), p. 3982–3992, 2019. Kenneth J Ryan. Estimating expected information gains for experimental designs with application to the random fatigue-limit model. Journal of Computational and Graphical Statistics, 12(3):585–603, 2003. Teddy Seidenfeld. Entropy and uncertainty. Philosophy of Science, 53(4):467–491, 1986. Ivan Sekuli ́ c, Silvia Terragni, Victor Guimar ̃ aes, Nghia Khau, Bruna Guedes, Modestas Filipavicius, Andre Ferreira Manso, and Roland Mathis. Reliable llm-based user simulator for task-oriented dialogue systems. In Proceedings of the 1st Workshop on Simulating Conversational Intelligence in Chat (SCI-CHAT 2024), p. 19–35, 2024. Burr Settles. Active learning literature survey. 2009. David Silver, Julian Schrittwieser, Karen Simonyan, et al. Mastering the game of go without human knowledge. Nature, 550(7676):354–359, 2017. Yueming Sun and Yi Zhang. Conversational recommender system. In The 41st international acm sigir conference on research & development in information retrieval, p. 235–244, 2018. Jianheng Tang, Tiancheng Zhao, Chenyan Xiong, Xiaodan Liang, Eric Xing, and Zhiting Hu. Target-guided open-domain conversation. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, p. 5624–5634, 2019. Jiacheng Wang, Linghe Kong, Fan Wang, Jieming Zhu, et al. Rec-r1: Bridging generative large language models and user-centric recommendation systems via reinforcement learning. Transactions on Machine Learning Research, 2025. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Repre- sentations, 2023. URL https://openreview.net/forum?id=1PL1NIMMrw. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022. Tsung-Hsien Wen, David Vandyke, Nikola Mrk ˇ si ́ c, Milica Gasic, Lina M Rojas Barahona, Pei-Hao Su, Stefan Ultes, and Steve Young. A network-based end-to-end trainable task- oriented dialogue system. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, p. 438–449, 2017. 12 Preprint. Under review. Jason D Williams and Steve Young. Partially observable markov decision processes for spoken dialog systems. Computer Speech & Language, 2007. Chien-Sheng Wu, Andrea Madotto, Ehsan Hosseini-Asl, Caiming Xiong, Richard Socher, and Pascale Fung. Transferable multi-domain state generator for task-oriented dialogue systems. In Proceedings of the 57th annual meeting of the association for computational linguistics, p. 808–819, 2019a. Wenquan Wu, Zhen Guo, Xiangyang Zhou, Hua Wu, Xiyuan Zhang, Rongzhong Lian, and Haifeng Wang. Proactive human-machine conversation with explicit conversation goal. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, p. 3794–3804, 2019b. Yaxiong Wu, Craig Macdonald, and Iadh Ounis. Goal-oriented multi-modal interactive recommendation with verbal and non-verbal relevance feedback. In Proceedings of the 17th ACM Conference on Recommender Systems, p. 362–373, 2023. Kerui Xu, Jingxuan Yang, Jun Xu, Sheng Gao, Jun Guo, and Ji-Rong Wen. Adapting user preference to online feedback in multi-round conversational recommendation. In Proceedings of the 14th ACM international conference on web search and data mining, p. 364–372, 2021. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, et al. Qwen3 technical report. arXiv preprint arXiv:2505.09388, 2025. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In The Eleventh International Conference on Learning Representations, 2023. URLhttps://openreview.net/ forum?id=WEvluYUL-X. Zihao Yi, Jiarui Ouyang, Zhe Xu, Yuwen Liu, Tianhao Liao, Haohao Luo, and Ying Shen. A survey on recent advances in llm-based multi-turn dialogue systems. ACM Computing Surveys, 58(6):1–38, 2025. Michael JQ Zhang, W. Bradley Knox, and Eunsol Choi. Modeling future conversation turns to teach LLMs to ask clarifying questions. In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=cwuSAR7EKd. Yongfeng Zhang, Xu Chen, Qingyao Ai, Liu Yang, and W Bruce Croft. Towards conversa- tional search and recommendation: System ask, user respond. In Proceedings of the 27th acm international conference on information and knowledge management, p. 177–186, 2018. A More Details about CUP The MCTS planning search proceeds through four phases: Selection. Starting from the root, traversing the tree to the leaf using the score function (Eq. 6) to balance exploration with exploitation. Expansion. At the leaf node, an unexplored action is sampled, weighted by EIG priors, to create a new child node. Rollout. Simulating future interaction trajectories from the expanded node using a lightweight deterministic simulator via direct attribute lookup (Chopra & Shah, 2025) during search simulation, enabling efficient estimation of long-term outcomes without expensive LLM calls. Backpropagation. The rollout return is propagated back, updating visit counts and action values along the search path. Moredetailedimplementationinformationlikepromptsareavailablein https://anonymous.4open.science/r/CUP-1BD8. 13 Preprint. Under review. B Uncertainty Reduction Analysis 12345 Turn 99 100 Decrease Ratio (%) (a) Beauty 12345 Turn 99 100 Decrease Ratio (%) (b) Fashion 12345 Turn 99 100 Decrease Ratio (%) (c) Home 12345 Turn 97 98 99 100 Decrease Ratio (%) (d) Inspired Figure 6: Uncertainty Decrease Ratio. To further understand how uncertainty-aware planning improves decision making, we analyze how quickly uncertainty over the candidate search space is reduced across inter- action turns. Uncertainty is quantified as the entropy of the belief state, and we compare against a size-matched uniform distribution as a reference. The normalized decrease ratio is computed through: DecreaseRatio t = H ours,t H uniform,t ,(12) whereH ours,t denotes the uncertainty of the belief state induced byCUPat turnt, and H uniform,t is the uncertainty of a uniform distribution over the same-sized candidate set, representing the uncertainty under random action selection. Figure 6 illustrates the decrease ratio across four datasets.CUPreduces uncertainty substan- tially faster than the uniform baseline, with a sharp increase in the decrease ratio during early turns. This indicates that the belief is concentrated on a smaller set of candidates more quickly, enabling earlier and more confident decisions. This improvement is driven by uncertainty-guided planning. By selecting actions based on their expected long-term impact on uncertainty,CUPeliminates irrelevant candidates more efficiently across turns, leading to higher success rates and fewer interaction steps. 14