4. On Quach. et al. 2023

We appreciate the reviewer’s pointing out that there is a distinction between traditional conformal prediction and the learn-then-test framework, although we consider them to be closely related. (The work by Quach et al. (2023) describes their method as “Translating this process to conformal prediction” and “an extension of conformal prediction,” although they also draw contrasts between their method and conformal prediction.) For clarity, in the two places where we cite Quach et al., we will broaden the scope as suggested, replacing “conformal prediction” with “conformal prediction and related methods".

5. Optimization method for CP-OPT

While we introduce the penalty term $\lambda$ to transform the problem into an unconstrained one (P2), our approach treats $\lambda$ as a hyperparameter, unlike penalty or augmented Lagrangian methods, where this parameter is iteratively updated during optimization. We appreciate the suggestion to explore these methods for solving (P2) and recognize it as an interesting direction for future work.

6. Optimization over $g$ and $\tau$

You are correct that $\tau$ can be deterministically obtained once $g$ is specified. We include $\tau$ explicitly in the formulation to simplify the objective and avoid the complexity introduced by computing $\tau$ as the $\alpha$ quantile of $g$ during optimization. Estimating $\tau$ after each update of $g$ would significantly slow down the learning procedure for $g$.

We appreciate your careful reading and thorough feedback. Thank you for highlighting the strengths of our work, particularly the simplicity of our methods and the effectiveness of CROQ in improving LLM predictions. We’re especially pleased that, like us, you found the idea behind CROQ very interesting and appreciated its surprising results. We appreciate your suggestion connecting CROQ to chain-of-thought reasoning, which provides an exciting perspective. Below, we address the specific concerns raised.

1. Coherence of the methodologies

We understand the reviewer’s concern regarding the perceived separation between CP-OPT and CROQ. While these methods can function independently, they are complementary and align with our broader goal of robust uncertainty quantification and accuracy improvement in LLMs. To make this connection clearer, we have added Hypothesis H3 and additional experiments (Table 11, 12, 13) demonstrating how CP-OPT enhances CROQ by producing smaller, high-coverage prediction sets that improve LLM performance in the second round of querying.

CROQ’s success depends on the size of the prediction sets it refines—smaller sets from CP-OPT reduce uncertainty and improve accuracy more effectively than larger sets from logits. Figure 4 further supports this by demonstrating that as prediction set size decreases (simulated using ground truth), CROQ's accuracy consistently improves. This evidence highlights the importance of CP-OPT in optimizing CROQ's performance. We believe this workflow provides a coherent and principled approach to reducing uncertainty and refining LLM predictions. We have revised the manuscript to highlight this connection more explicitly.

2. Writing inconsistencies

We appreciate your careful reading and suggestions with line numbers. We have updated the paper to incorporate most of them. The updates are highlighted in blue color. We clarified what we mean by flexible $\mathcal{G}$ and provide details in the Appendix B.1. We updated the draft to consistently use ''score function'', use $C(x ; g,\tau)$ in place of $C(x | g,\tau)$. We also found Figure 1 was not adding much, so removed it.

3. On the value of conformal prediction in CROQ

We agree that if the sole goal is to optimize accuracy, one could directly tune a quality threshold as suggested by the reviewer. However, the suggested procedure is conceptually equivalent to what CP provides, with CP adding meaning and theoretical gurantees to the process. Moreover, CP serves our broader goal of uncertainty quantification and making LLM's inference robust.

In our setup, LLMs produce an initial prediction set, which may then be refined and re-evaluated using the CROQ procedure. CP ensures that these sets are not only appropriately sized but also include the true answer with a specified probability (e.g., 95%). This ensures that CROQ operates on a solid theoretical foundation, balancing uncertainty reduction and accuracy improvement.

Directly optimizing a threshold might yield similar results in some cases, but CP formalizes the process and guarantees coverage, making it a more versatile and reliable approach. By leveraging CP, we align CROQ with a well-established methodology, enhancing its interpretability and applicability to a wider range of tasks. We hope this clarifies the importance of CP in the context of CROQ.

