Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in LLMs
Authors: Zhiyuan Hu
Chumin Liu
Xidong Feng
Yilun Zhao
See-Kiong Ng
Anh Tuan Luu
Junxian He
Pang Wei Koh
Bryan Hooi
Venue: NeurIPS 2024 poster (2024)
Keywords: Large Language Model
Planning
Uncertainty
Reseasoning
Information Seeking
Primary area: natural_language_processing
TL;DR: This work presents Uncertainty of Thoughts (UoT), an approach that enhances large language models' ability to ask questions and actively seek information by modeling their own uncertainty, significantly improving task performance and efficiency.

Abstract: 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).

Uncertainty of Thoughts: Uncertainty-Aware Planning
Enhances Information Seeking in LLMs
Zhiyuan Hul
Chumin Liu² Xidong Feng² Yilun Zhao
See-Kiong Ng¹ Anh Tuan Luu"
Junxian He Pang Wei Koh Bryan Hooi
1 National University of Singapore 2 Nanyang Technological University
Uniiersity College London Yale University
5 The Hong Kong University of Science and Technology
6 University of Washington
Abstract
In the face of uncertainty, the ability to seek information is of fundamental im- portance. In many practical applications, such as medical diagnosis and trou- bleshooting, the information needed solve the task 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 I) uncertainty simulate possible future scenarios and how likely they are to occur, 2) uncertainty- bused rewards motivated by information gain which incentivizes the model to seek information, and 3) a reward propagation scheme to select the optimal question medical
simulation approach which enables the model to
ask in way that maximizes the expected reward. In experiments 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 are released
Introduction
As the capabilities of large language models (LLMs) grow, they are being increasingly deployed challenging real-world settings involving uncer- tainty and ambiguity. In particular, recent work aims to develop LLM agents or assistants [36] 26) that effectively complete tasks in interactive envi- ronments, leading to growing need for LLMs that actively seek the information they need to solve a task by asking questions in conversational set- tings. For example, in medical diagnosis, patients often do not initially report their symptoms in full detail. In such situations, doctor's ability to ask effective questions is crucial, as a successful diag- nosis often depends revealing important details that the patient did not initially provide (Figure IT].
been having a headlache since yoolerdayy
Have you diserved any vision changees sensitiity to ligh?
Patient
you mendon it light recently
Doctor
head recontly?
Nh. I did hit my head a few days ago, but din't seem ous.
You may have post-concussion syndrome.
The importance of information seek- ing in medical diagnosis. The patient initially only complains of a headache, but by asking the right questions, the doctor uncovers the crit- ical information needed for a correct diagnosis.
Figure 1:
"Corresponding to: Zhiyuan Hu. Email: zhiyuan_hhatt hu u.nus.edu
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Recent techniques aim to improve LLMs' reasoning or planning abilities based on the given informa- tion rather than enabling LLMs to seek information efficiently. For example, Chain-of- (CoT) 35 and Tree-of- -Teeughhs (ToT) [38 allow L.LMs to express intermediate "thoughts' and reason over them. Unlike these methods, our focus is on enabling the LLM ask questions effectively by explicitly guiding the model toward reducing uncertainty, which these do not consider. Thus, they lack effective signals for questions that better reduce uncertainty by revealing critical information.
To enhance LLMs in actively seeking information, we introduce Uncertainty of Thoughts (UoT), a plug buug-and-pe and-play approach that improves LLMs' abilities to ask useful questions by modeling their own uncertainty. UoT is principled approach relying on mmccrtainty-basee rewards motivated by information gain, which incentivizes a model seek information in a way that maximally reduces the amount of information it does not know. To utilize these rewards, we develop an uncertainty-awe simulation framework, enabling the model to simulate possible future scenarios along with how likely they are to occur. Given these scenarios, we utilize a reward propagation scheme to select the optimal question to ask in a way that maximizes the expected reward.
Additionally, most standard benchmarks for LLMs, particularly in question amswering, assume that all necessary information to solve a task provided at the outset, and thus do not evaluate the model's active information-seeking capabilities. To close this gap, we first introduce a benchmark comprising 5 dataset: on tasks: 20 Questions, simplified medical diagnosis task, and basic troubleshooting task. These tasks are designed to measure the model's 's ability to ask questions effectively to gather the information they need. For example, the 20 Questions game, also studied by Noever al. [2].. requires the model to ask 'yes' or 'no' questions to determine an unknown object or entity. This scenario serves as a clear and easily analyzed test case, isolating the model's ability to recognize its own uncertainty, and to ask questions that guide it to the correct answer.
Our work is step toward LLMs that can effectively operate in settings with high uncertainty and ambiguity, beyond conventional QA settings where all the information needed to solve the task provided to the model the outset. To the best of our knowledge, UoT is the first approach for enabling LLMs to ask effective questions by explicitly modeling and seeking to reduce their uncertainty. Our key contributions are as follows:
1. We introduce Uncertainty of Thoughts (UoT), plug-and-play approach enabling LLMs to explicitly model and seek to reduce their uncertainty. UoT utilizes a principled approach based on an uncertainty-aware framework for simulating possible futures, rewards motivated by information gain, and a reward propagation scheme to select the optimal question to ask.
2. We introduce benchmark of 3 tasks and 5 datasets, designed to evaluate the ability of LLMs to seek the information they need by asking questions.
3. Experiments show that UoT improves the success rate of multiple LLMs by 38.1% on average compared with direct prompting, achieving top performance on both task success and efficiency. Our benchmark and code are publicly available.
2 Methodology
2.1 Problem Formulation
The problem setting involves two roles: the Questioner and the Answerer, performed by the LLM and a human, respectively. The goal of the Questioner is to deduce an unknown piece of infor- mation. We formulate this using a possibility space Q which is the set of all possible options, of which single element E S. is the true option in each given scenarid f For example, in a medical diagnosis setting, Q is the set of all possible diseases relevant in the context, e.g., Ω (Bronchitis, Flu,.... Hypertension], and for each patient, is the actual disease of the patient.
'We also incorporate the efforts of prior datasets 31 37 19 27,, through further work and refinement to construct this benchmark. Details are introduced in section 3 Experiments and Appendix 1.2]
*Under the -heaure-theoortic formulation of probability, the sample point w is an element of the sample space Qt and all random variables are defined to be functions of w. While we conform to this formulation, we try to avoid unnecessary measure- theorrtic background for ease of understanding: hence, it is sufficient for readers to understand w the 'true option' in each scenario.

---

Question Genematio and Simulation
(b) Innerninnt--assee -hased Reward
Reward Propagarion Scheme
L4M sunteer
Edilaato conellin
disess havel
Focd
lncker
peaceng...
MaY
LAM
cxeskeer
Jenda...
No.
leven
Navorn
Informatiin
Pravertd (lscci
Licernarr Uivect Hervnt R
Queeton Gererition
Simulate Plusble
R Raa R. -Ra
RR
Figure 2: UoT Overview: UoT includes three components: (a) Question Generation and Simulation, where LLM proposes candidate questions and simulates future scenarios; (b) Uncertainty- -based Rewards, measuring the uncertainty reduction from answers to a question, and (c) Reward Propagation computing accumulated rewards Rs over past questions, and expected rewards R. capturing expected future gains. The process ends by choosing questions with the highest expected reward.
The interaction between the Questioner and the Answerer occurs over multiple turns. For instance, the Questioner may ask, "Do you have a fever?", to which the Answerer responds, "Yes, I've had a high fever for the past two days." The Questioner then asks another question such as "Have you vomited?" This exchange continues either until the Questioner correctly determines the final answer, or the conversation reaches a maximum number of turns. At this point, the interaction ends, and the Questioner successful if it has correctly determined the true option w.
Most of the description of our approach focuses on the closed sel scenario, in which we assume that the Questioner starts with knowledge of the possibility space Ω2 e.g-, the set of all possible diseases in medical diagnosis. In our extension section 2.7 we adapt our approach to the open set scenario, in which this knowledge is absent. Moreover, as the questioning progresses, gradually refine this set of possibilities to those that are consistent with the current answers given so far by the Answerer. Define the current possibility set S2 as the subset of Q that consistent with all answers given by the Answerer before the start of the ith interaction step.
L.M to
As we diseuss more later, focus applications where answers be grouped into small number of semantically distinct categories (in our case, affirmative and negative responses), as this allows us compute meaningful uncertainty metrics in simpler way. Conceptually, our framework can straightforwardly be extended to allow for a wider selection of answers.
2.2 Uncertainty of Thoughts: Overview
As Figure shows, to effectively reduce uncertainty, our UoT method first generates multiple questions as candidates to ask, and simulates possible futures for each one in the form of a tree structure. Next, uncertainty-based rewards, motivated by information gain, are used to assess the questions within the simulation. Finally, a reward propagation scheme is used to compute the expected reward from asking each candidate question, allowing us to select the one with highest expected reward, to ask the Answerer.
2.3 Question Generation and Simulation
UoT starts by using an LLM to generate several candidate questions, then simulates future scenarios for each one. This simulation process allows us measure how much information we can expect to gain in the next few steps from each question, and thus to choose the most suitable question.
Question Generation Recall that our setting involves sequential interactions between a Questioner (c.g., a chatbot) and an Answerer (e.g.. a human patient). During the ith interaction step, the Questioner generates candidate questions, then selects one of these ask, denoted as q:-
To generate candidate questions to ask, UoT uses two inputs: (1) the history of past interactions h4 fq1,41.900 01.011.2... 12,02..... 9i-1, 0;-1) ), comprising the sequence of past questions and answers; and (2) the current possibility sei Ω2 These two inputs are combined to form prompt that includes instructions explaining the nature of the task (e.g., how the 20 Questions game works), provides the current history h; and the current possibility set Ω2 and asks an L.M to generate m candidate next questions, conditioned on the previous context. This prompt, denoted as Prompt (h, 24), is fed to
3

---

