Conformal Information Pursuit for Interactively Guiding Large Language Models
Authors: Kwan Ho Ryan Chan
Yuyan Ge
Edgar Dobriban
Hamed Hassani
Rene Vidal
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Models
Interactive Question Answering
Uncertainty Quantification
Twenty Questions
Primary area: general_machine_learning
TL;DR: Greedy approach to Interactive Question Answering in LLMs via Information Gain and Conformal Inference

Abstract: A significant use case of instruction-finetuned Large Language Models (LLMs) is to solve question-answering tasks interactively. In this setting, an LLM agent is tasked with making a prediction by sequentially querying relevant information from the user, as opposed to a single-turn conversation. This paper explores sequential querying strategies that aim to minimize the expected number of queries. One such strategy is Information Pursuit (IP), a greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty. However, obtaining accurate estimates of mutual information or conditional entropy for LLMs is very difficult in practice due to over- or under-confident LLM probabilities, which leads to suboptimal query selection and predictive performance. To better estimate the uncertainty at each iteration, we propose *Conformal Information Pursuit (C-IP)*, an alternative approach to sequential information gain based on conformal prediction sets. More specifically, C-IP leverages a relationship between prediction sets and conditional entropy at each iteration to estimate uncertainty based on the average size of conformal prediction sets. In contrast to conditional entropy, we find that conformal prediction sets are a distribution-free and robust method of measuring uncertainty. Experiments with 20 Questions show that C-IP obtains better predictive performance and shorter query-answer chains compared to previous approaches to IP and uncertainty-based chain-of-thought methods. Furthermore, extending to an interactive medical setting between a doctor and a patient on the MediQ dataset, C-IP achieves competitive performance with direct single-turn prediction while offering greater interpretability.

Conformal Information Pursuit for Interactively Guiding Large Language Models
Kwan Ho Ryan Chan
Yuyan Ge
Edgar Dobriban
Hamed Hassani
René Vidal
University of Pennsylvania
Abstract
A significant use case of instruction- -inetionn-- Large Language Models (LLMs)) is to solve question-answering tasks interactively. In this setting, LLM agent is tasked with making a prediction by sequentially querying relevant information from the user, as opposed to single-turn conversation. This paper explores sequential querying strategies that to minimize the expected number of queries. One such strategy is Information Pursuit (IP), greedy algorithm that at each iteration selects the query that maximizes information gain or equivalently minimizes uncertainty. However, obtaining accurate estimates of mutual information conditional entropy for LLMs very difficult in practice due to over- or under-confident LLM proba- bilities, which leads suboptimal query selection and predictive performance. To better estimate the uncertainty at each iteration, we propose Conformal Information Pursuit (C-IP), alternative approach to sequential information gain based conformal prediction sets. More specifically, C-IP leverages a relationship between prediction sets and conditional entropy each iteration to estimate uncertainty based on the average size of conformal prediction sets. In contrast to conditional entropy, find that conformal prediction sets are distribution-Fii method of measuring uncertainty. Experiments with 20 Questions show that C-IP obtains better predictive performance and shorter query-answer chains compared to previous approaches to IP and uncertainty-bast -based chain-of-thougee methods. Furthermore, extending to an interactive medical setting between a doctor and a patient on the MediQ dataset, C-IP achieves competitive performance with direct single-ture prediction while offering greater interpretability.
and robust
Init. Info: A 25.year-old the plysician for on exanination.
Introduction
Uncertain
query
Large Language Models (LLMs) [2, 3, 42, 83] fine- tuned on instruction datasets are capable of generating human-like dialogues. Although many use-cases con- strain these models to single-turn interactions [99, 111, 138), where single prompt typically provides all context and examples, more realistic conversations behave inter- actively [12, 70]. In this work, we are interested in the setting where LLMs interactively solve a prediction task in multi-turn, information-seedt seeeaiiniinneininnnneeeeaeen environment by ask- ing queries and obtaining information sequentially [71]. Popular examples of such settings include the game of 20 Questions (20Q) [11, 84, 143] and Interactive Medical Question Answering [70] (Figure 1).
Doctor: the patient's body temporature within the range?
Patient: The patient's body temperature is (98.0 'F).
a query
ronm forritin
ag/md.
Patient: The patient's zenm ferritin level nginl...
Confident Prediction
Prediction: (D) Intrarascular hemolysis
Figure 1: Example of diagnosis via Patient and Doctor LLM interaction.
"Correspondng author. Email: ryanckheseas. upenn edu
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

While there are many strategies to interactively arrive at a final prediction, we consider strategies that yield a small number of queries. One such strategy is to always ask the most "informative" query given the prior history, until the model is confident enough to make a prediction. This process is characterized a framework called Information Pursuit (IP) [16, 38], which defines the most informative query as the one that maximizes information gain at each iteration. This requires selecting the query whose answer has the maximum mutual information [18, 21, 30, 77, 145] with the prediction, given the history of prior query-answer pairs. Equivalently one can select the query whose answer minimizes the uncertainty of the prediction, as quantified by the conditional entropy.
In practice, implementing IP for LLMs requires estimating the conditional entropy. which is very challenging because the probabilities of LLM outputs, such as logits of output tokens, are often miscalibruted:: LLM predictions are of- ten strongly over- or under-confident [6, 31, 39, 55, 78, 109, 113, 118, 121, 128, 132, 142, 144, 147, 148]. Conse- quently, using probability estimates to measure uncertainty leads to inaccurate estimates of information and lower pre- dictive performance. We illustrate this phenomenon in Figure using the example of two LLMs playing 20 Ques- tions. In this setting, the Querier LLM has to guess the object that the Answerer LLM is thinking of by asking sequence of most informative questions. Idcally, the uncertainty and accuracy of the prediction should behave like the solid red and solid blue curves. At the first iter- ation, since the Querier LLM has not gathered sufficient information, the uncertainty of the prediction should be high. As iterations proceed, uncertainty should diminish and converge to a certain level, where any new query would no longer offer any additional information than what the Querier LLM already knows. Then, the Querier LLM should stop and make a prediction. However, we observe that using the LLM's output probabilities to estimate uncertainty yields a flat and uninformative curve (dashed red curve). Naturally, this leads to suboptimal query selection and lower predictive performance (dashed blue curve). This motivates the need for better uncertainty estimation.
3
1.0
0.8
Uncertainty
2
Accuracy
0.6
0.4
1-
0.2
0.0
0
4 8
12
16
20
Number of Queries Asked
Figure 2: IP with calibrated (solid) versus un- calibrated (dashed) measures of uncertainty.
To obtain more accurate measures of uncertainty for the outputs of the LLM, we propose an alternative approach to sequential information gain that leverages the notion of prediction sets from predictive inference and conformal prediction [5, 124]. Although the history of prediction sets dates back to the 1940s [103, 119, 120, 125, 133], the use of the expected size of prediction set as measure of uncertainty has been studied and popularized only recently [4, 28, 32, 58, 82, 100, 101]. In more recent applications, it has also been used calibrate the LLMs' output probabilities for a more accurate measure of model confidence [23, 61, 80, 95, 140]. By and large, standard entropy as a measure of uncertainty relies heavily on proper estimation of the target distribution, while prediction sets from conformal prediction allow for a distribution- free and mnstance-wise measure, offering more flexibility, robustness, and interpretability. Given its dual purpose of being a tool for uncertainty quantification and calibration, we are motivated to use prediction sets as measure of informativeness in lieu of conditional entropy.
Therefore, in this paper we propose Conformal Information Pursuit (C-IP), a greedy sequential approach that asks informative queries in the order of information gain by minimizing prediction set size instead of the standard entropy. We first leverage the relationship between entropy and the expected size of prediction sets using results from Correia et al. [27], allowing us to upper bound the entropy of the target distribution given the history of query-answer pairs by the expected logarithm of the size of the prediction set for the ground-truth answer given the history. Then, utilizing conformal prediction, we propose two ways of constructing sequences of prediction sets, which allows us to provide accurate measures of informativeness for any given query at any iteration of the algorithm. To demonstrate the properties and behavior of our method, we perform thorough study of our method in the setting of 20Q. Finally, we apply our method to the setting of interactive medical question answering on the MediQ [70] dataset. Our results demonstrate not only the applicability of our method in real-world settings, but also its competitive predictive performance. Our code is available at https: // //www/ gi thub. com/ryanchankll Caona ormal Inf ormatiimiiiooomm onPursuit/.
2

---