4. Clarification on Monty Hall connection

While the Monty Hall analogy is not critical to the methodology, we use it to: (a) provide a familiar conceptual framework to understand the effectiveness of CROQ, and (b) highlight the broader possibilities for defining oracles in CROQ.

In CROQ, the conformal set generated during the first stage contains the correct answer with a user-specified probability (e.g., 95%). This is conceptually similar to an oracle eliminating incorrect options ("goats") with high probability. The LLM is then re-queried with the remaining options, sometimes leading to improved accuracy by refining its predictions.

Unlike Monty Hall, where the host provides definitive external knowledge, the "oracle" in CROQ is probabilistic and derives its knowledge from the conformal scores. These scores can be sourced from the same LLM or external models, making the process flexible. We have updated the paper to clarify the analogy.

[ Response continues in the next comment ]

I thank the authors for the comprehensive answer. I would again like to make comments:

Regarding 1.

In contrast, our work aims to improve post-hoc uncertainty quantification of LLMs for MCQ and tool-selection tasks.

I am not convinced by this answer. From my understanding, for both MCQ and the tool selection task, one ends up with a setting that is almost identical to classification.

Regarding 2.

I thank the reviewers for this example. However, it is clear that this analysis only works for a random predictor, which is not interesting. In order for the argument to be convincing, the authors would have to demonstrate that such an analysis can be made for more relevant types of classifiers (ideally, any type of classifier). In general, I am afraid, it is straight-forward to see that no analysis or guarantees can be made. Hence, CROQ is an unnecessary detour in the general setting.

All in all, I am still highly convinced that this paper must not be accepted. I will therefore keep my score with high confidence.

1. Regarding the MCQ vs. classification query. These are fundamentally different problem settings. In classification, samples for each class share a common pattern, whereas, in MCQ tasks, there is no inherent pattern in the questions that determines which option is correct. For example, consider sentiment classification versus MMLU (MCQ). In sentiment classification, a sentence aligns with a specific label (e.g., "positive" or "negative"). However, in MCQ tasks, a legal question and a medical question might both have "A" as the correct answer, despite having entirely different features.

We reiterate that, to the best of our knowledge, CP-OPT is a novel contribution towards improving uncertainty quantification (UQ) and the accuracy of LLMs in finite response settings such as MCQ and tool-selection tasks.

2. Analysis for better than random predictors. In the previous example we chose to show the improvements for a random predictor as a worst-case scenario and to keep the example simple. However, it does not mean that the analysis or the guarantees do not extend to better than random predictors.

General Analysis

In general, consider a predictor (LLM) that has accuracy $a_k$ on questions with $k$ choices. It is fair to assume that as the number of choices $k$ decreases, the accuracy $a_k$ increases. This is also confirmed in our experiments (Figure 4). We refer to this as the monotone accuracy property of the predictor.

Now, let the initial number of options in the questions be $M$ and after revising them with conformal prediction (CP) the questions have $m<M$ choices and it is guaranteed by CP that the true answer is still in the $m$ choices for $1-\alpha$ fraction of the questions. Then, the gain in accuracy after CROQ is as follows,

$\text{Gain} = \text{Accuracy After} - \text{Accuracy Before}$ The $\text{Accuracy After} = a_m$ times the fraction of questions for which true choice is in the revised question = $a_m (1-\alpha)$

$\Delta(M,m,\alpha) = a_m(1-\alpha) - a_M = (a_m - a_M) - \alpha a_m$ If $\alpha$ is fixed, then we should see improvements whenever $a_m > \frac{a_M}{1-\alpha}$. And if $\alpha$ is not fixed, then the gain $\Delta(M,m,\alpha) > 0$, for any $\alpha < \frac{a_m - a_M}{a_m}$. By the monotone accuracy property of the predictor $a_m - a_M >0$, that means any $\alpha \in (0, \frac{a_m - a_M}{a_m})$ will yield a gain in accuracy.

