Research map / Large language models / Retrieval and knowledge
Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in LLMs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Uncertainty of Thoughts (UoT), a plug-and-play tree-search planning method that uses information-gain-based rewards and reward propagation to help LLMs ask more effective questions in 20 Questions, medical diagnosis, and troubleshooting.
Problem
LLMs often fail to actively seek missing information by asking effective follow-up questions in uncertain interactive settings such as medical diagnosis, troubleshooting, and guessing games, where standard QA benchmarks provide all information upfront.
Approach
Simulate possible future question-answer trajectories as a tree using LLMs as questioner and answerer simulators, score each node with an entropy-based information-gain reward (with a sharpening hyperparameter), and propagate accumulated and expected rewards to pick the question with highest expected information gain.
Key results
- UoT improves success rate by 38.1% on average over direct prompting across 5 datasets and 5 LLMs.
- UoT (closed set) with GPT-4 reaches 97.0% success on DX and 67.3% on troubleshooting (FloDial), versus 43.7% for direct prompting on troubleshooting.
- UoT outperforms Adapted-ToT by 12.4% and Reflexion by 29.9% on average success rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use UoT instead of Reflexion | GPT-4 · 20 Questions Common (CS) | success rate: 67.6 -> 71.2 | Helped |
| Use UoT instead of Reflexion | GPT-4 · 20 Questions Thing (CS) | success rate: 31.5 -> 37.5 | Helped |
| Use UoT instead of Adapted-ToT | GPT-4 · DX (CS) | success rate: 92.1 -> 97.0 | Helped |
| Use UoT instead of Adapted-ToT | GPT-4 · MedDG (CS) | success rate: 78.0 -> 88.0 | Helped |
| Use UoT instead of Adapted-ToT | GPT-4 · FloDial (CS) | success rate: 60.3 -> 67.3 | Helped |
| Replace UoT's uncertainty-based reward with heuristic self-evaluation (ablation) | UoT · 20 Questions, Medical Diagnosis, and Troubleshooting | success rate: 54.4 -> 48.5; 91.7 -> 89.0; 67.3 -> 66.0 | Hurt |
| Add the uncertainty-based reward to ToT (ablation) | ToT · 20 Questions, Medical Diagnosis, and Troubleshooting | success rate: 33.8 -> 45.3; 85.1 -> 85.6; 60.3 -> 66.0 | Mixed |
| Prune half of question nodes at each simulation step (ablation) | UoT · 20 Questions, DX, MedDG, and FloDial | success rate: 71.2 -> 62.2; 97.0 -> 92.1; 88.0 -> 83.3; 67.3 -> 63.2 | Hurt |
| Use maximum child reward instead of averaging child rewards at Questioner nodes (ablation) | UoT · 20Q-BIG-bench, Common, DX, MedDG, and FloDial | success rate: 79.3 vs 79.3; 63.7 vs 71.2; 95.1 vs 97.0; 83.1 vs 88.0; 62.6 vs 67.3 | Mixed |
| Select the single path with the highest cumulative reward (ablation) | UoT · 20Q-BIG-bench, Common, DX, MedDG, and FloDial | success rate: 75.9 vs 79.3; 68.5 vs 71.2; 94.2 vs 97.0; 82.9 vs 88.0; 61.4 vs 67.3 | Hurt |
Surprising findings
- Chain-of-Thought and planning prompting in closed-set setting underperform direct prompting for GPT-4 on 20 Questions.
- One-step simulation (depth 1) already achieves strong performance, with gains growing with depth.
Limitations
- Assumes answers are binary affirmative/negative and possibilities are eliminated discretely, not probabilistically.
- Benchmarks are simplified relative to fully open-ended real-world interactions.
- GPT-4 used as answerer/environment simulator, which may not reflect real humans.
Experimental setup
Datasets: Common (111 items, collected by authors) Thing (1854 items) 20Q-BIG-bench (29 items) DX (104 dialogues) MedDG (500 curated of 17K) FloDial (153 faults)
Benchmarks: 20 Questions (Common, Thing, 20Q-BIG-bench) DX MedDG FloDial
Metrics: success rate mean conversation length in successful cases mean conversation length
Baselines: Direct Prompting Planning Prompting Chain-of-Thought CoT-SC Reflexion Original-ToT Adapted-ToT
Builds on: Tree-of-Thoughts Chain-of-Thought Reflexion Monte Carlo Tree Search
Closest papers by meaning
- MediQ: Question-Asking LLMs and a Benchmark for Reliable Interactive Clinical Reasoning (NeurIPS 2024 · similarity 0.87)
- Learning to Think: Information-Theoretic Reinforcement Fine-Tuning for LLMs (NeurIPS 2025 · similarity 0.86)
- PlanU: Large Language Model Reasoning through Planning under Uncertainty (NeurIPS 2025 · similarity 0.85)
- Can LLMs Take Retrieved Information with a Grain of Salt? (NeurIPS 2026 · similarity 0.85)
- To Believe or Not to Believe Your LLM: Iterative Prompting for Estimating Epistemic Uncertainty (NeurIPS 2024 · similarity 0.85)
- DeLLMa: Decision Making Under Uncertainty with Large Language Models (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.