Conformal Information Pursuit for Interactively Guiding Large Language Models

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.

Limited Scope and Applicability

We 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.

Last 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.

Fundamental Methodological Gaps

We 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.

We 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.

Finally, 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). If 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.

Questions and Comments about Query set, such as "Heavy dependence on query set quality" and "optimal queries may not be pre-known"

Certainly, 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. From 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.

In 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.

Moreover, as a general practical strategy to approximately satisfy sufficiency, one 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.

[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.

Complementary Frameworks such as EVINCE

Thank 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.

In 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.

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.

Definition and Measurement of Uncertainty in Figure 2

Thank 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]$.

"Bias of prediction sets due to bias in sampled histories from LLMs"

We 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.

Performance Gains and Question regarding Figure 4

Thank 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".

However, 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).

Minor Comments about Formatting and Related Work

Thank 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.

Thank you for the clarification question.

Generally in conformal prediction, the calibration set contains samples from the distribution for which we are aiming to achieve coverage. For instance in the simpler setting of predicting $Y$ from $X$ that are drawn from a given distribution where the coverage guarantee is $P_{X, Y}(Y \in C(X)) \ge 1 - \alpha$, the calibration set is $D_{cal} = \\{(x_i, y_i)\\}_{i=1}^{N}$, where each datapoint is drawn from the same distribution. For a fuller explanation, please refer to [1].

In our case, since we are trying to satisfy the coverage guarantee (Equation 11), the calibration set contains samples of the query-answer chains. We proposed two ways of obtaining samples and the calibration set, which depends the setting of closed/open query set: (1) calibration samples in the closed query set setting are obtained from a uniform parameterization described in L204-209, and (2) calibration samples in the open query set setting are obtained by LLM simulations described in L210-214 as well as Appendix I, Algorithm 6. As to the number of samples, we use 100 samples for 20Q and 200 samples for MediQ, both described in L251, L345, and Appendix G.7. We will update the Appendix section G.7 with a more complete description to make this entire procedure clear.

Therefore, to add to our original comment about "Bias of prediction sets due to bias in sampled histories from LLMs", the bias of in sampled histories from LLMs is based on the empirical distribution of samples we obtain, in which the conformal prediction component of our method directly addresses by satisfying our desired coverage (Equation 11).

[1] Angelopoulos, A. N., & Bates, S. (2021). A gentle introduction to conformal prediction and distribution-free uncertainty quantification. arXiv preprint arXiv:2107.07511.

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.

"Highly Similar to Conformal Language Modelling [64]"

We 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. Our work focuses on interacting with LLMs via information pursuit by seeking 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.

The lack of theoretical justification

The 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.

Following 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.

Lack of Baselines and Marginal Improvements

We 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).

Regarding 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?

Furthermore, 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.

"Why not just calibrate the LLM instead?"

Thank 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. To 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.

Open query set, Binary query answers

Open query set, Free-text query answers

For 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.

For 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.

Overall, 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.

Thank you again for the insightful reviews. If there are any unresolved concerns and questions, feel free to ask any additional questions to which we may answer and provide additional clarification. If you feel our rebuttal has sufficiently addressed your concerns, we would appreciate it if you could kindly reconsider your evaluation.

Sincerely,

Authors

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.

The need for conformal prediction and calibration

Thank 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.

More 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:

1. computing mutual information (or conditional entropy) directly is challenging for complex distributions, especially here $q(X)$ is a distribution of text;
2. LLM probabilities are inaccurate (miscalibrated), which leads to poor estimates of conditional entropy and suboptimal predictive performance (as in our introduction);
3. Conformal Prediction provides theoretically justified and rigorous Fano-type upper bound to conditional entropy (for any $\alpha$), per our referenced proposition.
4. As we will discuss below, empirically we observe that C-IP performs better than IP with calibration methods. Hence, our work here derived the new formulation of C-IP, which leverages aspects of conformal prediction to select informative queries strategically.

Additional Baselines with Calibration Methods (Weakness and Question 3)

Thank 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. To 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.

Open query set, Binary query answers

Open query set, Free-text query answers

For 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.

For 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.

Overall, 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.

Clarification 1: Confusion about notation and computation

Thank you for the clarification question. We agree that "some constants" need to be taken into account.

The 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 $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)|]$ where $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).

For 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$. However, 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$.

Question 2: Implementation of Conditional Entropy and Expected Set Size (Question 2)

Using our relaxation in Section 3.2 (depending on the setting), we can find the prediction set using Algorithm 1 in Appendix I.

During 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.

Furthermore, 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.

Thank you again for the insightful reviews. If there are any unresolved concerns and questions, feel free to ask any additional questions to which we may answer and provide additional clarification. If you feel our rebuttal has sufficiently addressed your concerns, we would appreciate it if you could kindly reconsider your evaluation.

Sincerely,

Authors