Numerical Example

To instantiate it more clearly, Suppose LLM has 50% accuracy for questions with 10 options ($M=10$) and 60% accuracy for questions with 5 options ($m=5$) i.e. $a_{10} = 0.5$ and $a_5=0.6$. Suppose conformal prediction maps these 10 option questions to 5 option questions while ensuring that for 95% (i.e. $\alpha = 0.05$) of the questions, the true answer is still in the reduced set of 5 choices. With this, the new accuracy (after CROQ) will be,

$\text{New Accuracy} = a_5*(1-\alpha) = 0.6×0.95=0.57$
This means the new accuracy is 57%, which is an absolute improvement of 7% over the previous accuracy (i.e. before CROQ).

The above analysis and example clearly demonstrate that the accuracy improvements with CROQ extend to a wide range of predictors, not just random ones. This highlights how the use of conformal prediction (CP) in CROQ enables a systematic characterization of accuracy gains.

We sincerely hope the reviewer will consider our comprehensive responses and revisit their evaluation.

We thank the reviewer for their thoughtful feedback and constructive comments. We are pleased to hear that you found our methods natural and simple, and appreciated the experimental results demonstrating the effectiveness of our two-stage CROQ procedure. Below, we address your concerns in detail.

1. On set size reduction with CP-OPT

We acknowledge the reviewer's observation regarding the varying effectiveness of CP-OPT in reducing set sizes across different settings. We provide additional results (Table 10 and Figures 6-13) and insights to aid in understanding the effectiveness of CP-OPT.

a. Average set size reduction. In Tables 1 and 10 we see total 4 settings where CP-OPT reduces average set size significantly without losing on coverage and in rest of the settings (with a few exceptions) we see reduction in average set size with CP-OPT but at a slightly lower coverage than logits. In some of these settings we see logits were overcovering, thus bringing it down closer to 95% is desirable. Moreover, minor variations in the coverage are anticipated due to calibration on finite samples.

b. Distribution of set sizes. To better understand the set sizes produced by CP-OPT and logit scores we visualize the histograms of their set sizes in Figures 5-11 for the settings in Table 1. In these figures we can see CP-OPT consistently reduces the proportion of large set sizes and increases the proportion of smaller set sizes. This redistribution explains the settings where CP-OPT leads to improvements in the CROQ (Tables 11, 12, 13, 18, and 19) and deferral procedures (Figure 3).

c. Empirical factors. CP-OPT is a principled method designed to learn the optimal scores for conformal prediction (CP). By design, these scores aim to produce smaller prediction sets compared to LLM logits, while maintaining the same coverage level. However, empirical performance depends on several factors, such as the quality of features used for score learning, the number of samples available for calibration, and the specifics of the training procedure.

2. Insights on improvements with CROQ

We agree with the reviewer that if the predictor initially provides the correct posterior probability for each answer option, then the optimal action is to select the option with the highest probability. In this case, since the answer to the MCQ is precisely defined in our approach as the option to which the LLM assigns the highest probability, the LLM would get the question right on the first round, so there would be nothing to gain from querying the LLM again.

What we observe, however, is that reducing the set of available answers changes the probabilities that the LLM assigns to each answer option. Table 3 in the appendix illustrates that the highest probability answer changes approximately 3-15% of the time after CROQ (summing the cases when it changes from correct to incorrect and vice versa). These changes are what produce the overall increase in accuracy that we generally observe with CROQ.

3. Regarding the analogy to Monty Hall

We appreciate the reviewer's perspective, and we here attempt to explain our intended meaning more clearly. The conformal set which is produced in the first stage of CROQ contains the correct answer with some user-specified probability, say 95%. In that sense, we imagine that an (imperfect) oracle is opening some number of doors (answer options) that with high probability reveal only goats (incorrect answers). Those answer options are eliminated, and then the LLM is queried again with the remaining set of answers. As described above, we see that in some proportion of cases, the LLM "decides to switch" its answer as a result of this procedure.

