Adaptive Elicitation of Latent Information Using Natural Language

We thank the reviewer for their thoughtful feedback. We are encouraged that the reviewer found the problem setting to be well motivated, and our experiments and results to be presented clearly. Please see our responses to the particular concerns raised.

[Q1: Calculating confidence]

Confidence is calculated in the typical way as the softmax response for the predicted answer. In response to this concern, we will clarify this calculation in our revised paper, as well as clearly specify when we use related notions of entropy or variability.

[Q2: Computational Expense] In terms of analysis, we provide a brief overview for the reviewer. Let $n$ be the number of possible questions to ask and $m$ be the number of possible answers to each question. The computational complexity of the EIG method at each time step $t$ is $O(m\cdot n)$. This is because we need to calculate the conditional entropy of each answer for each feasible question in the set. To calculate the complexity of MCTS, let $z$ be the number of trajectories we simulate and $d$ be the depth of simulation. Then MCTS is $O(z\cdot n\cdot m\cdot d)$, as we have $z$ simulations up to depth $d$ for each question, and at each depth we need to perform an EIG calculation. We will provide a detailed computational complexity analysis in our final draft.

To compare the complexity of our method to other approaches, we note that other common methods like embedding-based methods will require a linear scan of the possible questions, yielding a complexity similar to our greedy method. Furthermore, methods that directly use LLMs to generate questions and responses require forward passes in the number of tokens in each question and responses, while our method only requires one forward pass in this respect. Applying MCTS on top of using LLMs to generate responses (as in UoT) will incur complexity $O(z\cdot n\cdot m\cdot d)$ multiplied by complexity of generating responses.

We acknowledge the complexity of the MCTS approach can be a bottleneck in scenarios with an extremely large question space or stringent real-time constraints. However, we also want to highlight that there are also many important applications (including some that we consider) where this should not be prohibitive.

For example, in educational settings the extra computation can be performed during the student’s response time, as the policy is updated while the student works on the current question—thus introducing a tolerable lag. Conversely, in real-time applications such as live diagnostics or interactive dialogue systems, the computational overhead of MCTS might be prohibitive, and more efficient strategies (e.g., greedy selection) may be preferred. We view our work as introducing a new conceptual perspective on uncertainty-guided questioning, and we hope that future work will build on our approach to develop more computationally efficient solutions.

[Q3: Comparison to other methods]

While there exists a growing body of literature on UQ in LLMs, much of this work is focused on different settings and types of uncertainty than we address here. In particular, much of this growing body of work is focused on short-form generation and QA style tasks [e.g., 1-5]. These works are primarily focused on improving the reliability in off-the-shelf LLMs, by quantifying existing uncertainty in some answer to a response to some question. This is a fundamentally different task than quantifying how observing the answer to some question will affect your uncertainty in other question/answers pairs, and using these estimates to make adaptive decisions to reduce uncertainty.

With respect to Uncertainty of Thoughts (UoT), we did not compare as a baseline because UoT uses the LLM to generate potential questions, while our setting involves choosing potential questions from a given question bank. If we adapt UoT to our setting, it would be equivalent to applying the EIG measure to the base LLM. We compare this in the ablation in Figure 6, and show that adapted UoT (EIG + base LLM) performs worse than random selection. We hypothesize that this worse performance is due to the specialized nature of datasets like OpinionQA and EEDI which may not be in the training set of the base LLM, pointing to the necessity of our meta-learning procedure.

• [1] Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation https://arxiv.org/abs/2302.09664
• [2] Shifting Attention to Relevance: Towards the Predictive Uncertainty Quantification of Free-Form Large Language Models https://arxiv.org/abs/2307.01379
• [3] Language Models (Mostly) Know What They Know https://arxiv.org/abs/2207.05221
• [4] Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback https://arxiv.org/abs/2305.14975
• [5] INSIDE: LLMs' Internal States Retain the Power of Hallucination Detection https://arxiv.org/abs/2402.03744

We thank the reviewer for their thoughtful and thorough review, and their recognition that our claims are well-supported by experiments. We response below to the concerns.

[Q1: Use of "counterfactual response"]

We apologize for the confusing use of the term "counterfactual response" in the paper. "Counterfactual" has no reference to its usage in the causal inference literature and a better term to use would be "simulated response". We will replace this in the final draft.

