Feedback-Aware MCTS for Goal-Oriented Information Seeking
Authors: Harshita Chopra
Chirag Shah
Venue: NeurIPS 2025 spotlight ()
Keywords: Information Seeking
Large Language Models
Uncertainty Reduction
Planning
Search
Primary area: applications
TL;DR: A framework that uses Monte Carlo Tree Search for guiding an LLM to ask information-seeking questions, learning from past successful strategies to solve problems more efficiently and accurately.

Abstract: Effective decision-making and problem-solving in conversational systems require the ability to identify and acquire missing information through targeted questioning. A key challenge lies in efficiently narrowing down a large space of possible outcomes by posing questions that minimize uncertainty. To address this, we introduce a novel framework that leverages Large Language Models (LLMs) to generate information-seeking questions, with Monte Carlo Tree Search (MCTS) to strategically select questions that maximize information gain, as a part of inference-time planning. Our primary contribution includes a hierarchical feedback mechanism that exploits past interaction patterns to guide future strategy. Specifically, each new problem is mapped to a cluster based on semantic similarity, and our UCT (Upper Confidence bound for Trees) formulation employs a cluster-specific bonus reward to prioritize successful question trajectories that have proven effective for similar problems in the past. Extensive empirical evaluation across medical diagnosis and technical troubleshooting domains shows that our method achieves an average of 12\% improvement in success rates and about 10x reduction in the number of LLM calls made for planning per conversation, compared to the state of the art. An additional 8\% gain in success rate is observed on average when we start with a constrained set of possibilities. Our results underscore the efficacy of feedback-aware MCTS in enhancing information-seeking in goal-oriented dialogues.

Feedback-Aware MCTS for Goal-Oriented Information Seeking
Harshita Chopra University of Washington, Seattle hchopra30cs.. washington, edu
Chirag Shah
University of Washington, Seattle chirags@uw. edu
Abstract
Effective decision-making and moblemm-solving in conversational systems require the ability to identify and acquire missing information through targeted questioning. A key challenge lies in efficiently narrowing down a large space of possible out- comes by posing questions that minimize uncertainty. To address this, introduce a novel framework that leverages Large Language Models (LLMs) to generate inforiation-ssekknng questions, with Monte Carlo Tree Search (MCTS) to strategi- cally select questions that maximize information gain, as a part of inference-time planning. Our primary contribution includes hierarchical feedback mechanism that exploits past interaction patterns to guide future strategy. Specifically, each new problem is mapped cluster based on semantic similarity, and our UCT (Upper Confidence bound for Trees) formulation employs a cluster-specific bonus reward prioritize successful question trajectories that have proven effective for similar problems in the past. Extensive empirical evaluation across medical diagnosis and technical troubleshooting domains shows that our method achieves an average of 12% improvement in success rates and about 10x reduction in the number of LLM calls made for planning per conversation, compared the state of the art. An additional 8% gain in success rate is observed on average when we start with con- strained set of possibilities. Our results underscore the efficacy feedback aware MCTS in enhancing information-secking in goal-oriented dialogues.
Introduction
Recent advances in conversational AI have transformed human-machine interactions, enabling more sophisticated goal-oriented dialogue systems. A fundamental requirement in these systems is the ability to identify and seek out missing information efficiently. When confronted with an initially under-specified problem, conversational agents must interact over multiple turns and strategically ask questions that reduce uncertainty while minimizing interaction overhead. This necessitates principled approach sequential decision-making wherein each question posed must maximize information gain and narrow down the solution search space. Large Language Models (LLMs) have shown strong capabilities in natural language understanding and generation, offering promising basis for enhancing these information-seeking strategies. However, effectively applying LLMs to domains that involve complex sollven- still requires overcoming challenges efficient planning, exploration-exploiae
trade-offs, and adaptation to domain-specific interaction patterns.
14 8 Notably, the Tree of Thoughts (ToT)) 222 approach has demonstrated the potential of leveraging hierarchical structures improve problem-solving and reasoning in language models. However, expanding the full tree can be computationally inefficient and expensive, especially in domains with large search spaces. A
LLMs have emerged powerful tools for planning using trees [2]
Our code is available at gggibuubccwwhasshhieeooooopmissp
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Description
Assign Embeddingg to Cluster O
Feedback Propogation: Update Bonus Resward of Queshions
e with Passibittiss
Updara Reot v child)/la)
Information seeking
By(t) P Re
Turpet
petectedion or
User Response
Astt Question
LUA
Direct Prompo
Y: decny fector
Optimal question(~))
Repeat for (lteaaionn
Early stage Questions
Selection
Expansion
Simulation
Backprooagation
depth d
Siiect ande uitaa puszaass UCTrmonceff (1.A)
Specific
Candidate
B,(o)
Questiona
Rallout til
Update Read!!)
Target E Q
Figure I: Overview of MISQ-HF. In the MCTS block, green nodes (0) and red nodes represent v and v respectively, corresponding to possibilities after affirmative and negative answers to question. The blue arrows indicate the information-seeking question loop (steps 4-8). Towards the end of decision-making, targeted questions are generated, denoted by the loop of dashed arrows (steps 9-6-7-8). Finally, when the user response a, (step 7) confirms the target detection, the conversation terminated (step 10) and the feedback mechanism updates the reward bonus along the successful questioning trajectory in the decision tree, enabling the system to adapt for similar future cases.
fundamental challenge lies designing systems capable of dynamically adapting their interaction strategy to converge on specific solution efficiently. To address these challenges, Monte Carlo Tree Search (MCTS) [3] has emerged as a promising technique for balancing exploration and exploitation in decision-making processes. It has been successfully applied in various domains, from game-playing 44, and is now being leveraged natural language processing tasks.
Al 17 18
to robotics
Building upon this foundation, our work introduces a novel framework that combines MCTS with hierarchical feedback mechanism achieve adaptive and efficient coommation-seeking Inspired by prior work on uncertainty- -ware planning, our approach presents three key contributions:
1. MCTS for Question Selection: LLMs generate multiple valid questions to narrow search spaces, but identifying the optimal ones is crucial. Tree-based approaches are known for comprehensive planning. By employing MCTS, system efficiently constructs and explores promising questions in the decision tree without exhaustive expansion, focusing both immediate and long-term information gain. Our modified variant of the Upper Confidence Bound for Trees (UCT) assigns higher weights to questions that have effectively narrowed the solution space in past interactions.
2. Cluster-Based Feedback Mechanism: We cluster similar cases using text embeddings derived from the user's initial problem description. After a successful interaction, the system propagates cluster-specifiy bonus rewards through the decision tree. This bonus reward decays with depth, emphasizing the importance of early-stage questions that effectively reduce the solution space by targeting broad, generalizable information.
3. Efficiency through reduced LLM calls: Our method minimizes computational overhead by strategically limiting LLM interactions during tree construction and simulation. We maintain a single decision tree for a given dataset, which expands as more data points stream in. We also employ lightweight rollout policies limited by predefined depth during the simulation step of MCTS. The significantly reduces the number of LLM calls without compromising performance.
balance avoids exhaustive tree expansion and
These innovations collectively enable our system to dynamically adapt its questioning strategy based on historical patterns, achieving greater efficiency and relevance. For instance, the integration of feedback mechanisms ensures that successful strategies for specific clusters are reinforced over time, while depth-aware MCTS ensures computational resources focused the most promising paths.

---