The oracle's "knowledge" comes from the distribution of the scores of correct answers, so it is not contained within the LLM's representation of any given query or the probabilities it assigns to the answer options for that query. In that sense, it is extra information that gets added to each query. Additionally, the score function and the resulting distribution of scores can come from any source. Although in our experiments we used the same LLM both to generate conformal scores and to answer multi-choice questions, the conformal scores could come from another LLM, from embeddings that measure semantic similarity between questions and answers, etc. The extra information that the conformal procedure represents can therefore come entirely from an external source. (In future work we plan to run experiments in which we generate conformal scores externally.)

We note that another reviewer expressed similar concerns and recognize that we did not explain our analogy convincingly. We hope that the above explanation clarifies our perspective. We have added similar explanatory language along these lines to the paper.

Part of Table 9 with Llama-3 model and Logit scores

Part of Table 9 with Llama-3 model and Ours (CP-OPT) scores

Part of Table 9 with Phi-3 model and Logit scores

Part of Table 9 with Phi-3 model and Ours (CP-OPT) scores

Thank you for the comment. We provide mathematical insights into why we expect CROQ to improve performance and empirical evidence (Figure 4 and Tables 4-21) showing that CROQ's improvements are consistent across a range of number of response options, suggesting the gains are due to the reduction in uncertainty.

1. Mathematical reasoning for CROQ is based on a simple fact that reduction in uncertainty can help even a random predictor. This principle is also at play in Monty Hall (and thus the connection). We explain how this helps with a deterministic and a probabilisitc oracles. Consider a random black-box predictor, when given $M$ choices, it selects one option randomly and outputs it as the answer, i.e., its probability of correctness is $1/M$.

a. If there is a deterministic oracle that can reduce the choices to $m<M$, while ensuring that the true answer is among the $m$ choices, then the probability of correctness of the same random predictor would be $1/m$. Implying accuracy improvement $\Delta(M,m) = \frac{1}{m} - \frac{1}{M} = \frac{M-m}{mM} > 0$. The smaller the $m$, the larger the improvement.

b. In practice, we do not have such a deterministic oracle that can reduce the choices to $m$ while retaining the true answer. Suppose, instead we have a "probababilistic oracle" $\mathcal{P}$ that reduces the initial set of $M$ choices (for a randomly drawn question $x$) to $m_x$ while ensuring that the true answer is in the selected $m_x$ choices with probability at least $1-\alpha$. With such an oracle, the improvement in accuracy is as follows,

$\Delta(M,m_x,\alpha) =\frac{1-\alpha}{m_x} - \frac{1}{M}=\frac{M(1-\alpha) -m_x}{m_xM} = \frac{M-m_x}{m_xM} -\frac{\alpha}{m_x} =\Delta(M,m_x) -\frac{\alpha}{m_x}$

Note, here $m_x$ is a random variable, which depends on the effectiveness of the probabilistic oracle $\mathcal{P}$ and $\alpha$. The gain approaches $\Delta(M,m)$ as $m_x \to m$ and $\alpha \to 0$. In other words, if $\mathcal{P}$ outputs a small subset (i.e., small $m_x$) with high coverage probability $1-\alpha$ (i.e., small $\alpha$), then we will have a higher gain in accuracy.

The above arguments show, in principle, that reducing uncertainty can help improve the accuracy of even a random predictor. Thus, even if we assume LLM as a random predictor, we should expect improvement in accuracy with CROQ, provided we can construct a probabilistic oracle $\mathcal{P}$, either using information from the same LLM or through external knowledge sources (such as other LLM, text embeddings, etc.) In our experiments, we see that LLM predictions are better than random, and we can construct $\mathcal{P}$ using the conformal prediction and information from the same LLM, resulting in improvements in accuracy.

2. Empirical results showing the accuracy improvement is due to a reduction in the uncertainty.