[Q2: Predictive perplexity / Joint likelihood]

Our formulation of uncertainty quantification derives from a large body of work on inference with missing data (e.g. [1-2]). Under this view, knowing $U$ is defined as being able to predict any answer $Y$, with errors only due to random, aleatoric variation. Observing the infinite sequence $(X_{1:\infty}, Y_{1:\infty})$ reduces all epistemic uncertainty, leaving only aleatoric uncertainty: $H(Y \mid U) = H(Y \mid X_{1:\infty}, Y_{1:\infty})$. Then, epistemic uncertainty in $U$ naturally corresponds to uncertainty in the missing data $Y_{t+1:\infty}$ given history $Y_{1:t}$. The joint likelihood $P(Y_{t+1:\infty} \mid X_{1:t}, Y_{1:t})$ exactly quantifies uncertainty about the missing data $Y_{t+1:\infty}$ which shows it is the correct objective. Under the special condition of exchangeability, this is precise: there exists $\theta(X_{1:\infty}, Y_{1:\infty})$, such that $H(Y \mid U) = H(Y \mid \theta(X_{1:\infty}, Y_{1:\infty}))$.

We will include a detailed description in the paper.

[Q3: Simulation to quantify epistemic/aleatoric?]

Simulating future trajectories allows us to quantify which actions will reduce the most epistemic uncertainty. To quantify uncertainty about a target $Z$ we calculate, $\text{Epistemic Uncertainty}(Z | X_{1:t}, Y_{1:t}) = (\text{Total}) H(Z \mid X_{1:t}, Y_{1:t}) - (\text{Aleatoric}) \mathbb{E}[H(Z \mid X_{1:\infty}. Y_{1:\infty})].$ In practice, we approximate this quantity using simulation to calculate existing epistemic/aleatoric uncertainty. The EIG then quantifies the reduction in epistemic uncertainty, which we also calculate by simulation.

[Q4: Exchangability assumption] We agree with the reviewer that the exchangeability assumption may be too strong in practice. We will outline these fundamental limitations in our camera-ready version. We also emphasize that exchangeability mainly serves as inspiration for our practical UQ framework, alongside our strong empirical results.

[Q5: Computational analysis] Define $n$ as the number of questions to ask and $m$ be the number of possible answers. The computational complexity of the EIG method at each time step $t$ is $O(m\cdot n)$ because we need to calculate the conditional entropy of each answer for each feasible question in the set. The complexity of MCTS is $O(z\cdot n\cdot m\cdot d)$, where $z$ is the number of simulations and $d$ be the depth of simulation, since there are $z\cdot d$ EIG calculations. We will include a detailed discussion of complexity analysis in the camera-ready version.

[Q6: Proof of A4]

Steps (5-7) in the proof outline a telescoping expansion of the KL divergence term. The telescoping sum consists of three terms. (5) is the difference between the ground truth distribution $q$ and $p$ conditioned on the optimal information $X_{p_{\theta}}^{\ast}$. (6) is the difference of $p(Y_{t:T} | X_{p_{\theta}}^{*})$ when $Y_{t:T}$ is simulated from $q$ versus $p$. Finally (7) measures the difference of conditioning on the optimal information $X_{p_{\theta}}^{\ast}$ and $X_{greedy}$.

Regarding Fact A.2, we apologize as we made a typo. Fact A.2 refers to the fact that for any $S \in \mathcal{S}, 0\leq H(S) \leq \log |S|$ on lines 671-674. The term $\log (|Y| (T-t))$ comes from bounding $H(Y_{t:T} | X_{p_{\theta}}^{*})$ on line 685. Because $Y_{t:T}$ is exchangeable and the ordering does not matter, then the cardinality of $Y_{t:T}$ is $|Y|(t-T)$.

[Q7: Realistic use cases] Thank you for this suggestion, we agree that incorporating more realistic use cases could strengthen the evaluation, especially in high-impact areas like medical diagnosis. While 20 Questions is synthetic, we highlight that EEDI and OpinionQA are real-world datasets in personalized tutoring and opinion polling, important domains where a technique like ours might make significant impact.

