💬 NLP

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

This paper introduces the Conversation Uncertainty-aware Planning (CUP) framework, which integrates language models with structured planning to treat uncertainty as a guiding signal for multi-turn decision making, thereby improving goal-oriented conversation success rates while reducing interaction turns.

Original authors: Xinyi Ling, Ye Liu, Reza Averly, Xia Ning

Published 2026-04-07

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Xinyi Ling, Ye Liu, Reza Averly, Xia Ning

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a personal shopper trying to find the perfect gift for a friend who hasn't given you a clear list. You know they like "something cool," but that could mean anything from a video game to a fancy watch.

If you just guess immediately, you might buy the wrong thing. If you keep asking endless questions ("Do you like blue? Do you like red? Do you like shiny things?"), you might annoy them or run out of time.

The Challenge:
The big problem in building AI chatbots that do this is balancing asking questions (to learn more) vs. making a guess (to finish the task).

Old School AI was like a robot with a rigid checklist. It could only ask about things on its list (e.g., "Do you like movies?"). If the user wanted something weird, the robot got stuck.
New AI (Large Language Models) is like a very chatty, creative friend. It can talk about anything, but it often gets distracted. It might ask a question, get an answer, and then forget the big picture, making a bad guess too early because it didn't plan ahead.

The Solution: CUP (The "Uncertainty Detective")
The authors of this paper created a new system called CUP (Conversation Uncertainty-aware Planning). Think of CUP as a super-smart detective who uses a special "Uncertainty Meter."

Here is how it works, using a simple analogy:

1. The Uncertainty Meter (The Compass)

Imagine you are in a foggy forest trying to find a specific tree.

High Uncertainty: You can't see anything. The fog is thick. You know you need to ask for directions.
Low Uncertainty: The fog is clearing. You can see the tree clearly. You are ready to walk straight to it.

CUP constantly checks this "Uncertainty Meter." It doesn't just look at the next step; it looks at the whole path. It asks: "If I ask this specific question, will it clear up the fog the most?"

2. The Two-Step Dance (The Brain & The Planner)

CUP has two parts working together, like a Creative Writer and a Strategic General:

The Creative Writer (The LLM): This part is great at language. It comes up with a list of possible things to say. "Should I ask about the color? Should I ask about the price? Should I just guess?"
The Strategic General (The Planner): This part doesn't care about fancy words. It cares about strategy. It simulates the future:
- Scenario A: If I ask about color, the user might say "Red." Then I'll know it's a red car.
- Scenario B: If I ask about price, the user might say "Cheap." Then I'll know it's a bike.
- The General calculates: "Which question clears up the most confusion for the longest time?" It picks the best move, not just the easiest one.

3. The Result: Efficient Shopping

Because CUP plans ahead, it doesn't waste time asking useless questions.

Old AI: Might ask 5 questions and still guess wrong.
CUP: Asks 2 or 3 perfect questions that cut through the confusion, then confidently says, "I think you want this specific item," and gets it right.

Why is this a big deal?

The paper tested CUP on many different tasks (like recommending movies or finding fashion items).

It wins more often: It successfully finds the right item much more frequently than other AI.
It's faster: It needs fewer turns of conversation to get the job done.
It's smarter: It doesn't rely on the AI being "smart" by accident; it forces the AI to think about the future consequences of every question it asks.

In a nutshell:
CUP teaches AI to stop being a "guess-and-check" robot and start being a strategic planner. It uses the feeling of "not knowing" (uncertainty) as a map to guide the conversation, ensuring that every question asked brings the AI one step closer to the perfect answer, without wasting time or annoying the user.

1. Problem Definition

The paper addresses the challenge of goal-oriented conversational systems, where an agent must identify a user's underlying intent through multi-turn interactions and commit to a specific target (e.g., recommending a movie or product).

Core Challenge: The system must make sequential decisions under uncertainty regarding the user's intent. It faces a trade-off between information acquisition (asking questions to reduce uncertainty) and target commitment (making a recommendation).
Limitations of Existing Approaches:
- Structured Methods: Enable multi-step planning but rely on rigid, predefined schemas and limited domain knowledge, failing to adapt to open-ended, free-form user inputs.
- LLM-Based Methods: Offer flexible interactions but lack explicit mechanisms for long-horizon planning. They often rely on local or heuristic strategies, leading to inefficient information gathering and premature or incorrect commitments.
Goal: To formulate goal-oriented conversation as an uncertainty-aware sequential decision problem that effectively coordinates information acquisition and target commitment over multiple turns.

2. Methodology: The CUP Framework