We have run CROQ with a groundtruth oracle to demonstrate that it is the reduction in uncertainty that helps LLM answer the revised question with higher accuracy. Please see Figure 4 in the Appendix (page 14). In this experiment, we use the Truthful QA dataset with 15 response options. We first construct conformal prediction sets using logit scores. With these prediction sets, we then leverage groundtruth knowledge to reduce the prediction set size by 0 to 10 options while ensuring that coverage remains constant. We can clearly see in Figure 4, the accuracy of the LLM after requerying increases as more choices are eliminated (smaller prediction set). These results are consistent with the above mathematical arguments on accuracy improvement with reduction in uncertainty and also motivate the use of a score function optimization (CP-OPT) to reduce uncertainty (minimize set sizes) while controlling coverage.

Further, we have extensive experiments on settings with 10 and 15 response options. Please see Tables 4 to 21 in the Appendix; we have also included Table 9 in the comment for your reference. We see CROQ improves accuracy in a vast majority of the settings. The tables provide improvements conditioned on set sizes, i.e., the number of response options in the revised question. As we can see, the improvements are not restricted to only small set sizes, suggesting the improvements are likely due to a reduction in the uncertainty.

We reiterate our focus is on validating the hypotheses (H1, H2, H3). We have provided mathematical insights into why we expect these hypotheses to be true and provided extensive empirical evidence to validate them. Our work shows LLMs can self-correct with CROQ, and it would be exciting future work to develop a precise mechanistic understanding of it.

We hope the above mathematical reasoning and empirical results in Figure 4, and the attached table address your concerns. We are happy to answer any further queries you may have.

Dear reviewer,

Thank you for your thoughtful feedback and constructive comments on our paper. We will provide a full response to all points shortly. We wanted to seek a quick clarification on the additional experiments due to time constraints.

Regarding your suggestion to run experiments on more models, we would be grateful if you could specify any particular models you would like to see included and the specific insights you hope these models will reveal.

Since experiments with large language models are both time-intensive and costly, early guidance on model selection would be greatly helpful as we assess and prioritize what we can provide within the rebuttal period, so that we can engage in as constructive a discussion as possible.

Thanks,

The authors.

Thank you for the thoughtful feedback and constructive comments on our paper. We are pleased to hear that you found our work well-motivated, well-written, and empirically promising for improving uncertainty quantification in LLMs in MCQ settings. Below, we address your questions and concerns in detail:

1. Evaluation on more language models

We evaluated our methods on gemma-2-9b-it-SimPO model (Meng et al., 2024) and the MMLU dataset with 4, 10, and 15 response options. Please see Tables 10, 11, 12, and 13 in the Appendix for the results. To aid in understanding and how they are used together, we have explicitly included Hypothesis 3 (H3). The results in this setting are consistent with our expectations and even more substantial than other settings for hypotheses H1 and H3. We discuss them below:

H1. Set size reduction with CP-OPT. In Table 10, we clearly see that CP-OPT reduces the average set size significantly while maintaining a similar coverage level. Moreover, in Tables 11, 12, and 13, CP-OPT reduces the fraction of points with larger set sizes and increases the fraction of points with smaller set sizes. For example, in Table 11, logit scores yield set size 15 for 41.7% of points, but CP-OPT reduces this to 25.96%.

H2. CROQ with logit scores improves accuracy relative to baseline. We observe small improvements in overall accuracy and significant improvements on points where logits produced smaller sets. While we expect CROQ to improve overall accuracy significantly, we find that logits have a higher proportion of points with large set sizes, meaning there is no substantial reduction in the uncertainty in a large portion of the revised questions. This explains the results on the overall accuracy. These results also highlight the unreliability of logits and how they can be a bottleneck in CROQ.

H3. CROQ with CP-OPT scores performs better than CROQ with logit scores. By design, CP-OPT scores minimize set sizes while preserving the coverage guarantee. Thus, using these scores in the CROQ procedure should lead to a large portion of questions having lower uncertainty (fewer response options) after revision, and, conditional on the correct answer appearing in the revised question, we expect LLMs to be more likely to answer correctly if there are fewer response options in the revised question. The results in Tables 11, 12, and 13 align with this expectation. We see that running CROQ with CP-OPT scores results in higher accuracy than running it with logits.