[Q8: Related work/qualitative examples] We thank the reviewer for pointing out missing related work; we will include these and additional references in our final version. We will also include examples of questions and answers in the paper, and show how uncertainty changes in practice.

[1] Edwin Fong, Chris Holmes, and Stephen G Walker. Martingale posterior distributions. Journal of the Royal Statistical Society, Series B, 2023.

[2] Naimeng Ye and Hongseok Namkoong. Exchangeable sequence models quantify uncertainty over latent concepts. arXiv preprint arXiv:2408.03307, 2024.

We thank the reviewer for their effort in reviewing our paper, and their thoughtful feedback. We are pleased that the reviewer appreciated the importance of the topic as well as the novelty of our approach. Below please see our responses to the particular concerns raised.

[Q1: Sensitivity to embedding model] As per the reviewer's suggestion, we ran additional experiments to ablate the importance of the embedding model. We tested 5 embedding models: stella_en_1.5B_v5, Qwen2-7B-instruct, e5-mistral-7b-instruct , OpenAI text-embedding-3-large, and AlibabaNLP/gte-large-en-v1.5 (which we used in our original paper), and measured their accuracy after conditioning on 3 in-context questions for the EEDI and OpinionQA dataset. We set the number of targets to be 5 and number of possible questions to ask as 20, which mirrors the setup in our paper. Here are the experiment results, where numbers reported are for each entry is an average over 10,000 different runs:

We find that while there is a bit of variation in the embedding model performance. For EEDI, we notice that the larger 7B models and OpenAI text-embedding-3-large have slightly higher performance. For OpinionQA, the performance is more varied. However, none of the embedding models make the In-Context Tuning + Embedding baseline outperform our method. Our method achieves 0.678 accuracy on EEDI and 0.597 accuracy on OpinionQA, as reported in Figure 3.

[Q2: Computational Complexity]

In terms of analysis, let $n$ be the number of possible questions to ask and $m$ be the number of possible answers to each question. The computational complexity of the EIG method at each time step $t$ is $O(m\cdot n)$. This is because we need to calculate the conditional entropy of each answer for each feasible question in the set. To calculate the complexity of MCTS, let $z$ be the number of trajectories we simulate and $d$ be the depth of simulation. Then MCTS is $O(z\cdot n\cdot m\cdot d)$, as we have $z$ simulations up to depth $d$ for each question, and at each depth we need to perform an EIG calculation. We will provide a detailed computational complexity analysis in our final draft.

To compare the complexity of our method to other approaches, we note that other common methods like embedding-based methods will require a linear scan of the possible questions, yielding a complexity similar to our greedy method. Furthermore, methods that directly use LLMs to generate questions and responses require forward passes in the number of tokens in each question and responses, while our method only requires one forward pass in this respect. Applying techniques like MCTS on top of using LLMs to generate responses will incur complexity $O(z\cdot n\cdot m\cdot d)$ multipled by complexity of generating responses.

We acknowledge that the complexity of the MCTS approach can be a bottleneck in scenarios with an extremely large question space or stringent real-time constraints. However, we also want to highlight that there are also many important applications (including some that we consider) where this should not be prohibitive.

For example, in educational settings the extra computation can be performed during the student’s response time, as the policy is updated while the student works on the current question—thus introducing a tolerable lag. Conversely, in real-time applications such as live diagnostics or interactive dialogue systems, the computational overhead of MCTS might be prohibitive, and more efficient strategies (e.g., greedy selection) may be preferred. We view our work as introducing a new conceptual perspective on uncertainty-guided questioning, and we hope that future work will build on our approach to develop more computationally efficient solutions (e.g., via distillation).

In response to the reviewer's concern, we will include a more detailed discussion of these trade-offs and complexity considerations in the camera-ready version.

[Q3: Related work on latent entity modeling]

We agree with the reviewer that a review surrounding latent entity modeling would be of major benefit. We will make sure to include this discussion in the camera-ready version of the paper.

We thank the reviewer for the time and consideration taken in reviewing our paper, and for recognizing our contribution to the application of uncertainty-driven question selection in important domains like education and healthcare. Below, we respond to your particular concerns.

[Q1: Modeling the latent, relationship to perplexity, and separation of epistemic + aleatoric uncertainty]

