PaperlayerView exact revision on arXiv

Source-linked AI summary

Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in Large Language Models

Zhiyuan Hu, Chumin Liu, Xidong Feng, Yilun Zhao, See-Kiong Ng, Anh Tuan Luu, Junxian He, Pang Wei Koh, Bryan Hooi

arXiv:2402.03271v3cs.CLcs.AIcs.LG

TL;DR

Conventional LLM benchmarks often assume all necessary information is given upfront, leaving active information seeking unevaluated. UoT uses uncertainty-aware simulation, uncertainty-based rewards, and reward propagation to guide question choice. Across multiple LLMs, it improves success rate over direct prompting, and the paper evaluates it in simplified scenarios.

  • Problem

    Most standard LLM benchmarks assume necessary task information is provided at the outset and do not evaluate active information seeking.

    Source: §1 · p. 2

  • Method

    UoT simulates likely future scenarios, uses information-gain-motivated uncertainty rewards, and propagates rewards to select questions maximizing expected reward.

    Source: §1 · p. 2

  • Results

    38.1% average improvement in success rate over direct prompting is reported across multiple LLMs.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The introduced benchmark evaluates information-seeking questions across 3 tasks and 5 datasets.

    Source: §1 · p. 2

    UoT is evaluated in simplified scenarios; more realistic ones raise challenges such as answers that do not fully eliminate possibilities.

    Source: §5 · p. 10, §6 · p. 11

Abstract

from arXiv · show