our generator LLM which then generates m candidate questions, denoted g. 12........ "....,,""" ..""
Q. = (Promptgeep (2))
Multistep Simulation As shown in Figure 2 (a), the Question Generation stage generates candidate questions such as qf "Did you vomit?" Next, during Simulation stage, for each such generated candidate question, we simulate possible futures for a few steps, forming a tree of possibilities. This process enables to compute rewards for each question, helping us to decide which question to ask.
Each node of the tree can be one of two types: Answerer Nodes where is the Answerer's turn to answer a question, and Questioner Nodes where it is the Questioner's 's turn to ask a question. At the root, a question has just been asked (e.g.. (.), so the root is an Answerer Node. Next, we explain how to construct tree by recursively expanding (or "branching') ) each node to construct its children, i.e., starting from the root, then proceeding to its children, and so on.
At each Answerer Node, a question has just been asked. Next, we need to further 'branch' the tree based on the possible answers to the current question. Rather than allowing completely open-ended answers, we instead focus on affirmative and negative response as this allows us to compute meaningful uncertainty metrics, as we discuss later. Hence, we branch the node into two children, corresponding to affirmative and negative answers.
At each Questioner Node, we prompt an LLM to generate m questions using the current history and possibility set, in the same way in the Question Generation step. Note that while the generation procedure is similar, the purpose is different: the Question Generation step generates candidate questions select from, while here we are generating simulated questions to form a tree for the purpose of evaluating the current question. The resulting m generated questions are added the tree as children of the current node.
In this way, we recursively generate tree nodes, stopping at a fixed number of levels (i.e., depth).
While generating this tree, we also recursively compute the current possibility set P. at each node v. Specifically, let h, be the current conversation history up to node v, combining both the actual conversation history hú and the simulated conversation up to node Then the current possibility set at this node, denoted f2. is the subset of the possibility space consistent with hg. At the root, the current possibility set is only limited by the actual conversation history, i.c., 24. Then, over the simulated tree, note that the current possibility set only changes at Answerer nodes, when an answer is added to the current history. Hence, at cach Answerer node v, we prompt new LLM (an 'Answerer Simulator' LLMans), to determine the further subset 22 C Q2 for which the answer to the current question is affirmative, and the corresponding Ω S2 \ 2 for which the answer is negative 0 This allows us to recursively compute the possibility sets of the children of (which themselves correspond to the affirmative and negative answers).
proceed
2 . LLMans (Promptasshs 24))
In this way, we can recursively compute the possibility set each node of the tree.
2.4 Eicertainty-Basee Reward Calculation
To develop suitable information-seeking approaches, critical question is how evaluate the effectiveness of a question, i.e., its contribution to reducing uncertainty. To address this, we turn to information theory, specifically the concept of information gain, which measures the amount by which uncertainty decreases after a particular observation. To reward information-ssekingg behavior, we assign rewards to questions based on how much they reduce the model's 's uncertainty about the unknown random variable. These reward signals are used by our UoT framework to determine which question to select, to maximize the reduction of uncertainty.
Entropy. Entropy and information gain are well dell-known concepts in information theory 29 In our work, use these concepts to measure how much information is gained (or equivalently, how much
$ "s shown Figure (a). for question 'Did you vomit?', possible aftirmative responses include "yes" 'I already vomited twice". while negative responses could be 'no" or don't have'. 'I practice, allowing overlap between Ω and Ω may be more realistic. However, in this work, we consider only the simplified scenario where they are disjoint.

---

uncertainty is reduced) by asking a question, to formulate our rewards. Entropy measures the level of uncertainty in random variable: higher entropy indicates greater uncertainty. The entropy of discrete random variable X taking values I1, ..., Cn is:
((X) E p(a,) -())) log ((:))
Since our goal is to reduce the uncertainty in the unknown w Q, we use entropy to measure this uncertainty. Formally, let Ω {wI.-.. ,Wn). and we define an additional set of arbitrary real numbers X = {x1,- -.1,,... In S which we will associate with each of these possibilities. Define random variable X 12 X' such that X(w) 24. Intuitively. X is a discrete random variable that takes the value 2; if the ith possibility is true, i.c., if w wi. X' serves to capture our uncertainty about w, since observing X is equivalent to observing the true option
As simple example, suppose our possibiliity space is f2 = fw1, W2, w2)))) we accompany these with real numbers T1, I2, Iz, and have distribution for random variable X reflecting prior beliefs over these possibilities: e.g. p(z1) = 0.2, p(22) = 0.3, p(za) = 0.5. Conceptually, our framework allows for any prior probability distribution over the possibilities (i.e., p(z;)), but in our experiments, we assume uniform distribution over them due to the lack of an informative prior.
Before asking any questions, our uncertainty about the unknown is given by HX)., in Eq. (3) At any node v of the trees described in the previous section, recall that we have a conversation history he which contains some answers given by the Answerer. This history limits the current possibility set to those in S2 C Q, thereby reducing our uncertainty. We model this using the standard notion of conditional probability
event: since Q2 S Ω2 thus Prp is an event which
condition on:
plz, = p(x:)//((2.) V such that wy E Qg
(4)
where p(2.)) is the sum of probabilities of the elements in 22. To illustrate, we continue from the earlier example, where p(x1)= = 0.2, p(x2) 0.3, p(z;)) = 0.5. If the conversation history h2 at node v is only consistent with I1 and æ2. i.c., Q, = (wi, W2). } we can adjust probability distribution by conditioning: e.g., the adjusted probability of 21 is p(x1) / 0.2/ + 0.3) 0.4.
Next, to quantify the uncertainty at node v, note that since X is conditionally distributed based on p(-(S.)) the entropy of this distribution is:
Hx(X) 100==x. En, ((x) por,((.))..))))
Intuitively, (X) is the remaining uncertainty in X at node o (i.e., after observing the history h2).
Information Gain at Node We now quantify the uncertainty reduction when receiving answers an Answerer node v. Recall that the answer given at v partitions 22 into two disjoint subsets:
Ωg = 2 U D. where 22 and 22 are the subsets of possibilities resulting in affirmative and negative answers to last asked question. Given an affirmative answer, the remaining entropy becomes:
(x)x) = >. Stw, Eng
p(z, (2))) log p(x,((())))
(6)
We define H (X) analogously for negative answers. Let De = p( and p p( (?, be the conditional probabilities of affirmative and negative answers node v. To compute the expected entropy after receiving the answer at node v, since we have a p probability of receiving an affirmative answer and p of negative answer, the expected entropy is:
PCC (X)( + NN HH(())
As such, the expected information gain at node is the difference in entropies before and after receiving the answer:
:= H,, p H²(()) - P. H (X)
(8)
We can simplify this: as proven in Appendix A the above equation reduces to:
(X) = - log pd - p log
This represents the expected reduction of uncertainty in X when receiving an answer at node v. Note that it has an entropy- like expression, and is therefore nonnegative.
5

---

Reward Formulation A natural approach would be to define the reward function (2(v) at node as the information gain (X): that is, the reward from the question at node is the expected information gain (X) from receiving its answer. In practice, we find that slightly modified function (G,(X) (X) is preferable. In particular, we find that (X) does not result in sufficiently sharp differences in reward over the typical ranges we encounter. Hence, we introduce an additional hyperparameter À 2 which helps to sharpen the rewards using scaling approach. We compare other scaling methods and determine the current design is optimal in performance and their corresponding benefits. Details are in the Appendix B
(u( = (X)
(x)))=IG((X))= = (-p, logr p. log )/(1))1111) + + P.
(10)
This definition ensures that (v) falls within the range [0. 1), providing a normalized and consistent
reward to measure uncertainty reduction. The reward function reaches its maximum when the subsets F and 22-5 have equal probability, reflecting the maximum reduction in uncertainty. It reaches its minimum when one of the subsets has zero probability, indicating no reduction in uncertainty. Appendix G Glots the reward function curve across values of p and p.
2.5 Question Selection Via Reward Propagation
Single-step rewards often fall short in dynamic settings they only consider immediate impact, overlooking long-term effects. To overcome this, our method uses a reward propagation scheme across simulation trees by defining 'accumulated rewards' that gather rewards over multiple simulation steps to reflect the effectiveness of past decisions. These accumulated rewards help compute 'expected rewards', indicating the likely benefits of the questions and guide the selection of candidate questions.
Accumulated Reward We first define the accumulated reward each node v, which accumulates the rewards at e and all its ancestors on the tree, defined recursively as:
0 Ra(v)= = (u( + Ra (Parentt())
is root otherwise
Here (v) is the uncertainty-based reward at node v defined in Eq. (TO), and R., (Parent(())) is the accumulated reward of the parent of v. We compute these accumulated rewards by starting the root and propagating down to the leaves. Intuitively, the accumulated reward at each leaf node represents the total reward we end up with at the end of the conversation that node.
Expected Reward Next, we compute the expected reward for each node Re (v). which represents the expected total value of rewards received on expectation on node and all its descendants on tree.
Ra(v) (e(v)= = p Pp Re +
if is leaf; otherwise: if e is an Answerer Node
1 (ieCChildee(() (w)
if e is Questioner Node
For the case where e is an Answerer Node, recall that p and ahd are the conditional probabilities of affirmative and negative answers node v, defined in section 2.4 4 and ! are its children, corresponding to the affirmative and negative answers. For the case where v a Questioner Node, we assign equal probability to the m questions asked from this node. In this way, we propagate the expected rewards from the leaves up to the root, allowing us to compute the expected gain at the root. We compare different reward propagation schemes and find that using cumulative rewards from all paths enhances long- term decision decision-making making benefits. See Appendix C for details.
Determining the Optimal Question Finally, to decide the question to ask, we select the question with highest expected reward (and therefore, the highest expected information gain, considering both immediate and future information gains):
= arg max Re (g())
(11)
n=1

---

2.6 U Summary
UoT first generates candidate questions q. q. ...... set Ω4 Then, we conduct multistep simulation to generate a tree for each candidate question qi Next, we compute the uncertainty-bact based rewards (v). and propagate over the trees to compute accumulated reward Ra, (v) and expected reward (v)... Lastly, the optimal question qf' with highest expected reward will be selected as q to interact with the Answerer. UoT generates candidate questions z: q 1....... o.t based on history and the current possibility set f2. It simulates tree for each question, calculates uncertainty-bant -bsed rewards R,(v), (v), and computes expected rewards (.(v). The question of" with the highest expected reward is chosen for interaction.
9. ...
based on the history h2 and current possibility
2.7 Extensions and Discussion
Open Set UoT. Recall that in the closed set scenario, the Questioner starts with knowledge of the possibility space Ω. In practice, the possibility space is often unknown, resulting in the open set setting. To adapt UoT to this case, we prompt Questioner initialize the possibility space 12 and then reinitialize the possibility set Q2 according to current history h4, Then, the rest of UoT is unchanged. The generalization in open-end answers. The UoT framework enables LLMs to update possibilities after each interaction, including atfirmmaive/negative or open-ended responses. Thus, it can be applied to open-ended answers scenarios. Pruned UoT. To enhance efficiency during simulation, pruning akin to Beam Search can be employed when constructing the simulation trees, which limits the number of paths explore over the tree to a predetermined size.
3 Experiments
3.1
Experimental Setup
Models We test various LLMs evaluate the generality of our method, including Llama-3-70B- Instruct [.. Mistral-Large [21]. Gemini-1.5-Pro (28). Claude-3-Opus 44] and GPT-4 [24]. We
also validate the performance of earlier released LLMs (Refer to Appendix D) including Llama
2-70B-Chat
(2), Cohere 99, PaLM 2 22. Claude 2 g and GPT-335-turbb 23
Baselines Direct Prompting (DP) prompts LLM directly generate the next response. Plan- ning Prompting (PP) is motivated by Wang et al. 33 We leverage another LLM to plan the future and, consequently, determine the question ask. Chain-of-Thought (CoT) 335 improves reasoning in LLMs by detailing reasoning steps. CoT-SC (Self-Consistency) (34 an is an ensemble method, explores multiple reasoning paths. We standardize sampling counts for fair computational cost com- parison with other methods. Reflexion (30] lets agents propose actions and self-assess to foster new ideas. Tree-of- Tree-of-Thoughts (ToT) (38 enables LLMs make decisions by exploring and evaluating multiple reasoning paths over a tree structure. We examine ToT under two setups: Original-ToT, which uses the standard approach of generating and evaluating questions, and Adapted-ToT (Ad.- ToT),, where we integrate heuristic experience into prompt for question generation and evaluation, focusing on questions that halve the search space. We matched the tree depth to the simulation steps in our UoT method for a fair comparison. We evaluate methods and LLMs in both open set (OS) and closed set (CS) settings. In open set, models are tested without prior knowledge of outcomes; in closed set, they are given complete information about all possible outcomes. For details, see Appendix [. for experimental settings and Appendix for prompts.
Scenarios and Datasets 20 Questions is a game where the answerer thinks of an item and the questioner asks up to 20 yes-or-no questions to guess it. We use two datasets, Common (collected by us, refer to Appendix for more details) and Things [14), including 111 and 1854 items separately, In this scenario. the maximal turns is set 20. In Medical Diagnosis, the doctor needs to ask questions to patients about their symptoms, to determine an accurate diagnosis. We use two datasets: DX (37, with 104 doctor- paationtppaiettttoo dialogues and 5 diseases in test set, and MedDG [19] with over 17K conversations across 15 disease types. We manually selected 500 high- samples for evaluation (see Appendix for selection process). Importantly Open-ended responses from patient are allowed in MedDG to validate UoT's generalization in open-ended scenarios. Both datasets are limited to 5 turns. Troubleshooting is a scenario where a customer support technician interacts with eustomers to identify and resolve faults or issues within computer systems, electronic devices, machinery, or
7

---

Table 1: Results from three different scenarios, assessing Success Rate (SR), Mean Conversation Length in Successful Cases (MSC), and Mean Conversation Length (MCL).
Questions
Dinguooss
Troubleshottnng
Common
Thing
DX
Flolial
MSC]
MCL,)
MSC
MC14
MSCJ
MCT.)
SR1
MSCJ
MC3.]
(18)
13.0
17.9
19.3
36.0
4.5
11.1
Limoc--008
(CS)
51.6
14.6
17.5
138
63.7
3.5
00.2
8.1
18.8
13.7
(CS)
53.9
12.6
155
25.0
90.4
1.0
27
47.1
7.6
DP/OS)
13.1
18.6
18.3
3.4
11.1
Mistrl-l.nge
UuT(O8)
27.0
15.1
18.7
34,0
2.5
DP (CS)
26.1
13.4
15.3
13.0
12.6
19.0
38.5
3.3
4.3
46.7
3.3
0.2
14.2
16.0
19.4
UoT (CS)
31.5
9.8
16.8
18.5
13.2
18.7
48.1
2.3
3.6
68.0
1.9
3.2
30.1
10.9
17.3
DF (OS)
36.0
16.8
15.8
17.5
14.4
19.0
26.9
3.5
4.6
23.7
4.0
4.8
9.15
15.6
19.6
Gemini-1.5-Ppg
TP (C:))
UpTrOS)
39.7
14.6
17.0
15.6
17.9
22.0
28.5
1.507
13.4
18.5
18.5
09.3
4
2.4
3.8
4.0
3.8
38.6
51.4
2.9
4.2
39..
19.0
12.1
14.00
18.5
T6.2
Unl (CS)
69.4
13.9
16.3
32.0
14.0
18.1
$1.7
2.1
2.6
81.4
2.1
2.6
53.6
11.3
15.4
DP1O6)
45.0
14.2
17.4
16.5
13.88
19.0
33.7
3.4
4.5
54.5
3.2
4.0
31.4
15.7
19.6
Claude 3 Opss
(T:5
RXT
14.4
TV%
168
16.5
"15.5
23.8
18.3
18.4
T67)
75.75
45.9
2.6
7.5
"X77"
3.0
"VES"
61.5
2.3
3.3
5.5
35.9
11.0
TK11"
16.8
Uaf (CS)
66.7
6.9
11.3
41.5
13.9
17.5
$1.7
2.2
2.7
79.3
2.4
2,9
56.2
6.2
12.2
DP(OS)
48.6
14.0
17.1
16.5
12.6
18.8
44.3
3.5
4.9
45.7
4.2
4.6
18.4
15.0
12.3
0-T005)
13.5
18.6
19.8
6.00
16.4
19.8
1.5
4.8
9.71
4.0
4.0
30.7
10.3
12.0
45.0
13.8
19.0
21.0
15.2
19.0
45.2
2.4
3.8
$1.4
2.7
3.8
35.3
15.3
17.7
GPT4
UNTrOS)
DF (C5)
50.5
$5.3
15.1
13.1
16.5
17.4
30.5
28,0
15.11
14.9
17.5
18.6
59..3
49.1
2.4
3.0
307
3.5
7E.
67.4
2.5
3.5
43.7
43.5
13.
12.0
17.1
16.8
(CS)
14.9
15.0
58.5
2.5
39.2
14.2
CoT (CS)
16.0
19.2
33.7
4.4
32.8
Colf (CS)
14.0
16.7
48.5
3.6
4.5
425
Reflesion
67.6
12.0
14.6
315
18.
52.5
3.9
4.3
28.6
Ongiral-Tol (CS)
28.6
15.5
18.7
19.1
10.3
3.3
3.8
32
38
40.4
Ad- (CS)
43.6
12.2
16.1
25.0
130
183
92.1
1.9
3.2
78.0
3.0
34
60.3
82
12.9
Pairal Dall (CS)
62.2
18.8
14.3
34.0
14.
18.3
92.1
1.9
21
83.5
37
31
63.2
83
12.5
UsT (CS)
71,2
10.8
135
37.5
14.4
17.9
97.8
2.0
211
88.0
2.6
29
67.3
7.8
11.8
other complex systems. Raghu et 22] introduce FloDial with 894 dialogues, containing 153 faults and we also conduct the data preprocessing of FloDial (See Appendix [.rffor details). We evaluate using a maximum of 20 turns. The answerer, simulated by GPT-4, is prompted with the patient's 's actual disease and conversation details for each case. For more details, refer to Appendix [.2 and see examples of these scenarios in Appendix K
UoT (Open Set) Setup We iteratively update LLMs' perceived possibilities based on conversational history, rather than defining them all upfront. In medical diagnosis and troubleshooting. initial descriptions from symptoms or issues help set up initial possibilities. In the 20-question game, we start with broad inquiries using the Direct Prompting method for the first three rounds to gather more information. The ToT tree structure method employs a similar strategy. Setup details in Appendix [.5)
Evaluation Metrics To measure efficacy and efficiency, we use: Success Rate (%): SR = S/T, where S is the number of successful cases, and T is the total number of cases; Mean Conversation Length in Successful Cases: MSC = Rs/S, where R, is the total rounds successful cases; Mean Conversation Length: MCL. R/T, where R is the total rounds in all cases. MCL measures efficiency based on the resources used in both successes and failures.
3.2 Performance
20 Questions As illustrated in Table 5 for all types of LLMs, those equipped with UoT outperform the baselines in both open set and close settings. Among the methods used on GPT-4 to enhance planning and reasoning, CoT (CS) and PP (CS) show inferior performance even compared to GPT-4 alone. UOT (OS) demonstrates superior performance, with with average 8.7% improvement than Adapted-ToiT (OS) in success rate. Moreover, UoT (CS) achieves the highest success rate, surpassing the second-best Reflexion by an average of 4.3%.
Medical Diagnosis UoT (CS) outperforms baselines in simplified medical diagnostics, achieving a 97.0% success rate on the DX dataset with GPT-4 On the MedDG dataset, UoT (CS) on Gemini- 1.5-Pro and GPT-4 achieve success rates of 81.4% and 88.0%. It also reduces conversation lengths to an average MSC of 2.0 on GPT-4 for DX, lower than 3.5 and 3.0 for DP methods. These results demonstrate the versatility of our UoT in handling both binary and open-ended interactions effectively.
8

---

Troubleshooting UoT (CS) with GPT-4 similarly achieves the highest SR of 67.3%, and the lowest MSC of 7.8. It also shows a remarkable improvement from 43.7% to 67.3% in Success Rate.
Overall Performance On average, UoT enhances the success rate by 38.1 % compared to DP across datasets and 5 different LLMs, including open source and commercial models. Notably, Success Rate increases 46.6% for Llama3-70B. Furthermore, UoT outperforms CoT-SC by 33.8% and Reflexion by 29.9%. Even compared to tree structure methods like Original-ToT and Adapted-Tol UoT still shows superior performance with gains of 28.3% and 12.4% respectively. Additionally, Pruned UoT, our pruning method to improve efficiency, outperforms Adapted ToT by 7.36%. Addi- tionally, our study shows that UoT''s one-step planning is effective due to effective reward design and question selection. We limit simulations to three steps for budgetary reasons, balancing efficiency and effectiveness (see Appendix E for further details on simulation depth). To determine whether the differences in success rates between the two methods were statistically significant, we performed a I-test. The results and details are in Appendix H
Case Studies and Reliability of GPT-4 as answerer Figure B] shows UoT, compared to direct prompting, more effectively reduce uncertainty and narrow down candidates, avoiding overly specific queries. After gaining initial information (e-g.. stomach pain), it generates targeted questions about related issues rather than general inquiries. Additionally, GPT-4's accuracy as answerer is evaluated by analyzing 10% of interactions from each dataset, consistently showing reliable responses. For quantitative details, see Appendix F
3.3 Analysis
3.3.1
Comparing Model Performance at Equal Computational Efficiency
We compare the performance of approaches with similar computational costs in closed set setting, in terms of token consumption. To do so, we first prune our UoT as described in section 2.7 Secondly, we expand exploration depth of Adapted-Tof ToT method to bring its token cost in line with that of UoT.
As shown in the top half of Table 2 the Pruned UoT method, despite its reduced efficacy compared to UoT, still outperforms ToT and other methods. Also, the bottom part of Table 2 shows that even when increasing the depth of Adapted ToT (Adapted-Tios - (D = 4)) to match the token cost of UoT (D 3), it still underperforms compared to UoT.
3.3.2 Effectiveness of Uncertainty Rewards
To further demonstrate the effectiveness of our uncertainty- reward, we compare it with the self-evaluation reward used in the original ToT based on GPT-4 model. We implement the uncertainty- based reward in place of the self-evaluation reward in ToT, creating a variant we call ToT (+UR). The results, as shown in left side of Figure 4 indicate that our reward significantly enhances planning efficacy by an average of 5.9%. Additionally, we use the heuristic self-evaluation reward in Adapted- ToT to replace our current mncertainty-basee reward in UoT, variant we refer as UoT (-UR). This change results in a performance decrease shown in the right part of Figure 4 further validating the effectiveness of our uncertainty-basee reward. Moreover, the performance of UoT (-UR) still surpasses that of Adapted-Te ToT illustrated in Table 5
Direct Prompting
UpT
Direet Prompting
Un!
Of living thing?
Is A1: X manmmade
Scffltepest: Steeachadss Pan is uppor andemind uree. No ciactos (Forale, 27 year eld)
a listng thing.
11 (and in Nueih Amenica?
OR 1x kugger then hummar?
AN No, in noe binger then humon
Q8 X camivure?
A2 Yos X anims
unims?
Al: No. I howen't experienced any resees somiting: The pain stamee around six
sumning?
Q1: Have you expesieaced any azssea or
Qt: Do experiance a barning gnawing scneatien in your sinmach. eppcially or as enply stomal?
Al Vos. I do have thr sesctton, zspcciall or enpty stonah. Qr: you
[49 No.
found Nooth Atterica
Yos,
delack ....
1010: 1a Srund in Alfica?
No. X is found Afiie.
Yes momonel
X mommal
02: Does paia onfine any other of No, dosalt shoukler?
any turry
[ALL: Yeu. X found is Asia. Specitic!
(011: found Acis?
resocraee with water?
Q5: X mammal that typoally
AS No, X act asseciated with water.
port body It's midile abdones, right dhove
grouds?
bot haven' vonted.
AD: nutterd the my
Q14: leeoued?
CR: X lesped!
Qs: Do graney foods?
A3: You are probably experiencing Gasusi sleer
A14:15 Yes. X xipa loquart
A9 You xype officoudd...
Q15k LxX sami lospand?
Q10:1 snow lnopord!
A5: No. any pain eating. toeling
More Direct and Efficient
A15:You You gressad X Stow loagand
pansed Snow looparet
d'clock...
Figure 3: Case studies from the 20 Questions game (left) and simplified medical diagnosis (right).

---

Table 2: Average success rates for 20Q, MD, and TB at comparable efficiency, measured by GPT-4 token use. k is sampling count, D is tree depth.
IITOT (TTT(-
BUSTCUR) BUST
5K1 85A
513
564
Method
Tokens
20Q
MD
TB
CoT-SC(k = 33)
4.6k
32.6
37.6
42.5
Ori--ToT(D = 3)
4.5k
23.7
65.3
40.4
Adapt-ToT(C 3)
4.5k
33.8
85.1
60.3
Figure 4: Success rate comparison between
Pruned UoT((D 3)
4.7k
48.1
88.4
63.2
Adapted-ToT and Adapted-ToT using uncer- tainty reward, and between UoT and UoT with- out uncertainty reward.
(TDpt--ToT(D>>>>) = 4)
9.3k
40.9
86.7
63.7
UoT(D 3)
9.2k
54.4
92.5
66.0
4
Related Work
Planning and Reasoning of LLMs LLMs show prowess in planning and reasoning. Wei et al. [35 introduced CoT prompting for intermediate reasoning; Yao al.(38) proposed ToT prompting using DFS/BFS. Besta et al. present GoT to solve elaborate problems. Feng et al. [12) illustrated TS-
LLM's tree-search guided decoding. ReAct 39] offers acting-basee prompting, while Reflexion 30
enhances this with feedback reflection. Zhou et al. 41 unify reasoning and planning.
Decision-making and Information-seeking by LLMs LLMs have evolved as pecision-making tools, with models like LLM+P [8]] and LLM-DP [1O combining external planners and LLMs for natural language-basse based programming. RAP [3 goes beyond structured language, using LLMs with Monte Carlo Tree Search (MCTS) 7 for dynamic decision-making This approach is also seen in the work of Zhao et al. 44), applying MCTS and LLM knowledge for complex tasks like robot control. However, MCTS struggles in uncertain scenarios due to its reliance on terminal states and specific modules for rewards and action selection. Additionally, to enhance LLMs' questioning abilities, Deng al. [1] introduce the Rephrase and Respond method. AVIS [15
represents autonomous visual question answering system that uses external tools. Pan et al. 25 introduce KwaiAgents for processing queries, following guidelines, and accessing external documents. Frameworks such as MEDIQ [17] and MDAgents [16] improve the reliability of LLMs in clinical settings by strengthening realistic diagnostic processes. S also explore Chatgpt's s information seeking strategy in 20 20-questions game.
information-seel seekiin capabilities and agent systems, thereby supporting
5 Limitation and Future Work
In practice, 2A and n. might overlap, as different answers (such as "yes" or "no") may lead to the exclusion of different of possibilities. Another similar limitation is that some questions or answers may not fully eliminate certain possibilities (e.g.."I don't 't have a fever" does not 100% eliminate the possibility of having COVID-19), Furthermore, compared to completely open-ended interaction in medical diagnosis or troubleshooting, our current benchmark represents a simplified scenario. In theory, such cases could be handled using the method of converting interactions into probability estimations and applying some kind of Bayesian update to the probabilities of each possibility, rather than just eliminating some subset.
Conclusion and Discussion
This paper presents the Uncertainty of Thoughts (UoT) algorithm, significantly improving LLMs in tasks requiring active information seeking through tree-baser simulation, uncertainty-based rewards and reward propagation scheme. On five datasets UoT increases success rate by 38. 1 % on average, establishing a new benchmark for evaluating LLMs in active information-sseking tasks. We evaluate UoT on simplified scenarios; more realistic scenarios raise challenges like allowing incomplete climination of possibilities by answers, and others which we leave for future work.
10

---

7 Acknowledgment
Pang Wei Koh supported by the Singapore National Research Foundation and the National AI Group in the Singapore Ministry of Digital Development and Innovation under the Al Visiting Professorship Programme (award number AIVP-2024-001).
References
[1] MetMeta. Llama 3 model card. 2024.
[2] Rohan Anil, Andrew M. Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, Eric Chu, Jonathan H. Clark, Laurent EI Shafey, Yanping Huang, Kathy Meier-Hellstern, Gaurav Mishra, Erica Moreira, Mark Omernick, Kevin Robinson, Sebastian Ruder, Yi Tay, Kefan Xiao, Yuanzhong Xu, Yujing Zhang, Gustavo Hernandez Abrego, Junwhan Ahn, Jacob Austin, Paul Barham, Jan Botha, James Bradbury, Siddharthh Brahma, Kevin Brooks, Michele Catasta, Yong Cheng, Colin Cherry, Christopher A. Choquette-Choo, Aakanksha Chowdhery, Clément Crepy, Shachi Dave, Mostafa Dehghani, Sunipa Dev, Jacob Devlin, Mark Díaz, Nan Du, Ethan Dyer, Vlad Feinberg. Fangxiaoyu Feng, Vlad Fienber, Markus Freitag, Xavier Garcia, Sebastian Gehrmann, Lucas Gonzalez, Guy Gur-Ari, Steven Hand, Hadi Hashemi, Le Hou, Joshua Howland, Andrea Hu, Jeffrey Hui. Jeremy Hurwitz, Michael Isard, Abe Ittycheriah, Matthew Jagielski, Wenhao Jia, Kathleen Kenealy, Maxim Krikun, Sneha Kudugunta, Chang Lan, Katherine Lee, Benjamin Lee, Eric Li, Music Li, Wei Li, YaGuang Li, Jian Li, Hyeontaek Lim, Hanzhao Lin, Zhongtao Liu, Frederick Liu, Marcello Maggioni, Aroma Mahendru, Joshua Maynez, Vedant Misra, Maysam Moussalem, Zachary Nado. John Nham, Eric Ni, Andrew Nystrom, Alicia Parrish, Marie Pellat, Martin Polacek, Alex Polozov, Reiner Pope, Siyuan Qiao, Emily Reif, Bryan Richter, Parker Riley, Alex Castro Ros, Aurko Roy, Brennan Saeta, Rajkumar Samuel, Renee Shelby, Ambrose Slone, Daniel Smilkov, David R. So, Daniel Sohn, Simon Tokumine, Dasha Valter, Vijay Vasudevan, Kiran Vodrahalli, Xuezhi Wang. Pidong Wang. Zirui Wang, Tao Wang, John Wieting, Yuhuai Wu, Kelvin Xu, Yunhan Xu. Linting Xue, Pengcheng Yin, Jiahui Yu, Qiao Zhang, Steven Zheng, Ce Zheng, Weikang Zhou, Denny Zhou, Slav Petrov, and Yonghui Wu. Palm 2 technical report. arXiv preprint arXiv:2305. 10403, 2023.
[3] Anthropic. Claude 2023.
[4] Anthropic. Introducing the next generation of claude. 2024.
[5] Leonardo Bertolazzi, Davide Mazzaccara, Filippo Merlo, and Raffaella Berardi. Chatgpt's information seeking strategy: Insights from the 20-questions game. In Proceedings of the 16th International Natural Language Generation Conference, pages 153-162, 2023,
[6] Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Michal Podstawski, Hubert Niewiadomski, Piotr Nyczyk, et al. Graph of thoughts: Solving elaborate problems with large language models. arXiv preprint UrXiv:2308.09681 2023.
[7] Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronek. Monte-carlo tree search: A new framework for game ai. In Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, volume 4, pages 216-217, 2008
[8] Cheng-Hap Chiang and Hung-yi Lee. Can large language models be an alternative human evaluations? arXiv preprint arXiv:2305.01937, 2023.
[9] Cohere. Cohere for ai, 2023.
[10] Gautier Dagan, Frank Keller, and Alex Lascarides. Dynamic planning with Ilm. arXiv preprint arXiv:2308.0639) 2023.
[11] Yihe Deng, Weitong Zhang, Zixiang Chen, and Quanquan Gu. Rephrase and respond: Let large language models ask better questions for themselves. arXiv preprint arXiv:2311.04205. 2023.
11

---

[12] Xidong Feng, Ziyu Wan, Muning Wen, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero- like tree-search can guide large language model decoding and training. arXiv preprint arXiv:2309.77I1 2023.
[13] Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong. Zhen Wang, Daisy Zhe Wang, and Zhit- ing Hu. Reasoning with language model planning with world model. arXiv preprini arOiv:2305. 14992, 2023.
[14] Martin N Hebart, Adam H Dickter, Alexis Kidder, Wan Y Kwok, Anna Corriveau, Caitlin Van Wicklin, and Chris Baker. Things: database of 1,854 object concepts and more than 26,000 naturalistic object images. PloS one, 14(10):a023372,, 2019.
[15] Ziniu Hu, Ahmet Iscen, Chen Sun, Kai-Wei Chang, Yizhou Sun, David A Ross, Cordelia Schmid, and Alireza Fathi. Avis: Autonomous visual information seeking with large language model agent. In Thirty-seventh Conference on Neural Information Processing Systems, 2023,
[16] Yubin Kim, Chanwoo Park. Hyewon Jeong, Yik Siu Chan, Xuhai Xu, Daniel McDuff, Cynthia Breazeal, and Hae Won Park. Adaptive collaboration strategy for Ilms in medical decision making. arXiv preprint arXiv:2404. 2024.
[17] Shuyue Stella Li, Vidhisha Balachandran, Shangbin Feng, Jonathan Ilgen, Emma Pierson, Pang Wei Koh, and Yulia Tsvetkov. Mediq: Question-asking Ilms for adaptive and reliable medical reasoning. arXiv preprint arXiv:2406.00992 2024.
[18] Bo Liu, Yuqian Jiang, Xiaohan Zhang, Qiang Liu, Shiqi Zhang, Joydeep Biswas, and Peter Stone. Llm+ p: Empowering large language models with optimal planning proficiency. arXiv preprint arXiv 11477, 2023.
[19] Wenge Liu, Jianheng Tang, Yi Cheng, Wenjie Li, Yefeng Zheng, and Xiaodan Liang. Meddg: entity-centti medical consultation dataset for entity- aware medical dialogue generation. In CCF International Conference on Natural Language Processing and Chinese Computing, pages 447-459. Springer, 2022.
[20] Yang Liu, Dan Iter, Yichong Xu, Shuohang Wang, Ruochen Xu, and Chenguang Zhu. G- eval: Nig evaluation using gpt-4 with better human alignment, may 2023. arXiv preprint arXiv:2303. 16634.
[21] Mistral.AI. Mistral large, our new flagship model. 2024.
[22] David Noever and Forrest McKee. Chatbots as problem solvers: Playing twenty questions with role reversals. arXiv preprint arXiv:2301.01743, 2023.
[23] OpenAl. Gpt-3.5 turbo: A high-performance language model, 2023. Whitepaper.
[24] OpenAl. Gpt-4 technical report. arXiv preprint arXiv:2303.08774 2023.
[25] Haojie Pan, Zepeng Zhai. Hao Yuan, Yaojia Lv, Ruiji Fu, Ming Liu, Zhongyuan Wang, and Bing Qin. Kwaiagents: Generalized cooommttion-sckinng agent system with large language models. arXiv preprint arXiv:23/2.04880 2023.
[26] Joon Sung Park, Joseph O' O'Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Generative agents: Interactive simulacra of human behavior. In Proceed- ings of the 36th Annual ACM Symposium on User Interface Software and Technology, pages 1-22, 2023.
[27] Dinesh Raghu, Shantanu Agarwal, Sachindra Joshi, and Mausam. End-to-end learning of flowchart grounded task-oriented dialogs. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 4348-4366, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.
[28] Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean- baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schritwieesr,, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context, arXiv preprint 2xXiv:2403.055500 2024.
12

---

[29] Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3):379-422 1948.
[30] Noah Shinn, Beck Labash, and Ashwin Gopinath. Reflexion: an autonomous agent with dynamic memory and self-reflection. arXiv preprint arXiv:2303. 11003,1136,. 2023.
[31] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprini arXiv:2206.04660 2022.
[32] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288 2023.
[33] Lei Wang, Wanyu Xu, Yihuai Lan, Zhiqiang Hu, Yunshi I Lan, Roy Ka-Wei Lee, and Ee-Peng Lim. Plan-and-solve prompting: Improving zero-shot ohain-hf reasoning by large language models. arXiv preprint urXiv:2305.0444 2023.
[34] Xuezhi Wang. Jason Wei, Dale Schaurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistnncy improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11177 2022.
[35] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances Neural Information Processing Systems, 35:24824-24837, 2022.
[36] Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al. The rise and potential of large language model based agents: A survey. arXiv preprint arXiv:2309.07888 2023.
[37] Lin Xu, Qixian Zhou, Ke Gong, Xiaodan Liang. Jianheng Tang, and Liang Lin. End-to-end knowledge-router relational dialogue system for automatic diagnosis. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 7346-766 -453,, 2019.
[38] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.10600
2023.
[39] Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting language models. arXiv preprint arXiv:2210.03629, 2022.
[40] Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models commonsense knowledge for large-scale task planning. arXiv preprint arXiv:2305. 14078, 2023.
[41] Andy Zhou, Kai Yan, Michal Shlapentokh-Roote Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning acting and planning in language models. arXiv preprint 130004406, 2023.
13

---

A Derivation of Information Gain Formula
Recall that the information gain at node u is defined as the expected change in uncertainty (or entropy) when receiving answer at this node, which defined as:
IGx :.. Hx( - p. H1 (X) - D HH (X)
(12)
We now show that: Proposition 1. The information gain at node is equal to:
(X) = - log p P log P
(13)
Proof. Note that for any outcome 24,, we have by the rules conditional probability:
p(a,11))) = p(xx|120) p(a,12p)
(14)
((22112)))
Now the information gain is:
(G.(X)
Ho(X) - ve HA(X) v.d (x
Σ p(x;112.) log p(r,(()))))
Ruw, E
P
Σ
(x,') log p( (22))
+ Pe
N
Σ
p
log
bwinny
Σ
p(z, (1og
logp(1;;{22)
Σ
(o,)(1,((2.),,
where the last equality holds by p p(z, that
(4) p(x,(R.). and similarly for p.y. We further compute
Σ
p(a (log log2(z:((2..)
Stor EA
p(x;1124) (244) Σ ((2;11221) log p(x,, (2,)
siw, EnA
Σ
(( log P.
-P- log Pa
Analogously the remaining term is -. log p.N. Finally we conclude that
IG. -p log P. logp."
(15)
In fact, this proposition can also be proven using some properties of information theory, particularly the definitions of conditional entropy and mutual information. As the more computational proof shown here is still relatively short and does not require defining certain additional probability distributions, provide the computational proof here instead.
14

---

B Comparison of Various Scaling Methods in Reward Function Design
We also consider multiple scaling schemes, including Logarithmic Transformation Scaling, Sigmoid Transformation Scaling and Piecewise Function Scaling. The results demonstrate that our current setting the optimal one. Additionally, our current design, particularly setting lambda > 0, is intended as straightforward method to incorporate our preference for a sharper reward, as it accelerates the decay of rewards as we move away from 0.5. Furthermore, is also intended to penalize questions that are too specific when the set of possibilities remains relatively large as 1 p will be large. We elaborate the scaling methods and their corresponding results below.
Vanilla Expected Information Gain (IG)
(X) = -Po log - pe log
(16)
Logarithmic Transformation Scaling (LTS), where
L(IG,(X)) log(1 + k (X))
(17)
log(1 k)
Sigmoid Transformation Scaling (STS), where 7 = 10 and 0.5
S(IG,(X)) 1 (
(18)
Piecewise Function Scaling (PFS), where À = 0.5
P(IG.(X))PP)
[GG(()
1G.(X) 1-1
Pp
if S if >>
(19)
p
Uncertainty-based Reward (UR)
R₂(w) = (X) = P log P. P. log P
(20)
X-1 pp P.
In particular, in this experiment, we 20Q-BIG-bench (introduced in 11.2 and Common dataset
instead of Thing dataset in 20 Question scenario. Datasets are the same as the main chapters in other scenarios.
Model
20Q-BIG-bench
Common
DX
MedDG
FloDial
IG
51.7
41.4
90.4
81.1
67.9
LTS
51.7
40.5
91.3
78.0
65.4
STS
51.3
35.1
89.4
82.3
63.4
PFS
37.9
36.9
89.4
81.3
67.1
UR
51.7
44.2
92.1
81.3
67.1
Table 3: Performance(Successuul Rate) comparison different reward methods based on GPT-3.5
C Comparison of Different Reward propagation Schemes
We also consider different reward propagation schemes and introduce their benefits as well as drawbacks.
Cumulative Reward Path Selection (CRPS): We used the strategy of calculating and comparing the cumulative reward for each path (from the root node to the leaf node), which involves multiplying the rewards of all nodes along the path and then selecting the path with the highest cumulative reward for the first question to interact with the user. This method focuses on identifying the single path that most likely to yield high reward. Its main limitation is that may rely too heavily on the performance of single path, neglecting the exploration of the overall problem space.
15

---

UoT-Max: Similar to the reward propagation scheme we are currently using, we considered adopting the approach of selecting the maximum reward among the children nodes (when the node questioner node) in the calculation of the expected reward. Opting for the maximum child node reward tends to pursue high rewards more aggressively, which may more effective in some situations but could also overlook the need for exploration, potentially not always being optimal in the long run.
(v) Py Re(v + pe Re( mddxwEChilree(() Rg (w)
if is leaf; otherwise: if is an Answerer Node
(c(v): =
if v is a Questioner Node
In particular, in this experiment, we use 20Q-BIG-bench (introduced in $1.2) and Common dataset
instead of Thing dataset in 20 Question scenario. Datasets are the same as the main chapters in other scenarios.
Models
Method
20Q-BIG-hench
Common
DX
MedDG
FloDial
CRPS
62.1
47.7
92.1
81.3
56.2
GPT-3.5
UoT-Max
48.3
41.4
92.1
80.3
60.1
UoT
65.5
62.2
92.1
83.3
63.2
CRPS
75.9
68.5
94.2
82.9
61.4
GPT-4
U-T-Max
79.3
63.7
95.1
83.1
62.6
UoT
79.3
71.2
97.0
88.0
67.3
Table 4: Performance (Success Rate) comparison of different reward propagation schemes. The results also demonstrate the superiority of our current reward propagation scheme.
Compared to the other two reward propagation schemes, the existing approach takes into account the cumulative rewards of all paths, providing more holistic and balanced decision maaiiinnmm mechanism. Instead of merely relying on the maximum short-term rewards or the performance of single path, it designed to capture long-term benefits, focusing on sustainable outcomes rather than immediate short-tens gains.
D Experimental Performance for Earlier Released LLMs
In these experiments, we use 20Q-BIG-bench (introduced in L and Common dataset instead of Thing dataset in 20 Question scenario. Datasets are the same as the main chapters in other scenarios.
Table 5: Results from three different scenarios, assessing Success Rate (SR), Mean Conversation Length Successful Cases (MSC), and Mean Conversation Length (MCL).
Questious
Medical Diagaosis
Troubleshoding FlaDial
Modd
Mathod
BIG-brnch
MedDG MSCJ
MSC| MCL]
MSCL
MCLJ
DP/OS)
Llum2: 700
DPCCS
17:2
13.5
18.9
6.31
12.0
19.7
29.8
4,6
3.5
26.2
14.5
18.7
LoT(CS)
20.7
13.2
18.6
10.8
15.6
19.5
51.9
3.4
33.9
1.4
31.4
15.8
18.7
DROS:
3.45
15.0
19.8
1.50
14.0
19.9
19.8
3.7
4.7
25.0
3.6
4.7
16.3
16.7
19.5
Cohere
DPCCS
6.30
12.0
19.4
1.50
12.5
19.8
35.6
3.3
4.4
33.3
4.0
4.7
27.5
16.3
19.0
CGT(CS)
34.3
8.50
16.0
16.2
11.7
18.6
45.5
2.6
3.9
75.7
2.7
3.3
41.4
8.7
15.3
35.1
14.4
7.69
4.0
Pa
13.0
4.4
DR(SS)
19.8
Gemini- Pr0
DPCSI
18.9
12.6
12.0
19.0
64.4
3.9
3.5
5,23
16.1
19.8
CoT(CS)
7.8
16.2
18.9
4,9
67.3
3.7
1.4
14.2
10.6
DROS:
46.3
9.8
15.1
20.7
13.8
18.2
45.2
3.0
4.1
60.7
4.1
4.5
39.7
14.3
17.7
Clande2
DRCS)
72.4
11.6
13.9
43.2
13.8
17.3
97.1
2.4
2.5
83.0
4.3
4.4
42.9
15.7
18.2
Lol
75.9
5.1
8.69
61.3
9.5
13.7
98.0
2.3
2.4
88.3
2.7
2.9
$2.6
6.3
12.8
DP/OS)
36.0
12.6
17.3
32.6
14.6
18.2
18.8
3.5
4.7
25.0
3.5
4.6
19.4
12.3
18.5
GPE33.
LoTrOS)
34.2
14.7
37.5
4.0
2.3
26.1
11.3
17.7
16

---

E Effect of Simulation Depth
In this experiment, use 20Q-BIG-bench (introduced in $1.2) and Common dataset instead of Thing dataset 20 Question scenario. Datasets are the same as main chapters in other scenarios.
As the below figure illustrates, we analyze the impact of simulation steps. Even with one-step reasoning and planning, our method can still have a strong performance, further indicating the effectiveness of our reward design and question selection mechanism. With the increase of the step, the performance can gradually rise. However, due to the constraints of computation resources and OpenAl API budgets, we only explore the simulation to the third step and argue that it can be the practical tradeoff between performance and efficiency.
95
92.5
90
86.7
85
82.6
Success Rate (%)
80
75.2
75
70
67
67.3
66.1
64.7
65
63.5
60
Depth
20 Questions
Medical Diagnosis
Troubleshooting
F
Reliability of GPT-4 as the Environment
As the impressive understanding ability of LLMs, previous research has validated the effectiveness
of evaluators served by ChatGPT GPT-4 [8] (20]. Consequently, we also adopt GPT-4 as the environment to provide feedback on our work. Prompts can be found in Appendix L.4] To assess the accuracy and reliability of employing GPT-4 as the environment simulator, randomly sample 10% interaction records (including the final judgment and intermediate feedback from the environment) from each dataset. As Figure 6 shows, GPT-4 can provide completely accurate judgment and also keep a high level of accurate feedback during the interaction. These experimental results can further support the effectiveness our method.
Table 6: Human evaluation results for the accuracy environment feedback served by GPT-4. IF represent the Accuracy of Intermediate Feedback.
Scenario
Judgement
IF
20 Questions
100
93.7
Medical Diagnosis
100
94.4
Troubleshooting
100
92.9
17

---

Uncertainty Reward Function R,(v) with 0.4
0.7
0.6
0.5
0.4
0.3
0.2
0.0
0.2
0.4
0.6
0.8
1.0
P
Figure 5: Curve uncertainty based reward on Eq 10 The horizontal axis p is conditional probabilities of affirmative node v, which are introduced in Section 2.4
where p can be replaced by (1- p:))
G Reward Function Details and Its Curve
Refer Figure for the curve of uncertainty- based reward function.
H Experimental Statistical Significance
We conduct three experiments on five datasets using Llama and GPT-4 to compare the performance of Direct Prompting (DP) and UoT methods in closed-set setting for significance testing. Due to LLM API quota limitations, the number of experiments are restricted. To determine whether the differences in success rates (SR) between the two methods were statistically significant, performed a I-test, The results are presented below.
GPT-4 Results
Table 7: GPT-4 Comparison of DP and UoT Success Rates (SR)
Dataset
DP (%)
UoT (%)
t-Statistic
p- P-Value
Significance Conclusion
Common
49.0
70.9
-10.8
0.00041
Significant (p < 0.05)
Thing
30.8
36.8
-8.04
0,00129
Significant (p < 0.05)
DX
89.4
97.0
-3.11
0.03581
Significant (p < 0.05)
MedDG
74.9
87.9
-7.33
0.00185
Significant (p < 0.05)
FloDial
42.5
67.8
-19.8
0.00004
Significant (p 0.05)
Llama 3 Results
Table 8: Llama 3 Comparison of DP and UoT Success Rates (SR)
Dataset
DP (%)
UoT (%)
t-Statistic
P-Value
Significance Conclusion
Common
47.7
56.5
-4.39
0.01180
Significant (p < 0.05)
Thing
14.8
24.8
-16.0
0.00009
Significant (p < 0.05)
DX
80.1
90.1
-4.65
0.00966
Significant (p 0.05)
MedDG
61.3
64.6
-4.15
0.01426
Significant (p < 0.05)
FloDial
29.9
46.4
-10.5
0.00047
Significant (p 0.05)
18

---

The t-test results indicate that UoT significantly outperform DP five datasets (p 0.05), evidenced by their higher mean scores.
I Experimental Setups
L11 Baselines Setup
Chain-of-Thooe Thought (CoT) We adapt the typical CoT prompt which instruct LLM to generate the explanation motivation for the proposed question first, then give the question to ask.
Chain of Thought with Self-Consistency (CoT-SC) To make the method spend comparable compute our approach for fair comparison, we sampled 33 times before deciding each action with the LLM's temperature of 0.7. The final selected question is the one repeated most times among 33 samples.
Planning Prompting To measure whether LLMs' planning ability can be enhanced through some crafted prompts like COT, ToT or Reflexion. We design the prompt to enable LLM to simulate multiple different sets of future interactions between questioner and answerer, then let L.L.M choose one most promising interaction (question) to ask.
Tree of Thoughts In the case of Original-ToT, a sampling method is employed generate questions from each answer node, and the self-evaluation method is utilized for reward calculation. Subsequently, breadth-first search will be used and 10 nodes from each step will be selected for later simulation. Additionally, the temperature of the LLM is configured to 0.7, consistent with the settings original ToT paper. In the case of Adapted-ToT, we provide more heuristical hints in prompt to generate the questions, e.g. "you should try to propose the question to halve the probability set'. Likewise, each answer node generates 3 questions, and the L.M selects 10 nodes with higher self-evaluation rewards to further simulation. The simulation steps are also 3.
Reflextion This approach involves the LLM agent suggesting questions iteratively until the question reward exceeds the threshold of 0.7 or reaches the maximum limit of 3 questions. The reward score is calculated using the formula principle of whether the question can effectively halve the probability set. If a candidate question achieves score above the threshold, the process of proposing questions is concluded, and that question is selected. In cases where no question meets the threshold, the one with the highest score is chosen.
min(pA, pp')/ ) max max(p" p This heuristic is based on the
Uncertainty of Thoughts Pruned After generating the candidate question based on the possibility set S2,, sorted these question nodes by uncertainty based reward and reserved half of them, serving the purpose of pruning. In subsequent steps of the simulation, this pruning operation will be continued. Other settings were the same as UoT, described in Section $
1.2 Scenarios Settings and Datasets
20 Questions game is classic guessing game where the answerer thinks of an object, person, place, or other, and the questioner, possessing no prior knowledge about the chosen entity, proceeds to pose series of up 20 yes-or-no questions to determine what the secret item is. The questions are designed to narrow the possibilities and ultimately guess the secret item within the 20 questions. 20 Questions in BIG-bench: is the sub-task of BIG-bench and can be found on the GitHub website consist of 29 items. Common Dataset Construction: We came across an official website B that introduces 20 Questions game, which mentions that common target categories in this game include animals, places, food, and objects. Therefore, we extracted and manually screened the targets mentioned on this website, resulting in dataset named "Common" comprising 111 1 targets, each belonging to one of the four aforementioned categories. Thing Dataset: It is collection of 1,854 varied object concepts, carefully selected from tangible and easily identifiable nouns in American English by Martin at al. [1]] which is publicly available on their official website")
http:///wwbboooeeeeooooommmme/mn https///sffio/jmm2
19

---

Medical Diagnosis In this scenario, the patient will simply describe their symptom first which we call 'Self-report', then doctor acted by LLM will start to ask questions to interact with patient to determine the disease.
Troubleshooting In FloDial dataset, trouble includes faults of car and laptop. Similar to Medical Diagnosis, the customer first describes some simple fault symptoms, then the customer support technician will chat with customer to further check the specific issues of device.
LLMs Serve as Questioner (Patient or Customer) In simulated interactions involving questioner and answerer scenarios, particularly for medical diagnosis and troubleshooting, the response given by an LLM acting answerer is guided by scenario instructions and real-world dialogue examples. This approach makes the responses of answerer more human-like like and enhances its accuracy in diagnosing diseases or identifying faults. While, in the game of 20-question, where the objective is to guess common items, the LLM acting the answerer only needs to provide simple 'yes' 'no' answers. Therefore, incorporating real-world dialogue into the LLM's prompts for this game is not necessary.
I.3 Dataset selection criteria and process for MedDG
In the original MedDG dataset, numerous conversations lacked a clear diagnosis, often concluding with advice for the patient to rest or seek further tests. This ambiguity arose from patients not detailing their symptoms sufficiently or doctors lacking the information or confidence diagnose. Consequently, these conversations hinder LLMs from accurately understanding disease and symptom information for effective patient role simulation. To address this, we curated our final evaluation set to include only conversations with explicit disease diagnoses.
Furthermore, to ensure a balanced representation across the 8 disease categories, we selected roughly 40 dialogues for each disease. We also excluded conversations that were too brief (1-2 turns) or excessively lengthy (over 10 turns). The curation process involved annotators: one for initial selection and another for verification.
Given these criteria, we finally pick 500 conversations for evaluation set, aiming to maintain the ovaluation's 's reliability and quality. We will also clarify this and add the details into the following version.
1.4 Data Preprocessing of FloDial
We process the dataset, FloDial, to convert troubleshooting flowcharts into a set of troubleshooting faults. The dialogue is grounded in specific faults, which correspond to the leaf nodes (descriptions and solutions of faults) in the flowcharts. After reviewing all the leaf nodes, we identify 153 faults that had corresponding dialogues. We then use GPT-4 to generate clear name for each fault based on the descriptions and solutions of faults, and randomly selected one corresponding dialogue history to construct the current dataset.
1.5 UoT (Open Set) Setup
To initialize the possibility set as the start of the algorithm, in medical diagnosis and troubleshooting. initial descriptions from patients or customers about symptoms or issues enable UoT to establish a possibility set right from the start. For the game of 20 Questions, where initial information is scant, prematurely establishing this set could misdirect the inquiry. Therefore, for the first three rounds, we employ Direct Prompting in Open-Set (DPOS) approach to gather information and feedback. After these initial rounds, UoT takes over, refreshing the possibility set each round to refine the questioning strategy.
For datasets Common, Things, DX, MedDG and FloDial, we configure the size of the possibility set for each update round, setting them at 10, 10, 5, 5, and 5, respectively. This parameter should prevent the increase in cognitive load and decrease in efficiency that comes with larger sizes, while also avoiding the limitations of focusing on a few specific items that come with smaller sizes. We experiments with values(size) between 5 and 50 based on this rationale, and the final selection of these hyperparameters is guided by empirical performance evaluations.
20

---

No. 1.6 Implementation
Empirically, we set the plan (simulation) steps as and the number of questions during the simulation is 3. The hyperparameter À in aucertainty-basee reward is 0.4.
J Impact Statement
This paper aims to enhance LLMs' information seeking abilities, allowing them make better decisions in challenging real-world settings involving uncertainty and ambiguity, and to interact more effectively with humans human-AI settings. On the whole, we expect that information seeking capabilities should allow models to behave in manner that is more reliable and well-aligned with human expectations, as it allows them to better resolve their uncertainty. There may be some potential societal consequences related to LLMs in general, such privacy and trustworthiness issues. However, we do not believe that any of these must be specifically highlighted here.
K Examples in Scenarios
Some examples of conversation in different scenarios are provided in Table 12
Table 9: Example for 20 Question. Q stands for Questioner and A stands for Answerer.
Target: Glass micropipette
Conversation
1: Q: Is X a tangible object?
A: Yes.
2: Q:
living organism?
3: Q: Is X household item?
A: No.
4: Q: X a type of transportation?
A: No.
5: Q: Is X used in construction?
A: No.
6: Q: Is X a wearable item?
A: No.
7: Q: Is X type of toy?
A: No.
8: Q: Is X a 'Glass micropipette'?
A: You guessed it. X is "Glass micropipette'.
Table 10: Example for Medical Diagnosis. D stands for Doctor (Questioner) and P stands for Patient (P).
Disease:
Allergic rhinitis
Self-report
Hello doctor, my son's throat easily becomes red and swollen been coughing and his throat has been red and swollen for the past half month. Conversation
winter comes. He has
I: D: Do you experience runny stuffy nose? P: Yes.
You may have 'Allergic rhinitis'.
Table 11: Example for MedDG. D stands for Doctor (Questioner) and P stands for Patient (Answerer).
Disease: Gastric ulcer
Self-report
Stomachache. Pain in the upper abdominal area. No diarrhea. (Female, 27 years old) Conversation
1: D: Do you experience a burning or gnawing sensation in your stomach, especially on empty stomach?
P: Yes. I do have this sensation, especially on an empty stomach.
2: D: Have you noticed any dark, tarry stools or vomit that looks like coffee grounds?
P: I haven't tt noticed the color of my stool, but haven't vomited.
3: D: You may have "Gastric ulcer'.
21

---

Table 12: Example for Troubleshooting. stands for customer support technician and C stands for customer.
Fault:
Brake fluid overflow
Self-report
Lately, have been having trouble with the brakes of my car. have checked it again and again but can't ton't figure out what's 's causing this. Please help me.
Conversation
2: T: Does the issue affect the rotation or movement of the wheels?
C: No.
3: T: Does the issue seem be related to the overall braking system?
C: Yes.
4: T: Are you experiencing a brake fluid leak?
C: No.
5: T: Are your brake pads worn out?
C: No.
6: T: Is the brake pedal feeling spongy or soft when you press it?
C: Yes.
7: T: Is there issue with the brake lines being air-filled or damaged?
C: No.
8: T: Your car may have a brake fluid overflow issue.
L Prompts
L.1 DP(OS) and DP(CS) Prompt
The specific prompts for the DP(OS) and DP(CS) baselines in each scenario are provided in Table
B 15
Table 13: DPOS and DPCS Prompt for 20 Question game. The two settings are the same except for the content noted in red, which is only for DPCS Prompt. The first time the content marked in red is mentioned at the beginning of interaction to inform the questioner of the entire probability set. The second mention serves as reminder for the questioner determine the target as soon possible when the conversation is nearing its end. We establish two phases with the aim of encouraging the questioner to guess the target as soon possible when the second phase of interaction is nearing its conclusion, in order to avoid failure at the end of interaction.
Prologue
Let play the game of 20 questions. am impersonating the thing, X. You will ask me up to 20 questions that start with 'Is X' and can only be answered by yes or no, and will answer each one truthfully based on being X.
Let us begin. Ask me the first question. Reply to me with your first question.
The X may one of the items below: [list of items]
Phase Q13))
None
Phase (Q14- Q20)
The X may be one of the items below: [list of items]
L.2
Planning Prompt
The specific prompts for Planning Prompt baselines in each scenario are provided in Table 27 As planning prompt method is close set setting, hence the probability set will also be informed in the prompt as DPCS prompt. We not repeat tables.
L.3
UoT Prompt
The detailed prompts for our UoT method in each scenario are attached in Table 21
L.4 Questioner Prompt
The specific prompt to guide the examiner in all scenarios is provided in Table 22 24
22

---

Table 14: DPOS and DPCS medical diagnostic prompts with similar structures. The key difference the inclusion of probability set information in red text for DPCS. This red text appears twice: initially to inform the questioner about all potential diagnoses and again towards the end of the interaction as a reminder to quickly confirm the disease. We establish two phases with the aim of encouraging the questioner confirm the disease as soon as possible when the second phase of interaction is nearing its conclusion, avoiding failure at the end of interaction.
Prologue
You are a doctor and your patient reports that: [self-report]
You should ask your patient questions in English with symptoms which can only be answered by yes or no, find what discase this patient suffers.
Let us begin, Ask me the first question.
Based on the symptoms above, if you find out the disease, please ask Are you a [disease name]?"
The patient may suffer from one of the diseases below: [list of diseases)
Phase (Q1)
None
Phase (Q3 Q5)
Based the symptoms above, if you find out the disease, please ask 'Are you a [disease
name]?'
The patient may suffer from one of the diseases below: [list of diseases]
Table 15: DPOS and DPCS troubleshooting prompts with similar structures, but DPCS includes unique content highlighted red. This red content appears first at the beginning, outlining all potential faults, and again towards the end reminder swiftly identify the fault. The two-phase structure of these prompts aims to ensure quick fault confirmation, especially in the final stages of the interaction, to prevent failure.
Prologue
You are a technician and your client reports that: [self-report]
You should ask your client questions about specific situation which can only be answered by yes or no, in order to find where the issue this client faces with located.
Let begin. Ask the first question.
The client may face one of the issues below:
list of issues
Phase (Q1-Q13
None
Phase (Q14 Q20)
Based on the situations above, if you find out the issue, please ask 'Are you a fissue name]?'
The client may face one of the issues below: [list of issues]
23

---

Table 16: Planning Prompt for 20 Question game. [CI] is the count of questions asked and [C2] is the count of questions remaining. The 'information gained' marked blue represents the previous interaction history. We divide it into three phases to discuss the probability set as quickly as possible, conduct simulation for planning, and remind the questioner to guess the answer.
Prologue
Same as prompts in Appendix L.
Phase (QI Q4)
The next question should narrow down the possible range of X. preferably in half.
Phase (Q5 Q15)
We are playing the 20 Question game, [C1] questions have been asked. And now we know:
[information gained]
Based on the features of X above, please guess what X exactly is and tell me your top 3 most likely answers. For these three candidate X, please separately complete the remaining [C2] questions and answer yes/no by yourself. Notably, you must guess the corresponding before the last question.
Phase (Q16 Q20)
Note that you should guess what X exactly is from now on. The question must start with Is X
Table 17: Planning Prompt for Medical Diagnosis. [CI] is the count of questions asked and [C2] the count of questions remaining. The 'information gained" marked blue represents the previous interaction history. We divide it into three phases to discuss the probability set quickly possible, conduct simulation for planning, and remind the questioner to confirm the disease.
Prologue
Same prompts in Appendix I.1
Phase 1
Skip because of the limited QA rounds in this scenario
Phase 2 (Q1 Q3)
You are the doctor asking questions to diagnose, [C1] questions have been asked. And now know about the patient:
[information gained]
Based on the symptoms of the patient above, please think about what disease the patient suffers from and tell me your top three most likely answers.
For these three candidate diseases, please separately complete the remaining (C2) questions and answer yes/no by yourself. Notably, you must determine the corresponding disease before the last question.
Phase 3 (Q4 Q5)
Note that you should determine what disease the patient suffers from now. The question start with Are you [disease name]?'
24

---

Table 18: Planning Prompt for Troubleshooting. [CI] is the count of questions asked and [C2] is the count of questions remaining. The 'information gained' marked blue represents the previous interaction history. We divide into three phases to discuss the probability set as quickly as possible, conduct simulation for planning, and remind the questioner to confirm the fault.
Prologue
Same prompis in Appendix L.1
Phase I [Q1 Q4)
The next question should narrow down the possible range of trouble issues, preferably in half
Phase 2 (Q5- - Q15)
You are technician troubleshoot, [CI questions have been asked. And now we know:
[information gained]
Based on the situation your client faces, please think about what the issue exactly is and tell me your top most likely answers.
For these three candidate issues, please separately complete the remaining [C2] questions and answer yes/no by yourself. Notably, you must determine the corresponding issue before the last question.
Phase 3 (Q16 Q20)
Note that you should determine what issue your client faces from The question
must start with Are you lissue name]?'
Table 19: UoT Prompt for the 20 Questions Game:
As is based on closed-set setting, information about probabilities will be given at the beginning of the interaction and will be reminded after Q14. Since is similar to previous prompts, we will not repeat here. In the "Prompt for Question Generation and Simulation', the count of YES/NO indicates the number of items that are consistent with the affirmatieeneegative response.
Prologue
Let us play the game of 20 questions. am impersonating the thing, X. You will ask me up 20 questions that start with 'Is X' and only be answered by yes no, and will answer each one truthfully based on being X.
Let begin. Ask the first question. Reply to me with your first question.
Prompt for Question Generation and Simulation
Please design a question about X and can only be answered by YES or NO. asked Then classify the possible X above based on this question. If the answer is 'YES', put this X into 'YES: ...', otherwise to 'NO: Finally calculate how many X in YES and NO.
Notably, this question should fulfill that the count of YES and NO are almost the same with permissible discrepancy of no more than one!
You should think about best questions to respond to. And your answer should be: Question 1: Is X ...?
YES: iteml, item2.
Count of YES:
NO: iteml, item2.
Count of NO:
Additional Reminder in Q14 - Q20
Note that you should guess and ask what X exactly is from now X is possible litem list str], or other. The question must start with 'Is X
25

---

Table 20: UoT Prompt for medical diagnosis: As it is based on closed-set setting, information about probabilities will given at the beginning of the interaction and will be reminded after Q3. Since is similar to previous prompts, we will not repeat it here. In the Prrompt for Question Generation and Simulation', the count of YES/NO indicates the number of diseases that are consistent with the affirmative/negative response.
Prologue
You are a doctor and your patient reports that: [self-report]
You should ask your patient questions in English with symptoms which can only be answered by yes or no, to find what disease this patient suffers.
Let begin. Ask the first question.
Prompt for Question Generation and Simulation
Please design a question to ask your patient with symptoms about disease and can only answered by YES or NO. Then classify the possible disease above based on each question. If the answer 'YES', put this disease into 'YES: ...', otherwise to 'NO: ...'. Finally calculate how many X in YES and NO.
Notably, this question should fulfill that the count of YES and NO are almost the same with permissible discrepancy of no more than one!
You should think about best n questions to respond to. And your answer should be: Question I:..?
YES: diseasel, disease2, ... (disease names only)
Count of YES:
NO: diseasel, discase2, discaee,,
(disease names only)
Count of NO:
Additional Reminder in Q3- Q5
Note that you should point out and ask what disease the patient suffers from now. The patient may suffer from one of diseases below: [list disease], or other. The question must be You may have [disease name]?'
26

---

Table 21: UoT Prompt for troubleshooting: As is based on a closed-set setting, information about probabilities will be given at the beginning the interaction and will be reminded after Q14. Since is similar to previous prompts, we will not repeat it here. In the Prrompt for Question Generation and Simulation', the count of YES/NO indicates the number of faults which are consistent with the affirmatie/negativee response.
Prologue
You are a technician and your client reports that: [self-report] You should ask your client questions about specific situation which can only be answered by yes or no, order find where the issue this client faces with located. Let begin. Ask me the first question.
Prompt for Question Generation and Simulation
Please design question ask your client with specific situation and can only be answered by YES or NO. asked Then classify the possible issue above based on this question. If the answer is YES', put this issue into 'YES: otherwise 'NO: Finally calculate how many issues in YES and NO.
Notably, this question should fulfill that the count of YES and NO are almost the same with permissible discrepancy of no more than one!
You should think about best n questions to respond to. And your answer should be: Question 1: !...?
YES: issuel, issue2, (issue names only)
Count of YES: ...
NO: issuel, issue2, (issue names only)
Count of NO:
Additional Reminder in Q14 Q20
Note that you should point and ask what disease the patient suffers from now. The patient may suffer from one of diseases below: [list of disease]. or other. The question must be You may have [disease name]?'
Table 22: Prompt for Answerer in 20 questions game. [target] is the name of the final target for each dialogue.
Prologue
Let us play the game of questions. You are the answerer and am the guesser. X "[target]'. I will ask you up to 20 questions and you should answer each one truthfully based on being If guess correctly what is X, answer me "You guessed "[target]""" Note that never directly tell me what X is all the time. Let us begin. Here my first question.
Table 23: Prompt for Answerer in medical diagnosis. [disease] is the name of the final disease for each dialogue.
Prologue
You are the patient suffering '[target]' and I am the doctor. will ask you up to 5 questions and you should answer each one truthfully based your disease. If point out correctly what disease you experience, answer me "You are right. am experiencing "[target]'. Note that never directly tell me what disease is all the time. Let us begin. Here is my first question.
Table 24: Answerer Prompt in troubleshooting, [fault] is the name of the final fault for each dialogue.
Prologue
You are the client with device that has '[targe]]' and am the technician. will ask you up to 20 questions and you should answer each one truthfully based on the issue your device. If point out correctly what your issue is, answer me "You are right. My device has "[target]'." Note that never directly tell me what the issue all the time. Let us begin. Here is my first question.
27

---

Table 25: ToT Prompt for 20 Question game. [C1] the count of questions asked. The 'information gained' marked blue represents the previous interaction history.
Standard Prompt
You are playing the game of 20 questions. am impersonating the thing, X. You will ask
me up to 20 questions that start with 'Is X' and can only be answered by yes or no, and will answer each one truthfully based on being X.
[CI] questions have been asked. And now we know:
[information gained]
Design question about X and only be answer by YES or NO.
Additional Reminder in Q14 Q20
Same as prompts Appendix
Table 26: ToT Prompt for Medical Diagnosis. [CI] is the count of questions asked. The 'information gained' marked blue represents the previous interaction history.
Standard Prompt
You are a doctor and your patient reports that: [self-report]
You should ask your patient questions English with symptoms which can only be answered by yes or no, to find what disease this patient suffers.
[C1] questions have been asked. And now we know:
jinformation gained]
Design a question to ask your patient with symptoms about disease and can only be answered by YES or NO.
Additional Reminder in Q14 Q20
Same as prompts in Appendix L.3
Table 27: ToT prompt for Troubleshooting. [C1] is the count of questions asked. The 'information gained' marked blue represents the previous interaction history.
Standard Prompt
You are technician and your client reports that: [self-report]
You should ask your client questions about a specific situation which can only be answered
by yes or no, in order to find where the issue this client faces with located.
[C1] questions have been asked. And now we know:
[information gained]
Design question to ask your client with specific situation and only be answered by
YES or NO.
Additional Reminder in Q14 Q20
Same prompts in Appendix L.3
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
28

---

Table 28: CoT Prompts.
Prologue
Same as prompts in Appendix|_1
Prompt for Generating Question and Explanation
What's s your next question? Let's think step-by-step and reply me with your explanation.
Your answer should be:
Explanation: [insert step-by-step analysis here]
Question: [next question]
Additional Reminder in Q14 Q20
Same as prompts in Appendix L.3
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer [[No] provided proper justifictiin is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either in the main paper or supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification:
As shown in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
As shown in the appendix ??.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification:
As shown in the appendix A
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced
statement of any theorems. The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
As shown in the experiment and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
30

---

Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibilitty In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code and data for this paper can be accessed through https:///ithhu com/zhiiyuae yuw.huuuuuannbuu//uuuo
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines btetps://nips.co.
ssioonicccynnssoo for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssionooiccy for more details. //wpss.c/ppublll wttp://cccc..guuueee////////ce// wwtpi///guissseCeooo Caaeeee/oooSSSemmieeeeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
31

---

Answer: [Yes]
Justification:
As shown in the experiments and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
As shown in the experimental results and analysis part.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
As shown in the Analysis section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
32

---

Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https/is.ttssse.op..p..ooooo///a
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
As shown in the appendix J
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
33

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The creators original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswithcode com /dttasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
The code and data for this paper can be accessed through
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
34

---

The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation,
or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/teview based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "QDbmCrhkT8", "reviewer": "Reviewer_Ho3e", "summary": "This paper presents an approach known as “uncertainty of thoughts (UoT)”, which builds upon related ideas of creating a tree of responses to answer a question, such as the “tree of thoughts” and related approaches. The key components of the system include 1) an approach to ask different types of questions and simulate yes/no sorts of answers, 2) uncertainty-based rewards that are somewhat motivated by information gain as measured by change in expected entropy, and 3) a reward propagation approach that computes sum of expected rewards. These combine to result in an approach where the system chooses a question from a set of questions until termination (which I did not fully understand). Experiments are conducted on benchmarks such as 20 Questions and Medical Diagnosis, and results generally seem favorable as compared to some baselines.", "questions": "Some questions and comments follow:\n\nIs there ever a situation where the probabilities for each remaining possibility are non-uniform? If so, please explain how these probabilities are obtained. From what I understood, only the possibility set is reduced over iterations.\n\nIs the output of the LLM in equation (1) obtained from a single inference query or multiple queries? If a single inference query, how does one ensure a variety of questions?\n\nThe output of the LLM in equation (2) seems problematic for open set case. Can you please explain how this is handled for open set?\n\nWhy does the modified reward in equation (10) work better empirically?\n\nFor the expected reward, why are downstream questions taken to be equally likely? I thought questions were decisions. If so, why is the max operator not used on those? Also, what is the meaning of the sum of the rewards in this situation? Why is this a suitable measure of reward? I believe the normalization nullifies the fact that each reward was originally a measure of information gain.", "limitations": "Much more discussion about limitations is needed.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "As per my understanding, the paper presents some novel ideas around using information gain to sequence questions using LLMs. I consider this a strength, but I did not see any description of how and when non-uniform probabilities are obtained for any set of remaining possibilities in the possibility space. The results also appear to be positive, from what I could understand.", "weaknesses": "I could not fully understand some important details in the paper. For instance, the open set case seems important but was not covered in sufficient detail in the paper. \n\nI found many choices to be somewhat ad-hoc and without any clear basis. For instance, the choice of reward (after some sort of normalization) and the accumulation of rewards (that are all between 0 and 1) did not make sense to me. I think some choices make the work less principled, which affects the soundness of the work in my view.\n\nFurther details about my concerns are provided later in the section on Questions. \n\nI am open to adjusting my score during the discussion period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your insightful feedback. Below, we provide clarifications to address the concerns, which we will incorporate in next version.\n\n> Q1: The open set case seems important but was not covered in sufficient detail in the paper.\n\nSorry for any confusion. We explain the open set setup in sections 3.1 and Appendix I.4. Here's a detailed explanation.\n\nIn the closed set setting, our algorithm starts with a known possibility space $\\Omega$. However, in the open set setting, we do not assume such a known $\\Omega$. Instead, we generate $\\Omega$ at the start of each conversation round (before UoT generates its questions), by prompting an LLM to generate a set of possibilities which are consistent with the current conversation history. Having generated $\\Omega$, the rest of UoT proceeds exactly the same as in the closed set case to generate questions in each conversation round.\n\nSpecifically, in the medical diagnosis and troubleshooting cases, since we have the initial symptom and issue descriptions available at the start, we use these to generate an initial possibility space. In each subsequent round, UoT refines the possibility space based on the current conversation history. In 20 Questions, since such initial descriptions are not available, we instead use Direct Prompting in Open-Set for the first three rounds. Afterward, UoT refines the possibility set each round.\n\nFor the datasets Common, Things, DX, MedDG, and FloDial, we configure the size of the possibility set for each update round, setting them at 10, 10, 5, 5, and 5, respectively. This approach helps prevent the cognitive load increase and efficiency decrease associated with larger sizes while avoiding the limitations of focusing on too few items with smaller sizes. We experimented with sizes between 5 and 50 based on this rationale, and the final selection of these hyperparameters is guided by empirical performance evaluations.\n\n>  Q2: Some choices seem ad-hoc, like normalized rewards. Why not use the max operator? What does the sum of rewards represent? Why does the modified reward in equation (10) work better?\n\n**Meaning of Accumulated Reward**\n\nAccumulated reward is essential for considering long-term effects in dynamic environments, rather than just immediate effects. By summing the rewards of a node $v$ and all its ancestor nodes, we reflect the effectiveness of past decisions, evaluating the total reward along the entire conversation path leading to a leaf node. The cumulative reward at a leaf node represents the total reward at the end of the conversation.\n\nFor instance, in a 3-step conversation, the immediate reward function $R_u(v)$ captures the information gained from receiving the answer at node $v$. However, the total information gained by the end of the conversation is the sum of the information acquired over the three rounds. Therefore, we accumulate the immediate rewards  $R_u(v)$ of a leaf node and its parent nodes to compute the accumulated reward, thereby accounting for the information gained across multiple rounds of the conversation.\n\n**Necessity of Normalization**\n\nNormalization ensures that reward values remain within a reasonable range during calculations, preventing extremely large or small values from skewing results. While normalization might affect the measurement of the original information gain, it ensures comparability of different rewards and stabilizes cumulative calculations. It's true that normalization can affect the measurement of original rewards (like information gain). However, the goal of normalization is to make rewards from different ranges comparable and to prevent certain rewards from disproportionately affecting the total. Choosing an appropriate normalization factor ensures that different types of questions or answers have reasonable weights in the calculations.\n\n**Why Downstream Problems are Considered Equally Likely**\n\nDownstream problems are considered equally likely to simplify calculations and ensure fair treatment of all potential questions in the absence of prior knowledge. This assumption allows the model to remain unbiased towards any specific question during calculations. In practice, other choices such as a \"damping coefficient\" which exponentially down weights each later round could also be used, based on our prior or application-specific knowledge.\n\n**Why Not Use the Max Operator**\n\nUsing the max operator is also a reasonable approach, which assigns rewards based on the most favorable downstream outcome. Our approach of using the expected value instead can be considered as a more \"risk-averse\" approach which considers all downstream outcomes as possible scenarios. This risk-averse approach is justified due to the high unpredictability and difficulty in predicting conversation outcomes.\n\n**Meaning of the sum of the rewards**\n\nAs discussed in “Meaning of Accumulated Reward,” the UoT uses the sum of rewards to guide question selection, balancing immediate and long-term benefits. Accumulated rewards indicate total uncertainty reduction, while expected rewards consider future gains, ensuring decisions that enhance task performance by reducing uncertainty across interactions.\n\n**Why does the modified reward in equation (10) work better empirically**\n\nOur modified reward design in equation (10), particularly setting lambda > 0, is intended as a straightforward method to incorporate our preference for a sharper reward, as it accelerates the decay of rewards as we move away from 0.5. Furthermore, it is also intended to penalize questions that are too specific when the set of possibilities remains relatively large as $|p_v^A - p_v^N|$ will be large. Meanwhile, there are alternative approaches to achieving this such as Logarithmic Transformation Scaling, Sigmoid Transformation Scaling and Piecewise Function Scaling. We provide the comparison results in Appendix B and the results show that our current setting provides better results, leading to our decision to use it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oyTPhK0pcw", "reviewer": "Reviewer_moAn", "summary": "The paper introduces Uncertainty of Thoughts (UoT), aimed at enhancing the ability of large language models (LLMs) to actively seek information by asking effective questions. UoT integrates an uncertainty-aware simulation method, uncertainty-based rewards motivated by information gain, and a reward propagation scheme to optimize question selection. The primary innovation lies in the model’s capability to project possible future scenarios and choose questions that maximize expected rewards, thereby efficiently gathering necessary information. This methodology has been shown to improve the performance of multiple LLMs in tasks such as medical diagnosis, troubleshooting, and playing the ‘20 Questions’ game.", "questions": "1. Could you provide some analysis of why there is a notable performance decrease between the baseline models (CoT and ToT) and direct prompting?\n2. How is information gain computed in the open-ended answers setting?", "limitations": "The limitations are described.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea of combining uncertainty-aware simulations with a reward-based system to guide LLMs in asking more effective questions is novel and interesting.\n2. The authors provide comprehensive experiments to validate their approach, comparing it against baseline models on three different tasks, which shows improvements in effectiveness.\n3. The paper is well-written and the problem formulation is mostly easy to follow.", "weaknesses": "1. Questionable Baseline Performance: There is a notable performance discrepancy between the baseline models (CoT and ToT) and direct prompting, especially in the 20 Questions task evaluated by GPT-4. Direct prompting achieves a 48.6% success rate in the open set, while CoT drops significantly to 13.5%. In the closed set, while direct prompting achieves 50.5%, CoT and ToT only reach 20.7% and 28.8% respectively. Such substantial decreases in performance warrant further investigation.\n\n2. Lack of Explanation: The paper lacks a detailed explanation of the prompts and setups used for CoT and ToT. Understanding why these methods underperform could be clarified through additional analysis and qualitative results.\n\n3. In the checklist, the author claimed yes to having the experimental statistical significance. But I did not see this in any table.\n\n4. Q: Did you consider the LLM’s own uncertainty? For example, the LLM proposed two questions but it could be more certain about one of the questions. In the paper, it seems that you considered each question to be equally possible when sampling.\n\n5. It is unclear to me how information gain is assessed in scenarios with open-ended responses. Did you still use the LLM to generate the output with the fixed template at the end so that you can apply the same evaluation framework as the closed set setting? Otherwise, how to know the reward?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your thorough review and insightful comments. Your feedback has encouraged us to refine and improve our work. We hope the clarifications below will adequately address the issues you mentioned.\n\n> Q1:  There's a significant performance gap between baseline models (CoT and ToT) and direct prompting in the 20 Questions task evaluated by GPT-4. Direct prompting achieves much higher success rates. The paper doesn't detail the prompts and setups for CoT and ToT, requiring further investigation to understand their underperformance.\n\nSorry for the missing of CoT and ToT's prompt in our paper. We use the standard idea of CoT and ToT (self reward). We provide the prompts here in a 20 question scenario here and will supplement the comprehensive prompts for all baseline methods in our final version.\n\n| CoT Prompts in 20 Questions |\n|---------------------------------------------------|\n| *Prologue*  |\n| Let us play the game of 20 questions. I am impersonating the thing, X. You will ask me up to 20 questions that start with ’Is X’ and can only be answered by yes or no, and I will answer each one truthfully based on being X. Let us begin. Ask me the first question. Reply to me with your first question. |\n| *Prompt for Generating Question and Explanation*|\n| What’s your next question? Let’s think step-by-step and reply me with your explanation.<br>Your answer should be:<br>Explanation: [insert step-by-step analysis here]<br>Question: [next question] |\n| *Additional Reminder in Q14 - Q20* |\n| Note that you should guess and ask what X exactly is from now on. X is possible a: [item_list_str], or other. The question must start with ’Is X ...  |\n\n| ToT Prompt for 20 Question game. [C1] is the count of questions asked. The ‘information gained’ marked blue represents the previous interaction history.|\n|---------------------------------------------------|\n| *Prologue*  |\n| You are playing the game of 20 questions. I am impersonating the thing, X. You will ask me up to 20 questions that start with ’Is X’ and can only be answered by yes or no, and I will answer each one truthfully based on being X. <br>[C1] questions have been asked. And now we know: <br>[information gained] <br>Design a question about X and can only be answered by YES or NO.                   |\n| *Additional Reminder in Q14 - Q20*  |\n| Note that you should guess and ask what X exactly is from now on. X is possible a: [item_list_str]. The question must start with ’Is X ...  |\n\n**Analysis of a notable performance decrease in CoT and ToT compared to Direct Prompting (DP)**\n\n**CoT**: CoT method focuses more on analyzing possible answers based on current responses and interactions rather than actively seeking information to further reduce uncertainty. CoT often performs extensive self-analysis after obtaining some initial information in the early rounds. It then tends to ask questions related to what it believes might be the correct answer. However, asking specific questions without sufficient information can easily lead to failure. This is especially true in tasks like 20 Questions, where there are many interaction rounds.\n```\nExample:\nTrue Option: Flamingo\n[ROUND 8]\nQuestioner:\nExplanation: So far, we have established that X is a living thing, an animal, a vertebrate, a bird, a large bird, lives near water, and eats fish.  This information narrows down the possibilities significantly.  A large bird that lives near water and eats fish could be a pelican, a seagull, a heron, or an eagle, among others.  To further narrow down the possibilities, we can ask about a specific characteristic that only some of these birds have.  For example, not all of these birds can dive underwater to catch their prey.\nQuestion: Can X dive underwater to catch its prey?\nAnswerer:\nNo, X does not dive underwater to catch its prey.\n[ROUND 9]\nQuestioner:\n\nExplanation: So far, we know that X is a living thing, an animal, a vertebrate, a bird, a large bird, lives near water, eats fish, but does not dive underwater to catch its prey.  This information narrows down the possibilities significantly.  A large bird that lives near water and eats fish but does not dive underwater could be a type of heron, stork, or pelican.  To narrow it down further, we can ask about a specific characteristic of one of these birds.  For example, pelicans are known for their large throat pouch used for catching prey and draining water before they swallow.\nQuestion: Does X have a large throat pouch?\nAnswerer:\nNo, X does not have a large throat pouch.\n```\n\n**ToT**: In the original ToT, the reward function is based on self-reward. Self-reward lacks the principle gradually guiding LLMs to choose questions that effectively narrow down the possibilities set, as seen in UoT. When relying on self-reward, the model often selects more general questions, making it difficult to obtain information about the targeted possibility.\n```\nExample:\nTrue Option: Meerkat\n[ROUND 1]\nQuestioner: Is X a man-made object?\nAnswerer: No, X is not a man-made object.\n[ROUND 2]\nQuestioner: Is X a food?\nAnswerer: No, X is not food.\n[ROUND 3]\nQuestioner: Is X a living organism?\nAnswerer: Yes, X is a living organism.\n[ROUND 4]\nQuestioner: Is X a plant?\nAnswerer: No, X is not a plant.\n[ROUND 5]\nQuestioner: Is X a mammal?\nAnswerer: Yes, X is a mammal.\n[ROUND 6]\nQuestioner: Is X a domesticated mammal?\nAnswerer: No, X is not a domesticated mammal.\n[ROUND 7]\nQuestioner: Is X a carnivorous mammal?\nAnswerer: No, X is not a carnivorous mammal.\n```\n**DP**: The DP method poses questions that are more coherent and logical overall. This is because the DP method uses shorter text inputs in LLMs, allowing for a better understanding of the conversation history. It avoids being misled by premature judgments in multiple rounds of interaction (such as CoT) since it analyzes implicitly, without relying on explicit but insufficient self-reward. This enables it to adjust the questioning logic in a timely manner.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aTI8PGpO47", "reviewer": "Reviewer_YbAg", "summary": "The paper addresses the problem of how to guide an LLM to find the right answer to a given question, in cases additional information must be elicited from the agent (possibly human) asking the question before knowing the right answer. The proposed algorithm, called Uncertainty of Thoughts (UoT), works by simulating possible questions to ask and answering it might receive to choose the question that will minimize the uncertainty over the right answer. UoT spans a tree of questions and answers, and chooses which question to ask at the end by estimating the value of information gained by the different questions. The authors perform a very extensive experimental evaluation of UoT, on 3 benchmarks, 5 LLMs, and quite a few LLM question-answering frameworks. The results are very impressive, showing that UoT can find the right answer faster and in more cases than all other options in almost all cases. Moreover, they created benchmarks for this important problem for the community to use.", "questions": "1.\tFor the case where the answers are open ended, I do not fully understand how would you branch over the possible answers and relate them to limiting the set of possible answers. It seems to me that you would need some way to relate every open ended answers to the set of possible “right answers” that are still consistent. Is this what is intended?\n\n2.\tI don’t fully understand why do we need the accumulated reward function. The basic reward function measures information gain for the leaf nodes. The expected reward function aggregates recursively the rewards from leaf nodes. Why do we need the leaf node to accumulate the rewards gained up to it? It would be more natural to have the reward at the leaf measure the information gained by reaching that leaf node, and then have the expected reward aggregate these values as it is defined now (without the accumulated reward).\n\n3.\tCurrently the tree is limited to a fixed depth. Why not use an MCTS type of search where the depth is not fixed (e.g., UCT)?", "limitations": "No limitations due to negative societal impact I can think of.", "rating": 10, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "In general, I am very excited about this work due to the following reasons:\n-\tThe problem they identified and formalized is very important and I believe relatively understudied in a formal way in the world of LLMs\n-\tThe proposed algorithm – UoT – is novel and exciting. It is likely to open many directions for future work\n-\tThe evaluation is very extensive and convincing. \n-\tThe appendices seem to cover most questions and justify more design choices (at least empirically).", "weaknesses": "Some design choices are quite ad-hoc, in particular in how the reward function is defined and propagated. That being said, the authors support most choices empirically in the appendix. \n\nMinor comment:\n-\tIn page 5: “… over the typical ranges we encounter.” – do you mean typical ranges of IG values?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing the value of our work and providing valuable suggestions. Your feedback is instrumental in enhancing the quality of our research. Below are some clarifications that we hope will address your concerns.\n\n \n> Q1: For the case where the answers are open ended, I do not fully understand how would you branch over the possible answers and relate them to limiting the set of possible answers. It seems to me that you would need some way to relate every open ended answers to the set of possible “right answers” that are still consistent. Is this what is intended?\n\nA somewhat complex aspect of our algorithm lies in how the Answer Simulation step works, as there is an apparent conflict between the Answerer providing open-ended answers, and UoT grouping responses into 2 categories (affirmative and negative) at each Answerer node. \n\nTo resolve this apparent conflict, we need to clarify that \"real\" answers (those given by the user in the actual conversation) are open-ended, as there are no restrictions on how the Answerer (e.g. the human) can respond. However, for the \"imagined\" answers in UoT's simulated futures, we consider these to have only 2 categories (affirmative and negative), as this is necessary to compute meaningful uncertainty metrics. To do so, at the Answerer nodes, instead of using an LLM to generate answers, we instead prompt the LLM to decide which of the possibilities among the current possibility set would lead to an affirmative answer, and which would lead to a negative answer. In this way, we partition the current possibility set into 2 subsets, which are then used as the current possibility sets of the 2 children of the current node. (Section 2.3, lines 124-134)\n\n> Q2: Why an accumulated reward function is necessary\n\nAccumulated reward is essential for considering long-term effects in dynamic environments, rather than just immediate effects. By summing the rewards of a node $v$ and all its ancestor nodes, we reflect the effectiveness of past decisions, evaluating the total reward along the entire conversation path leading to a leaf node. The cumulative reward at a leaf node represents the total reward at the end of the conversation.\n\nFor instance, in a 3-step conversation, the immediate reward function $R_u(v)$ captures the information gained from receiving the answer at node $v$. However, the total information gained by the end of the conversation is the sum of the information acquired over the three rounds. Therefore, we accumulate the immediate rewards  $R_u(v)$ of a leaf node and its parent nodes to compute the accumulated reward, thereby accounting for the information gained across multiple rounds of the conversation.\n\n\n> Q3:  Currently the tree is limited to a fixed depth. Why not use an MCTS type of search where the depth is not fixed (e.g., UCT)?\n\nThanks for your suggestion. Our current approach only considers fixed depth for simplicity.  We can use our current information gained based reward design with variable depth to extend dynamically based on the promising outcomes of the simulations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "crMwl4w5jw", "reviewer": "Reviewer_W6dt", "summary": "The authors propose an uncertainty-aware information-seeking framework. This approach involves having the LLM simulate future scenarios and select the question that maximizes information gain. They evaluate their method using the latest LLMs across various benchmarks and introduce new datasets specifically designed to assess the LLMs’ information-seeking capabilities.", "questions": "Do you always assume $p(x_i)$ is uniformly distributed? Can't you use token probabilities to set these probabilities?", "limitations": "Authors didn't add a limitations section but I think, they can add their methods' cost as a limitation.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The problem and the uncertainty-based approach are well-motivated, with relevant real-life examples.\n- The idea is clearly explained, providing a sufficient amount of detail.\n- The performance of their method surpasses that of the baselines, as demonstrated in Table 1.", "weaknesses": "- My biggest concern is the evaluation of the methods using GPT-4 as the answerer. In UoT, the LLM simulates future scenarios by itself and selects an optimal question. Since GPT-4 is the answerer in the evaluation rather than a human, this simulation might be more successful compared to real-life scenarios where a real person is the answerer. The authors should include at least one human-based experiment to validate their approach in real-life situations.\n- The authors should discuss the cost of their approach through experimental analysis.\n- I would like to see an evaluation of how robust this framework is to different prompts during the internal steps.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your detailed feedback and suggestions. Your comments have been very helpful in guiding us to enhance our work. Please find our clarifications below, which we hope will resolve your concerns.\n\n> Q1: The authors should include human-based experiments\n\nAs you suggested, we run this human-based answerer experiment in 20 Questions (Common) and Medical Diagnosis (MedDG) based on GPT-4 (close-set), and it shows that the results(Success Rate) for both DP and UoT method are very close to the GPT-based answerer experimental results. \n\nDue to the time limitation, we only conduct the current experiments, and will further supplement the experiments in different LLMs, datasets and baselines to Section 3.2 Performance to the next revision. \n\n| Dataset    | DP   | UoT  |\n| ---------- | ---- | ---- |\n| Common     | 45.9 (50.5) | 72.1 (71.2) |\n| MedDG | 74.0 (72.3) | 86.0 (88.0)  |\n\n*PS: | Results of human-based experiments (GPT-based answerer experimental results) |\n\n> Q2: The authors should discuss the cost of their approach through experimental analysis.\n\nWe discuss the computational efficiency of our method in Table 2 by examining token consumption in each turn interaction. Based on your suggestion, we carried out this experimental cost calculation, and we will incorporate these analysis into Section 3.3 Analysis in the final revision.\n\nAccording to our calculations, UoT with a depth of 3 consumes approximately 9.2k tokens per turn, while Pruned UoT with a depth of 3 uses about half that amount. Based on the official GPT-4-turbo pricing (USD 10.00 per 1M tokens) and the average conversation length for each dataset, the cost per task is USD 1.24 for Common, USD1.64 for Things, USD 0.19 for DX, USD1.08 for MedDG, and USD1.09 for FloDial. The total cost to run one experiment across these five datasets is USD 137.86, USD 3053.17, USD 20.09, USD 133.40, and USD166.10 respectively. If we use the latest GPT-4o API (gpt-4o-2024-08-06) at $2.5 per 1M tokens, the costs would be one-fourth of the current amounts. Especially, the cost is dominated by input tokens so the cost of output tokens is small enough to be neglected.\n\n> Q3: I would like to see an evaluation of how robust this framework is to different prompts during the internal steps.\n\nTo validate the robustness of our method to different prompts, we rephrase the current prompt and conduct close-set experiments in 20 Questions (Common) and Medical Diagnosis (MedDG) based on GPT-4, using the original experimental settings.\n\nOriginal Prompt: \n```\nPlease design a question about X and can only be answered by YES or NO. {asked} Then classify the possible X above based on this question. If the answer is 'YES', put this X into 'YES: ...', otherwise to 'NO: ...'. Finally calculate how many X in YES and NO.\n\nNotably, this question should fulfill that the count of YES and NO are almost the same with a permissible discrepancy of no more than one!\n\nYou should think about best {m} questions to respond to.\n```\n\nRephrased Prompt:\n```\nPlease formulate a question regarding X that can be answered solely with YES or NO. {asked} Then, categorize each possible X based on the response to this question. Place the Xs with a 'YES' answer under 'YES: ...' and those with a 'NO' answer under 'NO: ...'. Afterwards, tally the number of Xs in both the YES and NO groups. \n\nIt is important that the question ensures the counts of YES and NO are almost equal, allowing for a difference of no more than one. \nConsider the most appropriate {m} questions to answer.\n```\n\nExperiment results:\n\n| Dataset | SR          | MSC         | MCL         |\n| ------- | ----------- | ----------- | ----------- |\n| Common  | 70.3 (71.2) | 11.1 (10.8) | 13.7 (13.5) |\n| MedDG   | 86.0 (88.0) | 2.7 (2.6)   | 3.0 (2.9)   |\n\n*PS: | Result of experiment with rephrased prompts (original result in the paper) |\n\nAs the results shown in the above table, the metrics (SR, MSC, and MCL) for the rephrased prompts are very close to those for the original prompts. For example, the SR in the Common dataset changed from 71.2 to 70.3. These minimal differences indicate that our method remains robust and consistent, regardless of prompt phrasing. We will further supplement the experiments in different LLMs, datasets and baselines in our final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kbsz5yoQRk", "reviewer": "Reviewer_c9Ar", "summary": "This paper presents the Uncertainty of Thoughts (UoT) algorithm designed to enhance large language models (LLMs) by enabling them to actively seek information through effective questioning. UoT incorporates three key components: an uncertainty-aware simulation approach to model possible future scenarios, uncertainty-based rewards motivated by information gain, and a reward propagation scheme to select optimal questions. The algorithm is evaluated across multiple LLMs in various scenarios, including medical diagnosis, troubleshooting, and the ‘20 Questions’ game. The results show a significant improvement in task completion rates and efficiency, demonstrating the effectiveness of UoT in reducing model uncertainty and enhancing information-seeking behaviour.", "questions": "Given the complexity of UoT, do you think the inference delay of UoT will affect the user experience in real applications?", "limitations": "The limitations are discussed in Appendix H Limitation and Future Work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of uncertainty-aware planning and reward propagation for question generation is a novel and significant contribution to improving LLMs’ performance in interactive environments.\n2. The experiments are well-designed, covering diverse scenarios (medical diagnosis, troubleshooting, 20 Questions) and multiple LLMs, providing robust evidence of UoT’s effectiveness.\n3.  The algorithm achieves substantial improvements in success rates and efficiency and the use of entropy and information gain to measure and reduce uncertainty is effective.\n4. The codes are available for the replication and future research.", "weaknesses": "1. The UoT framework, with its simulation and reward propagation components, might be complex to implement and integrate into existing LLM systems without significant computational resources. Also, this paper lacks of the analysis and comparison of inference time between each method, which will largely  affect the user experience.\n2. The paper primarily uses success rates and conversation lengths as evaluation metrics, but additional qualitative analyses of the generated questions and their impact on the decision-making process could provide deeper insights. For instance, the impact of UoT on the user experience, particularly in terms of the naturalness and relevance of the generated questions, is not thoroughly explored.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We highly value the feedback you provided. Your suggestions have prompted us to refine certain aspects of our work. We hope the following clarifications will satisfactorily address the points you raised.\n\n> Q1: The paper lacks analysis and comparison of inference times, which are crucial for user experience. Do you think UoT's inference delay will impact user experience in real applications?\n\nSorry for the missing inference time. We also discuss the computational efficiency of our method in Table 2 of our paper by examining token consumption in each turn interaction. Based on the results, we can roughly estimate the inference time for different methods. Meanwhile, following your suggestion, we conducted this inference efficiency experiment. We provide the results and analysis below and plan to include these results in Section 3.3 Analysis in the next revision. \n\nWe supplement inference efficiency using the Time to One Turn Conversation (TTOTC, measuring the time LLMs received an answerer's last round of responses to when the question is asked in the current round). We randomly sample 10 times from each dataset and conduct tests during both peak and off-peak hours of the GPT-4 API twice. The average TTOTC is reported below.\n\nResults Table\n| Dataset | Avg. Time (s) |\n| -------  | ------------- |\n| Common           | 5.14   |\n| Thing           | 9.77       |\n| DX               | 3.64       |\n| MedDG        | 9.29       |\n| FloDial          | 4.07       |\n\n\n***Impact of delay***\n\nInference delay is crucial in real-time applications. Long inference times can impact user experience. While UoT may introduce delays, its benefits in information acquisition and task success can offset this. For example, in medical diagnosis, accuracy is often more important than speed. For example, in medical diagnosis, accurate and effective information acquisition may be more important than quick but less effective responses.\n\n***Ways to mitigate the influence of inference latency***\n* With the development of LLMs, inference efficiency will improve for both open-source and commercial models, also enhancing the efficiency of our UoT method.\n\n* One simple way to optimize the complexity of UoT is to prune our UoT search tree, which we also introduce in Section 2.7 Extensions and Discussion. As the results shown in Table 1 and Table2, the Pruned UoT can still be the SOTA method in 4/5 datasets and only require half token consumption, and It will double the inference efficiency according to our test.\n\n* In practice, we can train the LLM to be more efficient policy engines that can directly generate good questions without exhaustive tree search. For example, previous work uses tree search for a teacher model and distillation to train a student model to replicate the teacher's output without tree search [1]. Also, we can enhance LLMs through SFT and RLHF. \n    * RLHF with UoT: UoT helps generate preference data by evaluating and selecting optimal questions based on expected rewards, refining LLMs with nuanced data. \n    * SFT with UoT: UoT collects successful trajectories in contexts like 20 Questions, medical diagnosis, and troubleshooting, providing valuable training data for LLM refinement. These approaches can improve LLMs' autonomous information-seeking capabilities across various domains and make it more efficient in real applications.\n\n[1] [Learning by Distilling Context](https://arxiv.org/abs/2209.15189). Charlie Snell, Dan Klein, Ruiqi Zhong. \n\n\n> Q2: Additional qualitative analyses of the generated questions and their impact on decision-making are needed. The impact of UoT on user experience, especially regarding the naturalness and relevance of the questions, is not thoroughly explored.\n\nWe acknowledge that the current evaluation metrics do not fully reflect the user experience in real applications. \n\nWe conducted simple experiments based on the GPT-4 UoT method to test user satisfaction, generation fluency, and the relevance of generated questions using the MedicalDG dataset. Two annotators rated these factors on a scale from 0 to 5, resulting in average scores of 4.27 for user satisfaction, 5.00 for generation fluency, and 4.02 for the relevance of generated questions.\n\nWe will include these experimental results in the final version and further design user experience studies to gather feedback on the naturalness and relevance of the generated questions. Combining this with the analysis of task success rates and conversation lengths, we will provide a more comprehensive evaluation and deeper insights into the decision-making process and user experience.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their helpful comments and suggestions. Here is a summary of our responses to address the major concerns of reviewers.

**1. Elaboration of Open Set Setting (Proposed by reviewer1[Ho3e15])**

In the closed set setting, our algorithm starts with a known possibility space $\Omega$. In the open set setting, we generate $\Omega$ at the start of each conversation round by prompting an LLM with the current conversation history. After generating $\Omega$, UoT proceeds as in the closed set case to generate questions. 

**2. Clarification on Answer Simulation Step, and How Open-Ended Responses are Mapped to Categories (Proposed by reviewer2 moAn, reviewer3 YbAg)**

Our Answer Simulation step seems complex due to the apparent conflict between the Answerer providing open-ended answers, and UoT grouping responses into 2 categories (affirmative and negative) at each Answerer node. Below, we provide additional clarification to resolve this conflict, and will incorporate this into the explanations in the paper.

"Real" answers (those given by the user in the actual conversation) are open-ended, as there are no restrictions on how the Answerer (e.g. the human) can respond. However, for the "imagined" answers in UoT's simulated futures, we consider these to have only 2 categories (affirmative and negative), as this is necessary to compute meaningful uncertainty metrics. Thus, at the Answerer nodes, instead of using an LLM to generate answers, we instead prompt the LLM to decide which of the possibilities among the current possibility set would lead to an affirmative answer, and which would lead to a negative answer. In this way, we partition the current possibility set into 2 subsets, which are then used as the current possibility sets of the 2 children of the current node. (Section 2.3, lines 124-134)

**3 Approach to Deal with Non-Uniform Probabilities in Possibility Set (Proposed by reviewer1Ho3e15 and reviewer4 W6dt)**

Our current implementation assumes equal probabilities for all possibilities for simplicity. However, the algorithm description in the paper in fact allows for non-uniform starting probabilities, assigning higher probabilities to more common diseases: in the example in lines 156-159, we assign non-uniform probabilities $P(x_1)=0.2, P(x_2)=0.3, P(x_3)=0.5$. These prior probabilities will naturally affect the computation of expected rewards in UoT, giving greater weight to more probable diseases. 

This framework can be further extended using a probabilistic model between possibilities and answers, by using a Bayesian approach. Specifically, we start by assigning non-uniform prior probabilities based on disease frequencies. At each Answerer node, for each possibility $\omega$, we estimate the likelihood of observing a 'Yes' or 'No' answer to the current question (by prompting an LLM and extracting logits for these tokens). These likelihoods allow us to perform a Bayesian update to obtain the posterior probability of $\omega$ given the answer, leading to probability distributions for the children of the current node.

**4. Explanation of Reward Design (Meaning of Accumulated Reward) (Proposed by reviewer1 Ho3e15, reviewer3 YbAg)**

Accumulated reward accounts for information gains over multiple rounds of the conversation. Suppose we are evaluating the reward for a 3-step conversation. The immediate reward function $R_u(v)$ accounts for the information gained from receiving the answer at node v. However, at the end of a 3-step conversation, the total information we have gained is actually the accumulation of information we have gained over the 3 conversation rounds. Thus, we accumulate the immediate reward $R_u(v)$ at a leaf node with those of its parent nodes, to compute the node $v$'s accumulated reward.

**We also provide more details about these major concerns and remaining questions in the below individual response.**

Meta-review: Overall there is agreement that the paper is addressing an interesting problem and has offered a novel approach that yields strong empirical results. 

There were a number of presentation and clarification issues raised by reviewers that the authors should work hard to include in the final paper.
Decision: Accept (poster)