2. Choice of the score function $\mathcal{G}$ in CP-OPT

We emphasize that our CP-OPT framework for learning the score function is general and can work with any reasonable function class $\mathcal{G}$. Since CP-OPT is a post-hoc procedure, meaning it operates on an already-trained LLM, we aim to use a sufficiently flexible class $\mathcal{G}$ that is not computationally intensive to train. For our experiments, we chose 3-layer neural networks for score learning and used them consistently. We have added more details about this in Appendix B.1.

3. Notation

Thank you for noting the inconsistency in $n_t$ and $n$. The $n$ in these equations should be $n_t$. We have updated this in the paper.

4. Diminishing effect in Figure 3 (now Figure 2)

In this figure, we show results with varying coverage parameter $\alpha$. Recall that a coverage of $1-\alpha$ means that $1-\alpha$ fraction of the prediction sets from CP contains the true answer choice. As $\alpha$ increases, the coverage ensured by the CP procedure decreases, meaning that with larger $\alpha$, a larger portion of revised questions will not contain the true answer, making it less likely for the LLM to provide the correct answer.

Conversely, keeping $\alpha$ too small does not give a meaningful reduction in the noisy choices, so we do not see much improvement with smaller $\alpha$ either. In practice, this parameter can be tuned for a desired level of coverage and accuracy.

5. Extension to open-ended QA

There are a few works on using conformal prediction for LLMs in open-ended QA (e.g., Mohri et al., 2024). Extending our ideas to open-ended question answering (QA) would be an interesting direction for future work.

References

1. Meng et al., 2024, SimPO: Simple Preference Optimization with a Reference-Free Reward
   https://arxiv.org/pdf/2405.14734

2. Mohri et al., 2024, Language Models with Conformal Factuality Guarantees
   https://arxiv.org/pdf/2402.10978

I appreciate the authors response to this rebuttal discussion and providing clarifications.

The new experiments done on gemma-2-9b-it-SimPO seem promising from the results presented in Appendix Table 10-12 and seems to be in alignment with the previous hypothesis.

I would like to keep my score unchanged but am positively inclined towards acceptance.

5. CP-OPT vs logits on CROQ

The impact of CP-OPT on CROQ accuracy depends on the extent of set size reduction. To further investigate this, we conducted additional experiments specifically addressing Hypothesis 3 (H3) in the paper, which evaluates whether CROQ with CP-OPT scores outperforms CROQ with logits.

The results, as presented in Tables 11, 12, 13, 14, 17, 18, and 19, align with our expectation that CP-OPT improves accuracy when the set size reduction is substantial. For example, in TruthfulQA with 10 options, CP-OPT leads to significant gains by effectively refining uncertainty. However, in cases where the reduction in set size is minimal (e.g., Tables 4, 5, 8, 9, 15, and 16), the accuracy improvement is less pronounced. This highlights that the benefit of CP-OPT is most evident in scenarios with larger or more uncertain initial prediction sets.

Overall, we see that CP-OPT generally enhances CROQ performance, and the magnitude of improvement varies depending on dataset and task characteristics.

6. Results on TruthfulQA and MMLU in Figure 4

In Figure 4, CP-OPT leads to fewer deferrals in the TruthfulQA setting compared to logits, but in the MMLU setting, we do not see such a difference. This is due to differences in the distributions of the sets produced by these methods in the above settings. We have included histograms (distributions) of the set sizes in Figures 8(b) and 11(b) for MMLU and Truthful QA settings respectively. For a method to lead to fewer deferrals, it should have lower mass on larger set sizes and consequently higher mass on smaller set sizes. We see clear evidence for this in the TruthfulQA setting, but in the MMLU setting, the reductions on large sets are small, leading to nearly similar performance with logits on the deferral task.

References

1. Hendrycks et al., 2021, Measuring massive multitask language understanding.