Most latent entities have no obvious physical meaning (e.g., academic proficiency or political opinions), and can only be observed through noisy observations (e.g., student answers where they guess if they're unsure). Our framework avoids the need to perform such direct modeling, allowing us to build a framework that is able to be applied on existing LLMs to use their internet-scale pretrained knowledge to make robust, adaptive decisions.

Our formulation of uncertainty quantification derives from a large body of work on inference with missing data (e.g. [1-2]), and we will include a description of this relationship and our characterization of epistemic and aleatoric uncertainty in the paper. Under this view, knowing $U$ is defined as being able to predict any answer $Y$, with errors only due to random, aleatoric variation. Observing the infinite sequence $(X_{1:\infty}, Y_{1:\infty})$ reduces all epistemic uncertainty, leaving only aleatoric uncertainty: $H(Y \mid U) = H(Y \mid X_{1:\infty}, Y_{1:\infty})$. Then, epistemic uncertainty in $U$ naturally corresponds to uncertainty in the missing data $Y_{t+1:\infty}$ given history $Y_{1:t}$. The joint likelihood $P(Y_{t+1:\infty} \mid X_{1:t}, Y_{1:t})$ exactly quantifies uncertainty about the missing data $Y_{t+1:\infty}$ which shows it is the correct objective. Under the special condition of exchangeability, this is precise: there exists a function $\theta(X_{1:\infty}, Y_{1:\infty})$, such that $H(Y \mid U) = H(Y \mid \theta(X_{1:\infty}, Y_{1:\infty}))$ exactly.

Simulating future trajectories allows us to quantify which actions will reduce the most epistemic uncertainty. To quantify uncertainty about a target $Z$, we calculate $\text{Epistemic Uncertainty}(X_{1:t}, Y_{1:t}) = (\text{Total}) H(Z \mid X_{1:t}, Y_{1:t}) - (\text{Aleatoric}) \mathbb{E}[H(Z \mid X_{1:\infty}. Y_{1:\infty})]$ If we could infinitely simulate $Y \sim p_{\theta}$, we can exactly calculate epistemic/aleatoric uncertainty. In practice, we will simulate finite time steps to approximate this quantity.

In response to this concern, we will work to clarify these discussions in our revised paper.

[Q2: Data requirements]

We appreciate the reviewer's feedback about issues such as dataset imbalance or insufficient data. We will include a grounded discussion of the fundamental limitations of our approach---also shared by other approaches---in the camera ready version. While LLMs may learn average-case behavior, our meta-learning approach is designed to personalize to individuals by understanding what data to gather about each specific individual. A key advantage of our method is we can include any/all user information for the LLM to condition on for sufficient personalization.

[Q3: Complex Reasoning]

Our work takes on a different approach to reasoning by integrating explicit uncertainty quantification and estimation with the natural language capabilities of LLMs. Our method can be complementary to reasoning models such as OpenAI's O1 and DeepSeek-R1 by explicitly integrating reasoning with our uncertainty estimation capabilities. Such ideas are beyond the scope of this work, as we aim to first demonstrate the validity of our UQ framework.

[Q4: Computational Expense]

While MCTS can be a bottleneck in settings with large question spaces or strict real-time constraints, it remains practical for many applications including those we study. In education, for example, computation can occur during a student’s response time, causing only minor lag. In contrast, real-time tasks like diagnostics or dialogue may require faster methods such as greedy selection. Our work offers a new perspective on uncertainty-guided questioning, and we hope it inspires more efficient approaches (e.g., via distillation).

We also note that methods like embedding-based methods will require a linear scan of the possible questions, yielding a complexity similar to our greedy method. Furthermore, methods that directly use LLMs to generate questions and responses require forward passes in the number of tokens in each question and responses, while our method only requires one forward pass in this respect. We will include a detailed discussion of complexity/tradeoffs in the camera-ready version.

[1] Edwin Fong, Chris Holmes, and Stephen G Walker. Martingale posterior distributions. Journal of the Royal Statistical Society, Series B, 2023.

[2] Naimeng Ye and Hongseok Namkoong. Exchangeable sequence models quantify uncertainty over latent concepts. arXiv preprint arXiv:2408.03307, 2024.