In the face of uncertainty, the ability to *seek information* is of fundamental importance. In many practical applications, such as medical diagnosis and troubleshooting, the information needed to solve the task is not initially given and has to be actively sought by asking follow-up questions (for example, a doctor asking a patient for more details about their symptoms). In this work, we introduce Uncertainty of Thoughts (UoT), an algorithm to augment large language models with the ability to actively seek information by asking effective questions. UoT combines 1) an *uncertainty-aware simulation approach* which enables the model to simulate possible future scenarios and how likely they are to occur, 2) *uncertainty-based rewards* motivated by information gain which incentivizes the model to seek information, and 3) a *reward propagation scheme* to select the optimal question to ask in a way that maximizes the expected reward. In experiments on medical diagnosis, troubleshooting, and the `20 Questions` game, UoT achieves an average performance improvement of 38.1% in the rate of successful task completion across multiple LLMs compared with direct prompting and also improves efficiency (i.e., the number of questions needed to complete the task). Our code has been released [here](https://github.com/zhiyuanhubj/UoT)

1 Introduction

The introduction argues that LLMs need to seek information in uncertain interactive settings, since conventional QA often supplies all necessary information upfront. It presents UoT and a benchmark for evaluating question-based information seeking, reporting improved task success and efficiency.

1 Introduction

  • Conventional reasoning methods such as CoT and ToT do not explicitly guide question choice toward reducing uncertainty and revealing critical information.The introduction identifies this as a gap in enabling effective information-seeking questions.Source: §1 · p. 2
  • UoT combines uncertainty-aware simulation of likely future scenarios, information-gain-motivated uncertainty rewards, and reward propagation to select questions maximizing expected reward.The approach is presented as plug-and-play and aims to improve LLMs' ability to ask useful questions.Source: §1 · p. 2
  • The authors introduce a benchmark of 5 datasets across 20 Questions, simplified medical diagnosis, and basic troubleshooting to evaluate effective question-based information gathering.They note that most standard LLM benchmarks assume necessary task information is available at the outset.Source: §1 · p. 2
  • 38.1% average improvement in success rate over direct prompting is reported for UoT across multiple LLMs, with top performance on task success and efficiency.The benchmark covers 3 tasks and 5 datasets.Source: §1 · p. 2

2 Methodology

UoT selects questions by simulating possible conversational futures, rewarding expected uncertainty reduction, and propagating rewards to account for future gains. Its formulation covers closed- and open-set questioning, with simulations branching on affirmative and negative answers.

2.1 Problem Formulation

  • The Questioner aims to identify the true option through successive questions, with success determined by finding it before the turn limit.In the closed-set formulation, the Questioner knows the possibility space; the current possibility set retains options consistent with previous answers.Source: §2.1 · pp. 2–3

2.2 Uncertainty of Thoughts: Overview

  • UoT generates candidate questions, simulates future scenarios, assigns uncertainty-based rewards, and selects the question with the greatest expected reward.The overview combines question generation and simulation, uncertainty-based rewards, and reward propagation.Source: §2.2 · p. 3, Figure 2 · p. 3

2.3 Question Generation and Simulation

  • For each candidate question, UoT builds a multistep tree whose answerer branches represent affirmative and negative responses and whose questioner nodes generate simulated questions.The simulation tracks possibilities consistent with each node's conversation history.Source: §2.3 · p. 4

2.4 Uncertainty-Based Reward Calculation

  • UoT measures uncertainty with entropy and rewards questions for expected information gain; experiments assume a uniform prior over possibilities.The described answer branches are affirmative and negative, and the work focuses on this simplified scenario.Source: §2.4 · pp. 4–6

2.5 Question Selection Via Reward Propagation

  • UoT selects the candidate question with the highest expected reward, combining uncertainty-based rewards with accumulated and expected rewards across simulated paths.Accumulated rewards include rewards from a node and its ancestors; expected rewards are propagated from leaves toward the root.Source: §2.5 · p. 6

2.6 UoT Summary

  • The UoT procedure simulates a tree for each candidate, computes uncertainty-based rewards and expected rewards, then asks the candidate with the highest expected reward.The method also adapts to open-set cases by initializing and updating the possibility space, and offers pruning to limit simulation paths for efficiency.Source: §2.6 · p. 7, §2.7 · p. 7

2.7 Extensions and Discussion

  • Open-set UoT initializes possibilities from the current history; the framework also supports open-ended answers and pruning simulation trees to improve efficiency.Pruning limits the number of paths explored to a predetermined size.Source: §2.7 · p. 7

3 Experiments

The experiments evaluate multiple LLMs and baselines across 20 Questions, medical diagnosis, and troubleshooting, using success and conversation-length measures. Evaluations include open- and closed-set settings.

3.1 Experimental Setup

  • The study tests five current LLMs and reports additional validation on five earlier models, comparing UoT with prompting, reasoning, reflection, and tree-search baselines.Baselines include Direct Prompting, Planning Prompting, CoT, CoT-SC, Reflexion, and two Tree-of-Thoughts setups.Source: §3.1 · p. 7
  • Methods are evaluated in open-set and closed-set settings; open-set models lack prior outcome knowledge, while closed-set models receive complete information about possible outcomes.The open-set UoT setup updates perceived possibilities during conversation; 20 Questions begins with three Direct Prompting rounds.Source: §3.1 · pp. 7–8
  • The benchmark covers 20 Questions, medical diagnosis, and troubleshooting, using five datasets with specified item, dialogue, disease, and fault counts.The datasets include Common and Things for 20 Questions, DX and MedDG for diagnosis, and FloDial for troubleshooting.Source: §3.1 · pp. 7–8
  • Success Rate measures successful cases, while MSC and MCL measure conversation length in successful cases and across all cases, respectively.MCL counts rounds in both successes and failures.Source: §3.1 · p. 8

20 Questions

Across five datasets and five LLMs, UoT improves success rates over direct prompting, with strong medical-diagnosis and troubleshooting results. Comparisons at similar token costs and reward ablations also favor UoT and its uncertainty reward.

20 Questions

  • UoT outperforms baselines across open- and closed-set settings, and UoT (CS) surpasses second-best Reflexion by 4.3% in success rate.UoT (OS) improves success rate by an average of 8.7% over Adapted-ToT (OS).Source: §20 · p. 8
  • UoT (CS) with GPT-4 reaches 97.0% success rate on DX; on MedDG, UoT (CS) reaches 81.4% with Gemini-1.5-Pro and 88.0% with GPT-4.Source: §20 · p. 8
  • On DX with GPT-4, mean conversation length in successful cases (MSC) averages 2.0, lower than 3.5 and 3.0 for DP methods.Source: §20 · p. 9
  • UoT (CS) with GPT-4 achieves the highest troubleshooting success rate, 67.3%, and the lowest MSC, 7.8.Success rate rises from 43.7% to 67.3%.Source: §20 · p. 9
  • 38.1% average success-rate improvement over direct prompting across five datasets and five LLMs, including open-source and commercial models.Source: §20 · p. 9
  • Case studies show UoT narrows candidates with targeted questions rather than overly specific queries; GPT-4 answers were reliable in a 10% interaction sample per dataset.Source: §20 · p. 9

3.3.1 Comparing Model Performance at Equal Computational Efficiency

  • At comparable GPT-4 token use, Pruned UoT outperforms ToT and other methods, while Adapted-ToT (D = 4) trails UoT (D = 3).Table 2 reports average success rates for 20Q, MD, and TB at comparable efficiency.Source: §3.3.1 · p. 9, Table 2 · p. 10

3.3.2 Effectiveness of Uncertainty Rewards

  • Uncertainty rewards improve ToT planning efficacy by an average of 5.9%; replacing them with self-evaluation in UoT decreases performance.UoT without uncertainty reward still surpasses Adapted-ToT.Source: §3.3.2 · pp. 9–10, Figure 4 · p. 10

4 Related Work

Related work spans LLM reasoning and planning methods, decision-making systems, and efforts to strengthen information seeking. The cited work includes approaches with external planners, search, feedback, and task-specific tools.

  • Reasoning and planning work includes CoT for intermediate reasoning, ToT with DFS/BFS, GoT, TS-LLM tree-search decoding, ReAct, Reflexion, and unified reasoning-and-planning methods.Source: §4 · p. 10
  • Decision-making approaches combine LLMs with external planners or MCTS, while other systems address rephrasing, visual question answering, document access, clinical reliability, and 20 Questions.Source: §4 · p. 10
  • The cited discussion notes that MCTS struggles in uncertain scenarios because it relies on terminal states and specific modules for rewards and action selection.Source: §4 · p. 10

5 Limitation and Future Work

The benchmark simplifies open-ended medical diagnosis and troubleshooting, and its possibility-elimination approach may not capture overlapping possibilities or answers that fail to rule them out.

  • The benchmark simplifies open-ended diagnosis and troubleshooting; overlapping possibilities and answers that do not fully eliminate options may require probability estimates and Bayesian updating.Source: §5 · p. 10

6 Conclusion and Discussion

The conclusion reports UoT’s gains across five datasets while noting that evaluation uses simplified scenarios; the appendix gives a computational derivation of node-level information gain.

6 Conclusion and Discussion

  • UoT combines tree-based simulation, uncertainty-based rewards, and reward propagation to improve active information seeking.Source: §6 · p. 10
  • On five datasets, UoT increases success rate by 38.1% on average and establishes a benchmark for active information-seeking tasks.Source: §6 · p. 11
  • The evaluation uses simplified scenarios; more realistic settings may involve answers that incompletely eliminate possibilities, which the paper leaves for future work.Source: §6 · p. 11

A Derivation of Information Gain Formula

B Comparison of Various Scaling Methods in Reward Function Design

The section compares reward scaling and propagation designs, reporting the current propagation scheme as superior while describing the rationale and trade-offs behind the alternatives.

B Comparison of Various Scaling Methods in Reward Function Design

  • The current reward scaling setting is reported optimal among tested alternatives; λ > 0 sharpens rewards and penalizes overly specific questions when many possibilities remain.Source: B Comparison of Various Scaling… · p. 15

Uncertainty-based Reward (UR)

C Comparison of Different Reward propagation Schemes

D Experimental Performance for Earlier Released LLMs

The section identifies the datasets and metrics used for performance comparisons across three scenarios, but the supplied passages do not provide table values.

D Experimental Performance for Earlier Released LLMs

E Effect of Simulation Depth

The section examines simulation depth, GPT-4 environment reliability, and the uncertainty-based reward curve, reporting a performance-efficiency trade-off for deeper simulation.

E Effect of Simulation Depth

  • The depth experiment uses 20Q-BIG-bench and Common instead of Thing for 20 Questions, with the other scenarios using the main-chapter datasets.Source: E Effect of Simulation Depth · p. 17
  • Performance gradually rises with simulation depth, while one-step planning remains strong; the paper explores up to three steps as a practical performance-efficiency trade-off.Source: E Effect of Simulation Depth · p. 17

F Reliability of GPT-4 as the Environment

G Reward Function Details and Its Curve

H Experimental Statistical Significance

The section reports significance testing and success-rate comparisons between Direct Prompting (DP) and UoT, alongside descriptions of the evaluated baselines.

H Experimental Statistical Significance

  • The significance tests used three experiments on five datasets with Llama 3 and GPT-4; API quota limited the experiment count.The authors used t-tests to assess differences in success rates.Source: H Experimental Statistical Significance · p. 18

GPT-4 Results

  • Table 7 presents GPT-4 comparisons of DP and UoT on success rates.Source: Table 7 · p. 18

Llama 3 Results

  • UoT significantly outperformed DP on all five datasets in the Llama 3 t-tests (p < 0.05).Table 8 presents the Llama 3 comparison of DP and UoT on success rates.Source: Table 8 · p. 18, Llama 3 Results · p. 19

I.1 Baselines Setup

  • CoT prompts generate an explanation before a question, while CoT-SC selects the most repeated question from 33 samples.CoT-SC used temperature 0.7.Source: §I.1 · p. 19
  • Planning Prompt simulates future interactions; ToT variants use three-question branching, reward-based selection, and further simulation.Original-ToT uses self-evaluation and breadth-first search; Adapted-ToT adds question-generation hints, and pruned UoT retains half of candidate question nodes by uncertainty-based reward.Source: §I.1 · p. 19

I.2 Scenarios Settings and Datasets

The section describes evaluation scenarios and dataset preparation, then outlines open-set UoT configuration, implementation choices, and supplementary prompts and examples.

I.2 Scenarios Settings and Datasets

  • The evaluation covers 20 Questions, medical diagnosis, and troubleshooting, with datasets including 29 BIG-bench items, 111 Common targets, and 1,854 Things concepts.Medical and troubleshooting interactions begin with reported symptoms or faults; the answerer simulation uses scenario instructions and dialogue examples for those tasks, while 20 Questions uses yes-or-no answers.Source: §I.2 · pp. 19–20

I.3 Dataset selection criteria and process for MedDG

  • The MedDG evaluation set contains 500 dialogues with explicit diagnoses, selected across eight disease categories and filtered by conversation length.Two annotators performed initial selection and verification; dialogues with unclear diagnoses were excluded.Source: §I.3 · p. 20

I.4 Data Preprocessing of FloDial

  • FloDial preprocessing identified 153 faults with corresponding dialogues, named faults using GPT-4, and selected one dialogue history per fault.The faults correspond to leaf nodes in troubleshooting flowcharts.Source: §I.4 · p. 20

I.5 UoT (Open Set) Setup

  • For open-set 20 Questions, Direct Prompting gathers information for the first three rounds before UoT begins refining the possibility set each round.Medical diagnosis and troubleshooting can initialize the set from the initial symptom or issue description; possibility-set sizes were configured per dataset.Source: §I.5 · p. 20

I.6 Implementation

  • The implementation uses three simulation steps, three simulated questions, and an uncertainty-reward λ of 0.4.Source: §I.6 · p. 21

J Impact Statement

  • The impact statement expects information seeking to support more reliable, human-aligned behavior, while noting possible privacy and trustworthiness concerns related to LLMs generally.Source: J Impact Statement · p. 21

K Examples in Scenarios

L.1 DP(OS) and DP(CS) Prompt; L.2 Planning Prompt; L.3 UoT Prompt; L.4 Questioner Prompt

  • Prompt tables document DP, planning, and UoT prompts across the tasks, including probability-set information, staged reminders, and simulation instructions.The UoT prompts specify closed-set probability information and YES/NO counts; answerer prompts identify the target, disease, or fault.Source: Table 13 · p. 22, Table 16 · p. 24, Table 19 · p. 25
Loading 2402.03271v3…