2 Information Pursuit: A Framework for Sequential Information Gain
We first review the Information Pursuit (IP) framework [16, 38, 51], which will help us lay the groundwork for developing a greedy algorithm that asks queries using the information gain crite- rion 30, 51, 145]. Throughout the paper, (X, Y) denotes an input-output pair, where X : + X and Y : S2 + ) are random variables, 52 is the sample space, and X' and ) are the sets of values that they can take on. We denote by [X;; Y) the mutual information between X and Y. by (X) the entropy of the random variable X, and by HY X)) the conditional entropy of X given Y.
Setup. The modern generative version of IP is framework for making interpretable predictions: The user defines a set Q of task-relevant queries. Fach query q E Q is a function q X + A that maps the textual input x E X' an answer g(x) E A. For example, for the task of disease classification, X' contains the set of patient features (c.g., clinical notes), y is the set of disease labels (e.g. "pneumonia", "cardiomegaly") "), Q is a set of queries about the patient such "Are you coughing?" or "Do you have fever?", and A to be the set of possible query answers (e.g. "Yes, I do". "The patient feels warm."). Last but not least, for our question- question-answering answering task, all query-answers A and labels Y are a subset of the space of natural language X.
An important desired property of the query set is sufficiency, which states that for all x; y,
Pyy x) = Ply ((x)) = P(y | (x/ E X' ((x) = g(x),, Vq E ()).
That is, the answers to all queries about 2, 2(x) = {1(x) : q E 2), determine the posterior Pyy x)). In this work, we consider obtaining Q either from an offline set of answerable questions based on the task, by prompting an LLM pre-trained with open-domain knowledge, hence capable of generating any necessary query. In either case. Q is expected to satisfy sufficiency.
IP Algorithm. Given input r. X, the IP algorithm makes prediction for Y by sequentially selecting queries qt, 9 E Q in order of information gain, i.c., by maximizing the conditional information between query answer and the prediction given the history of prior query-answer pairs:
Q1 = IP()) = arg max (x))):
QEQ
(IP)
a++1 = IP( (P(1 ge ) = arg max (q((): 91:2 (xxbo))
When A: = O, the history of prior query-answer pairs is empty, i.e., Qi:k 0, and IP selects the query whose answer is most informative for predicting Y. When k 2 1, IP selects the most informative query conditioned on the history (z IP terminates at iteration L if Vgk+1 E Q, (9 Y (I)b)) = 0, meaning that additional query provides extra information about the target Y. In practice, evaluating P(Y 91.k (x=e())))) at test time allows us to observe how each query and answer affects the prediction at each iteration k = I,...,L.
IP for LLMs. Previous work of IP [16, 17, 19, 37, 60] involves learning the joint distribution P(Y, ((X)) (or the conditional distribution PY (x)x)))) from training data such that samples of TP(Y (1)) can be obtained efficiently. In contrast, here we assume that the conditional distribution given by an LLM directly: We construct a probabilistic predictor' f X + A()). which takes a text prompt as input and outputs a set of probability scores for each class. In particular, we first extract the logits of the output tokens of interest (such as class names), and then apply a softmax transform to obtain a predicted distribution (More details in Appendix $G.5).
Since P is given in this case, we can simplify by writing the equivalent formulation of (IP) as conditional entropy minimization, for each k:
argmax 7 ((g(X);3)))))))))(())))) gia ( (z = argmax (H(Y (2)a(2))))) - H( ((X)) qus })}
qEQ
qEQ
argmin (Y q(X), (1.)).i.(Ce (
gEQ
In other words, at any iteration, the query that maximizes the conditional mutual information also minimizes the conditional entropy. To find the query in (2), one would have to collect samples, estimate HY (zbb)) for each q, and select the query that minimizes the conditional entropy.
Note that PP( gl:k )x) = P(- (a' E E (xx)) = q (x for all i l,....k))
Here A A(Y) is the set of probability distributions over
3

---

However, as we have argued in I since f is not trained to model P(Y, Q(X)) but is extracted from an LLM that models (X) as a general language distribution, the output probabilities are often miscalibrated, motivating our need for an alternative approach to IP.
3 Conformal Information Pursuit: Information Gain with LLMs
3.1 Uncertainty Estimation via Predietive Inference
Next, we propose alternative approach which leverages recent developments in predictive inference and conformal prediction [5, 124]. Specifically, the results Correia al. [27] allow us to upper bound entropy by the size of certain prediction sets for the ground-truth answers, hence measuring uncertainty in a distribution- free and robust manner. We now turn to introducing this approach.
Preliminary on Predictive Inference. Consider function f that assigns to each value x the predicted probabilities f(x) = (f(z)..... (z) for the classes ...... |D/]. We may assume Paata- Predictive inference, generally speaking, seeks to provide guarantees about the prediction (X of new test sample
that ff is pre-trained with data drawn from some
(Xrest, Yuest) Pdata- One way of doing so is using prediction sels: For a threshold E [0, 1), prediction set function C- X - 2| selects labels with predicted probabilities ((r) larger than
(x) by y' fx m}}
(3)
Then, we seek to guarantee that the true label Yeest is in the prediction set C,- with probability 1 1- a.
While there are number of ways to set the threshold conformal prediction [102, 123] was introduced as non-parametris finite-sample way to achieve such guarantee. Specifically, we will introduce the method of Split Conformal Prediction (SCP) [88].
Let Deal = ((,,, Y i E [N]]. where (X,, Y.) ~ Paata and [N]] := [I.....N),
N). be a calibration dataset of leaeure-label, independent of the training samples of f. By only assuming the exchange- ability of the values f(X,),;, i E [N] U {lest., SCP satisfies the so-called marginal guarantee:
P PX Y Doat (Yeest E (+(ee)))) 2 1-a,
by setting as the [(1 - (N + 1)1 smallest of the values f(X.)r, E [N]S. Even if the distribution of f(X)y when (X, Y) ~ Paata does not have any point masses, then the coverage probability is also upper bounded by 1 aN for aN = a 1/(N + 1). Hence, (x) here is also commonly referred to conformal prediction set. As we will see later, while SCP assumptions are fairly mild, obtaining a calibration set from the same data distribution P in the sequential setting poses additional challenges.
Contrasting Notions of Uncertainty. There is plethora of work that uses notions from predictive inference, such as the size of a prediction set, as a means to measure uncertainty [4, 28, 32, 58, 82, 100, 101]. We seek mathematically characterize the relation between entropy and the size of prediction sets by leveraging a connection provided by Correia et al. [27] via the following proposition:
Proposition 3.1 (Correia et al. [27], simplified). For a E (0,0.5), consider any prediction set function C. satisfying
1 a S Px,y (Y E (X)) s 1 - aN.
(5)
Let A, == hs(a) + a -1 aN) logg a), where hB the binary entropy function. For the true distribution Paata, we have
H(Y X) < Aa + (1 Log
(6)
In words, the uncertainty of Y given data X is upper bounded by the expected size of the prediction set. The more uncertain one is about Y, the higher the entropy and the larger the prediction set size, and vice versa. The proposition also tells us the following: whatever the construction of the prediction set may be, as long as it satisfies the marginal guarantee, the relationship between entropy and prediction set holds. Next, using this fact, will derive conformalized formulation for IP.
*The definition typically requires defining a nonconformity score v ; X x y F. Here we directly define the ( y) = - Ply 2) for simplicity.
Which can be obtained via sample quantiles. See Algorithm 1.

---

3.2 Conformal Information Pursuit Algorithm
We will now formalize our proposed method. Since we leverage SCP to obtain prediction sets at test time, refer our new approach to IP as Conformal Information Pursuit (C-IP)). Throughout our work, we assume our prediction set takes the form
C. (vnaaat) = fUE E 3' P(Y (ua(t)))=== f()xx()))))))) (lona))) > >r)
Since both the query answers ((x) and the query-answer chains Q1:k (x) are represented as text, they both live in the domain of X. In the following, will use the results in $3.1 to derive new method for choosing the next query given history. For clarity, we use 7-) to denote r's dependencies.
C-IP: First Query Q1- To select the first query, recall from (2) that argmaxye ({((X); argminge@ H(Y ((X)). Therefore, we can use Proposition 3.1 to construct a C+(() for every q E @ that satisfies the marginal coverage guarantee (5):
1 1-a a S Px (Y C=(a) (q(x)) s aa.-
(8)
Then,
min H(Y [())) S min log Ex [(erso (((x))] TE
(9)
9E2
In words, C-IP selects the first query (1 by minimizing the above upper bound on the entropy.
C-IP: Subsequent Queries 9k. Similarly, for the subsequent iterations k 2 1, due to (2).
argmax, (g(X; 91.2 (2 argmin ge HYY q(X), (1xk)))))) Again, from Propo- sition 3.1, we construct a Cr (wobe)) for every E Q that satisfies the coverage guarantee (5) conditioned on the obtained 91:k (2oh)), i...
1- S PXXYD (Y Co (((()) qua (xoboo) 51- aN.
(10)
Then,
min H(Y |x(X), I1: S min log Ex [C [ (( (a(X)) I2 (1 q
(11)
qEQ
Our C-IP method aims to choose 9k by minimizing the above upper bound. We will refer to the algorithm that uses empirical estimates of the entropy the left-hand side of (11) IP and to the
algorithm that uses empirical estimates of the upper bound on the right-hand side of (11) as C-IP.
From our derivation above, directly applying Proposition 3.1 requires coverage guarantees in (8) and (10) that condition on the one instantiation of the history (x:b) obtained from running C-IP. Unfortunately, this is intractable in general [59, 64], as the number of possible Ll:k (z is exponentially large, of size ~ Q R. Even when the maximum number of iterations L is small, ensuring this would also in general require a large enough subset of the calibration dataset X,, i [N], with the same history qı (z:be)) Therefore, we propose related, but relaxed, formulation.
Obtaining Prediction Sets C. To ensure tractability, we propose the following guarantee:
1- S PX.Y Y E (=(a)(QLa(())) 1 - aN for l = 1,...,, L,
(12)
which means to offer guarantee over the distribution of random query-answer chains Q (X) with length l rather than single choice of 91:A (2:0b).. As result, our marginalized guarantee only requires us to construct L prediction set functions. We refer this as length marginalization.
With length marginalization in mind, we now turn the discussion to obtain samples from Q to construct C=(N) and satisfy (12). The question of how to efficiently sample histories arises in many occasions when implementing IP (see Related Work in Appendix $B for discussion). In this work, we consider two possible parameterizations, adaptive to the possible choices of the query set Q:
"We remark that "conformalized" often refers to a wrapper of method that enjoys conformal guarantee; this is not the sense in which we use it.
5

---

Sampling Histories from a Uniform Parameterization: When the query set Q is a closed set with pre-determined queries, an effective strategy to parameterize queries at each iteration with a uniform distribution over the query set. As for V-IP [17], we propose to marginalize our coverage over uniformly sampled histories of length k. At each iteration h = 1,...; It where I, is the maximum number of iterations allowed, let Qu: = (Q1, Qux) be selection of k queries sampled uniformly at random from the set 2, i.e.
Q l:k Unif( ( for k 1=1,..,,1 L.
(13)
Sampling Histories from LLM Simulations: If Q is an open query set with the space of questions in natural language, another option is to consider the distribution of histories obtained from LLMs. For a given observation bb and query chain gl.k= qk+11 can be obtained by directly prompting for the next query, i.e., 9k+11 ~ PLLM ( (2, (1))(=)))) We refer this strategy as Direct Prompting (DP) (see Appendix şI for the algorithm), where the distribution of queries is:
Q1:k ~ Y) for k == l=1....,1 L..
(14)
Hence, we obtain list of prediction set functions C=())...C C.II) for every length. The precise procedure is described in Appendix $1, Algorithm 1.
C-IP Algorithm. To summarize, the C-IP algorithm is as follows. First, we obtain a list of prediction set functions C₁2- Cr., based on the desired coverage a. Then, for any given observation 2o
Q1 C-IP(0) = argmin log Ex (IC)())((()))] sEQ
(C-IP)
qk+11 = C-IP((q, (x = argmin log Ex
(z
IEQ
Similar IP, the quantities in expectation are estimated by their empirical expectations. See Appendix ŞI for pseudocode for the IP, C-IP and DP algorithms.
Remark I: Stopping Criteria. As mentioned in $2, IP stops when Vi E 2,
0. From (2), this corresponds to Vqk+1 E Q, HY Ql:k4(2z0ng - HY gu (z)be)) 0 (also referred to as the stability criterion [17]. This also nicely extends to C-IP: When the model is highly confident, the prediction set should be on average a singleton, which implies V4k+1
Q, log Ex (IC+(e+++))) (k + 1] - log Ex [[Crra) (91:x = O. In other words, the stopping criteria are equivalent in IP and C-IP. In practice, this stringent stopping criterion may not be reached. Hence, we stop querying once the standard deviation of the estimated entropy for every query is smaller than chosen threshold 0. See Appendix $0.10 for more details.
Remark 2: Risk Control. Our marginalization approach is a means to estimate uncertainty. Ideally, one would characterize the full distribution over IP histories. We present our work first step in this direction, and consider the aspect of error control as future work.
Exploration with 20 Questions
To create simple synthetic setting for validating our framework, we explore the properties of IP and C-IP by playing 20Q with two LLMs, one Querier LLM and one Answerer LLM. The task is simple: The Answerer LLM thinks of animal and the Querier LLM is tasked guess it within 20 queries.
4.1 Experiment Setup
Dataset. We obtain 20 common animal names from the Animals with Attributes 2 (AwA2) [136] dataset. On the one hand, this ensures that the LLMs we consider have sufficient knowledge about each class, allowing us to accurately evaluate our algorithm in a setting where the LLM performance high. On the other hand, the Aw dataset provides an annotated set of binary attributes about each animal. This allows us to obtain a binary query set with expert-labeled answers. We consider a closed query set Qelosed, in which 85 annotated attributes from AwA2 are converted into textual questions. and an open query set Qopen, where queries are free-form questions obtained by prompting LLMs. We consider binary query-answers with Abinary = ("Yes", "No")) based on the AwA2 expert labels, and open gusre-answers with Areestext being the set of English sentences (Examples in Appendix 1). In the 20Q setting, the data space is equal to the label space (X' = Y), thus reducing the problem's complexity to help establish the effecttiveness of using info-theoretic quantities in guiding LLMs.

---

1.00
(N (lon Bin)
1.00
Baviiras Quity folwer
Estimated Entropy
Test Accuracy
0.75
Emprical 1
0.99
Coverage
Desied, 1-g-0
0.50
0.50
1.00
suy Qary femees
0.25
-andom thar Nh)
Random Iinn
0.75
[.Nandin))
0.00
GPIN01-9h)
0.50
1.00
(Kandan. C Sin.1
[8
1.00
CPP (8in]
Test Accuracy
0.75
E mtimmozz Entropy
0.75
Coverage
0.50
0.50
0.25
DP (on-dlin.)
(tin.)
P (Non Bin
:Bin.)
0.75
CPP (Noo (Non-Sin.)
- C-17 Itin)
0.00
0
B Number of Iterations
12
16
20
8 12
16
20
030
Number of Iterations
Number Inerations
Figure 3: Evaluations of C-IP with a closed query set Qeteed (top row) and open query set Qopen (bottom row). Each curve shows the average performance with shaded area as std.. Left column: Performance on the 20 Questions task of C-IP and baselines with binary (dashed) and non-binary (solid) query answers using Llama-3.1-8 1-88b. Middle columm: Uncertainty estimated by IP and C-IP, with cach curve evaluating the uncertainty of the selected query at cach iteration. Right column: Desired (dashed) and empirical (solid) coverage of C-IP. Hyperparameter choice is marked with different colors, with desired and empirical coverage as dashed and solid.
Models and Implementation. We consider three open-source instruction-tuned models: Llama-3.1 1- 8B [42], Qwen2.5-78 BBBBBBBBBBBBB. [7] and Phi-3-small [2]. We present results for Llama-3. 3-BB in the main text, and other results in Appendix $E.11 To achieve the target coverage for both closed and open query sets, we calibrate using 100 random histories and labels. Every entropy term is estimated with 4 randomly drawn samples. We obtain our prediction sets C's by sampling via (13) for the setting with closed query set Celoved and via (13) for the setting with open query set Copen- For LLM hyperparameters during generation, prompts, and further implementation details, refer to Appendix &G.
Baselines, To compare the performance of C-IP in the closed query set setting, we consider two baselines: Random, which uniformly selects query from Qelosed at each iteration, and IP, which evaluates (2) at each iteration. For the open query set setting, the baselines are Direct Prompting (DP) and Uncertainty of Thought (UoT) [49]. Direct Prompting, as described in $3.2 and Appendix $I, directly prompts the LLM for a single query at each iteration. Furthermore, we compare C-IP against IP with calibrated probabilities obtained via Platt Scaling [92] and Temperature Scaling [46].
4.2 Results
Predictive Performance. We evaluate C-IP against baselines on predictive performance Figure (top left). For each iteration up maximum of 20, we evaluate the test accuracy given (1."). We use a target coverage of - a = 0.9. For the results with binary answers, we observe a sharp difference between random selection and IP- basbd methods, with C-IP performing better each iteration. For non-binary answers, C-IP outperforms IP at every iteration, showing that early query selection weighs greatly for performance. While outperforming random selection in iterations 1-6, it performs comparably in iterations 7-20. We argue that this occurs due to the simplicity of the task, where the combination of open query- and random selection on task-relevant queries pre-determined by AwA2 provides sufficient information to achieve high accuracy. Overall, this result shows that C-IP is better method for selecting queries from a pre-defined, closed query set.
We perform a similar performance evaluation for C-IP with Qopen in Figure 3 (bottom left). Here, we observe that C-IP with 0.15 outperforms both baselines IP and DP. This shows that direct prompting may not always suggest the most informative query, and C-IP as an uncertainty estimate can potentially generalize to previously unseen queries.
Uncertainty Estimation. To ensure that C-IP selects informative queries, we evaluate the estimation of the entropy (Y 1 (X), (zbe)) at each iteration. C-IP bounds this via the size of prediction sets in (11) and IP directly estimates it as in (2). In Figure 3 (top middle), we observe that, for both binary Abiuar and free-text query answers Afree the C-IP bounds (blue curves) decrease as the algorithm progresses, whereas entropy estimates (orange curves) revolve around the same
7

---

level. This shows that C-IP uncertainty measures are more informative than entropy estimates. The results for C-IP with Qapen (Figure 3, bottom middle) also show a decrease in the estimated entropy as the number of iterations increases. In the case of binary query answers Abinary, while we observe less stable decay, C-IP still performs comparably with our baselines, showing that the estimation of uncertainty is robust despite noisy probabilities.
Empirical Coverage. To evaluate the coverage of our prediction sets, we choose three target values of a and evaluate the empirical probability that the true label is contained in the prediction set at each iteration over our test set (See Appendix $G. 11 for empirical formula). Our results are shown in Figure 3 (right column). For Celosed with both binary Abmary and free-text query answers Aree-wxt- the realized coverage is close to the target for
0.99, whereas our method undercovers for 1 1-a a 0.95 and 0.99. Overall, the choice of a largely influences the predictive performance of C-IP, which explains the superior performance for C-IP over IP and random query selection when 1 - a 0.99. On the other hand, for Copen with both binary Aninary and free-text query answers Arre- we observe a slight over-coverage for smaller choices of a and under-coverage for early iterations. This is likely due to the wide range of possible queries in few initial steps, leading to under-coverage and misspecification. See Appendix $F.1 for ablation studies regarding choices of a.
Comparison with Probability Calibration Methods. C- IP can be considered with miscalibrated measures of uncertainty. Here, we explore the option of first calibrating the predictive prob- abilities with popular calibration methods such as Platt Scaling and Temperature Scaling (TS), then applying IP with the updated probabilities. Briefly, Platt Scaling is parametric method that learns a linear regression model using the calibration data to re-calibrate probabilities, and TS is a non-parametric method that divides the predicted probabilities by some temperature scalar T. We evaluate three choices of temperature T E {0.5, 0.75, 1.25]. See more implementation details in $G.13.
version of IP that can be used
0.50
Test Accuracy
0.25
T5 IT-
(T- 0.75)
IP w T5 IT= 1.25)
IP w Platt Scating
CPP
0.00
4
8
12
20
Number of Iterations
1.00
Test Accuracy
0.75
The results of the comparison is shown in Figure 4. For an open query set Qopen. C-IP outperforms IP with cal- ibrated probabilities in the case of binary queries, and performs comparably with non-binary query answers. We hypothesize this occurs due to the complexity of the dis- tribution of histories, where distribution frree uncertainty quantification methods such as SCP shine.
0.50
IP T5 IT-
(T- 0.75)
0.25
IP w T5 IT 1.25)
IP w Platt Scalin
0.00
4
8
12
20
Number of Iterations
Comparison with UoT. We compare our method with a state-of-the-ar LLM reasoning method, Uncertainty-of- Thought (UoT) [49]. UoT handles multi-turn conversa- tions by propagating rewards based on information gain from future steps. At each iteration, it builds a shallow tree computing the information gain of a few potential trajectories, akin to seeing few steps ahead. Importantly, UoT applies only to the setting with open query set and binary query answers. We will compare UoT with IP and C-IP, as both are entropy- uncertainty quantification methods for interactive question answering. Further details are provided in Appendix G.
Figure 4: Comparison with Probability Cal- ibration Baselines under open query set- ting Qopen with binary (top) and free-text (bot- tom) query answers.
Our results are shown in Table 1. For bi- nary query answers, UoT achieves higher success rate than IP or C-IP. This is rea- sonable as accumulating information gain a few iterations ahead likely more ad- vantageous than using immediate rewards. However, for free-text query answers, C- IP achieves near 45% accuracy improve- ment, with a smaller average number of queries. Thus, using immediate reward with free-text query answers works better than accumu- lated entropy-based rewards with binary answers.
Table I: Comparison of C-IP with UoT reasoning, averaged across 5 runs with std..
Method UoT IP
Query Answers A
Avg. Len
Accuracy
binary
13.57 + 1.69
0.57 = 0.13
binary
11,40 - 0.78
0.31 0.04
IP
free-text
10.04 1: 0.45
0.65
C-IP (a - 0.1) C-IP (a (010=1)) 0.1)
binary
11.87 + 0.83
0.37 3.7
free-text
10.58 4 0.58
0.83 0.05
8

---

Internal Medicine (IM)
Pediatrics (P)
Neurolegy (N)
0.70
0.80
0.65
0.65
0066
0.55
0.55
0.62
0.53
0.45
Non-stq-entia
Enumerate
0.45
Enumerote
quette
0.44
Erumeratee
C-P
CIP
0.35
0.35
0.35
10
Number of Iterations
Number of iterations
Number of Iterations
1.0
1.0
1.0
0.9
0.9
0.9
Coverage
0.8
0.8
0.8
0.7
0.7
0.6
0.6
0.6
Desiad,
segiica Orperoa
0.5
0.5
5 6
2
3
4
5
6
3
5
Number of Iterations
Number of Iterations
Number of iterations
Figure 5: Top: Predictive Performance in Medical Interactive Question Answering on the MediQ dataset. The tasks are divided based on specialty. Desired coverage is - a = 0.8 for IM and P and - a = 0.7 for N. Bottom:
Comparison of empirical and desired coverage for C-IP. Desired coverage (dashed curve) is shown for 1 {0.7, 0.8, 0.9). Since the number of queries may depend the datapoints, Empirical Coverage (solid curve) iteration is evaluated for all test datapoints that have stopped at or before iteration Each curve averaged over three splits, with the shaded area denoting their standard deviation.
5
Application to Interactive Medical Question Answering
In this section, apply C-IP to an interactive medical We provide the basic setup here and other details (such as prompts) can found Appendix $G.
task on the MediQ dataset.
5.1 Setup
Dataset. MediQ [70] is an interactive medical question-answeriig dataset extended from MedQA [53], large-scale medical question-answering dataset designed to evaluate the profes- sional knowledge and clinical decision-making abilities of L.Mss. All data is drawn from medical licensing examinations the United States. Fach datapoint in MediQ contains medical question, four multiple-choice answers, label for the specialty/area, and a list of facts from context paragraph about the patient'. For IP this context, X' is the set patients' information, Q is the set (closed) queries one can ask about the patient, and ) is the set of multiple-choice answers.
The task simulates an interactive setting between an Expert LLM (the predictor and the querier in our nomenclature) and a Patient LLM (the svery-answerer), and the goal is that the Expert LLM diagnoses the patient by answering the provided medical questions.
our application, we consider medical questions from the following three categories: "Internal Medicine (IM)" (290 samples), "Pediatries (P)" (217 samples) and "Neurology (N)" (108 samples). We treat each category as single task, and the coverage is calculated using calibration data obtained from the same category.
Models and Evaluation. To ensure a fair evaluation, we divide each category into three equal sets: Dest for estimating entropy, Deal for calibration, and Diest for test-set evaluation. We perform three-fold cross validation and evaluate the average performance and its standard deviation. In our main text, we evaluate Llama-3.1-88 as both the Expert LLM and the Patient LLM. Similar to 20Q, we first obtain the output token's logit score based on the four options (A, B, C, D), then apply softmax to obtain an estimate of the posterior distribution P(Y (zbs)).
We compare with two baselines. In Non-sequential prediction, the Expert LLM makes single prediction based on all necessary information. This serves as an upper bound on the predictive performance, and has been shown outperform interactive methods [70]. In Enumerate, we provide the facts in the order of decomposition from the original context paragraph. Since our LLMs are inherently sequential, this acts if the LLM is reading the context paragraph in order.
Baselines.
The number of facts may vary depending the number of sentences each sample.

---

Context
Initial Info: An 84.year-old
with sacheelling urinary cotheter and history recureot aeplookthiass brought the energgancy Which of the following is most bieey to be present on this patient's wrine culnure?
Question:
Options:
(4) Gran-negarive onidsse-posiitee rult, (8) Grow-jorinne,, nomiiooc in-nsiistud cveel.
(C) Grau-pouttive gomnns-howsjj cocel, (D) Gram-aegative uxdaae-seggttvee rods.
qsi
What the moisture level of the patient's naicuu membranes?
2 qu (x
She has dry mnccuu membrrnee.
0.000
Q2i
W the white blood cell count to the urine?
History Qua ( (2nas)
2 9p (3rthee):
patiour ortented person, and the wrine stadies show WBC of 40:PPF
0.08
qa!
W the patiout's curvent body samprrauuee
0.06
Q3 (3
patiout's current body tomparature 38.3C (100.9"F).
0.04
qai
What the pationt's is currest body lomperature?
(x(
was broogght emergenccy deporiment from mursieg of
increusing confision over the past day.
0.00
3
(Suopping Critetia Reached, Output Final Prediction)
kumber berwiions
Prediction:
Explamation: The patient's symptoms and presentation suggest aringry tract infection (UT). The patient has an indwelling urinary catheterr which is fuctor UTb, pationt's sympttum of confusion common complecatio of UTIs, especiallyy in the elderly. The pationt's wrine studies show a high WBC count, which consiamou with a UTI The pattent's somperature of 38.3CC (100.) 9 "F) also suggests infection. Given these symptoms and patient's history of recurrent nepivalathiasss. the must likely cause of the UTI is a Gram negaiive, axidaee segaitve rod, such as Eacherichia coll coll), which is common cause of UTIs,
he indicativv d'olysirationn which is
especially in patients with Indwelling catheters, E. colt is Gram-aeguziiv, ouidast-neeuttiv rod, making option D the correct answer.
Figure 6: Example query-answe chain produced by C-IP for a patient in Internal Medicine. C-IP sequentially selects queries that approximately reduce uncertainty (i.c. average prediction set sizes from (11) at cach iteration. The posterior P(Y 91 (x)))) is also estimated and prediction is made. Once uncertainty drops below chosen threshold s, the C-IP algorithm stops and makes a final prediction. Based on the obtained query-answe chain and the prediction, an explanation is also generated.
Query Set Construction. We find that constructing a single query set for the entire test set often leads to queries with unknown query answers. Hence, we construct query set for each test datapoint based on the existing atomic facts in the input, by converting each fact into a question. Therefore, the goal of the IP algorithm is to select the queries with answers obtainable from the context. We find this setting more constructive compared to the setting with a single query set for all evaluations.
5.2 Results
Predictive Performance and Coverage. The performance of C-IP and the baselines for the three specialties is shown in Figure 5. C-IP and IP achieves comparable performance in all cases. This suggests that C-IP selects more informative queries during the interactive process. To explain the effectiveness of C-IP and why it did not strongly outperform baselines for N, we analyze their empirical coverage at each iteration. We observe that C-IP has valid coverage IM and but undercovers for N. This is likely due to the small calibration set size for N (36 datapoints).
Explanations. We show a run-down of the C-IP algorithm in Figure 6. Before any query selection, the Expert LLM is provided with initial information, the medical question, and possible options for the answer. Then, C-IP selects the first query 91 "What is the moisture level of the patient's 's mucous membranes?", to which the Patient LLM responds Qı (2* This process continues until the uncertainty measured based on the posterior of the answer options from the Expert I.I.M drops below 0.01. Once C-IP stops, it makes the final prediction "D", and summarizes the query-answe chain into a paragraph explaining the decision. More examples (including other specialties) are shown in Appendix $J.2.
"She has dry mucous membranes".
6 Conclusion and Future Work
In this work, we proposed C-IP, a novel sequential information pursuit algorithm that uses prediction set sizes as alternative to conditional entropy estimate uncertainty. We leveraged a mathematical connection between prediction sets and entropy, and proposed two sampling methods for obtaining histories. Through empirical studies on 20Q and MediQ datasets, demonstrated that our proposed approach performs well in practice, and that the size of the prediction sets is an effective measure of uncertainty. As suggested in $3 Remark 2, interesting avenue for future work is to provide guarantees for the correctness of the prediction given query-answer answer chains, P(Y q2s4 (1)h()))))), obtained by C-IP and for the query-answer chains (1rb themselves. Doing so would require careful characterization of the distribution Q IP({g, q (x))
10

---

Acknowledgements
K. H. R. C. would personally like thank Tianjiao Ding, Uday Kiran Reddy Tadipatri, Liangzu Peng, Darshan Thaker, Kyle Poe, Buyun Liang, Ryan Pilgrim, Aditya Chattopadhyay. and Zitong Yang for fruitful discussions. K. H. R. C., Y. G., and V. acknowledge the support from NSF 2031985, Simons Foundation 814201 (THEORINET), University of Pennsylvania Startup Funds, NSF Graduate Research Fellowship Program, Penn Engineering Dean's Fellowship and Amazon Fellowship. E. D. was partially supported by the NSE ARO, AFOSR, ONR, and the Sloan Foundation. H. H. was supported by the NSF CAREER award 1943694

---

References
[1] Z. Abbasiantaeb, Y. Yuan, E. Kanoulas, and M. Aliannejadi. Let the LLMs talk: Simulating human-to-human conversational QA via zero-shot LLM-to-LLM interactions. Proceedings of the 17th ACM International Conference on Web Search and Data Mining, 2023.
[2] M. Abdin, J. Aneja, H. Awadalla, A. Awadallah, A. A. Awan, N. Bach, A. Bahree, A. Bakhtiari, J. Bao, H. Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone. arXiv preprint arXiv:2404
2024.
[3] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, Akkaya, F. L. Aleman, Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[4] A. Angelopoulos, S. Bates, J. Malik, and M. I. Jordan. Uncertainty sets for image classifiers using conformal prediction. arXiv preprint arXiv:2009. /4/93, 2020.
[5] A. N. Angelopoulos and S. Bates. Conformal prediction: A gentle introduction. Foundations and Trends@ in Machine Learning, 16(4):494-51, 2023.
[6] Y. Ba, M. Mancenido, and R. Pan. Fill in the gaps: Model calibration and generalization with synthetic data. In Conference Empirical Methods in Natural Language Processing, pages 17211-17225, 2024.
[7] J. Bai, S. Bai, Y. Chu, Z. Cui, K. Dang. X. Deng, Y. Fan, W. Ge, Y. Han, F. Huang, et al. Qwen technical report. arXiv preprint WxXi::2309116609 2023.
[8] S. Bates, E. Candès, L. Lei, Y. Romano, and M. Sesia. Testing for outliers with conformal p-values. The Annals of Statisties, 51(1):149-177 2023.
[9] A. M. Bean, R. Payne, G. Parsons, H. R. Kirk, J. Ciro, R. Mosquera, S. H. Monsalve, A. S. Ekanayaka, L. Tarassenko, L. Rocher, et al. Clinical knowledge in Ilms does not translate to 2025.
human interactions. arXiv preprint arXiv:2504.189
[10] A. Ben Abacha and D. Demner-Fushman. A question-entailment approach question answering. BMC bioinformatics, 20:1-23, 2019.
[11] L. Bertolazzi, D. Mazzaccara, F. Merlo, and R. Bernardi. ChatGPT's information seeking strategy: Insights from the 20-questions game. In Proceedings of the 16th International Natural Language Generation Conference, pages 153-162, 2023.
[12] M. Biancofiore, Deldjoo, D. Noia, E. Di Sciascio, and Nardueci. Interactive question answering systems: Literature review. ACM Computing Surveys, 56(9):1-38, 2024.
[13] A. Bodrova, P. Xu, Varley, A. Zeng, A. Majumdar, D. Sadigh, Singh, F. Xia, N. Brown, L. Takayama, A. Z. Ren, A. Dixit, Z. Xu, and S. Tu. Robots that ask for help: Uncertainty alignment for large language model planners. ArXiv, abs/2307.0 021/2307701925 01922, 2023. URL. https: //api.semantics semanticschhlarr org/ CorppsId:: 259342058.
[14] L. Buitinck, G. Louppe, M. Blondel, F. Pedregosa, A. Mueller, O. Grisel, V. Niculae, P. Pretten- hofer, A. Gramfort, J. Grobler, R. Layton. J. VanderPlas, A. Joly. B. Holt, and G. Varoquaux. API design for machine learning software: experiences from the seikit-learn project. In ECML Languages for Data Mining and Machine Learning, pages 108-122, 2013,
PKDD Workshop:
[15] E. Y. Chang. Evince: Optimizing multi-llm dialogues using conditional statisties and informa- tion theory. arXiv preprint arXiv:2408. 14575, 2024.
[16] A. Chattopadhyay, S. Slocum, B. D. Haeffele, R. Vidal, and D. Geman. Interpretable by design: Learning predictors by composing interpretable queries. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[17] A. Chattopadhyay, H. R. Chan, B. D. Haeffele, D. Geman, and R. Vidal. Variational information pursuit for interpretable predictions. arXiv preprint 07X7v.2302.02886, 2023.
12

---

[18] A. Chattopadhyay. R. Pilgrim, and R. Vidal. Information maximization perspective of orthog- onal matching pursuit with upplications to explainable ai. Advances Neural Information 2023.
P Processing Systems,
[19] A. Chattopadhyay, K. H. R. Chan, and R. Vidal. Bootstrapping variational information pursuit with large language and vision models for interpretable image classification. In The Twelfth International Conference on Learning Representations, 2024.
[20] J. Chen and J. Mueller. Quantifying uncertainty in answers from any language model and enhancing their trustworthiness. In Annual Meeting of the Association for Computational Linguistics, 2023. URL https: att.aap..aaaaaa semanti cacantrscchoaa... wawaaarrrrrg//oeee arg/CorpusId: (0rppsI1d:636110555 263611057.
[21] Y. Chen, S. H. Hassani, A. Karbasi, and A. Krause. Sequential information maximization: When greedy near-optimal? In Conference on Learning Theory, pages 338-363, PMLR, 2015.
[22] Z. Chen, K. Zhou, B. Zhang, Z. Gong, W. X. Zhao, and J. rong Wen. Chatcot: Tool-augmented chain-of-thought reasoning chat-based large language models. ArXiv, abs/2305. 14323, org/ pdf 2305 14323. pdf.
2023. URL. https:ttpp/t
[23] J. Cherian, I. Gibbs, and E. Candes. Large language model validity via enhanced conformal prediction methods. In Advances in Neural Information Processing Systems, volume 37, pages 118812-1 2024.
[24] J. J. Cherian, I. Gibbs, and E. Candès, Large language model validity via enhanced conformal prediction methods. ArXiv, abs/2406.09714, 2024. URL wttph::t///app. /ppi......... semanticscholar. mng/CorppsId:
270521155.
[25] V. Chemoohukov, K. Wuthrich, and Y. Zhu. Exact and robust conformal inference methods for predictive machine learning with dependent data, In Proceedings of the 31st Conference On Learning Theory, 2018
[26] A. Comas, A. Chattopadhyay, F. Formosa, C. Liu, O. Camps, and R. Vidal. Incode: In- terpretable compressed descriptions for image generation. In The Thirteenth International Conference on Learning Representations, 2025.
[27] A. H. Correia, F. Massoli, C. Louizos, and A. Behboodi. An information theoretic perspec- tive on conformal prediction. arXiv preprint urXiv:2405.02144 2024.
[28] C. Cortes, A. Mao, C. Mohri, M. Mohri, and Y. Zhong. Cardinality-awar set prediction and top-k classification. arXiv preprint arXiv:2407.07/1 140, 2024.
[29] I. C. Covert, W. Qiu, M. Lu, N. Y. Kim, N. J. White, and S.-I. Lee. Learning to maximize mutual information for dynamic feature selection. In International Conference on Machine Learning, pages
PMLR, 2023.
[30] S. Dasgupta. Analysis of greedy active learning strategy. Advances in Neural Information Processing Systems, 17, 2004.
[31] G. Detommaso, M. Bertran, R. Fogliato, and A. Roth. Multicalibration for confidence scoring in LLMs. arXiv preprint arXiv:2404,0m 244.22994.046899 2024.
[32] G. S. Dhillon, G. Deligiannidis, and T. Rainforth. On the expected size of conformal prediction sets. In International Conference on Artificial Intelligence and Statistics, pages 1549-1557. PMLR, 2024.
[33] R. Dunn, L. Wasserman, and A. Ramdas. Distribution-free prediction sets for two-layer hierarchical models. Journal of the American Statistical Association, pages 1-12, 2022.
[34] B.-S. Einbinder, Y. Romano, M. Sesia, and Y. Zhou. Training uncertainty-aware classifiers with conformalized deep learning. Advances in Neural Information Processing Systems, 2022.
[35] S. Feldman, L. Ringel, S. Bates, and Y. Romano. Achieving risk control in online learning settings. Trans. Mach. Learn. Res., 2023, 2022. URL. https: //arxiv....i//////a///i wwtps/o.ggg///////e////. /2205. 09095. pdf.
13

---

[36] O. F'eron, J. Josse, Y. Goude, M. Zaffran, and A. Dieuleveut. Adaptive conformal predictions for time series. In International Conference on Machine Learning. 2022. URL https: //api. semanticscholar
[37] Y. Ge, K. H. R. Chan, P. Messina, and R. Vidal. Ip-crr: Information pursuit for interpretable classification of chest radiology reports. arXiv preprint arXiv:2505.00191 2025.
[38] D. Geman and B. Jedynak. An active testing model for tracking roads in satellite images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(1):1-14, 1996.
[39] J. Geng, F. Cai, Y. Wang, H. Koeppl, P. Nakov, and I. Gurevych. A survey of confidence estimation and calibration in large language models. In North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 6577-6595, 2024.
[40] I. Gibbs and E. Candès. ArXiv, abs/2106.00170, 2021. URL attpps///api semanticscholar org/Corpusio 235266057.
Adaptive conformal inference under distribution shift.
[41] I. Gibbs and R. Candès. Conformal inference for online prediction with arbitrary distribution shifts. J. Mach. Learn. Res., 15:162:: 2022. htt.https:/app URK.httpss/ppp...eant.cccoooo semanticscholar. org/ hrt/CorppsId::211ee 251622248.
[42] Grattafiori, A. Dubey, Jauhri, Pandey, A. Kadian, A. Al-Dahle, Letman, Mathur, A. Schelten, A. Vaughan, et al. The llama herd of models. arXiv preprint arXiv:2407.21783, 2024.
[43] L. Guan. A conformal test of linear models via permutation-augmenntel regressions. arXiv preprint arXivv2309.05450 05482, 2023.
[44] L. Guan. Localized conformal prediction: A generalized inference framework for conformal prediction. Biometrika, 1 110(1):33-50, 2023.
[45] L. Guan and R. Tibshirani. Prediction and outlier detection in classification problems. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(2):224-546, 2022.
[46] Guo, Pleiss, Sun, and Q. Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321-1330. PMLR, 2017.
[47] A. Holtzman, J. Buys, L. Du, M. Forbes, and Y. Choi. The curious case of neural text degeneration. arXiv preprint wxXiv:1904.097355 2019.
[48] B. Hou, Y. Liu, K. Qian, J. Andreas, S. Chang, and Y. Zhang. Decomposing uncertainty for large language models through input clarification ensembling. ArXiv, abs/2311.087/11 2023. URL https://aaaaaa
semanticsche
org/ Corpus 265213390.
[49] Z. Hu, C. Liu, X. Feng, Y. Zhao, S.-K. Ng, A. T. Luu, J. He, P. W. Koh, and B. Hooi. Uncertainty Thoughts: Uncertainty-awan planning enhances information seeking in large language models. arXiv preprint arXiv:2402.03277 2024.
[50] Z. Huang, S. Rossi, R. Yuan, and T. Hannagan. From predictions to confidence intervals: an empirical study of conformal prediction methods for in-context learning. In unknown, 2025. URL https: www.pisseaaaiiccolleeeeeeee wwwpchhlllr.r.oooeeoooeooeoooeee Id:://ooo::d::::::: :277999432.
[51] E. Jahangiri, E. Yörük,, R. Vidal, L.. Younes, and D. Geman. Information Pursuit: A Bayesian framework for sequential scene parsing, arXiv preprint
2017.
[52] P. Jiang, J. Rayan, S. P. Dow, and H. Xia. Graphologue: Exploring large language model responses with interactive diagrams. In Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, 2023.
[53] D. Jin, E. Pan, N. Oufattole, W.-H. Weng, H. Fang, and P. Szolovits. What disease does this patient have. Large-scale Open Domain Question Answering Dataset from Medical Exams. arXiv [cs. CLJ, 2020.
14

---

[54] Q. Jin, B. Dhingra, Z. Liu, W. W. Cohen, and X. Lu. Pubmedqa: A dataset for biomedical research question answering. arXiv preprint arXiv: 1e..9999996666, 2019.
[55] S. Kadavath, T. Conerly, A. Askell, T. Henighan, D. Drain, E. Perez, N. Schiefer, Z. Hattield- Dodds, N. DasSarma, E. Tran- Johnson et al. Language models (mostly) know what they know. arXiv preprint arXiv: 000022,,.22.... 2022.
[56] Kaur, S. Jha, A. Roy, S. Park. Dobriban, O. Sokolsky, and I. Lee. iDECODe: In- distribution equivariance for conformal outoo-ddistribution detection. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[57] R. Kaur, C. Samplawski, A. D. Cobb, A. Roy, B. Matejek, M. Acharya, D. Elenius, A. M. Berenbeim, J. Pavlik, N. D. Bastian, and S. Jha. Addressing uncertainty in llms to enhance relia- bility generative ai. ArXiv, abs/2411.02381, 2024. URL wtt.aap...mmaiiiiiim semanticscholas org/ GorpusId:2738220
[58] S. Kiyani, G. J. Pappas, and H. Hassani. Length optimization in conformal prediction. In Advances in Neural Information Processing Systems, volume 37, pages 99519-99563, 2024.
[59] C. Koch, C. Strassle, and L.-Y. Tan. Superconstant inapproximability of decision tree learning. Proceedings of Machine Learning Research vol, 196:1-32, 2024.
[60] S. Kolek, A. Chattopadhyay, K. H. R. Chan, H. Andrade-Loarge G. Kutyniok, and R. Vidal. Learning interpretable queries for explainable image classification with information pursuit. arXiv preprint arXiv:2312.11544 2023.
[61] B. Kumar, C. Lu, G. Gupta, A. Palepu, D. Bellamy, R. Raskar, and A. Beam. Conformal prediction with large language models for multi-choie question answering. arXiv preprint arXiv:2305. 1e223305.8444 18404, 2023.
[62] B. Kumar, C.-C. Lu, G. Gupta, A. Palepu, D. R. Bellamy, R. Raskar, and A. Beam. Conformal prediction with large language models for multi-choice question answering. ArXiv, abs/2305. 18404, 2023. URL https://api semanticscholas caw.aarroor/C/ooCoioooooo 258967849.
[63] P. Laban, H. Hayashi, Y. Zhou, and J. Neville. Lims get lost in multi-turn conversation. arXiv preprint arXiv:2505.0611 2025.
[64] H. Laurent and R. L. Rivest. Constructing optimal binary decision trees np-complete. Information processing letters, 5(1):15-17, 1976.
[65] J. Lei and L. Wasserman. Distribution-free prediction bands for non-parametric regression. Journal of the Royal Statistical Society: Series (Statistical Methodology), 76(1):71-96, 2014.
[66] J. Lei, Robins, and Wasserman. Distribution prediction sets. Journal of the American Statistical Association, 108(501):278-877, 2013.
[67] J. Lei, A. Rinaldo, and L.. Wasserman. A conformal prediction approach to explore functional data. Annals of Mathematics and Artificial Intelligence, 43, 2015.
[68] J. Lei, M. G'Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman. Distribution- freee predictive inference for regression. Journal of the American Statistical Association, 1136523):1094-11 1111, 2018.
[69] S. Li, X. Ji, E. Dobriban, O. Sokolsky, and I. Lee. PAC-Wrap: Semi-supervised pac anomaly detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
[70] S. Li, V. Balachandran, S. Feng, J. Ilgen, E. Pierson, P. W. W. Koh, and Y. Tsvetkov. MediQ: Duestion-asking Ilms and a benchmark for reliable interactive clinical reasoning. Advances in Neural Information Processing Systems, 37:28858-2888 28888, 2024.
[71] Y. Li, X. Shen, X. Yao, X. Ding, Y. Miao, R. Krishnan, and R. Padman. Beyond single-turn: A survey on multi-tum turn interactions with large language models. arXiv preprint 2rXiv:2504.04717. 2025.
15

---

[72] Z. Liang, Y. Zhou, and M. Sesia. Conformal inference is (almost) free for neural networks trained with early stopping. In International Conference on Machine Learning. 2023.
[73] Z. Liang, M. Sesia, and W. Sun. Integrative conformal p-values for out-of-distribution testing with labelled outliers. Journal of the Royal Statistical Society Series B: Statistical Methodology, page gkad133 38, 01 2024.
[74] Z. Lin, S. Trivedi, and J. Sun. Generating with confidence: Uncertainty quantification for black-box large language models. Trans. Mach. Learn. Res., 2024, 2023. URL https: //api. app.ssematicccciee semanticscholar org/ /Crrpussdd 258967487.
[75] C. Ling, X. Zhao, X. Zhang, W. Cheng, Y. Liu, Y. Sun, M. Oishi, I. Osaki, K. Matsuda, J. Ji, et al. Uncertainty quantification for in-context learning of large language models. arXiv preprint 10Xv:2240.10089, 2024.
[76] O. Liu, D. Fu, D. Yogatama, and W. Neiswanger. DeLLMa: Decision making under uncertainty with large language models. arXiv preprint arXiv:2402.02392 2024.
[77] S. Luttrell. The use of transinformation in the design of data sampling schemes for inverse problems. Inverse Problems, 1(3):199, 1985.
[78] Q. Lyu, K. Shridhar, C. Malaviya, L. Zhang, Y. Elazar, N. Tandon, M. Apidianaki, M. Sachan, and C. Callison- Burch. Calibrating large language models with sample consistency. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 19260-19268, 2025.
[79] D. J. MacKay, Information theory, inference and learning algorithms. Cambridge university press, 2003.
[80] C. Mohri and T. Hashimoto. Language models with conformal factuality guarantees. In International Conference on Machine Learning, pages (6029-36047 PMLR, 2024.
[81] C. Mohri and T. Hashimoto. ArXiv, abs/2402.100788, 2024. 267750963.
Language models with conformal factuality guarantees.
URL https://api. semanticscholar. wwwpllaarrrrr/oooruuee Corpusdd:
[82] Müller and M. W. Watson. Measuring uncertainty about long-run predictions. Review of Economic Studies, 83(4): 2016.
[83] H. Naveed, A. U. Khan, S. Qiu, M. Saqib, S. Anwar, M. Usman, N. Akhtar, N. Barnes, and A. Mian. A comprehensive overview of large language models. arXiv preprint 2023.
arXiv:2307.0644
[84] D. Noever and F. McKee. Chatbots problem solvers: Playing twenty questions with role reversals. arXiv preprint 2rX1122301.01743, 2023.
[85] A. Pal, L. K. Umapathi, and M. Sankarasubbu. Medmcqa: A large-scale multi-subject multi- choice dataset for medical domain question answering. In Conference on health, inference, and learning, pages 248-260. PMLR, 2022.
[86] A. Panchenko, E. Fadeeva, M. Panov, D. Vasilev, T. Baldwin, A. Tsvigun, K. Fedyanin, A. Shelmanov, E. Goncharova, S. Petrakov, A. Vazhentsev, and R. Vashurin. Lm-polygraph: Uncertainty estimation for language models. ArXiv, abs/2311.07388 2023. URL https: www.sseeaaiisiiiiieeeee
[87] Pang, H.-B Fan, P. Wang, J.-H. Xiao, N. Tang, S.-H. Yang, C. Jia, S.-J. Huang, and Y. Yu. Empowering language models with active inquiry for deeper understanding. arXiv preprint arXiv:2402.03719, 2024.
[88] H. Papadopoulos, K. Proedrou, V. Vovk, and A. Gammerman. Inductive confidence machines for regression. European Conference on Machine Learning, pages 345-356 Springer, 2002.
[89] S. Park, Bastani, N. Matni, and I. Lee. PAC confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020.
16

---

[90] S. Park, E. Dobriban, I. Lee, and O. Bastani. PAC prediction sets under covariate shift. In International Conference on Learning Representationss 2022.
[91] S. Park, E. Dobriban, I. Lee, and O. Bastani. PAC prediction sets for meta-learning. In Advances in Neural Information Processing Systems, 2022.
[92] J. Platt et al. Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods. Advances in large margin classifiers, 10(3):61-74, 1999.
[93] Qiu, Dobriban, and E. Tchetgen Tchetgen. Prediction sets adaptive unknown covariate shift. Journal of the Royal Statistical Society Series B: Statistical Methodology, page qkad069, 2023.
[94] V. Quach, A. Fisch, T. Schuster, A. Yala, J. Sohn, T. Jaakkola, and R. Barzilay. Conformal language modeling. ArXiv, abs/2306. 10193, 2023. URL https:t/aapp /ppi. https::/api..emanticeeeee semanticscholar. org/ htg/Corpusid: 259203582.
[95] V. Quach, A. Fisch, T. Schuster, A. Yala, H. Sohn, S.S. Jaakkola, and R. Barzilay. Conformal language modeling. The Twelfth International Conference on Learning Representations, 2024.
[96] H. Rajabzadeh, S. Wang, H. J. Kwon, and B. Liu. Multimodal multi-hop question answering through conversation between tools and efficiently finetuned large language models, arXiv preprint arXiv:2309.0888 2023.
[97] A. Z. Ren, A. Dixit, A. Bodrova, S. Singh, S. Tu, N. Brown, P. Xu, L. Takayama, F. Xia, J. Varley, Z. Xu, D. Sadigh, A. Zeng. and A. Majumdar. Robots that ask for help: Uncertainty alignment for large language model planners. ArXiv, abs/2307.01928, 2023. URL https: / //arxiv.orz .rt. /ssf/df/// 2307 01928.1911... pdf.
[98] A. Z. Ren, J. Clark, A. Dixit, M. Itkina, A. Majumdar, and D. Sadigh. Explore until confident: Efficient exploration for embodied question answering. arXiv preprint 19X1 2024.
[99] J. Robinson and D. Wingate. Leveraging large language models for multiple choice question answering. In International Conference on Learning Representations, 2023.
[100] Y. Romano, M. Sesia, and E. Candes. Classification with valid and adaptive coverage. Advances in Neural Information Processing Systems, 2020.
[101] M. Sadinle, Lei, and L. Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 1 114(525):223-2) 234, 2019.
[102] C. Saunders, A. Gammerman, and V. Vovk. Transduction with confidence and credibility. In Sixteenth International Joint Conference Artificial Intelligence, pages 722-726, 1999.
[103] H. Scheffe and J. W. Tukey. Non-paramettrt estimation. I. Validation of order statistics. The Annals of Mathematical Statistics, 16(2):187-192 1945.
[104] T. Schuster, A. Fisch, J. Gupta, M. Dehghani, Bahri, V. Q. Tran, Y. Tay, and Metzler. Confident adaptive language modeling. ArXiv, abs/2207.07061, 2022. URL https://arxin org/pdf/2201 07061. pdf.
[105] M. Sesia, S. Favaro, and F. Dobriban. Conformal frequency estimation using discrete sketched data with coverage for distinct queries. Journal of Machine Learning Research, 24(348):1-80 2023.
[106] H. Shahrokhi, D. Roy, Y. Yan, V. Arnouddoa, and J. R. Doppa. Conformal prediction sets for deep generative models via reduction to conformal regression. ArXiv, abs/2503. 10512, 2025. URL https://appp htttp::/api..seaaniicchooo semanticscholar
Prrg/Corpusid: 276961117.....
[107] F. Shannon. mathematical theory of communication. The Bell system technical journal, 27(3):379-422 4233, 1948.
17

---

[108] C. E. Shannon. A mathematical theory of communication. ACM SIGMOBILE mobile comput- ing and communications review, 5(1):3-55, 2001.
[109] M. Shen, S. Das, K. Greenewald, Sattigeri, G. Wornell, and S. Ghosh. Thermometer: Towards universal calibration for large language models. arXiv preprint arXiv:2403.08819 2024.
[110] W. Si, S. Park, Lee, E. Dobriban, and O. Bastani. PAC prediction sets under label shift, In The Twelfth International Conference on Learning Representations, 2024.
[111] K. Singhal, T. Tu, J. Gottweis, R. Sayres, E. Wulczyn, M. Amin, L. Hou, K. Clark, S. R. Pfohl, H. Cole-Lewis, et al. Toward expert-level medical question answering with large language models. Nature Medicine, pages 1-8, 2025.
[112] J. Song, Z. Wang. H. Chen, Y. Huang. and L. Ma. Look before you leap: An exploratory study of uncertainty measurement for large language models. ArXiv, abs/2307.102366 2023. URL CorpusId:
https://api www.nteemmniiimmmm eeemanticschol.. cscholar. org//orpusId:2599911 2599911114
[113] C. Spiess, D. Gros, K. S. Pai, M. Pradel, M. R. I. Rabin, A. Alipour, S. Jha, P. Devanbu, and T. Ahmed. Calibration and correctness of language models for code. In JEEE/ACM 47th International Conference on Software Engineering, pages 495-507. IEEE Computer Society, 2025.
[114] J. Su, J. Luo, H. Wang, and L. Cheng. Api is enough: Conformal prediction for large language models without logit-access. In Conference on Empirical Methods in Natural Language Processing, 2024. URL https://api www.nticscoolaattt...e. org/ wwt.:oorg///aae.. (oorpusId:2682308808
[115] H. Suri, Q. Zhang. W. Huo. Y. Liu, and C. Guan. Mediaqa: A question answering dataset on medical dialogues. arXiv preprint viXiv22108.08077 2021.
[116] J. H. Szabadváry. Beyond conformal predictors: Adaptive conformal inference with confidence predictors. arXiv preprint urXiv:2409. 15548, 2024.
[117) S. Tayebati, D. Kumar, N. Darabi, D. Jayasuriya, R. Krishnan, and A. R. Trivedi. Learning conformal abstention policies for adaptive risk management in large language and vision- language models. ArXiv, abs/2502.06884, 2025. URL https: //apx////iiv/////a///// or arggpdf/25000 06884.pdi
[118] K. Tian, E. Mitchell, A. Zhou, A. Sharma, R. Rafailov, H. Yao, C. Finn, and C. D. Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. arXiv preprint arXiv:2305. 14975, 2023.
[119] J. W. Tukey. Mon-paramettro estimation Statistically equivalent blocks and tolerance regions-the continuous case. The Annals of Mathematical Statistics, 18(4):529-539 1947.
[120] J. W. Tukey. Nomparametric estimation, III. Statistically equivalent blocks and multivariate tolerance regions-the discontinuous case. The Annals of Mathematical Statistics, 19(1):30-39, 1948.
[121] D. T. Ulmer, M. Gubri, H. Lee, S. Yun, and S. J. Oh. Calibrating large language models using their generations only. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics, pages 15440-15459, Association for Computational Linguistics, 2024.
[122] V. Vovk. Conditional validity of inductive conformal predictors. In Asian Conference on Machine Learning, pages 475-490. PMLR, 2012.
[123] V. Vovk, A. Gammerman, and C. Saunders. Machine-learinng applications of algorithmic randomness. In International Conference on Machine Learning, 1999.
[124] V. Vovk, A. Gammerman, and G. Shafer. Algorithmic Learning in Random World. Springer Science & Business Media, 2005.
[125] A. Wald. An extension of Wilks' method for setting tolerance limits. The Annals of Mathemat- ical Statistics, 14(1):45-55, 1943.
18

---

[126] B. Wang, X. Yue, and H. Sun. Can ChatGPT defend its belief in truth? evaluating LLM reasoning via debate. In Conference on Empirical Methods in Natural Language Processing. 2023.
[127] K. Wang, F. Duan, S. Wang, P. Li, Y. Xian, C. Yin, W. Rong, and Z. Xiong. Knowledge-Driven CoT: Exploring faithful reasoning LLMs for knowledge-intense question answering. arXiv preprini 2r0iv:2308. 13259, 2023.
[128] P. Wang, L. Li, L. Chen, Z. Cai, D. Zhu, B. Lin, Y. Cao, Q. Liu, T. Liu, and Z. Sui. Large language models are not fair evaluators. arXiv preprint arXiv:2305. 2023.
[129] Q. Wang, T. Geng, Z. Wang, T. Wang, B. Fu, and F. Zheng. Sample then identify: A general framework for risk control and assessment in multimodal large language models. ArXiv, abs/2410.08174, 2024. URL https://app //ppi. sewanticschollieee .ww.a...r////eee. org/CorpusIdl 273233940.
[130] X.
Wang and Hyndman. Online conformal inference for multi-step time series forecasting. arXiv preprint PrXiv:2410.13111 2024.
[131] Z. Wang, Q. Wang, Y. Zhang, T. Chen, X. Zhu, X. Shi, and K. Xu. Sconu: Selective conformal uncertainty large language models. In unknown, 2025. URL https://api. terg/Corpusid. 277954950.
[132] J. Wei, Y. Tay, R. Bommasani, C. Raffel, B. Zoph, S. Borgeaud, D. Yogatama, M. Bosma, D. Zhou, D. Metzler, et al. Emergent abilities of large language models. arXiv preprini arXiv:2206.0766
2022.
[133] S. S. Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathematical Statistics, 12(1):91-96, 1941.
[134] S. Wu, X. Shen, and R. Xia. A new dialogue response generation agent for large language models by asking questions to detect user's intentions. arXiv preprint arXiv:2310.03293 2023.
[135) H. Xi, K. Liu, H. Zeng, W. Sun, and H. Wei. Robust online conformal prediction under uniform label noise. ArXiv, abs/2501.11833,, 2025. URL https://pppi http:////ppp.sseaniiieeeeeeeo www.nticscholla.............a.aa org/
[136] Y. Xian, C. H. Lampert, B. Schiele, and Z. Akata. Zero-shot learning- a comprehensive evaluation of the good, the bad and the ugly. IEEE transactions on pattern analysis and machine intelligence, 41(9):2251-2266 2018
[137] G. Xiong, J. Bao, and W. Zhao. InteractiveKBQQA: Multi-turn interactions for knowledge base question answering with large language models. In Annual Meeting of the Association for Computational Linguistics, 2024.
[138] Z. Yang, P. Qi, S. Zhang, Y. Bengio, W. W. Cohen, R. Salakhutdinov, and C. D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question answering. arXiv preprint 1XXv:1809.09600 2018.
[139] S. Yao, J. Zhao, D. Yu, N. Du, I. Shafran, K. Narasimhan, and Y. Cao. ReAct: Syner- gizing reasoning and acting in language models. In International Conference Learning Representations, 2023.
[140] F. Ye, M. Yang, J. Pang, L. Wang. D. Wong, E. Yilmaz, S. Shi, and Z. Tu. Benchmarking LLMs via uncertainty quantification. In Advances in Neural Information Processing Systems, volume 37, pages 15356-15385, 2024.
[141] F. Ye, M. Yang, J. Pang, L. Wang, D. F. Wong, E. Yilmaz. S. Shi. and Z. Tu. Benchmarking lims via uncertainty quantification. ArXiv, 122794 2024. URL https: :/arxiv.. org/pdf /2411.20... 12794. pdf.
[142] M. Zhang, M. Huang, R. Shi, L. Guo, C. Peng, P. Yan, Y. Zhou, and X. Qiu. Calibrating the confidence of large language models by eliciting fidelity. In Conference on Empirical Methods in Natural Language Processing, pages 2959-2979, 2024.
19

---

[143] Y. Zhang, J. Lu, and N. Jaitly. Probing the multi-turn planning capabilities of LLMs via 20 question games. arXiv preprint arX1v:2310.01468, 2023.
[144] T. Zhao, Wallace, S. Feng, D. Klein, and S. Singh. Calibrate before use: Improving few-shot performance of language models. In International Conference on Machine Learning, pages 12697-12706, 2021.
[145] A. X. Zheng. Rish, and A. Beygelzimer. Efficient test selection in active diagnosis via entropy approximation. arXiv preprint arXiv: 1418, 2012.
[146] Z. Zhi. C. Feng. Daneshmend, M. Orlu, Demosthenous, L. Yin. D. Li, Liu, and M. Rodrigues. Seeing and reasoning with confidence: Supercharging multimodal Ilms with an uncertainty-aware agentic framework. ArXiv, abs/2503.08308, 2025. URL https://aaxas org/påf /2503. 08308. off.
[147] H. Zhou, X. Wan, L. Proleev, D. Mincu, J. Chen, K. A. Heller, and S. Roy. Batch calibra- tion: Rethinking calibration for in-context learning and prompt engineering. In The Twelfth International Conference on Learning Representations, 2024.
[148] C. Zhu, B. Xu, Q. Wang. Y. Zhang, and Z. Mao. On the calibration of large language models and alignment. Conference on Empirical Methods in Natural Language Processing, 2023.
20

---

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:
Our contributions and scope are clearly listed in our introduction (Section I))
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See limitations Appendix Section C.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect 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 the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
21

---

Justification:
We do not have any theoretical results in this work.
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 referenced in the statement of any theorems.
The proof' can either appear 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 affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
All of our experimental settings are listed in Section 4 and Section 5 in our main manuscript, as well as Appendix G. We will provide further instructions the Github repo for easily reproducible results.
Justification:
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 are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset 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 particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
22

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We will release the code upon acceptance.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
Seeea///guidee/ooeeeueeeeee wttpauumiiiiiiooiooiooiooo.oooee for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /CodeSubdeeeieeeeeeee
/nips. wttpccccppppcccceeecccc.ccccccct /utoii// ssi onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments 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 to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All of our experimental settings are listed in Section 4 and Section 5 in our main manuscript, as well as Appendix G.
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, 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]
Our experimental results shown in Section and Section 5 are all done over 5 runs with different random seeds. Each reported metric reports the mean and standard deviation.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
23

---

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 or the standard error of the mean.
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 to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in 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 execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computation resources used in this paper is described in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well 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 failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tterr///////.....eee wttppppp.cccppppppppppppppppp hegublii/thhicccuddelleeeeee
Answer:
[Yes]
Justification:
We follow the code of ethics strictly when performing research.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws 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:
See Appendix for where we dicuss broader impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate 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 as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.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 MI..
11. Safeguards
Question:
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)?
Answer: [Yes]
Our results are all produced with open-source LLMs. Safeguards set in place by those who trained the models. Please refer to each model's technical report for more details.
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All models and references are cited properly.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
25

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets 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.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: materials.
We will provide all necessary documentation and assets in supplementary
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel as part of 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing 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:
We do not have any human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor 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 much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not use any data that requires IRB review.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending 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.
26

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
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, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: LLMs are not used during the idea formulation. LLMs are only used for editing purpose for this work. All details of LLM usages for experiments are described in our experiment section.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:// //twur/eessp///e//e wtt/oc////co//ccccce/ / for what should or should be described.
27

---

Appendix
A
Outline
Appendix $B is the Related Work section.
Appendix $C discusses the limitations this work.
Appendix $1) discusses broader impacts.
Appendix ŞE provides additional results, which include results for other models, etc.
Appendix SF provides further ablation studies.
Appendix $G provides implementation details including hyperparameters.
Appendix ŞH provides the prompts used for generating responses with LLMs.
Appendix ŞI is the pseudocode for the different algorithms including IP, C-IP and DP.
Appendix ŞJ provides additional examples of query-answer chains.
Appendix SK provides examples of sampled queries in open query settings.
B Related Work
B.1 Large Language Models and Interactive Settings
Informationn-eekinn Environments of LLMs. In information seeking environments, LLM agents seek information by constructing well-design prompts and designing proper rewards with reinforce- ment learning (RL) to encourage proper information-seeking behavior. Prompting-base
meth- ods [1, 87, 126, 126, 127, 134] typically involve LLM agents interacting and solving task together. Advanced techniques include building graphs [52], using tools such APIs and databases [96, 137], and leveraging Chain-of-Thought (CoTT) methods [22, 49, 75, 127] to ensure interaction is valid and improve performance. However, they do not explicit attempt to minimize the average number of interactions needed. On the other hand, RL-based methods such ReAct and DeLLMa [76, 139] usually involves designing good reward or utility function (can be non-entropy-bann based) that balances between exploration and exploitation, which our method can be classified in the pure exploitation regime. By and large, prompting- boant methods and RL-based methods consider a different strat- egy that is not as explicit as work here, and are not always plug-au alug-and-play to the interactive question- -anweern setting.
Interactive Medical Question Answering Setting. As our motivation (see Fig. 1), interactive medical question answering is one potentially impactful application of our work. While there are many existing benchmarks of medical question answering on LLMs such as MedQA [53], MedQuAD [10], MedMCQA [85], PubMedQA [54], they mostly focus on single-turn one-input- one-response type interaction. Instead, we focus on more recently trending setting of interactive medical question answering and diagnosis. Datasets in this setting are still rare, with the two being the WMeDiaQA [115], which is chinese interactive dataset, and the MediQ [70]. Importantly furthermore, has been shown that LLMs interactive human-LLM medical/clinical settings are subpar: shown in Bean al. [9]. they perform nearly 30% worse than LLMs acting alone. Similarly, Li et al. [70] has also shown that directly applying LLMs for interactive settings perform worse without additional guidance to the iterative process.
To summarize, the research question of why LLMs a multi-turn, interactive environments perform worse than single-turn use-cases remains active and highly relevant in today's use-cases [63, 70]. Our work seeks to provide some answer via the lens of information gain.
B.2 Uncertainty Quantification
Predictive Inference and Conformal Prediction. Our proposed formulation uses entropy and mutual information, which are fundamental measurements of uncertainty that dates back to Shannon's Information Theory [79. 107, 108] and predictive inference [103, 119, 120, 125, 133]. Amongst exist- ing methods for predictive inference, conformal prediction has gained popularity due to its flexibility for constructing prediction intervals with marginal coverage guarantee under the exchangeability
28

---

of data points. While distribution-fre -ree inference and the conformal prediction framework have been extensively studied in recent works, with many going beyond standard assumptions [see, e.g.. 5, 8, 25, 33, 34, 43-45, 56, 65-69, 72, 73, 88-91, 93, 100, 102, 105, 110, 122-124), few has for- malized the framework in the interactive and iterative setting. Arguably, the most similar setting is the online or adaptive setting [35, 36, 40, 41, 1 116, 130, 135], where distribution shift exists and the exchangeability assumption no longer holds. This line of research is different from our work in two major ways: 1) they focus time series, with assumptions such as affine transformations for the distribution shifts, In contrast, work focuses on interactive question answering setting that depends multiple factors, such as the query set Q (open and closed setting), the query answers 91:k (z and the target distribution Y; 2) they focus on providing tighter risk control in online setting, whereas our work focuses on how to use uncertainty measured from prediction sets to drive decision making. While we agree adaptive conformal prediction and sequential information gain via conformal prediction draw some resemblances, we reserve the research of their precise relationship in a future work.
online setting where data points are sequentially provided, such as
Uncertainty Quantification for LLMs. Methods for quantifying uncertainty in LLMs largely revolve around controlling the quality and ensuring correctness of LLM generations, either via minimizing entropy with constructed distribution [13, 20, 48, 74, 86, 112, 141] or leveraging conformal prediction [24, 50, 57, 62, 81, 94, 97, 104, 106, 114, 117, 129, 131, 141, 146]. Here we highlight the ones that are highly relevant to our method: Ling et al. [75] considers the problem of uncertainty quantification in the context of in-context learning. Similar to our IP baseline, it also measures uncertainty by computing the entropy of distributions estimated from the token distribution. On the other hand, Kumar et al. [61] applies conformal prediction to question answering with multiple choices. Their method also extracts probability of each choice by obtaining the logits of each answer token, but their setting is single-turn rather than multi-turn. Last but not least, Chang [15] considers multi-turn LLM collaboration debates while using mutual information as a measurement of dialogue and diversity. As aforementioned, there exist multiple methods to measure uncertainty in LLMs, and we reserve how different choices might affect the interactive question-answerti process in this paper's 's setting for future work.
Uncertainty Quantification in Interactive Environments. The two closely related works are Uncertainty of Thought (UoT) [49] and EQA work by Ren et al. [98]. UoT is in the setting of efficient reasoning for LLMs, in which the method formulates its exploration as tree. At each iteration, UoT explores multiple branches of solutions with up to a depth at three, then evaluates the accumulated information gain at the leaf node, ultimately choosing the leaf with the highest information gain. Compared to C-IP, UoT considers only binary query-answers, considers accumulated rewards, and computes entropy directly, whereas C-IP considers free-text query answers, immediate rewards at each iteration, and utilizes calibrated information. On the other hand, Ren et al. [98] is positioned the setting of robotics, where the Vision-Languee exploring different parts of the room. While this work also uses conformal inference and prediction set size to estimate confidence, the connection to entropy was not presented. It also differs from our language-domaij setting by using a custom, domain- domain-specific score function called "relevance" rather than the probability score as in the case of C-IP.
Model (VLM) agent has answer a question by
B.3 Sequential Information Gain via Information Pursuit
Previous Iterations of IP. Information Pursuit framework was first proposed by Jahangiri al. [51] as an active-testing algorithm for scene parsing. Later learning- approaches, such as generative approach [16] and variational approaches [17, 19, 26], require having access to the data distribution and learning a model to estimate the posterior distribution. Our work differs from all of the above in multiple aspects: 1) learning-basee approaches of IP largely focus on computer vision tasks such as image classification and image generation, whereas our work focuses on the language domain; 2) their setting often provides sufficient samples that allows for a good estimation of the posterior distribution P(Y | (zbb),, which enables efficient implementation with faster and scalable inference and make applicable to large-scale tasks. In contrast, LLMs may not provide good estimates of the posterior distribution because they are pretrained models; 3) IP has mostly been written as an interpretability framework rather than a framework for interactive guidance. It's unclear yet how IP will perform in settings where multiple off-the-shelf models are involved; 4) query set in previous iterations of IP is always pre-determined fixed set, whereas our work explores explores both the closed setting and an open generation setting where queries are obtained from
29

---

LLMs iteratively; and 5) query answers in previous iterations of IP are either concept based or raw features such as pixel-values. All the reasons above provide strong motivation to our current work.
Efficient Sampling. The challenge of efficiently obtaining samples for estimating mutual information often arises in IP. The generative approach [16] learns a joint distribution of P(O(X) Y), then Langevin Dynamics to compute the conditional distribution. Alternative, V-IP [17]. the current state-of-the-art implementation of IP, learns query selection function 9 parameterized by neural network ga. which also requires efficient sampling of random histories. In this work, our uniform parameterization is inspired from V-IP, whereas our sampling via LLM prompting provides new domain-specinn way to sample query-answer chains. This technique is also applied to extensions of IP for other applications [19, 37, 60].
C Limitations
Our work explores the areas of using LLMs interactively and using information gain to obtain further information. While efficient, it still requires sampling in order to estimate quantities such conditional entropy and prediction sets. One potential exploration is to find ways to estimate posteriors via a single pass, for example, via tractable approximations. Moreover, the success of our method also relies on LLMs that can follow instructions well, which today's LLMs are still not fully reliable yet and eestruction-oolowiiii stated in Section 6, only using it as a measure of uncertainty but not using it as means to control risk and evaluate the correctness of the overall query-answer chains. We reserve these interesting directions for future work.
in general is still an active area of research. Furthermore, as not fully leveraging the potential of conformal prediction
D Broader Impacts
Our work studies the setting of using LLMs interactively, where information not provided all once but sequentially depending on the previous responses of LLMs. While currently understudied, this research direction aligns closely with how human-human or human-L.LM behaves in the real world, and potentially describes the predominant way of how human would use I.LMs as the capabilities of I.LMs grows. Hence, is crucial understand the behavior through careful mathematical formulation and experimental designs. We argue that the formulation in this work can serve as the foundational ground work for further analysis when interactively using LLMs. Our empirical study with interactive medical question answering also demonstrates potential applications of our method in real-worid medical settings.
30

---

E
Additional Results
E.1
20Q
The predictive performance of 20Q on two additional models (Qwen2.5-7B [7] and Phi-3-small [2] are shown in Figure and Figure 8, respectively. Moreover, we visualize the different thresholds obtained from split conformal prediction in Figure 9, with thresholds for each model in each row. We will discuss the performance of C-IP with respect to the thresholds obtained together, as they demonstrate picture of when C-IP would be successful and unsuccessful in guiding LLMs.
1.0
0.8
0.8
0.8
0.8
0.6
0.4
0.4
0.4
0.4
0.2
0.0
0
12
16
20
0.0
12
16
20
0.0
12
16
20
0.0
12
36
20
Number Beraioons
Number Renaiions
Number heraiions
Number of Bleretions
Cowwagg
64
64
64
60
15 Number ofteraatinn
64
11 Number of iterations
68
Number Rftrtoation
Number itrations
Qopen: Afre text
(b) Dopess Atiuury
(c) Qeluseds Aire text
(d) Octored Abinary
Figure 7: Predictive Performance of 20Q with Qwen-2.5-7B model.
3.0
3.0
Rendum Seloct
2.8
0.8
0.B
2.6
0.6
0.6
0.4
0.4
0.2
0.0
12
16
20
0.0
8
12
16
0.0
12
16
20
0.0
8
12
16
20
Aumbbr Itarotions
Number of Rerations
Numbbr locotioos
Number Mltaaiaoo
8.8
0.5
0.6
0.8
Cowwrag
0.6
0.6
2.4
0.2
022
0.2
0.2
17
Number of literatinns
Number lttrations
Number of ittration
Number Rteeiions
(a) Qopen: Afca-test
(b)
Copan Asiray
(c) Celavots Arnestust
(d) Qetoced. Anitary
Figure 8: Predictive Performance of 20Q with Phi-3-small model.
Successful Cases of C-IP. We first discuss the setting of 20Q with closed query set Qctosed- It is clear that for all three models (including Llama-3.1-85 from Figure 3), C-IP outperforms IP and random query selection, where it is able to achieve a higher accuracy at every iteration. One sign of this success can be attributed to the fact that our empirical marginal coverage guarantee follows closely to the desired guarantee at each iteration.
Alternatively, one can attribute this success by looking at the thresholds obtained through split conformal prediction from Figure 9, In the closed query set setting (right two columns), we observe a progressive increase in the thresholds also the number of iterations increase. This matches with our intuition: in the first few iterations, the model is not confident about its prediction, hence the threshold remains small, and large number of classes y would be in the prediction set. As the number of iterations increase, the predictor (on average relative to the calibration set) becomes more confident, hence the threshold 7 increases.
Unsuccessful Cases of C-IP. We now turn to the unsuccessful cases of C-IP, which largely pertains the open query set setting for Qwen2.5-7B and Phi-3-small. We observe that C-IP in fact does not
31

---

0.20
0.30
0.16
0.35
0.13
0.60
0.10
0.63
0.00
0.00
0.00
0.00
16
Number Bterattons
Kumberit Ieerationn
Number Blarations
Number berations
(a) Llama- 3.1- 3.B-B, Cupas Aunuy
(b) L.umo-3.1 3.1-8-.11-8. 3.8.88 Cuper- Amso
(c) Llama 3.1-0, Rctoodd Auiur
(d) Llama-3.1 1-S- Qeleed A
1.05
0.37
0.70
0.70
0.31
0.02
0.06
0.00
9.00
Number Itarattoos
Kumberat Iterattoon
Number Blarations
Number berations
(c) Qwen2.5. 5-7B, Qupes Autary
(I)
Qwen2.5-7B, Coper Ance-toc
(g)
Qwen2.5-7B. 7.B. Cassed Antor
(h) Qwen2.5-7B. Cctest- Anceaest
1.05
1.04
0.70
0.70
0.06
0.70
Lond
0.00
0.00
0.00
Number Itarations
Kumberat Iterations
Number of Blrations
Number berations
(1 Phi-3-small, Qapes: Anmory
Phi--smalli Qopen Arneare
(k) Phi-J-small. Qctood Astra
(I) Phic3-small, Ratoot Ameeara
a= 0.01
== 0.1
a = 0.2
0= 0.3
a= 0.4
= 0.05 = 0.15
a = 0.25
0 0.35
0= 0.45
Figure 9: Thresholds obtained through split conformal prediction 20Q. The legend below shows different colors Each color corresponds to different choices of target coverage a.
outperform the DP method. To understand why, we argue it from the perspective of meaningful calibration.
Recall that in the open query set setting. C-IP is calibrated query-answer chains obtained from DP. Turning to Figure (a, b) and Figure (a, b), we observe that the empirical coverage is below the desired coverage majority of the iterations, sharp contrast to successful cases of C-IP where empirical and desired coverage is mostly coincides. To explain the misalignment between the empirical coverage and desired coverage, jumsp in the thresholds the open query set setting for Qwen2.5-7B and Phi-3-small. From our results, observe the following: Given Qwen2.5-7B and Phi-3-small models are relatively strong models and our task is relatively simple, it is often the case where the label is guessed correctly within few iteration. Once the correct prediction made, becomes part of the history qı (x (e.g. "Is the animal a dolphin? Yes.") " and any new query no longer provides any meaningful information gain. This ultimately leads an wer-confident prediction for every data point, yielding an uninformative threshold. As a result, every prediction now requires a very high probability (near 1) to be an element in the prediction set. Consequently, the prediction sets cannot quantify uncertainty in a meaningful way, leading to suboptimal results.
also infer from Figure where observe sudden
While there exist cases where C-IP does outperform other methods, argue it is more inter- pretable than IP in that one can observe its failure modes from the thresholds obtained and empirical coverage, As discussed in our Future Work (Section $6) and Limitations (Appendix &C), this direction of obtaining the proper conformal coverage guarantee over distributions of natural language deserves further study, and we reserve this for future work.
32

---

Additional Comparisons with UoT. We provide the full comparison with UoT for Llama-3. in Table Focusing on IP and C-IP, we can see that C-IP is able to outperform IP all four settings, which aligns with our previous results regarding the predictive performance. Comparing C-IP with UoT, C-IP is able to outperform UoT free-text query answers, not in closed binary query answer setting. This can be explained by the design of the respective methods: C-IP relies on immediate reward (information gain) whereas UoT looks ahead, accumulates and propagates rewards up to the certain depth before selecting the next query.
As discussed previously in Section $E. while having binary query answers allow UoT look forward and accumulate rewards (akin to beam search), free-text query answers provide much larger marginal gain over binary query answers and more realistic setting consider.
Table 2: Comparison of C-IP with UoT reasoning, averaged across runs with shaded area as standard deviation.
Method
Query Set Q
Query Answers A
Avg. Len.
Avg. Success Len.
Success Rate
UoT
open open open closed
binary
13.57 1.69
8.75 0.82
0.57 0.13
IP
binary
11.40 0.78
10.48 + 0.98
0.31
IP
free-text
10.04 0.45
9.66 0.68
0.65 = 0.18
IP
binary
10.74 + 0.59
10.98 + 0.86
0.29 + 0.11
IP
closed
free-text
13.81 + 0.16
13.73 + 0.24
0.71 = 0.08
C-IP (a 0.1)
open
binary
11.87 0.83
1
0.37 0.11
C-IP (a 0.1)
open
free-text
10.58 + 0.58
10.45 = 0.63
0.83
C-IP (a 0.1)
closed
binary
11.26 0.84
10.58
0.29
C-IP (a 0.1)
closed
free-text
8.87 0.31
8.24
0.83 0.07
33

---

E.2 MediQ
The thresholds obtained through split conformal prediction shown in Figure 10, Similar to our observations in the 20Q case, we observe that useful and successful case of C-IP can be attributed having good calibration and finding meaningful thresholds.
0.58
0.39
Level=
0.00
0.00
0
12
16
20
12
166
20
B
12
16
20
Number of Itterations
Number Itteations
Number Iterations
(a) Internal Medicine
(b) Pediatries
(c) Neurology
= 0.05
a= 0.15
a = 0.25
a= 0.35
a= 0.45
Figure 10: Thresholds obtained through split conformal prediction for MediQ. The legend below shows different colors Each color corresponds different choices larget coverage a.
34

---

F
Ablation Studies
F.1 Varying Desired Coverage
We compare predictive performance of 20Q (Figure 11) and MediQ (Figure 12). In nearly all cases, we observe only minor differences between different levels of a, which indicates C-IP is fairly robust with the appropriate choices of oz.
0.8
0.6
0.5
0.8
0.6
0.4
9.4
0.3
R 0.2
0.2
F19
0.2
0.1
600
0.2
20
Number Iterations
Number of Harrtions
Number Itlostoon
Number of Harations
(a) Llam- 3. I-BB, Qoyes. Aberry
(b) Llumn-3.1 1-88, Qupen. Ance
(c)
Llama 3.1-BB Reteett Alerryy
(d) Liama-3.1-88 Qeoood Are
0.6
9.6
Accurery
0.4
0.4
THe
2010
02
0.2
12
16
20
12
16
20
16
20
8
12
16
20
Mumber Herootoona
bumber lerouoos
(e) Qwen2.5 5-BB, Qupes. Aneary
(1)
Qwen2.5 B.B. Cepe- Apes
(g) Qwen2.5 7B, Qcioad. Anmey
(h) Qwen2.5 5-B Cdasd Afee-o
0.6
0.6
0.8
b.6
0.6
0.6
0.4
9.4
0.2
0.2
12
16
20
8
12
16
20
12
36
20
8
12
16
20
Number Horrtionss
Number Moratioon
Phi-3-small, Qupers Alioay
P-i-ll- Qupen. Ameesntt
(k) Phi-3-amall, Delsed Ariay
(1) Phi small, Rebeads Aime-co
Figure 11: Predictive Performance of 20Q with different choices of az
0.65
0.65
0.7
Accuracy
0.60
20060
That Accura
Test TestAccurac Accuracy
0.55
0.6
0.50
0.55
0.45
0.50
0.5
CPP 6-58)
CIP D e-2.))
0.40
0.45
CIP 11 e-266
2
10
6 Number of iterations
10
Number of ieeraions
Number of Iterations
(a) Internal Medicine (IM)
(b) Pediatrics (P)
(c) Neurology (N)
Figure 12: Predictive Performance of MediQ with different choices of a.
F.2
Varying Number of Estimation Samples
We evaluate whether C-IP is sensitive the number of samples nest used during estimation for the task of 20Q on Llama-3. 3-BB (Figure 13). Recall that by the number of estimation samples ness we refer to the number of samples used to estimate the upper bound (C-IP). In our ablation study for 20Q on Llama-3.1-8 set Qopens binary query answers Asisary, we find that the number of samples do have impact on the performance. While one would expect the more is better, but we find that using Neat E {1, 2, 4, 8} performs somewhat similarly. One possible explanation that aligns with empirical observations of LLMs is that stochasticity plays role in obtaining better predictive performance in LLMs, akin to how L.LMs decoding via sampling based on output token distribution often outperforms greedy decoding where tokens are selected deterministically by choosing the most likely token [47].
with closed query set Qelosed. binary query answers Asinary and open query
35

---

0.6
Test Test Accuracy
Test Test Accuracy
0.4
0.4
nest 1
nest =
nest = 2
nest =
0.2
0.2
Best
nest
nest 8
nest
8 12
16
4 Number of Iterations
20
Number Iterations
(a) Closed Query Set Qcloeed
(b) Closed Query Set Qopen
Figure 13: Performance of 20Q with different number estimation samples. Each curve corresponds to averaged accuracy over 5 runs, with shaded areas representing their standard deviation.
F33 Varying Number of Queries Sampled for Open Query Set.
Test Accuracy
m = 3 m = 5
0.2
m 7
0.0
8 Number of Iterations
Figure 14: Performance of 20Q in the open query setting with different numher of sampled queries m. Here focus on Free-text Query Answer Aree Each curve corresponds the averaged accuracy over runs, with shaded areas representing their standard deviation.
We evaluate whether C-IP on Llama-3.1-8B for 20Q with the open query set Qopen sensitive the number of queries m asked at each iteration (Figure 14). We observe comparable performance for all choices of m.
36

---

G
Implementation Details
G.1
Reproducibility
Our code is available at
G.2
Computational Resources
The experiments conducted workstation of 8 NVIDIA A5000 GPUs. Each LLM used in this work is able to load and run on a single A5000 GPU.
G.3 Code
All experiments implemented in Python 3.12. The main packages used hugging- face, PyTorch, Numpy, and TogetherAI API (for UoT baseline). The three models used 1.11-BBInstruc.. and Qwen/Qwen2.n 5-7B-Instrun Instruct.. Unless stated otherwise, we use the default hyperparame- ters from huggingface. We use the following LLM hyperparameters every time inference: do do_sample True, temperature=0.7 7, and new_enessttttteeeeeeeeeeeeee
G.4 Classes for 20Q and MediQ
For 20Q, we select 20 classes from all 50 classes that are available in the Animals with Attributes 2 [136] dataset. The 20 classes are: giraffe, zebra, elephant, killer whale, dalmatian, polar bear, giant panda, hippopotamus, rhinoceros, lion, tiger, blue whale, walrus, grizzly bear, siamese cat, cow, german shepherd, gorilla, dolphin, and moose.
For MediQ, each medical question is a multiple-choice question with four options: A, B, C, and D. Note that the possible choices and order of the options are different for each problem.
G.S Obtaining Probabilities from LLM
In this work, focus LLMs where logit scores of output tokens are accessible. While there many methods for obtaining posterior distribution P(Y Qlaa (xobs) for given we estimate the posterior by first obtaining the LLMs' output token logits based the class labels' tokens, then applying softmax function. When certain class names consist of multiple tokens, we select the first token's 's probability consist of the same first token. In the case that happens, one may consider adding a prefix such as enumerations ("'.", "2." or leveraging special symbols trained with large language models.
represent the class's probability. For all of our models, none of the classes
G.6 Entropy Estimation
Estimation of terms such entropy in (IP) upper bounds in (C-IP) requires samples of (X, Y) pairs. We use 4 randomly drawn samples for all 20Q experiments whenever entropy term needs to be estimated and use 12 randomly drawn samples from the estimation set Dest for all MediQ experiments.
To be specific, the empirical estimation A( (1=(()) with probability estimator P(Y (1a(x)) = f((1a(x)) is estimated by
(( (x)( =
Σ
f(qux())) log, (x)
(15)
(
G.7 Calibration
Achieving marginal coverage in (12) requires calibration samples. For 20Q, we sample 100 randomly drawn labels. For MediQ, we sample 200 randomly drawn datapoints with replacement in the calibration set Deat-
37

---

G.8 Preprocessing Query Answers for 20Q
To avoid generating query-answers from LLMs at each iteration for every query, in the case of closed query set Retosed and free-text query-answee we generate query-answe offline by sampling 10 possible query-answers for every class and query. Then, in our experiments, for any given query and class, we select query answer by uniformly sampling one out of the ten generated answers. For binary answers, we only consider query-answers with "Yes" and "No", without any variability.
G.9 Evaluation of Predictive Accuracy
We discuss the two evaluation methods for 20Q and MediQ separately as they are different. 20Q is often played in manner that the Querier LLM keeps guessing until either it guesses correctly or until the maximum number of iterations is reached". Here, we following the same protocol. If the Querier LLM guesses the correct prediction ff, at iteration k. then yh Dr for i = k + I.... L. For MediQ, since the neither the Expert LLM or Patient LLM knows what the correct prediction is, require C-IP to reach the stopping criteria (See Appendix $G.10). For any given datapoint 2 suppose the stopping criterion is reached at iteration k < L and 03 is the prediction. Then assume the prediction does not change after iteration à and set út = U3 for = k + 1....,I. T.
G.10 Stopping Criteria
As mentioned in Section 3.2 Remark 1, arriving at [((();; Y (nse( = 0 in practice is highly unlikely. Here, we explain how one goes about arrive at an approximation ((((X); Y (ia(()))))) Rd
0.
One approach is utilize the model confidence P(Y 11:2(2 In previous variations of IP. including the generative version [16] and the variational approaches [17, 291, the algorithm stops querying once the posterior (2 4is (xbb))
for any y E y. This is suited for previous cases because the predictor model is learned from training data, which provides better estimates for the posterior. Unfortunately, in the case where model confidence miscalibrated, this process becomes unstable and unreliable.
Empirically, observe that while estimated conditional entropy (either with direct computation or with approximation via prediction sets) for every q. i.e. HY g(X), (1)e()))))) )). does not converge to 0 as the sequence length increases. However, it tends to converge to some constant number when the algorithm is confident enough some number. Hence we propose calculate the standard deviation between obtained estimations. Precisely, given a query set Q (closed or open), the query-answe answer chain 9i:k (znhh), ), and a stopping threshold E, the stopping criterion can be described as:
Step Let
64 -= (Y (X()), quaa ( (2ob)) for q E Q.
(16)
Step 2. Compute the estimated standard deviation
1
Gi
(c: 2)2.
(17)
Step Stop & < e. clse continue the algorithm.
G.11 Evaluation of Empirical Coverage
Suppose we have test set Drest = {zi His with size niet for evaluation. The empirical coverage iteration & is evaluated by
Thast
Px.Y.Qua.Dea (Y E C.. (Q)x()))
Σ 1/ E C+2 (x))))
(18)
Thest
where (x,, 9i) E Diest is the i-th test sample, Cs, is the prediction set for query-answed chains of length k. 91:A (zx) is the obtained query answer chain (e.g. from C-IP), and 1(-) is binary indicator function, which equals when the condition in the parameter true and otherwise.
'This is also consistent with UoT [49].
38

---

G.12 Hyperparameters for UoT Baseline
Unless specified below, we follow the default settings as suggested in UoT's main manuseript [49] and their Github repository attps://githie com/ (aalyuunnuuu//oo//tttaaa
For results in Table 1, ensure the faimess of the experiments, their method in_potentiall ial act ions in their code) to 5. Their experimental results are produced with API from Aog Please their website https: / // /www. together ai/ for more details. The total charges to produce our results for the three models cost no more than $50.
set the number of branches in
G.13 Details on Probability Calibration Methods
For Platt Scaling, for each length & E {1...., L), we sample randomo histories of length l from the calibration data Deal and train a logistic regression for each class. The logistic classifier is implemented using Scikit-learn python package [14] using default hyparameters (e 2-regularization and a inverse of regularization strength of 1).
For temperature scaling (TS), we did not do any hyperparameter search but reported the best three curves for T {0.5, 0.75, 1.25).
39

---

H Prompts
Here we provide the prompts used in our experiments.
H.1
20Q
System Instruction for Querier LLM
tollowing: (clare_names), aninal precise information posssble. may your reasoning first before aaking a prediction. End your response by zoking a guess and saying 'The aninal ie: I' (eig. The animal 1s: dog) at the end of your reasoning, shere is your guess. Do not provide should all in paragraph. you provided information, randon gueza.
expert animals. Your
gathered.
additional information. Your
Input Prompt for Querier L.LM Obtaining the Posterior
You have not gathered information Please nake randoa guese. history is capty
information you have gathered. history is expty (q1) (ei(x))
2. (q2) (g2(2))
(g3(x))
(q0) (o((x))
Given the information
Firat nake your guwsa gathered, intornediate SINGLE prodiction you aninal (w.g. ls: dog), your gussa, provide your reasoning. Do not provide any additional information. Your response should all fit in single paragraph. Make sure your prediction is one of the classes: (class_paxes)..
Input Prompt for Querier LLM Suggesting Queries in Open Query Set Setting
You not gatherad any information yet., make randors guess.. histary anpty
Baze la the inforsation have gathered. If history is
(g3( (e2(x)>
3. (43) (g3(a))
(q9) (p4(x))
Now sugpeat www.uunriex.prratte. _ttpp questionn, (nllaturn the queatiimn in this Vorrat:/nn("quuutiiiion [*QURSTTOR_11 < "QIESTIOO__"" _2", 'QURSTIOK_3*))>
System Instruction for Expert LLM for Non-binary Query Answers
question provided, anseer truthfully about question. directly tell the other player what you are thinking. Be as precise and direct possible, and anaver complete sentence. For atample, the quastion is "Does the aninal have taily", your ansper.
are espert on (label). Beaed
"The aninal
exying yeu no. eay
System Instruction for Expert LLM for Binary Query Answers
You are an expert on (label). Based the question provided, ansver trothfully about the question. Do not question thinking. Be and tail?", you ansver "3o.".
directly tell other
possible,
exazplo, Do not say the zame of the anixal in your ancvor. If you don't knov the ansver, zake guese, Do not ancvor anything other than "Yee." or "No.*.
singlo word.
40

---

H.2
MediQ
System Instruction for Expert LLM Obtaining the Posterior
You are a oedical doctor special issd in (spacialty), trained to provide accurate, wvidenca-haned reqqomee to
medical inquirias. les. Your goal is anaver queations with clarity, precision, and profesaionalaan shils established aedical guidelines. Ansvez compazz peeppaainmaalll Make prediction provide your reasoning as explanation. Respond following fornet:
your reaponses
accurately,
( annuer": "6/0/C/0", "erplaration": *YOUR EXPLANATION HEAE*))
Input Prompt for Expert LLM Obtaining the Posterior
Answer the mitiple choice based the context.
Contaxt:
(contaxe)
Qowntiio::
Equaatioon
Options:
(optioon_a)
Coption,bi
[option_c]
(optioo__))
Please select the nost appropriate ansver (A/8/C/D).
System Prompt for Converting Facts into Queries
fact steelf. The abould be specitic Convert the medical fact question, which the any questions not paticat's to pariect's condition. Flease medical history or condition. Suggest one quection only, Return only your question and nothing else.
Medical fact:
productive
for months.
Osestion: come prelinizary eypptons?
Medical fact: He complains of mausea and 1 opieode of voniting during the day. Qsestion: Did patient complain about naueea?
System Prompt for Converting Facts into Queries
Medical fact: (fact)
41

---

I Pseudocode for Implementation
Algorithm 1 Constructing Prediction set functions for each length C₁2 ...Cr.-
Input: Calibration set Deal with Neat samples, Desired Coverage - maximum iteration L, LLM--ased predictor f.
1: for each length k 1 1... do
2:
3: Step 1: Obtain conformal scores
4:
for (x) E 'Dal do
5:
Option 1.1: Uniform Sampling
6:
Sample random history Qi:k ~ Q1ik based on Equation 13,
7:
8:
Option 1.2: DP Sampling
9:
Sample histories from direct prompting 91:k DP(X, Y) based Equation 14. Obtain scores based on LLM's output token logits for each class
10:
8: (ri, Ui) ((1: (1:))
end for
12:
13:
Step 2: Quantile Estimation
14:
Estimate quantiles using the obtained scores:
Quantile
{st))tt
Pat [Mnat + 1)(1 a)l
Real
16:
Step 3: Prediction Set Construction
Construct and define the prediction set function using the calculated quantile
C+p (x)) ty y f(qu)( +}
18: end for
return Prediction functions for each length C; ... C+..
Algorithm 2 Information Pursuit with a closed query set Qetosed-
Input:
Observation or test sample dbs maximum iteration L, LLM-based predictor f. query set
2 Ocloseds estimation set Des
Output: Selected queries Qi:k and predictions ÿ1.k
1: Set iteration 1: + 0
2: Initialize empty history S.
3: while stopping criteria is met or l: < L
4: Predict 1 argmax, f(8x),
5: Estimate the entropy y given each query using Dea select the most informative query
gk+1 argmin (Y Sk)
qe
6: Compute query answer q obx) and update current history
S St U {gx++ (2x)
7: k - k+1
8: end while
42

---

Algorithm 3 Information Pursuit with a open query set Qxpen-
Input: Observation or test sample = maximum iteration L, LLM-based predictor f, an LLM LLM(.), queries to sample at each iteration, estimation set Dest Output: Selected queries Qi:k and predictions V1:k
1: Set iteration & f- 0
2: Initialize an empty history S. =
3: while stopping criteria is met or k < L do
4: Predict 1 = argmax,Ey/ f Sx))
5: Prompt language model for queries based current history
1 + LLM()), 91:k (x m)
6: Estimate the entropy of Y given each query using Des select the most informative query
gk+1 argmin HY Sx)
sE
7: Compute query answer 9&+1 (x: and update current history
Sk-1 Sy {9k+1 (2
8:
k- k-
9:
end while
Algorithm 4 Conformal Information Pursuit with a closed query set Qelosed-
Input: Observation or test sample ot maximum iteration L, LLM- predictor f, query set Qcloset, Prediction set functions for each length C,, ... C+2,, estimation set Des.. Output: Selected queries (isk and predictions ÿ1:k
1: Set iteration k t- 0
2: Initialize an empty history Sg = 0
3: while stopping criteria is met or k < L do
4: Predict ūk+1 = argmax, f(Sk)
5: Estimate the entropy of Y given each query using Des select the most informative query
9k+1 = min (A, + (1 (1- - ax) log Ex [[Cr..n (q(X), St)1]}
QEQ
6: Compute query answer Uk+1 (b) and update current history
SK41 Sr U 1 (2)2
7: k - k+1 1
8: end while
43

---

Algorithm 5 Information Pursuit with a open query set Qxpen-
Input: Observation or test sample 2ht, maximum iteration L, LLM-based predictor f. an LLM LLM(-), m queries to sample each iteration, Prediction set functions for each length Cr, ... Ci. estimation set Dest
Output: Selected queries Qi:k and predictions Vi:k
1: Set iteration k: + 0
2: Initialize empty history So [}
3: while stopping criteria is met or k < L do
4: Predict f/++1 argmax,e>* [ Ss))
5: Prompt language model for m queries based on current history
Q + (LM()), 91:k (2 (, m)
6: Estimate the entropy Y given each query using Dest select the most informative query
9k+1
min rEQ
a>a (1 aN)
) log Ex i (g(X), S.)l]
7: Compute query answer 9k+1 (x) and update current history
S Sy U (g
8: k
9: end while
Algorithm Direct Prompting
Input: Observation test sample hn maximum iteration L, Querier LLM QuerierLLLM()), Expert LLM ExpertLLM()). LLM-based predictor f
Output: Selected queries qı:k and predictions ýı:k
1: Initialize an empty history So = 0
2: for k 0. T. do
3: Predict with f
0k argmax fly S4) yey
4: Prompt Querier LLM for one single query given history
4++1 (M)r)erLLM(Ss)
5: Obtain query answer and update history
gk+ (hm) ExpertLLM (MELL,
S = S₃ U (x
6: end for
44

---

J Additional Examples of Query-Answer Chains
In this section, we provide additional examples of query-answer chains obtained using C-IP. All the examples we provide in the following are correct predictions. Here we only show the iteration that the method stopped.
J.1
20Q
Here we provide one example for each setting, which is either open or closed query set and either binary or free-text query answers.
Example of 20Q with Closed Query Set and Binary Query Answers
Systen Instruction
You are expert on animals. Your goal predict aninal given infommation you gatbered. aniral most be one of the tolloking: 'giraffe', 'zebra", 'elephant' 'killer shale', "dalzatiann 'polar bear', "giant panda", "hippopttans', "shinoceron', "lion", "tiger', "blse shale", 'valrus", 'grizzly bear" 'slamese 'dolphin', 'moose', Be your responce making guees
cas', "cou", 'german chepherd', provide your reasoning
and direct possible. eaying
may
naking prediction. anisal is: X' (e.g. The asinal is: dog) at the end of your reasoting, shere 2 is your guesa. Do nos provide any additional informatios Your reeponse chould all fit in single paragraph. If you are not provided any information,
randon
Input Proupt
Bere 18 the information have gathered. anisal live Arctic? No. have stripes7
3. Is the aninal donestic? Yes.
Given the
First your guesa gathered, provide your reasoning. Do not provide any additional information. paragraph, Hake sure your prediction i5 one of the classes: 'giratte', 'zebrs', 'elepbant', 'killer whale', "dalnatian' "polar beaz". 'giant panda', 'Ltppopotazus" 'shinoceros', 'lie'', 'coe". 'gezzan shepherd', 'gorills', 'delphin"
intornediate SINGLE 'The ansnal
dog), you think animal your gueso, (a.g. Your response chould all fit in single
shale',
'valrus" 'grizzly
st Response
anisal
information animal
elixinates
valrua, and grizzly bear, opticas such as cow.
desentic, elisinates most anisela, leaving dommaticated
Example of 20Q with Closed Query Set and Free-text Query Answers
$ Systen Instruction
informttion you getherad. following: 'giraffe", "sabra", 'slaphant', 'Killer shale', "dulaatian", 'polar 'giant panda'. 'hippopotamss' "shinocerna'. "lion", "tiger', "blle whale', 'uslrua' 'grizely bear 'astanens owt'. "coa", 'german sbephard', 'gorilla', 'dolphin', "eapphinn.'monnn 'mnose". Be precise and direct sa possible. You provide your zeasoning first before naking predietios.
wxpert aninala. goal predict
anital muat
your response aaking gueaa X (e.g. aninal fa: dog) the of your ranson ing, where your guaes. Do not provide any additional information. Your rwaponan should all fit in single paragraphh If you arw not provided any information, zake randon
asying
Input Proupt
Bere 18 the inforzation you have gathered.
This aninal primarily inbabitx grasalands ands and
rather than dense foresta.
Given the information you have gathered, nake an interzediate SINGLE predtction shat you think the anteal 16. First nake your gosea in the foreat "The ananal is: (a.g. The animal ia: dag), where ia your gusss, then provide your reasoning. Do not provide additional information. Your responas should all fit in aingle 'giratte', 'zebra', 'elephant', dullstiin'. 'polar hear', 'giant panda', 'hignopatarma', 'rhinoceron' "lion', 'siger', "blus shale', "walrus". ;, 'grizzly bear", siamese
paragraph.
your prediction
shale',
" cat', 'coe", 'gorzan shopherd', 'gorills', 'dolphin', 'moose".
Rasponae
The aniral 16: zebra. This is because the informatio prorided suggects a grazeland or cavanna babitat, which + aligna with the typical habitata of zebras, as they are comsonly found grasslands and navannas.
45

---

Example of 20Q with Open Query Set and Free-text Query Answers
$ Bysten Instruction
gathered, of the following: 'gizaffe", "sabre", 'wlaphant's 'Killer shale', "dulaatian', 'polas "giant panda', "hippopotana'' "shinoceres", "Lion', "tiger", "bise shale", 'valrus" ,, 'grizzly bear" 'stanese car', "cos", "german cheptord', "gorilla', "doiphin",' "moose", Be precise and direct as possable. You may your respause saking gueaa
expert animals. Your
aninal
information
must
provide your zeasoning first before naking predictios. dog) the of your reasoting, shere your guesa. Do provide
auying
X' (e.g- 4 any additional informatioe. Your rwapenan should all fit in aingle paragraphh. If you arw not provided any information, zake randon
Input Prompt
Bere ia the inforzation you have guthered.
This aninal pricarily lives on land.
Earopa
later introduced icas and Africa. neat.
aninal carnivere by natural inscinct prinarily
Givan the inforsation have gathered, nake intersediate SINGLE prediction of what think the uniral is. fornat 'The
Firat your gossa
(o.g. anixal is: shere La your gueas, provide your reasoning. not provide any additional information. Your reaponss should
aingla paragraph. Make sure your prediction in one of the classea: 'giratl'', 'zabee', 'eleghant', 'killer shale', "daleatian', "polar beaz", "giant panda', 'hippopotazus", 'shinoceros', 'Lion', 'riger', "blue shale', 'ualrux', 'grissll
tone". "gerran shaphard', 'garilla', 'dalphin'
s9 larponne
The aniral ix: daleatian. The animal prinarily lives on land, which natchea with the fact. that it is nacive introduced Asaricas Africa, antral in carnivore by natural instinct and primartly feeds on diet rich in reat, which al aligge with the charactariat latic of dalmation.
Europe lain,
babitat.
Example of 20Q with Open Query Set and Binary Query Answers
Systen Instruction
You are an oxport on animale. Your goal 15 to predict the animal given the information you have gatbered. The + aniral must be ose of the tollowing: 'girafte', 'zebra", i 'elephant', 'killer whale', 'dalzatian" 'polar bear', "giant panda', "sippopotanux'. 'thinonernn', "lion", 'tiger', "bllw whale', 'salrua', 'grizely bear' 'alaanss precise
as possible. provide your reasoning first before naking prediction. and your reeponse by making a guees and eaying "The anieal ix: X (a.g. The asinal is: dog) at the and of your rassoning, where I in your gueaa. Do not provide single paragraph. you
cas',
'german chepberd', 'gorilla', 'dolphin' 'moose'.
may
additional information. Your gasss.
ebould
provided
** Input Proupt
Bara the inforration have gathered.
the
primarily est plante?
Does the antmal primarily live on land? Yea.
3. Doex the anival have four lega? Yea.
animal
(over xg)? Yes.
6. Is the aninal knoom to be aggressive? Yes.
7. Does the animal have long nock? Ko.
Does the animal have clave? Yes. the aninal carnivoze? Yes.
10. Is the animal nammll? Yeo.
Given the informatios
Firet nake your guees gathered, provide your reasoning. Do not provide any additional information. Your response should all fit in single paragraph. Hake sure your prediction is one of the classes: 'giratte'. 'zebra', 'elephant', 'killer whale', 'ntppopotanue", 'rhinoceroe', '1son', 'tiger'. 'blue shale', 'valrus', , 'grizzly beaz' "siaxese cat', 'coe', 'gerzan sbopherd", 'gorills', 'delphis' 'soose".
internediate SINGLE prodiction ie: dog), shore your guese,
you
aniral
"The anenal
(e.g.
'dalnation, 'polar bear" 'gtant
tt Horponce
fact that aninal carmivore anisal lion. based prediction aggressive (6). characteristics aze commonly acsociated with large body size (4),
land (2),
< big cate, and the 1ion is one of the nost aggressive and large land carnivorous zareals.
46

---

J.2 MediQ
Here we provide one example for each specialty. Recall that, query answers (denoted as Patient's Fact in the prompt), is obtained in the order that C-IP obtains. When formatting as input, we ignore the query that provides repetitive information the query answer.
Some text that involves characters o; are unable to render in our example, so we replace with with spelled out words, i.e. "alpha".
Example of Diagnosis in Internal Medicine
Inpur
medinal
ansvering
redical
gueations.
your
basic and clinical science, medical imozledge, and zechanime underlying health, dicease, pattent care, and modea of therapy, ansuer the following sultiple choice quastion. Select one corract ansver from to D. Bass ansuer on the current. and standard practioss referenced in nedical guidelinea. Repand in the folloving
EC ansuer": "A/8/C/D", "asplacation": *FOUR EXPLANATION HERE"))
mitiple
Instial Info: b4-rear-old vonan preeents to the energency department due recens onset of high fever, headsche and nack stieff.x..
4
Convercation Log betseen dector and patient:
Hara ia the inforration have gathered.
Pstient'e e Pact: patient's
bload
112/71
curzently treusouppeseans
kidney transplant ago.
o medication reginen includex immnoaugpreeentss
Patient'c in Fact: The patient is 54 years old.
Patient's 's Pact:
patient
rapidly progressive glomeroloneghrtte. She also undervent currestly iammouupreesatee
traneplant nonths ago
Patient's e Fact: The patient's 's current body texperature is 102. (39r0),
Patient'a is Pact: The patiens'a neck pain 18 severe with neck flaxion and rectprocal knee flexton. Pacta 9 and are the
this
Patient's
pationt
question
typical triad sysptone associated
aeiingitie..
Patient's ic Fact: Her respirations are 22/nin.
Question:
Vhich of the following characterietice is true of the zest likely causs of this paticat's diserder?
Options:
Anacrobic spore forning
Catalase negative
D
Tunbling notility in broth
select bost uppropriate ansver (A/B/C/D).
Medical conditions are complex, you chould seek to understand their cituations acroes many features, Firet, necessary
consider shich medical apecialty would zake right modical judgaent. Think step by step, reason about the patient information, inquiry, and the optione.
patient's
anawer": *D", "usplanation':
patient's presentation high fever, aevere henlache, nack stiffmess, neck pain with zeck flexion and reciprocal ine flexies (positive Brudeiaski's sign) suggests nomingitis. shich is an inflamation of the protective zembranes covering the brain and spinal cord, knom as the zeninges. kidsay trampplant, ahe patient's la inability ansver questions about typical incressed assoctated with moningitic (headache, fever, and stiff neck) furthor supports this diagnosis.
Given pacient's history inmuoouupresson
oppertmistic infections.
of sysptons
Inzunosuggresee
likely nosocytogenes. Listeria monocytogenes graz pocitive,
susceptible
pathogens,
coningitie in this cutalase-ungative bacteriun that uxbibita tuilt ing zotility in broth. This characteristic is unique to Listeria species, naking option D the correct ansver.
Listeria nosoyytoezee common cause zeningitis immmocopproised individuals, particularly these history of organ transpaactation. It is also a cause of amiiggiti in proguant sosen, the elderiy, and individuala with cartain underlying oedical conditions. The other options not accurataly describe the Listeria mmncytogezes. inserobic spore-forsing characteristic Staptylococcus aureus,
typical
(option A)
commaly
associated with Clostridiun species. Coagulase positive (option and shile sose asserable bacteria may exhibit catalas-saggttve (option B), this is sot specific characteristic of the zest likely cause of this pailent's disorder.")
47

---

** Input
You are redical doctar ansvering real-sorld redical entrance guextions. Beaed underatanding of
knowledge, zechaniasa underlying modes therapy, ansver the follosing multiple chotce question. Select one correct anever from to D. Base your ansver on the current and standard practices referenced in medical gridelinss, Repond in the fallocing
busic clinical scisnce,
foreat:
{C <tannuer": "A/B/C/D", "ssplanation":
EXPLANATION HERE)))
Inswer the mittple choice baxed the
Instial Info: in 8-year-old girl Actan descent 15 brought to the physician becauce of fatigue.
Converaation Log betseen doctor and patient::
you gathered.
Patient'a a Pact: patient's eye coler and aрpearance la that pala conjmetivae.
Pstient'c Fact: The pations's nean corpuscular volume is 74 und.
Patient's Pact:
gyn complaint
with of her
masily.
Patient'e Fact: The patient tires eastly during paysical activities becsuse the 15 not able to keep up with hor + clarenates in clase and brought to the physician becauze of fatigue. Thin ie also due to her pale conjunctivee
small, pale rad blood calla.
Patient'e Fact: The patient's current liengglobin lerel is 11.0 g/dl.
Patient's i Fact: the has norzal. hemoglebin electropboresis. Benoglobin clectzopboresie is normal.
Question: Vhich of the following best describes the pathogeaesis of the disease process in this patiens?"
Options:
Decreazed production of beta-globin
acid eubstirution
globia protein
Cie deletion of alpha-globis globin gezes
D Acquired inhidition of here syathosis
appropriate
Medical conditions are complex, you chould seek to understand their cituations acroes many features, Firet, which medical specialty patient's zake right modical judgaent. step by step, reason about the patient information, inquiry, and the options.
teatures doctor
Responce
ananver": '0", "explamation": "This patient's presentation of fatigue, pale cosjunctivae, and seall, pale red blood colls (microcytosis) is sugeetive of azomia. The parient' nean corpuscular volume (807) of 73 us3 The
zicrocytic or thalaseezia najor. iron overload. Bosever, the patient' 5 hezoglebin level is los, which is not consistent with irem overload. The most li2ely disgosis is beta thalaceeii trast, shich is mild form thalaseenta. Beta thalarrenia trait the beta-globia genes, deletion ancnss, which consistent fasigue and pals conj unetiven are due the asesie, and the small, pals red blood cella ase consistent with sicrocytic menna.. The norall henoglobin electrophozenis and elevated ferritin level support this diaguosis. Therefore,
electrophoresie rules out henoglobinosatilee augeesaa ferritin
cell
ag/al elerated,
caused
reduced pariect's is presestation.
protein.
pasient's
Cis deletion of alpba correct
uciually dia the beta-glebia
beta- thelazeiia truit, not alpha-tislasee genes but the options provided do not have beta-globin, so the closest option 18 C.*) Vend(lotlisting)
48

---

Example of Diagnosis in Neurology
$t Input
world medical busic clinical aciance, uedical knowlaige, zechaniata undarlying health, diseise, patient caze, modes of therapy, ansver the folloving sultiple choice question. Select eue corzect ansver from to D. Base your ansver on the current and standard practices referenced in nedical guidelince. Bepond in the follocing forsat:
medical doctor
Based your understanding
6C' (("amuerr:: "A/B/C/D", "asplacation" *FOUR EXPLANATION HERE"))
multiple choice based the
Initiol Info: 26-year-old nas presents to the ER after atreet Light.
Converaation
doctor and
inforsation you gathered.
Patiaent's is Pact; He hax been rapidly decorpananting since several hours after the initial hit. Since then, he has c. been rapidly decoppnntting.
S pain. Rouwver, patient
head nental status. The staric factual statamenta oa that ansver the queation partially are: He is grabbing bis head in pain.- His zental atacua is altered. Patient's is Fact: The pationt's right pupil is dilated. The information comes from fact 27.
Patient's Fact:
the patient experiencing pain
the altered
Queation: this patient's 's ayaptoxa are allowed to progresa intervantion, which following
+ expected to accur?
Optiona:
Right sided benipareaia
Dosn in gaze of the right pupt)
C. Right. aided hommyyoux bwsianogain in.
D Right with un inability abducc
Please select nost uppropriata ansver (A/B/C/D).
Medical conditions compler,
should peak understand their situntions features, First, consider nedical apecialty patient's
necessery would need to rake the right medical jodgrent. Think step by step, reason about the patsent information, the inquiry. and the options.
+
Response
the patient' ayrptoms of rapidly decompansating altared mental statox G and bead pain, along with a dilated pupil on the right zide, the nost likely disguesia is mas lasion in the techesic stroks. The dilated conprasaion,
('anmur': *A", "erplanation"
brain, such hezorrhage
third crantal
patienta with space-ocmpying
It this patient's is symptore are alloved to progress without intervention, it is likely that the razs lasion eill continue to increase in aise and cause further brain damage. This could lead to body on oppoeste
of complications
including right-eided henipareste, which
Ri Right-aided hariparssi is common consequance of left-aided brain lasion, as the ootor tracta in the brain to opporite side the body. The space-accupying
gaze directly related right pupil with a third crantal nerve palsy, but the paticat's is sysptons are not consictent with this diaguosis. Right-eaded hononymous hentanopeia would be nore consistent with leston the vieual patheay, and an would consistent with sixth crantal palay, suggected by patient's sysptone."
expected
imability to abdect the
49

---

K
Examples of Sampled Queries
Here we provide some brief examples of queries sampled in the 20Q open query set setting, Here the number of queries to sample m = 3.
Example of Sampled Queries at Each Iteration
"Dowa the unizal have four lega?" "Does anizal live land?",
}.
spota atripwx?", prisarlly land?", "Does the anisal have long nock?*
"Dows
}.
"Does
prinarily eat plants?',
"Boss the snizal live in group?", "Doua the unisal have distinctive coat palteru?"
"Dosa the unisal have long nack?",
"Boea the aniral primartly banboo?",
"Does mnizal give birth single tixe?*
"Dowa the unizal have large body sime?",
pattern?"
].
anival have rwtractable claza?", "Boee the antral have distinetive pattern of black and white stripes rather than agots""
3.
"Doee the antral primarily feed planta?", "Dosa the anival have herbivaroux diet?", "Is animal native Assa?"
"Doee the animal primartly feed bamboo?", "Ia the animal carnivere?", largo body compared
"Doce animal primartly all foure?", Long gestation period?*, animal nember the Uraidan farily?*
},
aniral long mnnu??" "Is the mital sative to Africa?",
"Done the antral have large body eize compared to its neck?"
},
"Doee the antral primarily live land?",
"Is the animal carnivere"',
"Doee animal
compared anirale l1st7"
50


Reviews:
[{"review_id": "OElj1EEkOh", "reviewer": "Reviewer_HBRz", "summary": "This paper looks at interactive multi-turn dialogues where an LLM is able to ask questions and obtain information before giving a final prediction (e.g., as in the 20 Questions game). The strategy the authors pursue is motivated by \"information pursuit\" (or choosing to ask queries that maximize information gain at each step), but via the use of conformal prediction sets instead of measures of conditional entropy that rely on estimated probabilities from the LLM (which are unreliable). Specifically, the approach is to minimize prediction set size at each iteration --- which the authors connect to an upper bound on the standard entropy. Empirically, the authors show good performance on 20Q + MediQ at getting good predictive accuracy within a small number of iterations.", "questions": "- I'm a bit confused by L169, where the claim is made the the uncertainty of Y given data X is upper bounded by the expected size of the prediction set. I think the more precise claim is + some additional constants that depend on $\\alpha$ and $|\\mathcal{Y}|$ (which, looks like it can be quite large, unless $\\alpha$ is near $0$ --- for instance, for $\\alpha$ near 1 this bound is vacuous, as it bounds the conditional entropy by the entropy of a uniform distribution over $\\mathcal{Y}$). It's also weird to me to related the conditional entropy to the expected set size, marginal over $X$ --- this is then a bound that is no longer dependent on the input example?\n\n- I'm also a bit unclear on how $E_X[ \\mathcal{C}(q(X)) \\vert \\vert \\mathcal{H}]$ is computed. Are the same set of query trajectories applied to the calibration set for all $X$? In the open query set, what happens when $q$ does not apply to some $X_i \\in \\mathcal{D}_\\mathrm{cal}$?\n\n- The calibration set is used quite extensively for the CP algorithm. Have you tried also using it for the baselines, e.g., to calibrate the confidence of the LLMs by histogram binning or platt scaling?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written, and the motivation (reducing uncertainty set size) is well-motivated. The experiments also indicate that the proposed method is effective. However, I also have a number of questions (see below), and at a high level, while I buy that a measure that is less susceptible to estimation error like conditional entropy is, I am not fully convinced of the need for _conformal_ prediction and calibration. Specifically, the primary advantage of conformal prediction---the formal coverage guarantee---is not a central feature of the algorithm's goal, which is to minimize uncertainty for query selection, not to produce prediction sets with valid coverage (and even so, the benefits of the marginal conformal guarantees are somewhat dubious here --- which is made even more marginal here due to tractability issues). For me, this raises a bit of a question of whether the complexity of the conformal framework is justified over simpler, alternative uses of the calibration data (which does not seem to be used for the baselines).\n\nMore concretely, the proposed C-IP method uses the average size of a conformal prediction set as a proxy for uncertainty. The size of the conformal sets also depend on the LLM probabilities, but in a more discretized way, i.e., the count of how many outputs have confidence > $\\tau$. $\\alpha$ doesn't seem to be used in any important way here, so searching over $\\alpha$ hyper-parameters I believe could also be viewed as just measuring the average number of labels per X that are above some confidence threshold. I would be curious to compare this to other, simple baselines that use metrics like this --- like the average top-label confidence, the average difference between the top label's confidence and the second-to-top label's confidence, or if the confidence score is noisy, the average accuracy of the top-label (so, ranking queries by their conditional accuracy).", "was_revised": true, "final_justification": "I think that some of the theory is a bit \"fluff\" --- I'm not quite convinced that the exercise to connect information pursuit to conformal prediction is necessary, I still think it seems likely that a baseline around discretizing uncertainty estimates and calibrating them on a calibration set would yield similar gains, though I'm not exactly sure what it would be. That said, this is definitely and interesting method, and does achieve that goal (better sequential information pursuit) with encouraging empirical results.", "rebuttal": "Thank you for your review and questions. We are glad to hear that you find our work \"well-written and well-motivated\". Please kindly see below for our response. \n\n**The need for conformal prediction and calibration**\n\nThank you for this question. We would like to clarify that the central research problem of this work is not conformal prediction or calibration, but how to interactively guide LLMs using Information Pursuit (IP). Our use of conformal prediction serves only as a mean to improving the quality of IP for LLMs.\n\nMore specifically, by the definition of IP, this requires estimating the mutual information between the random variables $q(X)$ and $Y$. Our motivation for using conformal prediction is that:\n1) computing mutual information (or conditional entropy) directly is challenging for complex distributions, especially here $q(X)$ is a distribution of text;\n2) LLM probabilities are inaccurate (miscalibrated), which leads to poor estimates of conditional entropy and suboptimal predictive performance (as in our introduction);\n3) Conformal Prediction provides theoretically justified and rigorous Fano-type upper bound to conditional entropy (for any $\\alpha$), per our referenced proposition. \n4) As we will discuss below, empirically we observe that C-IP performs better than IP with calibration methods. \nHence, our work here derived the new formulation of C-IP, which leverages aspects of conformal prediction to select informative queries strategically.\n\n**Additional Baselines with Calibration Methods (Weakness and Question 3)**\n\nThank you for the additional baseline suggestion. We agree that there is the possibility that the alternative method of \"first calibrating LLM probabilities then estimate uncertainty using entropy\" might find success.\nTo test this hypothesis, we performed additional experiments by first applying temperature scaling (TS) and Platt scaling (PS) to calibrate LLM probabilities, then inference with standard IP (not the conformal version). Note that TS (for a fixed temperature) does not depend on calibration data, whereas PS does depend on calibration data. We evaluate 20Q in two of the open query set settings as before, and average each accuracy curve over 5 random seeds.\n\n*Open query set, Binary query answers*\n| Iteration             |        0    |        1 | 2    | 3                | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   | 20   |\n|-----------------------|-------------|----------|------|------------------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|\n| IP w/ TS ($T=0.5$)    | 0.05        | 0.12     | 0.2  | 0.2              | 0.26 | 0.29 | 0.29 | 0.29 | 0.31 | 0.33 | 0.34 | 0.34 | 0.36 | 0.36 | 0.39 | 0.41 | 0.41 | 0.43 | 0.43 | 0.44 | 0.45 |\n| IP w/ TS ($T=0.75$)   | 0.05        | 0.07     | 0.11 |             0.11 | 0.14 | 0.17 | 0.21 | 0.23 | 0.26 | 0.27 | 0.29 | 0.29 | 0.31 | 0.32 | 0.32 | 0.32 | 0.32 | 0.34 | 0.36 | 0.37 | 0.37 |\n| IP w/ TS ($T=1.25$)   | 0.05        | 0.1      | 0.18 | 0.26             | 0.27 | 0.3  | 0.35 | 0.38 | 0.41 | 0.42 | 0.42 | 0.42 | 0.44 | 0.46 | 0.46 | 0.47 | 0.48 | 0.48 | 0.48 | 0.49 | 0.49 |\n| IP w/ Platt Scaling   |        0.05 | 0.17     | 0.23 | 0.27             | 0.3  | 0.33 | 0.4  | 0.42 | 0.43 | 0.45 | 0.46 | 0.46 | 0.47 | 0.47 | 0.48 | 0.51 | 0.51 | 0.51 | 0.51 | 0.52 | 0.53 |\n| C-IP ($\\alpha = 0.1$) |        0.05 | 0.13     | 0.19 | 0.23             | 0.31 | 0.35 | 0.41 | 0.43 | 0.44 | 0.45 | 0.46 | 0.46 | 0.48 | 0.51 | 0.52 | 0.54 | 0.57 | 0.58 | 0.58 | 0.59 | 0.59 |\n\n*Open query set, Free-text query answers*\n| Iteration              |        0    |        1 | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   | 20   |\n|------------------------|-------------|----------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|\n| IP w/ TS ($T=0.5$)     | 0.05        | 0.25     | 0.44 | 0.49 | 0.57 | 0.61 | 0.69 | 0.71 | 0.74 | 0.81 | 0.81 | 0.84 | 0.84 | 0.84 | 0.84 | 0.85 | 0.85 | 0.85 | 0.85 | 0.85 | 0.86 |\n| IP w/ TS ($T=0.75$)    | 0.05        | 0.28     | 0.44 | 0.56 | 0.62 | 0.62 | 0.64 | 0.69 | 0.69 | 0.71 | 0.75 | 0.77 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 |\n| IP w/ TS ($T=1.25$)    | 0.05        | 0.34     | 0.47 | 0.57 | 0.61 | 0.66 | 0.69 | 0.72 | 0.78 | 0.81 | 0.81 | 0.84 | 0.84 | 0.84 | 0.84 | 0.84 | 0.85 | 0.85 | 0.86 | 0.86 | 0.86 |\n| IP w/ Platt Scaling    |        0.05 | 0.3      | 0.43 | 0.52 | 0.61 | 0.64 | 0.74 | 0.75 | 0.77 | 0.81 | 0.82 | 0.84 | 0.84 | 0.88 | 0.89 | 0.89 | 0.9  | 0.91 | 0.91 | 0.91 | 0.91 |\n| C-IP ($\\alpha = 0.15$) |        0.05 | 0.35     | 0.53 | 0.6  | 0.67 | 0.72 | 0.75 | 0.8  | 0.81 | 0.83 | 0.86 | 0.88 | 0.88 | 0.89 | 0.9  | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 |\n\nFor TS, logits obtained from LLMs are divided by a temperature scalar $T \\in \\\\{0.5, 0.75, 1.25\\\\}$ before applying softmax. We observe that C-IP outperforms IP with TS in all settings. \n\nFor standard calibration methods that require calibration data (e.g. PS), we note that we cannot directly \"plug-in\" and apply; similar to C-IP with marginal guarantee over only samples, they still require us to obtain samples with the exact history $q_{1:k}(x^{\\text{obs}})$ during inference (See L190-195 for our original, full argument). Hence, to run Platt scaling with calibration data, we also need to do random sampling as for our method. In our additional experiments with 20Q, we found that IP with PS performs worse in the earlier iterations but comparably in later iterations for free-text query answers. Moreover, IP with PS performs worse in all iterations of the binary query answer setting. \n\nOverall, our additional baseline results find that C-IP outperforms IP with calibration methods of TS and PS. We argue that in the open query set settings, where the distribution is more complex, conformal prediction is a better method for good estimations of uncertainty, showing that calibration alone is not sufficient and our formulation is necessary.\n\n\n**Clarification 1: Confusion about notation and computation**\n\nThank you for the clarification question. We agree that \"some constants\" need to be taken into account.\n\nThe bound we showed is derived from Correira et al. 2021 Corollary 3.1 and Equation (7). The precise bound is the following. For $\\alpha \\in (0, 0.5)$, suppose $P_{X, Y} ( Y \\in C(X)  \\mid H_k ) = 1 - \\alpha$ holds, then\n$$H(Y | X) \\leq h_b(\\alpha) + \\alpha E_{X, Y \\mid Y \\not \\in C (X)} [\\log ( | {Y} | - | {C}(X) | )] + (1 - \\alpha) {E}_{X, Y \\mid Y \\in {C}(X)} [\\log | {C}(X)|]$$\nwhere $h_b$ is the binary entropy function. Therefore, $\\alpha$ is a hyperparameter to be chosen between $(0, 0.5)$. In practice, the choice of $\\alpha$ is ideally small. In our experiments, we evaluate C-IP by searching over multiple $\\alpha$'s and find the one that sufficiently captures the uncertainty $Y$ at each iteration. We show that the bound is not vacuous as long as the desired coverage $\\alpha$ is close to the empirical coverage (which we evaluate using the test set in Figure 3 (right column) as well as Appendix Figure 6, 7 (bottom row). \n\n\nFor the second part of the question, recall that the conditional entropy $H(Y | X)$ depends only on the distribution of $X$, and not on the realized value $x$ of $X$. Hence, neither the left or right hand side depend on the values of $X$.\nHowever, when we apply this bound, we use it conditional on the (non-random) query $q$. So, it depends on the information provided by the query $q$ about the input $X$ (but not on the specific value of $x$), which is what we want. Then, we can optimize this over the query $q$.\n\n\n**Question 2: Implementation of Conditional Entropy and Expected Set Size (Question 2)**\n\nUsing our relaxation in Section 3.2 (depending on the setting), we can find the prediction set using Algorithm 1 in Appendix I. \n\nDuring inference, we assume we have access to an estimation dataset $D_{est} = {\\\\{(x_{i}, y_{i})\\\\}}\\_{i=1}^{N_{est}}$. Now, with $ q\\_{1:k}(x^{obs}) $ in our history, we estimate $E_X [ | C_{\\tau} ( q(X) ) | | H ] = \\sum^{N\\_{est}}_{i=1} |{C}({q\\_{1:k}(x^{obs}) \\cup q(x\\_i)})|$. We will update and clarify this in the Appendix. \n\nFurthermore, for the second part of your question, suppose $q$ is a query that is irrelevant, say \"How many wheels does the animal have?\", then this query is naturally uninformative for the task, hence is unlikely to be selected. In other words, our method already takes the possibility of uninformative, irrelative queries into consideration when estimating uncertainty."}, {"review_id": "4qrftoXdJc", "reviewer": "Reviewer_spQy", "summary": "This paper introduces conformal information pursuit, which extends the information pursuit framework for guiding LLMs in sequential question selection. Specifically, C-IP uses conformal prediction sets to estimate uncertainty in a distribution-free manner for subsequent query selection. The method is evaluated on the 20 Questions and MediQ datasets.", "questions": "See above.", "limitations": "yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n- The proposed framework is easy to implement.\n\n- The study is well-motivated by the open-ended nature of queries and answers in conversational settings.\n\nWeaknesses\n\n1. Lack of Theoretical Contribution\n\n- The study relies heavily on theoretical analysis from prior work [18, 64], with limited novel theoretical development.\n\n2. Insufficient Theoretical Justification for History Sampling and Multi-Round Settings\n\n- The construction of prediction sets across dialogue histories involves marginalization steps that lack theoretical grounding.\n\n- Additionally, the paper proposes two potential methods for history sampling, but neither is supported by formal theoretical analysis.\n\n3. Limited Baselines and Marginal Improvements\n\n- There is no comparison to learned query policies, calibration-based methods, or reinforcement learning-based strategies.\n\n- The performance improvements appear modest and primarily limited to baseline comparisons, with gains mostly in early stages.\n\n4. Why Not Calibrate the LLM Instead?\n\n- The paper assumes that LLM outputs are too miscalibrated for entropy-based selection, but makes no effort to calibrate the LLM’s own confidence scores.\n\n5. Similarity to Prior Work\n\n- The proposed method appears highly similar to [64].", "was_revised": true, "final_justification": "The authors partially addressed my concerns about comparisons. So, I have updated my score to 4.", "rebuttal": "Thank you for your review and questions. We are glad to hear that you find our \"well-motivated by the open-ended nature of queries and answers in conversational settings.\" Please kindly see below for our responses.\n\n**\"Highly Similar to Conformal Language Modelling [64]\"**\n\nWe strongly disagree that our work is similar to Conformal Language Modeling (CLM) [64]. They develop a method for conformal language modelling, which requires repeated (iid, non-interactive) sampling from an LLM until a certain correctness criterion is met, using conformal risk control.\nOur work focuses on interacting with LLMs via information pursuit by \nseeking to ask informative questions. We start from Information Pursuit (IP), entropy maximization, and leverage conformal prediction to get a feasible method. Notably, CLM uses conformal risk control, while we connect to standard conformal prediction as one way of estimating uncertainty. Thus, while LLMs and conformal prediction are used in both our work and CLM, our problem setting, formulation, and experiments cannot be farther apart from those of CLM. \n\n\n**The lack of theoretical justification**\n\nThe central contribution of our work is methodological, not theoretical. Specifically, we propose an efficient method to interactively guide an LLM by choosing queries based on maximizing information gain and use of conformal prediction to improve query selection with IP. Thus, we politely but firmly disagree with the reviewer that we would need novel theoretical developments (given the additional significant methodological innovation). Our work is theoretically inspired by the work [18]. Regarding the marginalization step and sampling methods, as we already stated and justified in the paper, they well in practice and in our experiments. We argue that a complete theoretical justification is beyond the scope of our work; because this goes well beyond the current theoretical frontier in conformal prediction and may require significant and completely novel theoretical approaches. \n\nFollowing current standards in the field (as can be checked in papers in recent conferences), having theoretical contributions in a methodological paper is not a requirement to acceptance at NeurIPS.\n\n**Lack of Baselines and Marginal Improvements**\n\nWe have already provided thorough comparisons to state-of-the-art methods, including information pursuit and Uncertainty-of-Thought, an entropy-based chain-of-thought method applicable to binary queries. We have compared to all methods that we know of to have high performance on the problems of iterative information seeking; following best practices in the area. We found considerable performance gains (say a success rate increase from 0.5 to 0.8). \n\nRegarding other comparisons, we do not think that there is a clear RL baseline that is directly comparable; as one would have to define an appropriate reward, environment, etc.. We are not aware of appropriate existing ``learned query policies\" that one could use for information seeking. Can you clarify which related works exactly you mean should be compared?\n\nFurthermore, our work focuses on the strategy of IP that yields short query-answer chains; we argue performance of earlier iterations demonstrate ability to choose informative queries, and performance of later iterations demonstrate ability to converge to the full posterior with a subset of queries (i.e. $KL(P(y | x) \\mid P(y \\mid q\\_{1:k}(x)))$). Overall, our work focuses on interactivity with information gain, a dimension of LLM research that remains largely unexplored. \n\n\n**\"Why not just calibrate the LLM instead?\"**\n\nThank you for the additional baseline suggestion. We agree that there is the possibility that the alternative method of \"first calibrating LLM probabilities then estimate uncertainty using entropy\" might find success.\nTo test this hypothesis, we performed additional experiments by first applying temperature scaling (TS) and Platt scaling (PS) to calibrate LLM probabilities, then inference with standard IP (not the conformal version). Note that TS (for a fixed temperature) does not depend on calibration data, whereas PS does depend on calibration data. We evaluate 20Q in two of the open query set settings as before, and average each accuracy curve over 5 random seeds.\n\n*Open query set, Binary query answers*\n| Iteration             |        0    |        1 | 2    | 3                | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   | 20   |\n|-----------------------|-------------|----------|------|------------------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|\n| IP w/ TS ($T=0.5$)    | 0.05        | 0.12     | 0.2  | 0.2              | 0.26 | 0.29 | 0.29 | 0.29 | 0.31 | 0.33 | 0.34 | 0.34 | 0.36 | 0.36 | 0.39 | 0.41 | 0.41 | 0.43 | 0.43 | 0.44 | 0.45 |\n| IP w/ TS ($T=0.75$)   | 0.05        | 0.07     | 0.11 |             0.11 | 0.14 | 0.17 | 0.21 | 0.23 | 0.26 | 0.27 | 0.29 | 0.29 | 0.31 | 0.32 | 0.32 | 0.32 | 0.32 | 0.34 | 0.36 | 0.37 | 0.37 |\n| IP w/ TS ($T=1.25$)   | 0.05        | 0.1      | 0.18 | 0.26             | 0.27 | 0.3  | 0.35 | 0.38 | 0.41 | 0.42 | 0.42 | 0.42 | 0.44 | 0.46 | 0.46 | 0.47 | 0.48 | 0.48 | 0.48 | 0.49 | 0.49 |\n| IP w/ Platt Scaling   |        0.05 | 0.17     | 0.23 | 0.27             | 0.3  | 0.33 | 0.4  | 0.42 | 0.43 | 0.45 | 0.46 | 0.46 | 0.47 | 0.47 | 0.48 | 0.51 | 0.51 | 0.51 | 0.51 | 0.52 | 0.53 |\n| C-IP ($\\alpha = 0.1$) |        0.05 | 0.13     | 0.19 | 0.23             | 0.31 | 0.35 | 0.41 | 0.43 | 0.44 | 0.45 | 0.46 | 0.46 | 0.48 | 0.51 | 0.52 | 0.54 | 0.57 | 0.58 | 0.58 | 0.59 | 0.59 |\n\n*Open query set, Free-text query answers*\n| Iteration              |        0    |        1 | 2    | 3    | 4    | 5    | 6    | 7    | 8    | 9    | 10   | 11   | 12   | 13   | 14   | 15   | 16   | 17   | 18   | 19   | 20   |\n|------------------------|-------------|----------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|------|\n| IP w/ TS ($T=0.5$)     | 0.05        | 0.25     | 0.44 | 0.49 | 0.57 | 0.61 | 0.69 | 0.71 | 0.74 | 0.81 | 0.81 | 0.84 | 0.84 | 0.84 | 0.84 | 0.85 | 0.85 | 0.85 | 0.85 | 0.85 | 0.86 |\n| IP w/ TS ($T=0.75$)    | 0.05        | 0.28     | 0.44 | 0.56 | 0.62 | 0.62 | 0.64 | 0.69 | 0.69 | 0.71 | 0.75 | 0.77 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 | 0.79 |\n| IP w/ TS ($T=1.25$)    | 0.05        | 0.34     | 0.47 | 0.57 | 0.61 | 0.66 | 0.69 | 0.72 | 0.78 | 0.81 | 0.81 | 0.84 | 0.84 | 0.84 | 0.84 | 0.84 | 0.85 | 0.85 | 0.86 | 0.86 | 0.86 |\n| IP w/ Platt Scaling    |        0.05 | 0.3      | 0.43 | 0.52 | 0.61 | 0.64 | 0.74 | 0.75 | 0.77 | 0.81 | 0.82 | 0.84 | 0.84 | 0.88 | 0.89 | 0.89 | 0.9  | 0.91 | 0.91 | 0.91 | 0.91 |\n| C-IP ($\\alpha = 0.15$) |        0.05 | 0.35     | 0.53 | 0.6  | 0.67 | 0.72 | 0.75 | 0.8  | 0.81 | 0.83 | 0.86 | 0.88 | 0.88 | 0.89 | 0.9  | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 | 0.91 |\n\nFor TS, logits obtained from LLMs are divided by a temperature scalar $T \\in \\\\{0.5, 0.75, 1.25\\\\}$ before applying softmax. We observe that C-IP outperforms IP with TS in all settings. \n\nFor standard calibration methods that require calibration data (e.g. PS), we note that we cannot directly \"plug-in\" and apply; similar to C-IP with marginal guarantee over only samples, they still require us to obtain samples with the exact history $q_{1:k}(x^{\\text{obs}})$ during inference (See L190-195 for our original, full argument). Hence, to run Platt scaling with calibration data, we also need to do random sampling as for our method. Here, we will run IP with Platt scaling using the same calibration data as our experiments with C-IP. In our additional experiments, we found that IP with PS performs worse in the earlier iterations but comparably in later iterations for the free-text query answers setting. Moreover, IP with PS performs worse in all iterations for the binary query answers setting. \n\nOverall, our additional baseline results find that C-IP outperforms IP with calibration methods of TS and PS. We argue that in the open query set settings, where the distribution is more complex, conformal prediction is a better method for good estimations of uncertainty, showing that calibration alone is not sufficient and our formulation is necessary."}, {"review_id": "mzhLYEn8EI", "reviewer": "Reviewer_QsyY", "summary": "In the paper an Information Pursuit strategy is applied to settings where LLMs can interactively query the user to make a prediction, e.g. in a medical diagnosis setting. Such strategies typically maximize the information gain (or equivalently the conditional entropy) of each query. While LLMs output probabilities over their outcome, these probabilities are known to be miscalibrated and therefore do not serve as a reliable measure of uncertainty need to estimates the conditional entropy. The paper therefore proposes to leverage the upper bound on the entropy base on the cardinality of prediction sets (see Correira et al.), in order to circumvent the miscalibration issue.", "questions": "* For the results in Figure 2: How is \"uncertainty\" defined and measured?\n---\n\n**An explanation regarding the following two questions would likely make me increase my score:**\n\n---\n* Since the LLM predictions are miscalibrated, the sampled of histories from LLM simulations should also be biased and therefore the predictions sets, too, might be biased. Is it some kind of \"averaging out\" of biases that makes the construction work well in the end nevertheless?\n---\n* Section 5.2 says:\n> The performance of C-IP and the baselines for the three specialities is shown in Figure 4. C-IP consistently obtains higher test accuracy at each iteration than IP for IM and P while achieving comparable performance for N. \n\nIn Figure 4 on the **IM dataset**, to me it looks like that C-IP has lower accuracy for 1,2,5,6 and 7 iterations and higher accuracy for 3,4, 9 and 10 iterations. On the **P dataset**, it looks like C-IP performs better for 2,3,4,7,9 and 10 iterations and worse for 1,5,6 and 8 iterations. Am I misreading Figure 4? Otherwise, I would suggest weakening the statement \"consistently obtains higher test accuracy\" to \"achieves comparable performance\".", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n* the approach is theoretically sound as it is based on a mathematical relation between the entropy and the cardinality of prediction sets.\n* reducing the number of questions in such interactive LLM-settings is an important research aim and the suggested approach is as far as I know an original combination of the Information Pursuit, Prediction sets and LLMs. \n* clear motivation and easy-to-follow introduction of the background material on Information pursuit and conformal prediction.\n\n**Weaknesses:**\n*  it is not fully clear to me if there are performance gains in the application setting in Section 5 or not\n\n**Minor comment:**\n* The legend in Figure 4 is very small and difficult to read.\n* It is fairly uncommon to have the Related Work Section in the Appendix only. Usually explaining how the work builds upon the existing literature is an integral part of a paper.", "was_revised": true, "final_justification": "My concerns were addressed with the additional clarifications and I therefore updated my score to recommend acceptance.", "rebuttal": "Thank you for your positive. We appreciate the clear instructions on how to improve our scores. We are glad you find our paper \"theoretically sound\" with \"clear motivation.\"  Also, thank you for acknowledging that our direction of \"interactive LLM-settings is an important research.\" Please kindly see below for our response. \n\n**Definition and Measurement of Uncertainty in Figure 2**\n\nThank you for the clarification question. Figure 2 is intended to serve as a motivating figure that abstracts from Figure 3. The results shown here is exactly that from 20Q with Llama-3.1-8B with a closed query set. The dashed curve corresponds to the measurement of conditional entropy $H(Y \\mid q(X), H\\_k)$, directly estimated from probabilities obtained from LLM logits. The solid curves correspond to the measurement of expected size of the prediction set $E\\_{X}[C(q(X)) \\mid H_k]$.\n\n**\"Bias of prediction sets due to bias in sampled histories from LLMs\"**\n\nWe thank the reviewer for the clarification question. The issue of bias is exactly the reason why conformal prediction is needed, and the process of finding the threshold $\\tau$ based on the conformal guarantee is the exact step in accounting for this bias. To be more explicit, let's consider the construction of the prediction set $C_\\tau$: Suppose we fix $\\alpha = 0.05$. From the calibration set $D\\_{cal} = \\{(x\\_i, y\\_i)\\}\\_{i=1}^{N}$ and their sampling of histories, we can observe the probability of the correct label $P(Y = y\\_i \\mid H\\_k)$. If the probabilities are biased towards something small, say below 0.5, then the threshold $\\tau$ we obtained will also be smaller than 0.5. In fact, $\\tau$ is the threshold where $100(1-\\alpha)$\\% of the correct samples are above the threshold. In other words, the biases are considered and adjusted in the process of conformal prediction itself. Therefore, assuming test samples and calibration samples are exchangeable, we are effectively accounting for this bias during inference. \n\n**Performance Gains and Question regarding Figure 4** \n\nThank you for your comment. We agree that, relative to Section 4 and experiments with 20Q, the performance gains shown in Section 5 with Interactive Medical Question Answering is minor. For Figure 4, we agree that the statement is slightly over-claimed and will change it to \"achieves comparable performance\". \n\nHowever, we would also like to emphasize that the purpose is to demonstrate the potential and broad applicability of C-IP to real-world settings. It's worth noting that we do observe performance gains of C-IP over sequential baseline (enumerate). \n\n\n**Minor Comments about Formatting and Related Work**\n\nThank you for the suggestions. We will increase the size of the legend to make it more readable. As for the Related Work section, at the time of writing we believed that the introduction and build-up of the work has sufficiently mentioned the nearest neighbors of our work. However, since it is not a complete full-fetched Related Work section, we decided to add a full section in the appendix for coherence and clarification."}, {"review_id": "8eVNrWzGlk", "reviewer": "Reviewer_zf88", "summary": "C-IP provides a mathematically rigorous solution to uncertainty quantification in sequential querying, using conformal prediction sets to address fundamental LLM calibration issues. While offering strong theoretical guarantees and demonstrated performance improvements, the approach has limited scope beyond sequential questioning scenarios and does not directly enhance reasoning quality. The contribution is significant within its domain, with clear potential for broader application and integration with complementary reasoning frameworks.", "questions": "Good work.  A couple of questions...\n\n1. Your method's effectiveness appears heavily dependent on the quality and comprehensiveness of the available query set Q. In real-world scenarios where optimal queries may not be pre-known or where the query space is naturally limited, how robust is C-IP to suboptimal query sets? Could you provide guidance on when practitioners should expect the method to fail or underperform?\n\n2. While C-IP effectively addresses uncertainty quantification, it doesn't directly improve the quality of reasoning or handle LLM hallucinations. Given the demonstrated complementarity with approaches like EVINCE that focus on reasoning quality, have you considered how C-IP could be integrated into broader multi-LLM reasoning frameworks? What would be the technical challenges and potential benefits of such integration?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "A. Strengths of this work:\n\nA.1. Rigorous Theoretical Foundation: The work is grounded in conformal prediction theory, providing mathematically principled uncertainty quantification with formal coverage guarantees. Notably, the approach is distribution-free and does not require calibrated probability estimates, addressing a fundamental limitation of traditional entropy-based methods.\n\nA.2 Demonstrated Practical Effectiveness: C-IP shows consistent performance improvements across multiple domains (20 Questions, medical QA), with clear mathematical stopping criteria and computational efficiency for discrete classification problems. The method provides robust uncertainty estimates even when LLM probabilities are miscalibrated.\n\nB. Weaknesses of this work:\n\nB.1 Limited Scope and Applicability:\n\nNarrow focus on sequential query scenarios limits broader applicability\nPrimarily designed for discrete classification problems\nHeavy dependence on query set quality and availability\nNo mechanisms for improving reasoning quality or argument coherence\n\nB.2 Fundamental Methodological Gaps:\n\nDoes not address core LLM limitations (bias, hallucination, error propagation)\nStatic approach lacks adaptive mechanisms for evolving problem complexity\nLimited to uncertainty quantification without enhancing underlying reasoning processes\n\nOverall Assessment: C-IP makes a significant contribution to uncertainty quantification in sequential querying through rigorous mathematical foundations. However, its impact could be substantially enhanced through integration with complementary reasoning frameworks like EVINCE [1], which addresses the broader challenges of LLM reliability and reasoning quality that C-IP does not tackle.\n\n[1] Optimizing Multi-LLM Dialogues Through Information-Theoretic Control, E. Chang, August 2024.\nhttps://www.researchgate.net/publication/383425368_Optimizing_Multi-LLM_Dialogues_Through_Information-Theoretic_Control", "was_revised": true, "final_justification": "The paper presents a theoretically sound and empirically validated method for interactive LLM querying. However, its contributions are incremental and the scope narrow, leading to my weak accept rating. The proposed method acts as a bandaid to improve LLM answer quality—greedy in nature, with performance heavily dependent on data and query specifics. \n\nI acknowledge the rebuttal from the authors to be reasonable, but the weak accept rating already reflects my respect to the work with the following weaknesses:\n\nBottom Line Weaknesses\n\nNarrow focus - Only addresses calibration, ignores other critical LLM problems\nLimited novelty - Core information-theoretic approach may not be sufficiently novel\nPractical limitations - Requires good query sets, unclear how to scale (RAG may not guarantee high quality data)", "rebuttal": "Thank you for the positive review. We are glad to hear that you find our work to have \"Rigorous Theoretical Foundation\" and \"Demonstrated Practical Effectiveness.\" Please see below for our response. \n\n**Limited Scope and Applicability**\n\nWe respectfully disagree that our paper has limited scope and applicability. To the best of our knowledge, the setting of interactions between multiple LLMs by maximizing information gain is a relatively unexplored direction. We have also demonstrated via interactive medical question answering setting that it can be extended to real-world tasks. Our thorough experiments, we argue, provide a strong justification for the applicability and potentiality of our work. \n\nLast but not least, our method does not explicitly consider reasoning. We neither require or leverage reasoning LLMs. Therefore, we believe that ``improving reasoning quality or argument coherence\" is a completely orthogonal problem to what is considered in our paper. \n\n\n\n **Fundamental Methodological Gaps**\n\nWe address the major \"core LLM limitations\" relevant to our problem.  For our problem, the core issue with LLMs, as stated in our introduction, is the fact that LLMs probabilities are miscalibrated. This also serves as our motivation to develop our proposed method C-IP. While bias, hallucination, error propagation are all important research directions, they are not as important for our specific problem. For instance, when interacting in a 20 questions setting, LLMs must simply choose among 20 different possibilities, and so issues of bias or error propagation are not the most salient ones. While improving performance on these issues, We believe that there is higher payoff to remedy calibration problems and that's why we focused on that task here. \n\nWe disagree that our work \"lacks adaptive mechanisms.\" Our method C-IP is adaptive by design: C-IP is a sequential algorithm, and selects/answers queries based on the provided context and information obtained adaptively. \n\nFinally, we are unclear what the reviewer is referring to as \"reasoning process,\" as our work involves no LLM reasoning (In the sense of modern reasoning LLMs such as o1, o3, or DeepSeek). \nIf this is meant informally, then we would like to clarify that our method does in fact improve reasoning (compared to standard baselines such as information pursuit or chain of thought), by appropriately prioritizing the questions to ask.\n\n**Questions and Comments about Query set, such as \"Heavy dependence on query set quality\" and \"optimal queries may not be pre-known\"**\n\nCertainly, there is some mild dependence on the query set, but this is reasonable and easily satisfied at least approximately in practice.  Basically, in our experiments we found that our method works well with a variety of query sets.\nFrom the definition of our problem (see equation (1)), we assume that our query set is *sufficient*: which means that the set of all queries fully describes the given task $Y$. In our work, we have explored both settings where query set is known ahead of time (closed query set) and is unknown (open query set). In both settings, we find that C-IP is not impacted by the fact that the query set may not be known ahead of time. \n\nIn our experiments, we have demonstrated that our method works well in both closed query set setting where the user predefined a fixed query set and open query set setting where the queries are prompted from LLMs. \n\nMoreover, as a general practical strategy to approximately satisfy sufficiency,\none may resort to pre-processing methods such as retrieval augmented generation with knowledge bases or prompting techniques to acquire a sufficient query set. While this direction has been explored in previous versions of IP [1], the task of generating good questions/queries from LLMs remains a worthy research direction. \n\n[1] Aditya Chattopadhyay, Kwan Ho Ryan Chan, and Rene Vidal. \"Bootstrapping variational information pursuit with large language and vision models for interpretable image classification.\" In The Twelfth International Conference on Learning Representations. 2024.\n\n**Complementary Frameworks such as EVINCE**\n\nThank you for the suggestion. We were unaware of this work and will add this to our related work section; we agree that the work is complementary and could be incorporated in our framework. We will reserve this as a future direction. \n\nIn our work, we have presented the simplest setting for interacting with LLMs, selecting queries in the order of information gain. We agree that this setting can potentially be extended from simple to complex multi-LLM settings, such as reaching consensus and forming arguments and debating. As an example, it might require us to modify the query-answering mechanism to allow for multi \"expert\" LLMs, or modify the objective to allow for estimating mutual information among multiple LLMs. We argue that the method and framework we have presented in this framework, because of its simplicity, allows a multitude of modifications that can adapt to many current, exciting LLM directions, including the EVINCE framework."}]

Author rebuttal:

Meta-review: The paper proposes an approach for efficient multi-step problem solving for LLMs. The approach aims to ask the most “informative” query at each iteration given prior history, until the model is confident enough to make a prediction. 

They use Information Pursuit framework and define the most informative query as the one that maximizes information gain at each iteration, or equivalently the query whose answer minimizes the uncertainty of the prediction. They remark that estimating conditional entropy for this purpose is challenging due to the fact that the LLM outputs are often miscalibrated and propose an alternative approach to quantify sequential information gain that leverages the notion of prediction sets from conformal prediction. They argue that prediction sets from conformal prediction leads to more robust estimates compared to standard entropy. They utilize conformal prediction sets based on probability estimates from the LLM, and at each iteration seek to minimize the prediction set size as LLM gains more information at each turn. 

The problem is clearly motivated and the approach is theoretically founded. The paper demonstrates practical utility of the proposed approach via experiments showing reduced number of questions required by the proposed approach. Discussions during the rebuttal period helped address some of the reviewer concerns (e.g. how simpler calibration methods would compare to proposed approach, clarification about notation, clarification on bias of prediction sets), with general agreement amongst reviewers on the technical soundness and supporting empirical results.
Decision: Accept (poster)