An overview of our framework, MISQ-HF (Monte Carlo Tree Search for Information Seeking Questions with Hierarchical Feedback), is illustrated in Figure !
We evaluate our approach across diverse conversational tasks. Results demonstrate that our system outperforms existing baselines in both task success and efficiency in scenarios requiring complex reasoning and hierarchical decision-making We also highlight the individual contributions of depth-aware MCTS and cluster-based feedback in enhancing the system's performance.
2 Related Work
The integration of LLMSs with tree search algorithms has proven effective for enhancing multi-step reasoning and decision-maker makiin... Guez et [ introduced MCTSSnets combining tree search with neural networks for tasks like Sokoban. While focuses on discrete planning, our approach extends MCTS to hierarchical conversations, optimizing question selection with depth-aware strategies and semantic embeddings. Yu et al. [23] applied MCTS for dialogue planning with LLM-baseed simulations, but their method differs by using open-loop search without feedback mechanisms and focusing solely on persuasion tasks. Hui et [ proposed the Reflection on Search Trees (RoT) framework for generating state-specific guidelines to improve search performance. Unlike RoT, which prioritizes reasoning efficiency, our approach maintains a single decision tree while incorporating cluster-specific rewards to guide question selection. Zhu et al. (28) framed retrieval and answering as partially observed Markov decision process to adaptively gather evidence but does not address learning from feedback in conversational settings. In the clinical domain, Li et al. 12] introduced MEDIQ, an adaptive framework leveraging LLMs to identify missing information and ask follow- up questions. While it focuses reliability in high-stakes contexts, method generalizes by prioritizing early-stage questions to narrow the solution space effectively.
Our work draws inspiration from the Uncertainty of Thoughts (UoT) algorithm which enhances LLMs' ability to seek information through effective questioning. UoT uses uncertainty- based rewards and tree structure to guide question selection, improving performance across various domains and baselines like Chain of Thoughts (20) and Tree of Thoughts [22]. Extending these principles, we integrate a depth-aware MCTS algorithm for selecting questions based intelligent planning, along with a cluster-based feedback system that leverages historical successes. Recent works like Language Agent Tree Search (26 and ExACT 24 also combine LLMs with MCTS to handle open-ended agent tasks, where models simulate unstructured actions through language prompts in rich environments. In contrast, our method MISQ-HF is tailored for structured infornation-seeking dialogues. It uses a quantitative information gain reward and beedback-guided search within a constrained space of possibilities. The depth-aware bonus reward prioritizes early-stage questions, balancing efficiency and adaptability.
3 Methodology
3.1 Problem Formulation
The task modeled as a sequential interaction between a Questioner (an LLM) and an Answerer (a human; here, simulated by an LLM). Let Ω be the space of possible target outcomes, with an unknown target w Ω. The interaction proceeds over turns = 1.... T, where T is the maximum allowed turns. At each turn, the system asks question q. and receives an answer dr, which is either previous
binary (yes/no) or open-ended. The history h, = {yr, .i,...,,9.. .t- at-1) represents interactions. At each step I, the current possibility set Ω is updated based on prior interactions. The updated set 22, contains all elements consistent with the history hG. Questions in the first 8 * T turns, where 5 (0, 1), are selected strategically by traversing the decision tree of potential questions, and the remaining turns are reserved for making informed decisions about what the outcome (target) is, based on h4 and Q4. Here, denotes the proportion of turns reserved for asking ceermattion-eekking questions. The process ends when the Questioner identifies w or reaches the maximum turns T.
Upon reaching terminal states in the decision tree (where [24] < 2), the Questioner LLM transitions from asking -nformationnseekiin questions to making targeted questions about specific outcomes. In the Closed Set scenario, where the target is one of the items within a predefined set Ω the tree construction is well-defined. However, this space often unknown in real-world situations, leading to Open Set scenario, where the models operate without prior knowledge of the outcomes. To
3

---

address this, we follow the approach used in [8, where we directly prompt the Question Generator to first define the initial possibility space 92 based on the problem description and then update progressively based on the history of interactions h4. In practice, it is important to declare the set of all possible items Q in the initial prompt for the Questioner I.L.M to avoid longer dialogues and failures due to arbitrary guesses in the Closed Set scenario. Hence, we ensure that the Questioner LLM is explicitly informed about 52 once at the beginning of each interaction. This helps fixing the items that appear in the targeting questions. To justify this modification, we report results with and without the flaware prompt.
3.2 Decision Tree of Questions
The question generation process employs hierarchical approach that combines LLMs with MCTS to efficiently construct tree of potential questions represented by nodes, In the information-seekinn phase, at each turn f, the system either traverses or expands the tree to find the most optimal questions to ask, with the goal of maximizing information gain. This tree is cached and reused across all data-points belonging
given dataset.
The root node represents the initial conversational state in the decision tree, containing the complete predefined set of possibilities Ω in a dataset or specific domain. Over each of the question-answw turns, some of these possibilities are climinated by asking information-sseeing questions. Starting with a common, fixed superset of possibilities allows for efficiency, as the generated questions (child nodes) can be reused for future samples. This can lead to more general or broadly applicable questions in the beginning. However, for more relevant questions, we can initialize the root node as a constrained set of possibilities 22 S 92 conditioned by user's s problem description. Specifically, when a new problem arrives, the LLM is prompted to classify likely and unlikely outcomes in S based on the user's problem. Upon determining S2., we search the existing first layer of tree for a root node whose possibility set Proot is a superset of the constrained set, i.e., Pront 2 Q. If such root node is found, we initiate the questioning process from that node, leveraging the existing question paths or generating more from there. Otherwise, new root node is added to the tree, initialized with the constrained set Ωg. This can lead to a wider tree, as there are multiple possible root nodes, essentially representing different subsets of Ω. We report results with both types of initializations.
The LLM- question generator takes two inputs at turn t: the current possibility set Ω4 and the ancestral context An: which consists of the sequence of question-anseee answer pairs corresponding to all the ancestor nodes of the current node that led the formation of 22, This context prevents the generation of redundant or previously asked questions, thereby providing a clearer path of deduction. Let represent a node the decision tree at turn l. With slight abuse of notation, we define Q, as the possibility set corresponding to node v. For each non-terminal node v, where [S2, > 2, the LLM generates m candidate questions which form its immediate child nodes:
Qu = =(g!" _g (....!!!m)) } = LLL gen Ani)
For each generated question, L.I.M gen performs a binary partitioning of the possibility set St into two disjoint subsets D and S2 corresponding to affirmative and negative responses respectively, such that 22 = Ω U The LLM is prompted to generate questions that maximize information gain by creating balanced partitions where: ||2,! 52 1 O.
Each question spawns two child nodes A and N.N corresponding to affirmative and negative responses, storing 22 and 22 respectively. For example, if the possibility set is Ω, (flu, pneumonia, enteritis, asthma). the question "Do you have difficulty breathing?" will partition the set as: Ω {pneumonia, asthma], S {flu, enteritis).
3.3 Information Gain
To quantify the effectiveness of each question in reducing uncertainty, entropy- metrics are N employed (18). Following the formulation of reward structure in UoT, let Pe | and p = /.- The expected information gain at o is:
(2) The reward function, given by RIG(v), achieves its maximum value when the subsets 2 and 2 have equal probabilities, signifying the greatest reduction in uncertainty. It attains its minimum value
IG) = -P, logrd - Pe log

---

when one of the subsets has probability of zero, indicating no reduction in uncertainty. To normalize and sharpen rewards, a scaling parameter > 0 is employed. Formally.
RIG(U) Pe log p p log
+ p p
The expected reward of asking a question, (V), is obtained by recursively adding the immediate reward (I)(2) (information gain at the current node) and the expected rewards of its child nodes. The total information gained until node v of an interaction trajectory denoted by the accumulated reward, Ro (v), which is obtained by starting at the root and propagating down to the node v.
Ro(v)= (oo( + fo
(
is root, (parentt(()))) otherwise.
(v) Ro(()), pet Ro (o( ve (
t is leaf, otherwise.
(5)
where V and V. are the child nodes of u corresponding to affirmative and negative responses respectively. For each non-terminal response-specifie node v", a E [A,N), the expected reward Re (e") is the average expected reward of its child nodes, denoted as children(v")) Formally,
Re (v²)
E V'E children(
(e
(6)
children((n))
3.4 Monte Carlo Tree Search (MCTS)
The decision tree of questions is constructed iteratively when MCTS is executed over K iterations at each decision-making step across samples. Each iteration includes four phases:
Selection: Considering the current node as the root, child node selected based on the widely used UCT formulation that balances exploration and exploitation:
Rooia (v) No
I No
UCT(v)
CV
where Rrota (v) refers to the cumulative reward, N, is the visit count of node v, N2 is its parent node's visit count, and the exploration constant. We initialize (v) and N, 0 when a node is added to the tree. Reotal (v) is updated by adding expected reward (e(v) over time.
This selection strategy follows the UCT algorithm [1 which applies UCB1 (Upper Confidence (1)(
Bounds) from multi-armed bandit theory to guide Monte Carlo Tree Search. The first term Ny estimates the average reward of the node, promoting high-reward questions (maximizing information gain). The second term Cy In
N. derived from UCBI, encourages exploration of under-visited nodes and grows as No, remains small relative to the parent's 's visit count Np. This balance enables UCT to trade off exploitation and exploration effectively. UCT has been proven consistent, with the probability of selecting suboptimal actions at the root decreasing polynomially with more samples [.. Empirically, it has shown strong performance in large-scale scale domains such as Go and planning under uncertainty 2
The expansion step aims to create child nodes by generating potential questions that split the possibility set, thereby narrowing down the search space of the tree. When the selected node non-terminal (192,] > 2) and does not have child nodes, candidate questions are formulated according to Equation [ If child nodes already exist, we skip this step and proceed to simulation.
2. Expansion:
3. Simulation: A rollout policy is used to estimate the expected reward of the selected node by simulating a random interaction up to a predefined depth d, or a terminal state, whichever occurs first. In the rollout phase, we traverse d, levels down from the selected node, choosing one of its child nodes at random, following a single level of expansion if child nodes did not exist. This step provides an estimate of the long-term utility of selecting particular question.
Backpropagation: After reaching leaf node u the end of the simulation, the expected reward R. (u) is backpropagated up the tree to update the ancestor nodes along the path to the selected
5

---

(simulated) node. During backpropagation. the cumulative reward, (uoa((u) of every ancestor node of u is updated, and their visit counts are incremented by Formally, for each node in the path from to the root:
Raotal (v) f- Ruoal (v) + (u)
This backpropagation process ensures that nodes closer successful outcomes, i.e., nodes leading higher rewards, are more likely to be selected in subsequent iterations.
Finally, after completing K iterations of MCTS, the system asks the question having the highest expected information gain. This corresponds to finding v", the child node of the current root having the maximum expected reward:
eº = arg max R. (v() e'eo()))))
3.5 Feedback Mechanism and Cluster-Basse Reward Adjustment
Learning from experience is critical component of decision- Decision-making making systems. We introduce clustering- based approach for dynamic reward adjustments by propagating feedback through the tree after a successful conversation. When the system successfully identifies the target, it triggers series of updates to the bonus rewards of nodes that led to the target.
3.5.1 Cluster Assignment and Creation
When new sample (user) arrives, generate text embedding of their problem description. This embedding is then compared with existing cluster medoids to determine its assignment. A similarity threshold r is used to decide whether assign the embedding one. Let e represent the embedding of the current data point and my denote the medoid of cluster k. The similarity condition is given by:
existing cluster create new
Similarity(e, m&) ||||z
m
2T
(10)
m
where represents the dot product, and ||. represents the 1.2 norm. If no existing cluster satisfies this condition, a new cluster created with e as its initial medoid. If assigned to an existing cluster, is added that cluster's set of embeddings CR. and the medoid m is recomputed as:
m
argmax Σ
X y.y
(11)
| lyll
xEC₂
YEC,
3.5.2 Bonus Rewards for Feedback Propagation
For each node v, maintain dictionary B& (v) which maps each cluster k the bonus reward (initialized as zero) earned on reaching the target successfully. Once the target (w) is correctly identified, (x(v)
updated for each node along the path from the current node back the root, E Ωr B3 (v) is proportion of the node's 's cumulative reward and depends on the absolute depth of the node, given by d, controlled by an exponential decay as we move upward in the tree. The bonus reward for node corresponding to cluster k is updated after every success:
(x(w) (x(e) + B (v)ta(()) 7d
(12)
where / is task-specific scaling factor (denoting proportion of total reward), and E (0. 1) is decay factor that controls the influence of the bonus. (x(v) is a scalar value that is higher for etrly-stage questions which have proven effective to narrow down the large possibility set, and lower for later-stage questions near the terminal nodes which are often more specific to each unique case.
To incorporate these bonus rewards into decision-making we modify the UCT formula used in the selection step handle similar cases while maintaining exploration capabilities. We introduce cluster-specific bonus term to bias selection toward question nodes that led to successful outcomes for similar data points in the past. The modified UCT formula becomes:
Reoral (v) N,
In
UCT icedback (v. ks)
+ CV
+ Ba
(13)
N

---

3.6 Efficiency Gains
We evaluate the number of LLM calls re- quired for planning. Consider using an ex- haustive tree search to find the most reward- ing question. At each node one I.L.M call can generate m candidate questions, each splitting Ω into affirmative and neg- ative response sets, thereby giving rise to b = 2m child nodes. In the first simulation, every node up to depth da must be pro- cessed. Hence, the total number of LLM
Algorithm 1 MISQ-HF
Require: Dataset S, question ratio Embedding model, cluster-embeddiins hashmap C, similarity threshold т, maximum turns T, MCTS iterations K, LLM
1: Initialize (v) = 0, Ak E {1, (1,2, [C]] for each node
for sample s
3:
e, f- Fimbeeddnggdexcrrpptoonn
4:
C2 4 --sssignChssteree,... C,,
> Use Eq.
10
5:
Initialize Ω2 = 1 at current root node 17
6: Initialize conversation history ht = 0 and (
calls equals the total number nodes:
while < and target(s) undetected do
bd. -1
8:
if < 8 + and [92, 2 2 then
Σ
9:
8" + MCTS(v, K, Cx) 9: question(e")
D Use Eq
10:
Usc Eq
11:
0, UserResponse(qus
In subsequent turns, only the nodes at the frontier (depth d,) expanded, requir-
12:
6 < child( (a.)
13:
else
ing 8yd calls. Thus, the overall computa-
14:
q: < (TrgetingPrompp(2..) UserResponse h)
tional cost for exhaustive search be rep- resented as ( = (((2m) (1)2m))) which grows exponentially with depth.
15:
16:
end if
17:
< hU (q., + +++++11
18:
An iteration of MISQ-HF proceeds four stages. During selection, the tree 20:
19:
end while
targen(s) detected then Successful conversation
traversed according to the UCT policy
21:
v + u
> Feedback Propagation
(Eq. 7B identify promising node,
22:
while parent(u') ) A do Update B₂(v'))
which does not require LLM prompting. 23:
> Use Eq.
12
The expansion of the selected node requires 24:
v' <- parent(v')
at most one LLM call; none if child nodes 25:
end while
26:
end if
exist in cached tree. In simulation, dom rollout explores the tree to depth d,;
27:
end for
each step may involve one LLM call, re- sulting in fewer than d, calls per rollout. Finally, backpropagation updates values along the path to the root, requiring no LLM prompting. Therefore, each iteration costs most d, LLM calls, and performing K iterations per decision gives QGC & K (d. + 1), which leads to complexity of O(K d.), highlighting the linear scaling advantage over exponential growth of exhaustive search.
Hierarchical feedback adds a bonus reward (Eq. 12 which improves efficiency without changing asymptotic complexity. Semantic clustering for cluster assignment requires O(ne) comparisons per sample, but this cost is negligible compared to LLM calls and amortized across turns. Hence, MISQ-HF HF achieves significantly better efficiency while retaining deep search capability.
Experiments
In this section, we provide overview of the datasets, baselines, evaluation metrics, and implemen- tation details. Algorithm shows the pseudocode of the proposed framework.
4.1 Datasets
We demonstrate the effectiveness of our approach by focusing on three diverse domains: Medical Diagnosis (MD), Troubleshooting (TS), and 20 Questions. We use the following datasets pre- processed by 8 In Medical Diagnosis, patient initially reports a brief description of their symptoms, based on which the doctor asks questions diagnose the disease. The maximum number of turns T was limited to 6 in the experiments. Two datasets were used. The DX dataset [21] contains 104 doctor-patient dialogues and five diseases in test set. The MedDG dataset, which originally included over 17,000 conversations across 15 disease types, was refined by removing inconsistent samples. We used 454 high-quality samples for evaluation. Open-ended responses are allowed in MedDG to test the system's 's generalization capabilities in less constrained scenarios. Both datasets
7

---

limit interactions to 6 turns. In the Troubleshooting domain, customer support technicians interact with users identify faults in systems such as cars or electronic devices. We use the FloDial dataset 15]. containing 153 dialogues across 153 unique fault types. Maximum number of turns 7 was limited to 20. In the 20 Questions domain, the task involves identifying target item by asking up to 20 yes-or-no questions. The Common dataset includes 111 items spanning categories such as animals, places, food, and objects, and the Things dataset was filtered to include 200 items.
4.2 Baselines
We evaluate two primary baselines: Direct Prompting (DP) and the Uncertainty of Thoughts (UoT) framework H DP directly queries the L.LM to generate the next question without structured planning, serving as minimal-effort benchmark to highlight improvements achieved by strategic decision- making. UoT uses tree-based planning to expand question paths that maximize information gain. While effectivve in reducing uncertainty, its exhaustive tree exploration can be expensive. This baseline assesses the efficiency improvement of the proposed MISQ-HF approach, which selectively expands promising branches. Comparisons with Chain-of-Thougee (CoT) (20) and Tree-of- ofTTuhghttt (ToT)
12 are omitted, as prior work shows UoT consistently outperforms these methods.
4.3
Evaluation
We use three key metrics to evaluate our system's effectiveness and efficiency. First, Success Rate (SR) measures the percentage of cases where the system correctly identifies the target within the maximum allowed turns. Second, Mean Conversational length in Successful Cases (MSC) to track the number of turns required. Finally. we introduce a novel metric to track Question Generation Calls (QGC), defined the number of LLM prompting calls required for question generation during planning. LLM invocations constitute the dominant cost in both latency and resources. QGC offers a model-agnostic and reproducible signal of efficiency compared to variable wall-clock runtime.
4.4 Experimental Setup
Models. We employed three different LLMs of varying sizes the Questioner. Llama 3.3 70B Instruct (5) and Mixtral 8*7B Instruct [T0 were accessed via the AWS Bedrock (1. GPT-4o was accessed via API from OpenAl 13. The user (Answerer) was simulated by Llama 3.3 70B Instruct in tasks. We prompted the model with ground truth details (e.g., the patient's disease or fault description) and maintained separate conversation history. The temperature set to O. The ratio of turns was defined by d = 0.6.
MCTS implementation. We set the number of iterations K 10 and exploration constant C' 0.2. Maximum simulation depth de was set effectiveness. For each Q,, the LLM was prompted to generate m = 3 potential questions to maintain diversity. For the reward calculation RV)(v), , the scaling parameter was set to 0.4. Experiments were on an 8-core CPU with 16 GB RAM.
balance computational efficiency with search
Feedback mechanism. We used decay factor 7 0.9 for the bonus rewards. The cluster similarity threshold 7 was set to 0.9 in terms of cosine similarity. and the bonus scaling factor 3 was set to 0.2 for all tasks. Problem descriptions were embedded using DistilBERT (16) for the troubleshooting domain, and Clinical- -ERT [19 for medical diagnosis. To optimize computational efficiency, we cache the decision tree, allowing reuse across all samples within each dataset. The system tracks Mean QGC through thread-safe counter.
5 Results and Discussion
Table shows results in the Closed Set scenario. Our approach requires fewer QGC while maintaining higher SR compared to baseline methods, indicating both improved effectiveness and computational efficiency. Notably, the Q-aware Questioner consistently performs better as compared to when unaware. To demonstrate the importance of the feedback mechanism, we also report the results using MISQ, our framework without the hierarchical feedback component, to rationalize the design choice and support an ablation study.
Across both datasets in the MD domain, MISQ-HF achieves superior performance, with an overall average reduction of 6.77 times in Mean QGC over UoT. Notably, using Llama 3.3 70B, MISQ-HF

---

Table 1: Results MD and TS domains in Closed Set scenario. Ω-aware denotes whether the
Questioner Model was informed about the possibility space f2 at the beginning of the conversation.
MD: MedDG
TS: FloDial
Model
Method
P-aware
SRT
MSCJ
QGCL
SRT
MSCI
QGCL
SRT
MSCJ
QGCL
UpT
X
72.11
1.54
0.36
79.51
2.09
4,95
34.64
6.84
43.76
MISQ
X
75.00
2.17
0.05
86,56
3.39
0.40
35.29
9.09
3.99
Llama 3,3
MISQ-HF
X
80.76
1.94
0.21
86.78
3.29
0.78
39.86
9.09
4.07
70B Instruct
DP
88.46
3.15
84,14
3.93
21.36
13.72
U6T
79.80
1.65
0.77
89.86
2,16
4.84
60.78
8.47
44.61
MISQ
1.28
0.48
92.29
3.44
3.59
62.74
MISQ-HF
98.07
1.84
0.04
93.39
3.35
0.54
67.97
9.81
3.97
DP
50.00
3.50
76.43
3.91
16,99
14.23
Mixtral
UpT MISQ
76.92
1.43
0.45
83.70
2.19
5.70
39.21
7.01
45.11
8*7B Instruct
63,46
2.63
0.08
76.55
3.33
0.17
47.71
10.45
1.66
MISQ-HF
76.92
2.40
0.06
84.58
3,08
0.33
49.01
9.62
1.46
DP
73.07
3.48
81.27
3.98
43.79
14.86
UoT
82.69
1.18
0.17
88.79
2,03
1.81
59.47
8.14
41.86
GPT-4o
MISQ
87.50
1.97
0.05
89.20
3.46
0.60
74.50
10.15
4.10
MISQ-HI
99.03
2.19
0.03
90.30
3,42
0.41
72.54
10.36
2.94
Table 2: Results MD and TS Domain in Closed Set scenario, when the root node is initialized with the constrained set of possibilities Q. S Ω. Leads to improvement in SR and MSC.
MD: DX
MD: MedDG
TS: FloDial
Model
Ω-aware
SRT
MSCL
QGC|
SR
MSCJ
QGCL
SRT
MSC)
QGCJ
Llama 70B Instruct
85,57
0.93
0.20
80.61
2.81
6.13
43.13
6.83
28.26
98.07
0.96
0.21
89.20
2.67
4.09
72.54
8.25
23.35
Mixtral 8 Instruct
90.38
1.48
0.24
89.87
2.27
4.69
59.47
7.18
30.30
GPT-4o
99.03
0.54
0.05
92.95
2.15
3.69
78.43
7.18
13.47
required only 0.04 Mean QGC compared to UoT's 0.77 DX, showing 19.25 times reduction. Similarly, a reduction of 8.97 times is observed on MedDG. This efficiency stems from selective tree expansion rather than exhaustive exploration. In the medical domain, the cost of misdiagnosis far outweighs the overhead of a few additional clarifying questions. While MSC is marginally higher for MISQ-HF compared UoT, this trade-off can be overseen by the higher success rate of diagnosis, which directly impacts patient outcomes.
In the TS domain, MISQ-HF continues to excel with higher SR, surpassing UoT by 20.68% improvement on av- erage across the three LLMs. Our framework also achieves notable computational efficiency as compared to UoT, with average of 18.63 times reduction in Mean QGC. While troubleshooting conversations typically require more turns due fault complexity, MISQ-HF maintains a similar MSC (a difference of less than 3 turns on average) while delivering improved performance.
vs MISQ-HF (suparset) LCT
MedDG
FloDill
Table 2 reports the performance when we initialized the root as constrained set of possibilities. This generates more relevant questions early on, based on the user's 's prob- lem description. Figure shows the notable gain in SR using GPT-4o. On average, across the three I.LMs on MD datasets, we find that SR is improved by 27.52% over DP, 11.91% over UoT and 5.58% over MISQ-HF initialized with full superset. Across both domains, average of x8% gains were observed using constrained set. This comes with a trade-off in QGC, as the tree gets wider and increases the planning require- ments. Additional analysis, example conversations and prompts are provided the Appendix
0
20
40
60
80
100
Improvement
Figure 2: Gain in SR when using MISQ- HF initialized with a constrained set.

---

performance on the general information-seen -eeking domain, evaluated us- ing 20-Questions on Common and Things datasets. Due to lack of problem descrip- tion or initial hints about the target, we cannot evaluate MISQ-HF here. For both datasets, MISQ consistently outperforms UoT and DP in all three metries. These re- sults demonstrate the scalability of the pro- posed approach to larger possibility spaces. See Table in Appendix for statistical sig- nificance of performance gains.
Table 3: Results on 20 Questions Data: Closed Set
f2-
Common
Thing
Method aware
SR
MSCJ
QGC|
SRT
MSCJ
QGC|
Llama 3.3 70B Instruct
UoT
x
39.63
8.27
4.08
19.00
9.78
4.48
MISQ
41.44
8.43
5.05
23.5
9.57
1.57
45.94
13.70
32.50
13.27
UoT
61.26
9,94
7.92
35.50
11.43
3.40
MISQ
74.77
9.90
4.74
59.50
10.68
3.31
Mixtral 8 Instruct
DP
8.10
14.33
7.50
13.46
We report results for the Open-Set scenario in Appendix B and further validate our framework the Situation Puzzles bench- mark [27]. a challenging free-text reason- ing domain, in Appendix [ Overall, our extensive evaluation shows that the MISQ- HF outperforms other baselines datasets with different sizes of possibility spaces.
UoT
28.82
11.56
4.34
12.50
13.52
5.91
MISQ
37,83
11.38
2.39
20.00
11.50
0.06
GPT-4o
DP
63.06
14.72
40.50
14.16
UoT
74.77
8.59
5.88
47.00
9.13
2.75
MISQ
85.58
8.51
4.86
55.50
9.54
2.19
The hierarchical feedback mechanism enables the system to learn from successful questioning trajec- tories, especially in domains like troubleshooting and medical diagmosis, where similar cases often recur. Performance without hierarchical feedback (MISQ) further emphasizes the benefits of this approach. Compared to exhaustive methods like UoT (Table D. MISQ-HF achieves =000 reduction in Mean QGC while delivering 112% improvement in SR across these domains. This performance is underpinned by the LLM's capability to generate questions that provide near-optimal information gain. Our empirical analysis supports this, showing that the model achieves average possibility-saace split of 52.82 + 3.49%, thereby confirming the effectiveness of our reward formulation.
Limitations. The system currently does not incorporate mechanism to learn from mistakes in failure cases, which could potentially refine its decision-making process and adapt to edge cases more effectively. Penalizing redundant suboptimal quality of questions also requires careful design of reward function and remains an open challenge. Incorporating confidence metrics to better quantify uncertainty in risk-sensitive domains is another potential improvement. Addressing these limitations presents promising avenue for future research.
Conclusion
In this paper, we introduced Monte Carlo Tree Search for Information Seeking Questions with Hicrarchical Feedback (MISQ-HF), a novel framework that addresses fundamental limitations in adaptive question-askin
for goal-oriented conversational systems. Our approach makes three key contributions to the literature on conversational planning: (1) principled inference-time planning procedure for selecting optimal questions via selective tree expansion, (2) a hierarchical feedback mechanism that incorporates historical performance signals in the UCT formulation to modulate cotoratioonexpliiatattii trade-offs, and (3) an effective and efficient method that reduces the number of LLM calls made during the planning phase. Empirical validation across domains such as medical diagnosis, technical troubleshooting. and general information seeking demonstrates substantial improvements in task performance, while reducing and resource utilization by order of magnitude. The observed gains in constrained possibility spaces further suggest promising avenues for integration with domain-specific knowledge structures.
The broader implications of our work extend beyond immediate performance metrics address fundamental challenges in human-machinn collaborative problem-solving. By combining structured planning with adaptation mechanisms derived from historical interactions, we establish a foundation for conversational AI systems capable of reasoning under uncertainty. Future directions include extending MISQ-HF to multi-agent settings, integrating explainability into planning, and investigating theoretical convergence under varying domain characteristics. We posit that MISQ-HF represents a significant step toward conversational systems that can engage truly adaptive, efficient, and goal-directed information acquisition-al critical capability for next-generation AI assistants.
10

---

Acknowledgements
This work is supported by the National Science Foundation (NSF) award IIS-2336769. The authors thank Hafsah Usman, student of the University of Washington, Seattle, for her valuable assistance in running a part of the experiments.
References
[1] A. B. API. Build Generative AI Applications with Foundation Models Amazon Bedrock AWS, 2023. (tLLhttts:///
amazon. com/bedrock/
[2] G. Chaslot, S. Bakkes, I. Szita, and Spronck. Monte-carlo tree search: new framework for game ai. In Proceedings the Fourth AAAI Conference on Artificial Intelligence and Inteructive Digital Entertainment, AIIDE 08, page 216-217. AAAI Press, 2008
[3] G. Chaslot, Bakkes, I. Szita, and P. Spronck. 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
[4] T. Dam, G. Chalvatzaki, J. Peters, and J. Pajarinen. Monte-Carlo Robot Path Planning. IEEE Robotics and Automation Letters, URL pttp/ttsss:/ieeeeeppaee
Oct. 2022. ISSN 2377-3766. doi:
10.1 2tw.H/AA..02..1999990
ieee
9886033
[5] A. Grattafiori, Dubey, Jauhri, A. Pandey, A. Kadian, A. AI-Dahle, A. Letman, A. Mathur, A. Schelten, A. Vaughan, A. Goyal, A. Hartshorn, A. Yang, A. Sravankumar, A. Korenev, A. Hinsvark, A. Rao, A. Zhang, A. Rodriguez, and A. Gregerson al. The Llama Herd of Models, Nov. 2024. URL htttp://axiiv... org/ wbwg/baa//aaa abs////a//// 21783 arXiv:2407.21788
[6] A. Guez, T. Weber, I. Antonoglou, K. Simonyan, O. Vinyals. D. Wierstra, R. Munos, and D. Silver. Learning to search with MCTSnets. In Proceedings of the 35th International Conference on Machine Learning, pages 1822-1831. PMLR, July 2018. URL https://
gww.gueeeaa1. proceedings mlr. /r..ss/////guueel....... html
[7] M. N. Hebart, A. H. Dickter, A. Kidder, W. Y. Kwok, A. Corriveau, C. V. Wicklin, and C. I. Baker. THINGS: A database of 1,854 object concepts and more than 26,000 natu- ralistic object images. PLOS ONE, 14(10):00233792, Oct. 2019. ISSN 1932-6203, doi:
1..1371/journal.pomm 0223399. URL wttthttps:////// htttps://jourrnaaaa 1d=10.1371/3
plos. org/ plwsson/aaticclee"
pone. 0223792
[8] Z. Hu, C. Liu, X. Feng. Y. Zhao, S.-K. Ng. A. T. Luu, J. He, P. W. Koh, and B. Hooi. Uncertainty of Thoughts: Uncertainty-Aware Planning Enhances Information Seeking in LLMs. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, Nov. 2024. URL
[9] W. Hui and K. Tu. RoT: Enhancing Large Language Models with Reflection on Search Trees, July 2024. URL http://///// wttp://wwwww...///////./0.0.
arXiv:2404.05449 [cs].
[10] A. Q. Jiang, A. Sablayrolles, A. Roux, A. Mensch, B. Savary, C. Bamford, D. S. Chaplot,
D. d. I. Casas, E. B. Hanna, F. Bressand, G. Lengyel, G. Bour, G. Lample, L. R. Lavaud,
L. Saulnier, M.-A. Lachaux, P. Stock, S. Subramanian, S. Yang, S. Antoniak, T. L. Scao, T. Gervet, T. Lavril, Wang, T. Lacroix, and W. E. Sayed. Mixtral of Experts, Jan. 2024. URL org/ / 2401. 04088 LtXiv:2401.040% [cs].
http://arxiv. wwaesiiivrrg//aae
[11] L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In J. Fürnkranz, T. Scheffer, and M. Spiliopoulou, editors, Machine Learning: ECML 2006, volume 4212 of Lecture Notes in Computer Science, pages 392-293. Springer, Berlin, Heidelberg, 2006. ISBN 978-3-540- 45375-8. doi: 10.1007/11877
29. URL https:/t/:///... org/ 10. 1007 1117/101711/1111...
[12] S. S. Li, V. Balachandran, Feng. J. S. Ilgen, Pierson, P. W. Koh, and Y. Tsvetkov. MediQ: Question-Asking LLMs and Benchmark for Reliable Interactive Clinical Reasoning. In The Tiiht Annual Conference on Neural Information Processing Systems, Nov. 2024.
[13) OpenAI, Achiam, S. Adler, Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, R. Avila, I. Babuschkin, S. Balaji, V. Balcom, P. Bal- tescu, H. Bao, M. Bavarian, J. Belgum, and I. Bello al. GPT-4 Technical Report, Mar. 2024. arXiv:2303.08774 [cs].
BtLptt/::/ //wvvvaaivvvvv/aa hbrp/bb/223000 08774

---

[14] P. Putta, E. Mills, N. Garg, S. Motwani, C. Finn, D. Garg, and R. Rafailov. Agent Q: Advanced Reasoning and Learning for Autonomous Al Agents, Aug. 2024. httt:////arxxx org/ abs/2408 07199, arXiv:2408.0711 19999
[15) D. Raghu, S. Agarwal, S. Joshi, and Mausam. End-to-End Learning of Flowchart Grounded Task- Oriented Dialogs. In M.-F. Moens, X. Huang, L. Specia, and S. W.-t Yih, editors, Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 4348- 4366, Online and Punta Cana, Dominican Republic, Nov. 2021. Association for Computational Linguistics. doi: 10. wttp5///122221.elm-mmooo 2021. emnlp- maillppmmii... 357/
URL httts:://aclaatthh///a// org/
[16] V. Sanh, L. Debut, J. Chaumond, and T. Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. ArXiv, abs/1910.00100. 2019.
[17] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrit- twieser, Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap. M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis. Mastering the game of Go with deep neural networks and tree search. Na- ture, 529(7587):484-489, Jan. 2016. ISSN 1476-4687. doi: 10. 10.1038/nature16661 URL
https://wai http:://wwwwnauur.e..mmmm
nature. http://eeeeeoeeetcceeeeeeeattaaa
[18] D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap. K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi. and Go through self-play. Science, 362(6419): 1140-11 1144, Dec. 2018. doi: 10.1 16t11//eeceeeaarreee.o.. /126/science doi/10. 1126/ science. aar6404
URL https: htwp::///www... www.ww/wcienc..... org/
[19]
G. Wang. X. Liu, Z. Ying, G. Yang, Z. Chen, Z. Liu, M. Zhang, H. Yan, Y. Lu, Y. Gao, K. Xue, X. Li, and Y. Chen. Optimized glycemic control of type 2 diabetes with reinforcement learning: proof-of-concept trial. Nature Medicine, 29 2910):263332242 Oct. 2023. ISSN 1546- 170X. doi: 10. 19918/444511-02-02255
URL htttps://ww..nr nature. com/ coom/artillss
841591-023 023- 022-02522---2
[20] J. Wei, X. Wang, D. Schuurmans, M. Bosma, B. Ichter, F. Xia, E. H. Chi, Q. V. Le, and D. Zhou. th-tuut prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, pages 24824-24837, Red Hook, NY, USA, 2022. Curran Associates Inc ISBN 978-1-71387-103
[21] L. Xu, Q. Zhou, K. Gong, X. Liang, Tang, and Lin. End-to-End Knowledge Relational Dialogue System for Automatic Diagnosis. Proceedings of the AAAI Conference on Artificial Intelligence, 33001):7366-7333, July 2019. ISSN 2374-3468. doi: 1609/aaa
v33101.33017333
BtL.tttps: aaai org/ index.iddxx///// http:/iinnxxppppppee htpp/AAA//article//aaae v//22/222w/// 4722
[22] S. Yao, D. Yu, J. Zhao, I. Shafran, Griffiths, Y. Cao, and K. Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Ad- vances in Neural Information Processing Systems, volume 36, pages 11809-11822. 2023. URL https::/prroceedee (
nww.ips.eippp. www..ae.....pppprrreeeeee.. filaaperrrlle//eeeeeeeeeeeeeeeer fww.fffllaappleee /appr//0222///1le//// h/tpp//ppp////s//ppp////////////
Conferrnce pdf
[23] X. Yu, M. Chen, and Z. Yu. Prompt-Based Monte-Carlo Tree Search for Goal-oriented Dialogue Policy Planning. In H. Bouamor, J. Pino, and K. Bali, editors, Proceedings of the 2023 Con- ference on Empirical Methods in Natural Language Processing, pages 7101-7125, Singapore, main..39,
Dec. 2023. Association for Computational Linguistics. doi: 10. URL BRLLhttp::/// htttps://aclatthllllee/
argg2023 emnlp- waapppmmiin.... main.439/
[24] X. Yu, B. Peng, V. Vajipey, H. Cheng, M. Galley, J. Gao, and Z. Yu. Exact: Teaching ai agents to explore with dffective-mets and exploratory learning. In Proceedings of the International Conference on Learning Representations (ICLR) 2025, 2025. URL https Poster paper.
//openrevie httpe/viiwnnentffrroneeeeee www.nnee//formmme wiw.ummmdidddiiiiSiiSG
[25] Z. Zhao, W. S. Lee, and D. Hsu. Large language models as commonsense knowledge for large-scale task planning. In Proceedings of the 37th International Conference Neural Information Processing Systems, NIPS '23, pages 31967-31987, Red Hook, NY, USA, May 2024. Curran Associates Inc
12

---

[26] A. Zhou, K. Yan. M. Shlapentokh-Rothmee H. Wang, and Y.-X. Wang. Language agent tree search unifies reasoning, acting, and planning language models. In Proceedings of the 41st International Conference on Machine Learning, ICMII'24. JML.Rorg 2024.
[27] Z. Zhou, X. Feng. Z. Zhu, J. Yao, S. Koyejo, and B. Han. From passive to active reasoning: Can large language models ask the right questions under incomplete information? In Proceedings of the 2025 International Conference on Machine Learning (ICML) - Poster Session, Jul 2025. pett:foorumm.ddeCCTTPppyarr
URL httpt::// htttp:://pperrviieee
[28] Y. Zhu, L. Pang, Y. Lan, H. Shen, and X. Cheng. Adaptive Information Secking for Open- Domain Question Answering. M.-F. Moens, X. Huang, L. Specia, and S. W.-t. Yih, editors, Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pages 3615-3626, Online and Punta Cana, Dominican Republic, Nov. 2021. Association for Computational Linguistics. doi: 10.18653/v 1/001//mmmmmmmmmmmmm2299999 293. URL https://
ac.lanthology.org/22000 htg/20221.mmlppmmainn
13

---

Appendix
A Improvement in Success Rate with 2g
Figure 3 demonstrates the % Change reported in Table 4 We find that additional 8% gain in success rate is observed on average when we start with a constrained set of possibilities as compared full superset of possibilities using MISQ-HE. Even larger gains are observed compared to baselines UoT and DP.
70B Instruct
DX
Liarna 3.3
MedDG
FloDial
Mixtral 8'7B Instruct
DX
MedDG
FloDial
DX
GPT-40
MedDG
MISQ-HF
VS UoT
FloDial
www00000
DP
50
100
150
200
250
% Improvement in Success Rate
Figure 3: Improvement in Success Rate on MD and TS Domain in Closed Set scenario, when initializing the root node with constrained set possibilities Q. C Ω.
Table 4: Improvement in Success Rate MD and TS Domain when using MISQ-HF-c, that is, initialization of root node with the constrained set of possibilities Ω S Ω. MISQ-HF-s denotes initialization from full superset the root node.
Change over
Change over UoT
% Change over MISQ-HF-s
Model
Dataset
DP
UoT
MISQ-HF
MISQ-HF-c
DX
73.07
82.69
99.03
99.03
35.52
19.76
0.00
GPT-4o
MedDG
81.27
88.79
90.3
92.95
14.37
4.68
2.93
FloDial
43.79
59.47
72.54
78.43
79.10
31.88
8.12
DX
88.46
79.8
98.07
98.07
10.86
22.89
0.00
Llama 3.3
MedDG
84.14
89.86
93.39
89.2
6.01
-0.73
-4.48
70B Instruct
FloDial
21.56
60.78
67.97
72.54
236.45
19.35
6.72
DX
50.0
76.92
70.19
90.38
80.76
17.49
28.77
Mixtral
MedDG
76.43
83.7
84.58
89.87
17.58
7.371
6,25
8+7B Instruct
FloDial
16.99
39.21
49.01
59.47
250.03
51.67
21.34
For testing significance, we conducted the experiments in Table 5Jasing the LlaMA 3.3 70B Instruct as Questioner model, in the closed set, Q-aware scenario. Each experiment was run three times. and we report the mean and standard deviation of the evaluation metrics. For success rate (SR), we state-of-the-an UoT model across datasets, with statistical significance at p < 0.05 based on paired t-tests. Due to limitations in L.MM API quotas and the costs associated with hosting large models, the number of experiments was restricted; however, ensured that evaluations were performed for every dataset to provide comprehensive coverage.
find that MISQ-HF significantly outperforms
14

---

Table 5: Comparison of UoT and MISQ-HF initialized from a constrained set of possibilities. Values denote mean + standard deviation.
Dataset
Method
SR1
MSCI
QGC
UoT
74.36 + 5.23
1.77 0.20
0.66 = 0.09
DX
MISQ-HF
94.55 + 2.52
1.30 0.24
0.39 + 0.13
UoT
85.02 + 1.00
2.16 2 0.09
5.19 + 0.17
MedDG
MISQ-HF
88.84 = 0.27
2.79 0.19
4.81 0.99
UoT
63.83 + 2.22
8.26 0.52
43.89 2.32
FloDial
MISQ-HF
75.82 + 2.33
8.11 # 0.31
24.70 + 5.82
UoT
65.47 = 3.06
9.49 0.50
6.12 1.29
Common
MISQ-HF
78.98 + 2.97
9.67 = 0.20
4.22 = 0.41
UoT
37.17 + 1.70
10.76 0,48
5.01 # 1.95
Thing
MISQ-HF 54.33 + 3,70
10.19 0.37
3.05 # 0.26
B Open Set Results
The results in the Open Set scenario demonstrated two datasets where the range of possible outcomes is often unpredictable and varies in size. Problem descriptions were used to initialize 12 to a set of 5 possibilities, and it was progressively updated based conversation history. We used FloDial for troubleshooting, which has a larger possibility space, and DX for medical diagnosis, which has a smaller possibility space. Table shows consistently lower Mean QGC while maintaining similar SR in both domains.
Table 6: Results in the Open Set scenario. Possibility set Ω is unknown to the Questioner LLM.
FloDial
DX
Method
SR
MSCJ.
QGCJ
SR1
MSCJ
QGCJ
DP
16.99
14.80
29.80
3.22
UoT
28.10
7.56
11.42
35.57
2.35
10.22
MISQ
28.
8.02
5.33
36.53
2.73
6,52
MISQ-HF
28.75
6.95
5.10
37.50
2.35
6.32
C Results on Dataset: Situation Puzzles
To demonstrate the robustness of our framework in challenging open-set domain, we evaluated MISQ on the Situation Puzzles (SP) benehmark (27] This task requires the LLM, acting as detective, to ask series of yes/no questions to narrow down free-text explanations for a mystery, presenting an inherently open-set reasoning scenario. SP benchmark originates from concurrent work [27] and is thus included as supplemental results.
Unlike the closed-set domains where the possibility space Ω is known and fixed, SP requires asking logical, case-specific questions to identify unique, free-text explanations for every puzzle. This open-set nature requires an adaptive approach:
1. Initialization: We initialize the candidate set Ω with possibilities generated from the puzzle description after two initial question-answer turns.
2. Dynamic Update:
During the information-seeking phase, Ω is updated dynamically when- ever the set remaining candidates narrows down to two possibilities. This process refines the candidate set based on the collected clues to guide the subsequent questioning strategy.
We compare the performance of Direct Prompting (DP), Uncertainty of Thoughts (UoT), and MISQ (our method without Hierarchical Feedback). In this setting, the direct reuse of prior successful search paths (MISQ-HF) is less meaningful, as each case demands a unique questioning path shaped by different possible explanations. Note that MISQ still offers clear advantages over UoT as its
15

---

boudback-driver scoring within a single episode prioritizes high-utility questions, effectively reducing redundancy in the search tree.
In T we report the SR, MSC, and QGC on the Situation Puzzles test set (100 mystery puzzles) under maximum allowed turns (7 maxx of 10 and 25. The results show that MISQ improves the Success Rate while reducing the number of turns in conversation and Question Generation Calls compared to UoT, further validating the efficiency of our core search strategy even in complex open-set environments.
Table 7: Performance on the SP benchmark under different turn limits. MISQ offers clear advantages over the state-of-the-art UoT by prioritizing high-utility questions, significantly reducing QGC.
Taax 25
Tmax 10
Method
SR t
MSC
QGC
SR t
MSC 1 QGC
DP
57.0
14.89
39.0
6.33
UoT
62.0
10.55
6.79
51.0
5,40
6,47
MISQ
66.0
6.77
5.18
54.0
5.07
3.91
D Measure of Efficiency
Our primary measure of efficiency is the reduction in LLM calls, as these model invocations lead to the dominant cost in practice, considering both the latency (time consumed by API calls) and resource demands (higher cost) of LLM inference. In Table we report wall-clock runtime estimates for every MCTS-base decision step, which includes the latency of any required LLM API calls, alongside the time taken by MCTS algorithm's auxiliary operations. However, this total runtime is highly susceptible to hardware and parallelization variability, making it unreliable proxy for true algorithmic expense. Therefore, we emphasize that our main metric centers on reducing the number of these expensive invocations (QGC in Table 1), as it offers a model-agnostic, reproducible signal of efficiency consistent across different hardware environments. Crucially, this efficiency compounds over time because both the standard MCTS selection process and our hierarchical feedback mechanism enable the system to increasingly reuse high-reward paths, leading to a significant long-ten term decrease in both the total number of calls and overall runtime, thereby reinforcing the practical value of the approach especially in resource-constraiiee settings.
Table 8: Average wall-clock time (in seconds) for one MCTS-based question selection step (decision turn) in the closed set scenario, using Llama 3.3 70B.
Method
DX
MedDG
FloDial
UoT
0.41 +: 0.79
2.89 + 4.04
15.57 + 14.26
MISQ-HF
0.35 + 0.22
3.25 + 0.81
8.66 = 1.20
E
Broader Impacts
The proposed framework enhances goal-oriented conversational systems in domains like medical diagnosis and troubleshooting. By optimizing question-asking strategies, it improves decision-making success rates with reduced computational overhead. This can lead to more efficient diagnostic systems and customer support interactions, potentially benefiting both users and service providers. While general concerns about privacy and trustworthiness in LLMS persist, they are not specifically pertinent to the proposed system in this work. However, we acknowledge that use of LLMs as core component of a system inherently brings challenges related to privacy and model biases, which must be carefully managed to ensure responsible deployment and maintain user trust.
While MISQ-HF is optimized for algorithmic efficiency, the practical deployment of such a system must consider the importance of user-centered design and conversational norms. The selection of questions must incorporate balance which can be achaived by tuning the exploration component of UCT to sometimes favor questions that, while perhaps not strictly optimal in Information Gain,
16

---

necessary to establish user trust, confirm initial context, align with expected dialogue flow. Future work should investigate reward shaping that explicitly penalizes questions that violate conversational norms or are perceived as overly abrupt by human evaluators.
F Conversation Prompts for 20 Questions
F.1 Questioner Prologue
Let us play the game of 20 questions. am impersonating the thing. X. (inform_set) You will ask up to 20 questions which 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.
(inform_set)
"X is possibly one of the following: Q "
This is given only once the beginning of the conversation.
F22 Answerer/User Simulator Prologue
Let us play the game of 20 questions. You are the answerer and I am questioner. X is (target_item)" I will ask you up 20 questions and you should answer each one truthfully based on being X, by saying Yes or No. Note that you must never reveal X. until guess correctly. If I guess X correctly in my question, directly respond "You guessed it. X is "(targetjitem""" instead of saying yes. Let us begin. Here is my first question.
Starget_item)
the ground truth target item based on which user responds
F33
Targeting Prompt
Note that you should guess and ask what X exactly is from now on. X is possibly one of the following: {item_set set___e__t__ set_terminal), or other from the initial set of possibilities. Use the past conversation for context to avoid redundant questions. The question must start with 'Is X
jiten_set_terminal]
fy (the set of items remaining at leaf node v)
Target Question: X (itemm??
F.4
Question Generation Prompt
Here all the X: (item_set)
Design question about X that can only be answered by Yes or No. Then classify the possible above based 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!
Sincestral_conter.
Based on this information, create most relevant {m} questions to classify the above correctly, Your response should strictly follow the template:
Question 1: X ...?
YES: comma- separated, list of things,
Count of YES:
NO: comma-separadee list of things, Count of NO:
17

---

(item_set)
fy (the set of items remaining at node v)
(ancestral_context)
"For context, following questions were already asked to build the above set of possibilities: Question? No: Question? Yes; Question? Yes..." " if ancestral question nodes exist, else blank string.
{m}
number of potential questions to generate (actions)
G
Conversation Prompts for Medical Diagnosis
G.1 Questioner Prologue
You are doctor, and your patient self-reports that: should ask your patient questions in English regarding their symptoms which can only be answered by Yes or No, in order to diagnose what disease this patient suffers. Carefully review the patient's problem and the ongoing conversation. Avoid redundant questions. Let us begin. Ask me the first question.
{inform_ser (eroommmsetr>>__ You
The text "which can only be answered by Yes or No is omitted in case of free-answer conversations.
G.2 Answerer/User Prologue
You are the patient suffering from "(target_item?) and am the doctor. will ask you up to questions, and you should answer each one truthfully based on your disease, by saying Yes or No. Note that you must never reveal the disease until mention or ask about it. mention your disease in my question ask about its symptoms, then you must directly respond "You right. I am experiencing (target_item)". while saying Yes. Let us begin. Here is my first question.
In the beginning of the conversation:
You are patient suffering from the disease of "(target_item" and communicating with a doctor. Here is your conversation history with another doctor: (coov_historyy>
Remember the conversation above to answer current doctor's question in English and do not reveal the disease until the doctor correctly mentions or asks about it. If the doctor mentions your disease in their question or asks whether you experience item, you must directly respond "You are right. I experiencing "harget_item]"
G.3 Question Generation Prompt
You are a doctor. Here are all the possible diseases that the patient may suffer from: (item_set)
Design a question to ask your patient regarding symptoms of their illness that can only be answered by Yes No. Then classify the possible diseases above based this question. If the answer is 'YES', put this disease into 'YES: ...,, otherwise to 'NO: .... Finally calculate how many diseases are in YES and NO. Notably, this question should fulfiil that the count of YES and NO are almost the same with a permissible discrepancy of no more than one! fancestral. 3l__tttte
Based on this information, create most relevant (n) questions to ask (and classify the above diseases). Your response should strictly follow the template: Question 1: ...?
YES: comma-separee samaaateeaatted, list disease names,
Count of YES:
NO: somma-separated, list of disease names,
Count of NO:
18

---

G.4 Targeting Prompt
Note that you should point out and ask what disease the patient suffers from now. The patient is likely suffering from one of the diseases below: from the initial set of possibilities.
other
Refer the past conversation about patient's symptoms. Never ask redundant questions. Respond with new question only, following the format: "Are you experiencing [disease name]?" Ensure that [disease name] was not asked before.
Target Question: Are you experiencing "(item}"?
G.5 Classify Prompt
Here all diseases that the patient may suffer from: {item_set}
derpeeepddccriiioonn/ According to the patient's symptoms, classify each possible disease given in the above set into 'YES:... ...' if even slightly possible, otherwise to 'NO: if completely unlikely. Only classify the diseases in above given set, do not add anything else. Your answer should be like: YES: comma-separated, list of disease names, NO: comma-separated, list of disease names,
G.6
Open Set Prompts
Initial Prompt:
You are doctor, and your patient self-reports that: senedddecrppiion. Please propose {size} diseases that you think your patient may suffer from. Your response should only be list like: ["diseasel", "disease2", ...]
Renewal Prompt:
Based on the conversation history, please propose {size) diseases that your patient may suffer from. The list of {size} diseases should contain peristing_itemsst Your response should only be list like: ["diseasel" "disease2",...
H
Conversation Prompts for Troubleshooting
H.1 Questioner Prologue
You technician, and your client self-reports that: gerrolem__escriptii You should ask your client questions with specific situations which can only be answered by Yes or No, in order to find which issue this client is facing. Use the ongoing conversation for context to avoid redundant questions. Let us begin. Ask me the first question.
[inform_set]
H.2 Answerer/User Prologue
You are the client with device that has '[target_itens and am the technician. I will ask you up to 20 questions, and you should answer each one truthfully based on the issue of your device, by saying Yes or No. Note that you must never reveal the issue name until tell it correctly. If tell your issue correctly in my question, directly respond: "You are right. My device has issues with "(target_item?) Let us begin. Here is my first question.
H.3 Question Generation Prompt
You are technician. Here are all the issues that the client may face: {items_set}
Design question ask your client with a specific situation that can only be answered by YES or NO. Then classify the possible issues above based on this question. If the answer is 'YES', put this issue into 'YES: ...', otherwise to 'NO: 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!
Finally calculate how many issues are YES and
sancestral_conterr
19

---

Based on this information, create the most relevant {n) questions to classify the above issues correctly. Your response should strictly follow the template:
Question 1: ...?
YES: comma-sepane -spaaaated list issue names,
Count of YES:
NO: comma-separated, list of issue names, Count of NO:
H.4 Targeting Prompt
Note that you should now point out and ask what issue the client facing. The client is likely be so you must consider these. Refer the past conversation for problem context. Respond with new question only, follow the format: "Are you experiencing [issue name]?" ? Ensure that [issue name] was not asked before.
facing one of the issues below: {item_sett seeem__sttterrnneeee
Target Question: Are you experiencing "(item}"?
H.S Classify Prompt
Here are all the issues that the client may face: {item_set}
{problem description) According the user's problem, classify each possible issue given in the above set into 'YES: ...'ff even slightly possible, otherwise to 'NO:... absolutely unlikely. Only classify the issues in above set, do not add any other. Your answer should be like: YES: comma-separated, list of issue names,
NO: comma-separated, list of issue names, ...
H.6
Open Set Prompts
Initial Prompt:
You technician, and your client self-reports that: crrroblemddscrrpttie Please propose (size} issues that you think your client may face with. Your response should only be a list like: ["issuel", "issue2".
Renewal Prompt:
Based on the conversation history, please propose {size) issues that your client may face with. The list of (size) issues should contain (existing_item) ittmms). Your response should only be a list like: ["issuel", "issue2",
I Examples
Two sequences of history are maintained respectively for Questioner LLM and User (Answerer LLM). Each stores the questions asked and answers given so far. At the beginning of the conversation, the Question LLM is given the Questioner Prologue as the first prompt, and the Answerer LLM is given the Answerer Prologue as the first prompt. The rest of the conversation history remains the same. except for the switching between the "system" role and the "user" role for each LLM. Table I0 show example conversations from three domains.
20

---

Table 9: An example conversation from FloDial dataset using MISQ-HF with GPT-4o.
S.No. System
User
Problem Description:
My car continues overheat. The hood is so hot that think could melt cheese on the hood! Please help.
1
Is the issue related to the vehicle's brak- No.
ing system?
2
Is the issue related to power or electri- No.
cal problem?
3
Is the issue related to overheating tem- Yes. perature control?
4
Is the issue related to mechanical part? Yes.
5
Is there any visible fluid leaking from Yes. the vehicle?
6
Are you experiencing a radiator leak? You are right. It's a Radiator leak.
Table 10: An example conversation from MedDG dataset using MISQ-HF with GPT-4o.
S.No. System
User
Problem Description:
At the age of 28, recently there has been slight pain both sides of the stomach, the stomach has been bothering for a few days, the stool is slightly bloody, and the stomach slightly painful, but comes in waves.
Do you experience Actually, I've been experiencing burning sensation my stom- symptoms that ach, and it seems to be triggered by certain foods and activities. including drinking alcohol. The pain usually on both sides of my stomach and comes in waves. I've also had some bloody stools recently. However, I'm not sure if fatty foods specifically make it worse, but do feel like my stomach is more bothered after drinking or eating certain things.
worsen after eating fatty foods?
2 Do you experience abdominal pain that improves after cat- ing?
The pain in my stomach is a bit unpredictable, but it doesn't really fact, sometimes feel like my stomach is burning, and it can be uncomfortable. The pain is usually on both sides of my stomach and comes waves. It's been bothering me for about 20 days now, and I've also had some other symptoms like slightly bloody stools.
seem to improve after eating.
3 Are you experienc- ing a gastric ulcer?
No, I'm not sure about that. I've been having some stomach issues, like pain on both sides of my stomach, and it's been bothering me for about 20 days. I've also had some other symptoms like slightly bloody stools and a burning sensation in my stomach. But haven't been diagnosed with gastric ulcer. I did talk to another doctor who suggested I take some medication, omeprazole, to help with my symptoms. You are right. have Gastritis.
4
Are you experienc- ing gastritis?
Table 11: An example conversation from Common dataset using MISQ with GPT-4o.
S.No. System
User
1
Is X living organism?
Yes.
2
Is X an animal that primarily lives in water?
No.
3
Is X type of food?
No.
4
Is X mammal?
No.
5
Is X capable of flight?
No.
6
Is X reptile?
Yes.
7
Is X capable of changing its skin color for camouflage?
Yes.
8
Is X 'Chameleon'?
You guessed it. X is Chameleon.
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's 's contributions and scope.
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 be 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 to other settings.
is fine to include aspirational goals as motivation as long as 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:
Limitations are mentioned separately under Results and Discussion section.
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 a separate "Limitations" section 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 how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on 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 is low 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 used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
22

---

The paper provides clear formulations of the theoretical constructs, including the reward structure and MCTS algorithm, with detailed equations and explanations. The focus is applying and adapting these constructs to the proposed framework rather than deriving new theoretical guarantees. Reward structure is adapted from prior literature which includes the complete proofs. These references are appropriately cited in the relevant sections.
Justification:
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 in the 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 are encouraged to 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
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide a detailed algorithm and all necessary descriptions of the proposed architecture and its components.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
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 it possible for others to replicate the model with the same dataset, 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 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 NeurIPS 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) the contribution is primarily a new algorithm, the paper should make clear how 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 (c.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 are welcome describe the partieular way they provide for reproducibiliity In the case of closed-source models, it may be that access to the model is limited in
23

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide a publicly available link to well-documented code and data.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
mublic/guided CodeSuumisssoonollo.....ooooo
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is 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 reproduce the results. See the NeurlPS code and data submission guidelines (https http/ooeeuummmsssooooosssseeeeee
//nips wwwpli//guudee/e/eeeeeeeeeee
for more details.
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. If 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 (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Reported in Section 4.4 Experimental Setup.
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 a 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, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report the statistical significance of the results in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
24

---

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, or 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 1-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 show in tables figures symmetric error bars that would yield results that are out 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 execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Reported in Section 4.4 Experimental Setup.
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 compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: httee://eeuuuiieee hww.rpuu...../. cwteriisscccpppuieee ccc//ubllc/ttiicccuidel......
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
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 (c.g.. if there special consid- eration due to laws or regulations in 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: Mentioned in Conclusion and Section E of Appendix.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
25

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess 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 tied to particular applications, let alone deployments. However, if there is 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 out 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.
If 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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper does not pose any 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 usage guidelines or restrictions to access the model or implementing safety filters.
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
Question: Are the creators or 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?
Answer: [Yes]
Justification: Data sources, models and code used in the paper properly cited, and URLs are provided wherever applicable in references.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a 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.
26

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/dataseta
latasets.paperssit
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
We provide publicly available link to our code repository.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/coodemmodll 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 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 details about compensation (if any)?
Answer: [NA]
Justification: The study does not involve crowdsourcing or human subjects; all interactions are simulated using LLMs
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According 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: Since the research involves simulated interactions with LLMs and not real human subjects. IRB approval is not applicable.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

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 we expect authors to adhere to 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.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: The Problem Formulation and Method sections describe the use of LLMs (e.g.. Llama 3.3 70B, Mixtral 8*B,, GPT-4o) as essential components for question generation and response simulation, aligning with the proposed framework.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should not be described.
http://uipppscccooeeeeeeeeeeeeee /
28


Reviews:
[{"review_id": "NcfNn1adiJ", "reviewer": "Reviewer_m8dK", "summary": "They bolt feedback-aware MCTS onto an LLM, recycle good question paths, and end up diagnosing faster and cheaper than vanilla planners, but the trick still struggles without a fixed answer list and never punishes bad decisions.", "questions": "See Strengths And Weaknesses", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nBy folding Monte-Carlo Tree Search around an LLM, the system asks dramatically fewer questions yet lands on the right answer more often. It reuses a single search tree across cases, cashing in on past successes, and the cluster-based bonus gives it a built-in memory that nudges the planner toward historically efficient moves. Tests across medical triage, fault diagnosis, and even a 20-Questions game show double-digit accuracy gains while slashing API calls by roughly an order of magnitude, and it works with everything from Llama 3 to GPT-4o—so the gains come from the search strategy, not some hidden model magic.\n\nWeaknesses:\n\nThe method reinforces only successful branches—there’s no penalty signal—so it keeps repeating bad ideas instead of learning from them. When the answer space is open-ended, its hit rate drops to ~28 %, showing the approach doesn’t generalize well outside neatly bounded domains.", "was_revised": true, "final_justification": "The authors address my concerns, I will support to accept this paer.", "rebuttal": "Thank you for thoroughly reviewing our paper and sharing your feedback. \n\nWe appreciate your positive recognition of our method’s core strengths, including the practical efficiency of feedback-aware MCTS along with the system’s memory and reuse abilities. Below, we address the two main weaknesses you identified.\n\n---\n\n> ### W1. Lack of Penalty Signals\n\nOur feedback mechanism is designed so that positive rewards are propagated only along successful questioning trajectories, that is, when the system solves a case, those specific question nodes receive a bonus, making them more likely to be chosen for similar future problems. As a result, effective questions in the beginning are reinforced and preferred in analogous contexts, improving efficiency and accuracy over time.\n\nHowever, in this work, we do not actively penalize failed questioning paths when a trajectory does not succeed. They are neither incentivized with a bonus reward nor punished, effectively remaining **neutral** in the search process. We would like to highlight that the absence of feedback **does not lead to repeating bad ideas**. Importantly, because MCTS uses visit counts and average reward estimates to guide selection, low-reward nodes naturally become less likely to be explored again. In practice, when our system encounters a new case that does not correspond to any known cluster or lacks prior successful trajectories, it **defaults to standard MCTS behavior** without using bonus term. This means such cases proceed without any inherited bias from past failures, eliminating the risk of getting stuck on repeatedly unsuccessful paths.\n\nAssigning a simple penalty signal presents certain challenges. \n* Penalizing every failure could introduce **noise** in the learning process, as a question that is unhelpful for one specific scenario might be the right choice for another that is only subtly different. \n* Propagating negative feedback uniformly could suppress useful exploration or inadvertently **destabilize** long-term learning.\n\nCrafting an effective penalty mechanism in this setting **is non-trivial** and requires careful consideration to avoid discouraging paths that may actually be valuable in neighboring problems. Approaches such as confidence-weighted penalties, where only repeatedly unsuccessful and low-confidence trajectories are penalized, represent promising directions.\n\nWe have discussed this challenge in our **Limitations section (line 353)** and will expand our rationale and potential solutions in the revised version. We sincerely acknowledge that this represents a valuable avenue for future work.\n\n---\n> ### W2. Generalization in Open-Ended Domains\n\nThe primary reason for the overall drop in hit rate in open-set domains is the combinatorial complexity and ambiguity of unconstrained target spaces, which make the task inherently more difficult, ***affecting not just our approach but all other planning methods*** [Hu et al., 2025]. In such settings, the system must not only generate effective questions but also dynamically construct the set of possible outcomes on the fly. This compounds the uncertainty and leads to lower success rates because we expect the response to exactly match the ground truth.\n\nAs shown in **Table 5** of the Appendix, all tested baselines exhibit similar or lower performance in the open-set conditions, with MISQ-HF still outperforming them. This suggests that the performance drop is not specific to our method, but reflects the underlying challenge of generalization in these domains.\n\nWe agree that improving robustness in open-ended settings is a valuable direction. Extensions of this work could integrate retrieval-augmented methods or external knowledge bases to help dynamically construct and refine candidate outcome sets. \n\nWe appreciate your feedback and will clarify that while our method is primarily designed for and excels in closed set scenarios, addressing open-ended answer spaces remains an important open challenge we hope to advance in future work."}, {"review_id": "suKESCDQmA", "reviewer": "Reviewer_pFgi", "summary": "This paper proposes a generation framework for information-seeking questions.  They have applied MCTS to select questions with a strategy and introduce a hierarchical feedback mechanism to exploit past interaction pattens to guide future strategy. They provide extensive empirical evaluation across medical diagnosis and technical troubleshooting domains to show effectiveness.", "questions": "1. How UCT is defined in Line 176? Can you explain more about this one?\n2. in terms of the uncertainty problem, how do you evaluate it?", "limitations": "yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength:\n1. They are utilising LLM and MTCS to generate reasonable responses for information-seeking questions. Overall, the architecture design is diligent and reasonable. \n2. The problem formulation and method description are clear and easy to follow.\n3. Experimental results are effective in demonstrating their methods.\n4. They provide very detailed implementation details such as code, prompts and a case study to make it trustworthy.\n\nWeakness:\n1. Engaging more baseline models to compare.\n2. It would be better to incorporate more explanations into the method description sections. e.g., in Line 176, what's the fundamental motivation for the UCT, and why it can be formulated as (7)?", "was_revised": true, "final_justification": "Thanks for authors' response, it's very detailed, and it raised my concern to a large extend. I would recommend this paper to be presented in NeurIPS.", "rebuttal": "Thank you for thoroughly reviewing our paper and sharing your feedback. \n\nWe appreciate your positive recognition of the strengths of our work, including the clear problem formulation, architecture design, implementation, and extensive empirical validation across domains. We hope the clarifications below will adequately address your concerns.\n\n---\n\n> ### W1: Baselines\n\nWe benchmarked our approach against three main baselines: Direct Prompting (DP), Uncertainty of Thoughts (UoT), and MISQ without the hierarchical feedback mechanism. \n\nUoT (Hu et al., 2025) is the current state-of-the-art in this domain. We would like to highlight that the UoT paper includes rigorous **evaluations against prior baselines** such as Chain-of-Thought (CoT), Tree-of-Thought (ToT), and Reflexion on the same datasets we use. Their results show that UoT consistently outperforms these methods, which justifies our use of UoT as the **strongest comparison**. We cite these works accordingly in the Related Work and Baselines sections and did not duplicate experiments that were already well-covered by the state-of-the-art baseline.\n\nIn the Experiments section, our goal is to highlight the contribution of our hierarchical feedback mechanism by comparing against DP (a minimal-effort baseline), UoT (the strongest available method), and MISQ without feedback as an ablation. This allowed us to isolate the impact of our contribution while also keeping computational demands manageable.\n\n---\n\n> ### W2 and Q1: Defining UCT\n\nThank you for requesting more information on this important component of our paper. We agree that further explanation of the UCT formulation in Line 176 would improve clarity. \nUCT (Upper Confidence bounds applied to Trees), originally introduced by Kocsis and Szepesvári (2006), is used as a principled strategy for node selection in Monte Carlo Tree Search. In our implementation, each node $v$ maintains a visit count $N_v$ and an accumulated reward $R_{\\mathrm{total}}(v)$, initialized to zero when the node is first created during the Expansion step. The UCT score used in the Selection step is given by\n\\begin{equation}\n    UCT(v) = \\frac{R_{\\mathrm{total}}(v)}{N_v} + C \\sqrt{\\frac{\\ln N_p}{N_v}}\n\\end{equation}\nwhere $N_p$ is the visit count of the parent node and $C$ is a tunable exploration coefficient. This formulation balances exploitation (favoring actions with high empirical reward via $\\tfrac{R_{\\mathrm{total}}(v)}{N_v}$) and exploration (favoring less‑visited actions via $\\sqrt{\\tfrac{\\ln N_p}{N_v}}$). The logarithmic scaling ensures diminishing exploration pressure as nodes become well‑sampled, while still encouraging discovery in underexplored parts of the tree. This approach builds directly on **foundational work in bandit‑based planning** [1,2]. We will cite these foundational papers and revise Section 3.4 to make the motivation, variable definitions, and intuition behind UCT more explicit.\n\n**Proposed Addition to Section 3.4 point 1. Selection**\n\n\"\"\"\nThis selection strategy follows the UCT algorithm [1], which applies UCB1 (Upper Confidence Bounds) from multi-armed bandit theory to guide Monte Carlo Tree Search. We initialize $R_{\\mathrm{total}}(v)=0$ and $N_v=0$ when a node is first added to the tree.​​​\nThe first term estimates the average reward of the node, promoting high-reward questions (maximizing information gain). The second term $\\[ C \\sqrt{\\frac{\\ln N_p}{N_v}} \\]$, derived from UCB1, encourages exploration of under-visited nodes and grows as $N_v$ remains small relative to the parent’s visit count $N_p$. This balance enables UCT to trade off exploitation and exploration effectively. \nUCT has been proven consistent, with the probability of selecting suboptimal actions at the root decreasing polynomially with more samples [1]. Empirically, it has shown strong performance in large-scale domains such as Go and planning under uncertainty [2].\n\n\"\"\"\n\nReferences:\n- [1] Kocsis, L. and Szepesvári, C. “Bandit based Monte-Carlo Planning.” ECML 2006.  \n- [2] Chaslot, G., Bakkes, S., Szita, I., and Spronck, P. “Monte-Carlo Tree Search: A New Framework for Game AI.” Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), vol. 4, pp. 216–217, 2008.\n\n---\n\n> ### Q2: Uncertainty reduction\n\nThank you for raising this important clarification question. Uncertainty evaluation is a fundamental part of our approach and directly addresses the core challenge of information-seeking under incomplete information.\n\nUncertainty stems from the fact that users often begin with underspecified problem descriptions, missing out various relevant details. \nThis creates an uncertain decision space where the system must systematically gather missing information through targeted questioning to converge on the correct solution by narrowing the possibility space $\\Omega$.\n\n- Each time the system generates a candidate question, it is rewarded based on how well it splits the current possibility space into two balanced subsets. This is measured using the **entropy** **$IG_v$** $= -p_A \\log p_A - p_N \\log p_N $, where $p_A$ and $p_N$ are the proportions of possible outcomes consistent with an affirmative or negative response. According to information theory, **entropy** is **maximized** when $p_A = p_N = 0.5 $. \n\n- The logic and evaluation closely follow prior work (Hu et al., 2025), where entropy and information gain drive the reward signals that are used for selecting questions.  By always aiming for questions that most sharply reduce uncertainty, our method is designed to be principled and efficient in uncertainty resolution.\n\n- The closer a question gets to dividing the remaining options in half, the more it reduces entropy, which is inherently incentivized in our reward calculation for question selection. In Response to **Q1 by Reviewer 54vp**, we highlight that this ratio of splitting the possibility space is empirically found to be near 52.82\\% on average across samples. This supports the uncertainty quantification and the premise that LLMs can reliably generate questions that closely approximate the optimal information gain."}, {"review_id": "80AlaxHChh", "reviewer": "Reviewer_2p6X", "summary": "This paper proposes a mechanism to dwindle down a set of possible questions (combining Monte CarloTree Search with a hierarchical feedback mechanism) for LLMs during reasoning tasks. The authors devise MISQ-HF to select an optimal sequence of specific questions to reach a \"target\" state. The proposed method is validated on real-world medical datasets.", "questions": "1. While I understand this is likely out of scope, I would have loved to seen a human subject experiment that validates from a set of questions which one would a human pick, which one would an LLM pick, and which one would be optimal. This would help motivate the practical utility of MISQ-HF. \n2. How does the cost of the response to an information-seeking query fold into this setup? Some questions are more costly to answer: asking for a person their date of birth is easier (and less effort for the person) that asking a person for their current body temperature. How would this change the feedback and question selection mechanism? This consideration seems crucial for deploying this system in practice.\n3. Can you please add a pictorial depiction of closed vs open set considerations to Figure 1? It would help guide uninitiated readers.\n4. Please add a computational complexity comparison of UoT and MISQ-HF to the end of Sec 3.", "limitations": "Information-seeking questioning is a blessing and a curse. I would have expected the authors to add significant detail (either to the conclusion or the Broader Impacts in Appendix H). An optimal set of questions may not be accepted by users themselves as (1) users may provide ancillary information or (2) users may view certain questions as coupled -- doctors might be expected to ask Questions A, B, C before jumping to the more invasive yet relevant Question D no matter how optimal omitting Question A, B, C are. I strongly encourage the authors to add such thinking (with their own expansion of course) to the manuscript. It will significantly improve that societal implications of this work.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The MCTS for question selection and cluster-based feedback mechanism are both, to my knowledge, novel and are rightfully presented as so. The use of UCT is natural to guide information-seeking questions.\n- This paper is v well written and clear in its exposition. I do suggest that the authors add a running example is added to the main text (Sec 1) to get a larger audience excited about this problem, such as a medical example to motivate why (1) an optimal sequence of direct information-seeking questions matters and (2) feedback propagation looks like intuitively.\n\nWeaknesses\n- I would have prefer a stronger grounding in existing literature. It would help to flesh out Related Work to make clear how MISQ-HF differs from baselines. In an ideal world, this could be added to Figure 1 to visually depict the sub optimality of existing methods (specifically UoT). \n- I would have liked to see examples in the main text of the how the MCTS information-seeking questions differ from UoT: I am convinced that the experimental results are sound but cannot wrap my head around how (semantically) these questions are different.", "was_revised": true, "final_justification": "I am pleased with the author's engagement in discussion. I look forward to seeing this paper published.", "rebuttal": "Thank you for thoroughly reviewing our paper and sharing your feedback.\nWe appreciate your positive assessment of the paper and are encouraged by the recognition of our method’s novel contributions, clarity and technical soundness. \n\n---\n\n> ### Addressing W1:\n\nTo strengthen the positioning of our approach with respect to existing literature, we can refine Section 2, Related Work, to more clearly articulate the limitations of prior work and how MISQ-HF fills these gaps. While we discuss UoT in the second paragraph of section 2, we will elaborate on its performance bottlenecks and how our proposed approach overcomes them. We would like to emphasize these conceptual distinctions:\n- UoT performs exhaustive tree expansion up to a fixed depth, incurring high computational cost;\n- MISQ-HF avoids this overhead by employing selective expansion through MCTS based on an exploration-exploitation tradeoff.\n- UoT does not incorporate any form of feedback; MISQ-HF enables feedback-driven adaptation during inference time by using semantic similarity to generalize and improve tree search for new cases.\n\nTo make the distinctions more accessible, we will add a compact visual comparing the exhaustive tree expansion with MISQ-HF’s selective, feedback-driven search. We believe this will enhance the foundation of our approach.\n\n---\n\n> ### Addressing W2:\n\nThank you for highlighting the need for an intuitive comparison. The distinction between MISQ-HF and UoT does not just lie in efficiently reaching the target, but also in *how* questions are selected during the search/planning phase. While the semantic form of the questions may not always be very different, the key distinction lies in *when* (depth-aware) and *why* (cluster-specific bonus) a question is prioritized, based on the combination of current information gain and historical feedback.\n\nUoT performs an exhaustive expansion, relying solely on immediate information‐gain at each node. In contrast, MISQ-HF selectively focuses on the most promising subtrees, skipping low‐reward or semantically redundant branches.\n\nBeyond efficiency, MISQ-HF uses feedback‐driven prioritization based on the depth‐decayed bonus derived from past successes in similar cases. Where UoT ‘*forgets*’ previous interactions and treats every decision anew, MISQ-HF remembers which early‐stage questions historically delivered the greatest narrowing of the solution space. For example, if identifying *upper abdomen pain* as an early question consistently leads to rapid and accurate diagnoses of gastric ulcers, MISQ-HF will accelerate the selection of such broad, high-impact questions in future, similar cases. In contrast, UoT does not retain or reuse information from previous dialogues, so it tends to ask less strategic or even repetitive questions.\nThis learning and adaptation allow MISQ-HF to generate higher-quality, more generalizable question sequences tailored by experiential feedback.\n\nIn addition to discussing the above details, we will include a compact table of qualitative examples in Section 5, contrasting MISQ-HF vs UoT trajectories on the same input.\n\n---\n\n> ### Response to Q1: Human judgements\n\nWe agree that incorporating human judgments would be valuable in assessing semantic appropriateness and human preference of questions. However, due to resource and time constraints, this was out of scope for the current version. That said, the core design idea behind the system is to reflect generalization across cases - which aligns with how humans tend to learn from repeatedly seeing similar examples. \nWe will note this point in the Limitations section, highlighting the potential for future work on a case study comparing human and model-generated questions.\n\n---\n\n> ### Response to Q2: Effort cost of questions\n\nThank you for raising this point. In our current setup, we do not explicitly model the effort cost of answering each question. However, our medical diagnosis prompt is carefully designed to elicit symptom-based questions, typically answerable via yes/no or brief open-ended responses, thus naturally avoiding high-effort or invasive queries. In contrast, our troubleshooting domain does include more situation-dependent questions, where the cost to respond could vary more.\n\nWhile incorporating response cost remains out of scope for this work, we fully agree it’s a critical consideration for real-world deployment. One promising direction we are interested in exploring is to have the LLM assign a cost score to each question it generates, which could be integrated into the reward design or selection criteria. That said, real-world datasets often lack ground truth for high-effort questions, making such modeling challenging in practice. We will include this as a future extension in the paper.\n\n---\n\n> ### Response to Q3: Figure showing closed-vs-open set\n\nWe will add some details to Figure 1 to highlight the difference between closed and open set scenarios. Specifically, around steps 3 and 8 in the diagram, we will visually separate the initialization of the possibility set: for the closed set, the system will start from a fixed, pre-defined set of outcomes, while for the open set, the system will begin with a dynamically generated or expanded set based on user input. We will also add clear legends and labels to explain this distinction to aid readers’ understanding.\n\n---\n\n> ### Response to Q4: Complexity analysis\n\nOur paper includes a brief complexity analysis in Appendix G: QGC Efficiency. As suggested, we will move it towards the end of Section 3. For clarity, we will focus on the derivations for theoretical grounding and add the following details to Appendix, adhering to page limits.\n\nUoT uses exhaustive expansion to maximize information gain. At each question node \\$v\\$, it generates \\$m\\$ candidate questions and evaluates both branches, creating \\$b = 2m\\$ child nodes.\n\nTotal number of question nodes up to depth \\$d\\_s\\$:\n\n$ N_{\\text{nodes}} = \\sum_{k=0}^{d_s-1} b^k = \\frac{b^{d_s} - 1}{b - 1} $\n\nEach node requires one LLM call. So:\n\n$ C_{\\text{UoT}} = O(b^{d_s}) = O((2m)^{d_s}) $\n\nThis exponential growth reflects a scaling challenge.\n\nMISQ-HF employs selective expansion via MCTS, balancing exploration and exploitation with UCT (Eq. 7; 13). Each iteration has:\n1. Selection: Tree traversal (no LLM calls)\n2. Expansion: ≤1 new node (≤1 LLM call)\n3. Simulation: Random rollout to depth \\$d\\_s\\$ (≤\\$d\\_s\\$ LLM calls)\n4. Backpropagation: Value updates (\\$O(d\\_s)\\$, no LLM calls)\n\nPer iteration: ≤ \\$d\\_s + 1\\$ LLM calls\n\nTotal per decision:\n$$ C_{\\text{MISQ}} \\leq K(d_s + 1) = O(K \\cdot d_s) $$\n\nHierarchical Feedback:\nThe bonus reward term \\$ B_k(v) = \\beta \\cdot R_{\\text{total}}(v) \\cdot \\gamma^{d_v} \\$ adds efficiency without changing asymptotic complexity. \n\nCluster Assignment Complexity: Semantic clustering via embeddings requires \\$O(n\\_c)\\$ comparisons per sample, where \\$n\\_c\\$ is the number of clusters. This is amortized across turns and negligible compared to LLM cost.\n\nHence, MISQ-HF offers a key advantage: linear scaling \\$O(K \\cdot d\\_s)\\$ vs exponential growth \\$O((2m)^{d\\_q})\\$ in exhaustive tree search. \n\n---\n\n> ### Addressing Broader Impact:\n\nWe appreciate your encouragement to highlight the broader impacts of optimal question selection, especially around user expectations and social dynamics. We acknowledge that maximizing information gain does not always align with conversational norms, particularly in sensitive settings like healthcare or customer support. In practice, users may expect certain standard question sequences for reassurance or trust-building. They may also provide unprompted information or interpret omitted questions as inattentiveness. Skipping over familiar or obvious questions, even when optimal, can lead to confusion or make the dialog feel unnatural. Similarly, some questions are naturally perceived as coupled and are best asked together for reasons beyond efficiency.\n\nIn the MedDG dataset, we allow for open-ended responses where the user (simulator) often shares additional details. We use the classification prompt (Appendix D.5) to infer the response and update the possibility set accordingly, though this does not fully address all scenarios of spontaneous disclosure.\n\nTo reflect these considerations, we will expand our discussion in Appendix H: Broader Impacts, to emphasize the importance of balancing algorithmic optimality with user-centered design in the domain of information seeking. We would also propose that future work models spontaneous disclosures and adaptive conversational flows more comprehensively, allowing systems to integrate ancillary information and adjust strategies mid-dialogue."}, {"review_id": "aZ6shEvbNK", "reviewer": "Reviewer_54vp", "summary": "This work focuses on using MCTS to improve information seeking systems in dialogue tasks. The authors proposed modifications to the MCTS algorithm for finding information-maximizing questions by prompting LLMs; and a feedback mechanism that enables learning from experience (i.e., previous runs) by updating the search tree across runs. The authors experimented with their framework in several datasets spanning medical diagnosis, trouble-shooting, and 20 questions and showed improvement compared to prior baselines.", "questions": "Questions:\n- How often can LLM really be prompted to generate questions that maximize information gain, as mentioned in line 150-151?\n- Why is simulation (L184-188) based on random interaction? In many previous work that applies MCTS with LLM it is quite common where the simulation process is against another LLM (by prompting or after training)?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n- The proposed modifications to MCTS to maximize information gain is intuitive.\n- The authors conducted thorough experiments in multiple datasets (medical diagnosis, trouble-shooting, and 20 questions) and showed improvement performance compared to two prior baselines.\n\nWeakness:\n1. The proposed system adds significant complexity both in compute and in time. MCTS is already highly time-intensive to run, and the authors also added methods such as clustering and using embeddings of new user problems to assign bonus rewards for future tree search. However, the authors did not report statistics such as runtime in the main results (e.g., Table 1).\n2. There are many LLM based MCTS omitted in the related work section. Example includes [1-2]. Since the main contribution is a modified MCTS algorithm for the domain of question asking, the author should at least compare against one of these prior work to show that the proposed approach outperforms a \"vanilla\" LLM + MCTS implementation.\n\n\n---\n\nReferences\n\n[1] Zhou, Andy et al. “Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Models.” ArXiv abs/2310.04406 (2023): n. pag.\n[2] Yu, Xiao et al. “ExACT: Teaching AI Agents to Explore with Reflective-MCTS and Exploratory Learning.” ArXiv abs/2410.02052 (2024): n. pag.", "was_revised": true, "final_justification": "I believe the authors response have clarified my concern on runtime as well as a few questions on whether an LLM can really be prompted to generate information-maximizing questions. This work is about LLM+MCTS, yet omitted a few other MCTS based approaches designed for open-ended tasks. The authors argues that sufficient baselines in the question asking were included, and I believe the comparisons made in this work is reasonable.\n\nHowever, I think these responses did not significantly improve the current quality of the work beyond 3 (good), as this work situates itself within the information seeking domain and likely cannot generalize to open-ended tasks like other LLM+MCTS work. I therefore keep my original judgement.", "rebuttal": "Thank you for thoroughly reviewing our paper and sharing your feedback.\n\nWe appreciate your positive assessment of the paper, particularly your recognition of the intuitive design of our MCTS modifications and the strength of our experimental validation across diverse tasks.\n\n---\n\n> ### Addressing W1: Complexity and Runtime\n\nOur paper includes a brief note on efficiency in Appendix G. We also address the computational complexity in detail in our response to Q4 by Reviewer 2p6X. In our setting, the main bottleneck is LLM call invocations, which dominate overall runtime and cost. Tree traversal and clustering/embedding operations are negligible by comparison (on average, cluster assignment takes about 0.007 seconds per data point).\n\nTo provide an estimate, we recorded the average wall-clock time (in seconds) per full MCTS-based question selection step (decision turn) for the following datasets in the closed set scenario with Llama 3.3 70B:\n\n| Dataset | UoT (s) | MISQ-HF (s) |\n|---------|---------------|-------------------|\n| DX      |     0.35      |      0.33         |\n| MedDG   |     2.89      |      2.56         |\n| FloDial |     14.32      |      8.12         |\n\nAs the results in Table 1 of the paper show, MISQ-HF achieves substantial efficiency gains over UoT due to its selective expansion and feedback reuse. Due to compute and time constraints, we cannot report runtime for every setting, but will aim to include these numbers with standard deviation in the Appendix. We believe this further supports our primary focus on LLM call counts as the most relevant cost metric for our framework.\n\n\n---\n\n> ### Addressing W2: Prior Work\n\nWe acknowledge the importance of comprehensively situating our work within the landscape of LLM-based MCTS research. The referred papers: Language Agent Tree Search (LATS) by [1]Zhou et al. and ExACT by [2]Yu et al. focus on open-ended, interactive agent tasks involving rich, unstructured environmental actions, where the LLM reasons about complex state transitions and performs future action simulations through language prompts. Their settings differ fundamentally from ours; MISQ-HF centers specifically on structured information-seeking dialogues with a predefined or dynamically constructed possibility set. It leverages entropy-based information gain as a quantitative reward to guide selective question generation within bounded domains - an approach that is both computationally efficient and principled.\n\nImplementing LATS or ExACT directly in our setting would require redesigning our interaction model as open-ended agent-environment loops, adding complexity and computational overhead. Importantly, please note that our baseline MISQ (without HF) already captures a vanilla LLM+MCTS approach tailored to question selection, serving as a relevant comparison.\nNonetheless, we will more clearly mention these connections and expand our related work section to discuss the relationships and boundaries between these methods and ours.\n\n---\n\n> ### Response to Q1: Questions that maximize information gain\n\nOur empirical analysis across LLM calls for question generation in the MD (DX, MedDG) and TS (FloDial) domains shows that the average ratio of affirmative-consistent possibilities to total possibilities is approximately 52.82% ±3.49%. This near-50% balance indicates that, when appropriately prompted, LLMs are reasonably effective at producing questions that closely approximate optimal information gain, as entropy peaks at balanced partitions. We will add this detail in the revised manuscript. \n\n---\n\n> ### Response to Q2: Random rollout in MCTS Simulation\n\nIn traditional MCTS, random simulations (where actions from a given node are chosen at random during the rollout phase) are a foundational practice used to provide unbiased, tractable estimates of long-term utility and facilitate theoretical convergence [1,2,3]. This approach is not only computationally efficient but also widely adopted in influential systems like AlphaGo, where random or fast simulated rollouts underpin robust planning performance.\n\nRecent LLM + MCTS frameworks like GDP‑Zero[4], RoT[5], and PG-TD[6] replace random rollouts with LLM-driven simulation to better capture the complexities of natural language tasks. GDP‑Zero leverages a single LLM to simulate both user and system responses during search, acting jointly as policy, value function, and world model for dialogue planning. RoT (Reflection on Trees) enhances tree search by using a strong LLM to reflect on past search trajectories and generate guidelines that improve future search accuracy in semantically rich domains. PG-TD employs LLM-driven code simulations, prompting the model to generate likely next code snippets at each step.\n\nThe *objective and quantifiable nature of our reward* (information gain measured by entropy reduction) allows us to rely on random rollouts during simulation. Since R_IG can be calculated directly from the current partition of the possibility set, this approach yields an objective and meaningful signal for the search tree without incurring repeated or costly LLM calls during simulation. It also ensures that each simulation step precisely reflects progress toward reducing uncertainty, which is crucial for efficient information-seeking. This method is consistent with the theoretical roots of MCTS, and we will add that future work could incorporate semantically-aware or language-based rollout policies if richer feedback or open-domain reasoning becomes essential for the task\n\n---\n[1]: Kocsis, L. & Szepesvári, C. “Bandit based Monte-Carlo Planning.” ECML 2006.  \n\n[2]: James, S., Konidaris, G., & Rosman, B. (2017). An Analysis of Monte Carlo Tree Search. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1).\n\n[3] Vodopivec, T., Samothrakis, S., & Ster, B. (2017). On monte carlo tree search and reinforcement learning. Journal of Artificial Intelligence Research, 60, 881-936.\n\n[4] Yu, X., Chen, M., and Yu, Z. 2023. Prompt-Based Monte-Carlo Tree Search for Goal-oriented Dialogue Policy Planning. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (EMNLP ’23). Association for Computational Linguistics, 7101–7125. \n\n[5] Hui, W., and Tu, K. 2024. RoT: Enhancing Large Language Models with Reflection on Search Trees. arXiv:2404.05449 [cs]. \n\n[6] Zhang, S., Chen, Z., Shen, Y., Ding, M., Tenenbaum, J. B., and Gan, C. 2023. Planning with Large Language Models for Code Generation. In International Conference on Learning Representations (ICLR ’23)."}]

Author rebuttal:

Meta-review: This paper proposes MISQ and MISQ-HF, an MCTS-based framework for selecting information-seeking questions, with a hierarchical feedback mechanism that reuses successful search paths across cases. The method targets domains such as medical diagnosis, troubleshooting, and 20-Questions, with information gain used as a principled reward.

Main strengths including:
- Clear novelty in applying selective MCTS for question selection and in the cluster-based feedback that reuses experience.
- Strong empirical gains across five datasets in three domains, with large reductions in LLM calls and consistent accuracy improvements over strong baselines such as UoT.
- Clarity of exposition and solid implementation details. Code and prompts are described in depth, which supports reproducibility.

The rebuttal and follow-ups were detailed, constructive, and addressed the key points. The remaining items are addressable in the final version and do not block acceptance:
- Expand discussion to situate MISQ-HF relative to general LLM+MCTS frameworks such as LATS and ExACT, and clearly delineate differences in problem setting and reward structure.
- Include the complete UCT derivation and notation, and move the complexity comparison with UoT into Section 3 with a concise, reader-friendly summary.
- Add a small runtime table with mean and standard deviation for representative settings, alongside QGC, and clearly state that LLM calls dominate cost.
- Include the Situation Puzzles results in the appendix with a short methodological description of the adaptive candidate set. Make clear that this is supplemental due to post-deadline release.

Overall, the paper presents a clear and useful advance in inference-time planning for information-seeking tasks, with solid empirical evidence, good clarity, and meaningful efficiency gains that are attributable to the search strategy rather than model choice. The authors engaged thoughtfully, added supplemental open-ended results, and committed to camera-ready improvements that address residual concerns. While two reviews are borderline due to scope and positioning, the technical contribution and demonstrated benefits warrant acceptance.
Decision: Accept (spotlight)