2. Kumar et al., 2023, Conformal prediction with large language models for multi-choice question answering.

3. Su et al., 2024, Conformal prediction for large language models without logit-access.

4. Qu et al., 2024, Tool learning with large language models: A survey.

5. Tang et al., 2023, Toolalpaca: Generalized tool learning for language models with 3000 simulated cases.

Thank you for the detailed and constructive feedback. We appreciate your positive assessment of the paper's presentation, experiments, and contributions. Our response to the concerns is as follows:

1. On MCQ-setting

First, we emphasize that the MCQ (or finite response options) setting is a fairly broad setting that covers several use cases of interest, e.g., tool selection (Tang et al., 2023; Qu et al., 2024) and question answering (Kumar et al., 2023; Su et al., 2024). Moreover, popular benchmarks, e.g., MMLU (Hendrycks et al., 2021), to evaluate language understanding of LLMs, are based on MCQ. In general, the scenarios where LLMs have to select from a finite number of responses can be expressed as MCQs, and our framework will be directly applicable to those settings. Second, there are a few works on using conformal prediction for LLMs in open-ended QA (e.g., Mohri et al., 2024), so the ideas presented in our paper can potentially be extended to open-ended response settings. Exploring this would be an interesting direction for future work.

2. Perceived orthogonality of our methods

We agree that CP-OPT and CROQ can function independently to reduce uncertainty and improve accuracy in LLMs. However, when used together, they complement each other effectively, serving the common goal of reducing uncertainty in LLM outputs. CP-OPT refines prediction sets by minimizing their sizes while maintaining coverage guarantees, and CROQ utilizes these refined sets to reduce the number of answer options presented to the LLM, improving its performance. The motivation for integrating CP-OPT with CROQ is supported by evidence in Figure 4, which demonstrates that as prediction set size decreases (simulated using ground truth), CROQ's accuracy consistently improves.

To make this connection explicit, we have added Hypothesis 3 (H3) to the paper, which evaluates the combined effectiveness of CP-OPT and CROQ. Specifically, H3 examines whether CROQ with CP-OPT scores outperforms CROQ with logits. The hypothesis is supported by empirical results showing that CP-OPT generally leads to better accuracy in CROQ, reinforcing the complementary nature of these methodologies. While there are cases where the improvements are marginal, the overall findings underscore the advantage of using CP-OPT scores in CROQ, demonstrating their synergy in improving decision-making with LLMs.

The loose coupling between CP-OPT and CROQ is by design. CP-OPT can be used generally to reduce set sizes in conformal prediction, and CROQ can work with any score function, including CP-OPT and LLM logits.

3. Novelty

a. CP-OPT. It is designed to address the need for principled score functions in decision-making settings such as MCQs, where prior works have relied on either model logits or heuristic scores (Kumar et al., 2023; Su et al., 2024). Cherian et al., 2024, focus on factuality guarantees in open-ended generation tasks. In their setting, there is not necessarily a single correct response, so the notion of coverage is redefined around acceptability or factuality rather than correctness. In contrast, CP-OPT aims to generate the smallest possible set of response options while ensuring that the correct option is included with high probability, adhering to the coverage guarantee based on correctness.

b. CROQ. While re-querying a model might seem conceptually straightforward and there could be several heuristic strategies to prompting and re-querying, CROQ is a unique and principled framework leveraging conformal prediction (CP) to create a refined question. Since CROQ revises the question with the options in the prediction set obtained from CP, it ensures that the correct answer remains in the revised question with high probability, due to the coverage guarantee of CP, which is distribution- and model-agnostic. Our experiments show that re-querying with CROQ consistently improves accuracy.

c. Combining CP-OPT and CROQ. Together, CP-OPT and CROQ form a coherent pipeline where refined prediction sets from CP-OPT are used in CROQ to obtain a refined question. Our experiments show that running CROQ with CP-OPT is a better choice than running it with logits.

4. Uncertainties and significance of accuracies in Figure 3 (now Figure 2)