The authors propose Conversation Uncertainty-aware Planning (CUP), a framework that integrates Large Language Models (LLMs) with structured planning. The system operates as a partially observable sequential decision-making process with three core components:

A. Belief & Uncertainty Modeling

Belief State ( $b_t$ ): The agent maintains a probability distribution over a candidate set $C_t$ based on conversation history $h_t$ .
Initialization: Beliefs are initialized using semantic similarity (cosine similarity of embeddings) between candidates and the initial user query.
Uncertainty Quantification: Uncertainty is measured using the entropy ( $H$ ) of the belief state. High entropy indicates dispersed beliefs (high uncertainty), while low entropy indicates confidence.
Commitment Trigger: A commitment is triggered if the normalized entropy drops below a threshold ( $\epsilon$ ) and the maximum belief probability exceeds a threshold ( $\theta$ ), or if the candidate set is small or the turn limit is reached.

B. Uncertainty-Guided Planning (The Core Innovation)

Instead of greedy selection, CUP uses Monte Carlo Tree Search (MCTS) to evaluate actions based on their long-term impact.

Action Generation: An LLM proposes a set of feasible actions ( $A_t$ $A_{t}$ ), categorized as:
1. Ask: Querying an attribute with provided options.
2. Commit: Selecting a candidate to present.
Expected Information Gain (EIG): The system calculates the EIG for each potential action to estimate the expected reduction in entropy (uncertainty) after the user responds.
- $EIG(a_t, b_t) = H(b_t) - \sum p(o|a_t)H(b_t|o)$
MCTS Scoring: Actions are scored using an adapted Upper Confidence Bound (UCB) formula that balances:
1. Exploitation ( $V$ ): Estimated cumulative reward (success, efficiency, uncertainty reduction).
2. Exploration: Driven by the EIG-based prior ( $P(a_t, b_t)$ ), encouraging the search of actions likely to reduce uncertainty significantly.
Reward Function: Balances task success, interaction efficiency (penalizing long turns), and uncertainty reduction.

C. Language-Grounded Action Execution

The selected action is converted into a natural language utterance by the LLM.
- For Ask actions: The LLM generates a question and options that partition the candidate set.
- For Commit actions: The LLM generates a recommendation, potentially refining it based on conversation history.
State Update: Upon receiving a user response, the candidate set is pruned (removing inconsistent candidates), and the belief state is updated using a Bayesian multiplicative logic, reweighting candidates based on new semantic similarity.

3. Key Contributions

Uncertainty as a Signal: The paper identifies uncertainty not just as a metric, but as a guiding signal for multi-turn decision-making, moving beyond myopic scoring functions.
CUP Framework: Proposes a novel architecture that combines the flexibility of LLMs with the rigor of structured planning (MCTS) and uncertainty modeling (EIG).
Empirical Validation: Demonstrates consistent improvements in both effectiveness (Success Rate) and efficiency (Average Turns) across multiple datasets and model backbones.

4. Experimental Results

The method was evaluated on four datasets (Beauty, Fashion, Home, Inspired) using various LLM backbones (Qwen3-4B, Mistral-7B, Llama-3.1-8B).

Performance: CUP consistently outperformed all baselines, including retrieval-based (SBERT), heuristic LLM (Direct Prompting, CoT), and uncertainty-aware planning methods (UoT, ATD, BED-LLM, MISQ-HF).
- Example: On the Inspired dataset with Qwen3-4B, CUP achieved an 89.80% Success Rate, significantly surpassing the next best method (MISQ-HF at 67.35%).
Efficiency: CUP achieved higher success rates while requiring fewer interaction turns on average compared to baselines.
Robustness: The performance gap between different LLM backbones was smaller under CUP than for LLM-only methods, suggesting the planning mechanism reduces reliance on raw model capacity.
Ablation Study: Confirmed that structured planning is the dominant factor for success, while LLM-based commitment provides additional gains. Removing planning (Random selection) caused a drastic drop in performance.
Candidate Dominance: Analysis showed that CUP rapidly increases the "dominance ratio" of the target candidate in the early turns, indicating efficient narrowing of the search space.

5. Significance and Conclusion

This work bridges the gap between rigid structured dialogue systems and flexible but short-sighted LLMs. By treating uncertainty as a planning signal, CUP enables agents to:

Coordinate information acquisition and target commitment effectively over long horizons.
Reason about the long-term impact of questions, avoiding myopic strategies that waste turns.
Adapt to diverse, open-ended conversations without requiring predefined schemas.

The results suggest that integrating uncertainty-aware planning with LLMs is a critical direction for building robust, efficient, and intelligent goal-oriented conversational agents.