The goal of this figure is to show how CROQ reacts to variations in the coverage parameter $\alpha$. We elaborate on the differences between CP-OPT and logits in CROQ in point 5 below and refer to the added discussion on Hypothesis 3 (H3) in the updated paper. Running the CROQ procedure for all $\alpha$ is computationally demanding, so unfortunately, we cannot provide them in the rebuttal period; however, we will include them in the camera-ready version.

[Response continues in the next comment]

2. Novelty of CP-OPT

We have clarified the novelty of our work with respect to Stutz et al. (2022) and Cherian et al. (2024), both in our paper and in the previous response. We hope to clarify it further here,

The procedure in Stutz et al. (2022) is applied at training time, aiming to improve the classifier's training so that the softmax outputs are better tailored for conformal prediction. Cherian et al. (2024) (Section 3.3) extend the ideas from Stutz et al. for post-hoc learning of scores, focusing on a conditional coverage guarantee defined on factuality.

In contrast, CP-OPT performs post-hoc optimization of set sizes, subject to a marginal coverage guarantee defined on correctness. This approach is specifically designed to improve uncertainty quantification for LLMs in MCQ tasks, a gap not addressed in prior works in these settings.

Empirically, we evaluate CP-OPT across three LLMs and datasets on MCQ and tool selection tasks, with variations in the number of options. We demonstrate the efficacy of CP-OPT in reducing set sizes, improving accuracy in CROQ, and lowering the number of high-uncertainty points, thereby reducing the number of deferrals.

To the best of our knowledge, these are novel contributions towards improving UQ and the accuracy of LLMs in finite response settings such as MCQ and tool-selection tasks.

We hope our response addresses your concerns on the efficacy of CP-OPT in CROQ and the novelty of CP-OPT. We are happy to answer any further questions you may have.

Thank you for the comment. We provide clarifications on the two points that you mentioned,

1. Effectiveness of CP-OPT in CROQ

We summarize our results over all the 21 settings considered in the paper (see tables in the comment). We see in 16 (out of 21) settings, using CP-OPT leads to higher accuracy than using logits in CROQ. In 1 of the settings, we do not see improvements, and in 4, there is a slight drop in accuracy with CP-OPT. Moreover, most of the times, we see numerically larger improvements than the drop in the 4 cases. These results provide substantial evidence on the effectiveness of using CP-OPT in CROQ. The cases with a drop in accuracy are likely an artifact of the empirical procedure based on finite samples thus, if we consider the relative improvements in the range $(-1,1)$ as insignificant, we can conclude in 9/21 settings, CROQ with CP-OPT does significantly better and in other cases it performs similar to logits.

In the tables below, $a_0$= accuracy after CROQ with logit scores and $a_1$ = accuracy after CROQ with CP-OPT scores.

Results on CROQ with CP-OPT and logits (part 1 of the table)

Results on CROQ with CP-OPT and logits (part 2 of the table)

Results on CROQ with CP-OPT and logits (part 3 of the table)

2. Visualizations for set size distributions

We added histograms visualizing the set size distributions for CP-OPT and logit scores (Figures 6–13 in the Appendix). These figures show that CP-OPT consistently reduces the proportion of large sets while increasing smaller ones, aligning with its design to minimize uncertainty. This redistribution explains the observed improvements in CROQ and deferral tasks.

3. Impact of set size reduction on accuracy and motivation for CP-OPT in CROQ

We conducted an additional experiment (Figure 4) to demonstrate how reducing prediction set size improves accuracy with CROQ. Using the Truthful QA dataset with 15 response options, we generated conformal prediction sets based on logits and simulated varying levels of set size reduction by using ground truth to eliminate 0 to 10 incorrect answers while maintaining a constant coverage of 95%. The results reveal a clear trend: as more incorrect answers are removed, the LLM's accuracy after requerying consistently improves. This underscores the need of a score function like CP-OPT, which minimizes set size while preserving coverage, helping CROQ to boost accuracy.

We look forward to discussions and addressing any additional questions.