Conformal Language Modeling

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

The LTT framework might return null hyper-parameters, which might happen more often should the admissible function by the human be stricter than ROUGE

This is true, however, the opposite is also true when the human evaluation is less strict than ROUGE at a high threshold (since by the same argument, the fact that ROUGE is sensitive to exact wording agreement between the generation and the reference can also lead to it being conservative).

ROUGE was also used in the pipeline (detecting duplicate) so it's kind of "being its own judge"

Yes, ROUGE is also used in the pipeline, but this does not affect the validity of the calibration process (calibration is still computed based on similarity to the labeled answers only). In fact, we argue that having a similarity function that is directly connected to the final evaluation via transitive-like properties is a good thing. That is, if "$=$" is defined to be our similarity operator, $A$ and $B$ are two generations where $A = B$, and $C$ is the target generation, we can choose to reject either $A$ or $B$ without incurring any increased risk. Of course, ROUGE-L and other proxies don't necessarily satisfy this, which is why we must calibrate thresholds simultaneously.

What does "These thresholds are picked through manual validation" mean exactly?

The ROUGE-L thresholds for the admission functions were selected by the authors by manually inspecting a sample of random examples (~O(100)), evaluating ROUGE-L, and selecting the minimum value of ROUGE-L such that all samples with ROUGE-L greater than this threshold were acceptable. "Acceptable" in this context means that the generations were faithful and complete with respect to the perceived ground truth (which is inferred from the input and the collection of annotations available).

Of course, this inevitably includes some error, as described in the paper. Though outside the scope of this paper, uncertainty in these labels can also be incorporated though methods like those explored in Angelopoulos et. al., 2023 and Stutz et. al., 2023. What makes a generation "acceptable" can also be better codified—for example, by following methods like Nenkova and Passonneau, 2004.

In general, as described in our limitations and assumptions section, figuring out what makes a generation "acceptable" requires some careful thought and domain expertise. Still, fortunately our framework is general—and we can still bound the risk for any instantiation of $A(y)$. The design we used in this paper is illustrative, in addition to being reasonably effective in of itself.

Another potential improvement is to include a stronger baseline than first-K - for example, the duplicated responses (maybe even basing on rouge) should at least be deleted?

Thanks for the suggestion—we added a variant with rejection. Please refer to our general response.

[1] Prediction-Powered Inference. Anastasios N. Angelopoulos, Stephen Bates, Clara Fannjiang, Michael I. Jordan, Tijana Zrnic. 2023.

[2] Conformal prediction under ambiguous ground truth. David Stutz, Abhijit Guha Roy, Tatiana Matejovicova, Patricia Strachan, Ali Taylan Cemgil, Arnaud Doucet. 2023.

[3] Evaluating content selection in summarization: The pyramid method. Ani Nenkova, Rebecca J Passonneau. 2004.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

I wonder how the computational time (or relative excess samples) changes with regard to the choice of $k_\mathrm{max}$?

Increasing $k_\mathrm{max}$ will decrease the minimum achievable risk, but also increase the computational time (in the worst case). However, even with a high $k_\mathrm{max}$, one can still select a $\hat{\lambda}$ that has similar performance to a different $\lambda$ derived using a lower $k_\mathrm{max}$ (e.g., by placing a higher weight on fewer excess samples in Eq. 7).

One practical advantage of setting $k_\mathrm{max}$ to a lower value is that calibration can be faster. For example, in our implementation we first sample $n \times k_\mathrm{max}$ samples in parallel for the calibration set, and then calibrate $\lambda$ offline.

I wonder if it could be possible to treat $k_\mathrm{max}$ as a tuning parameter as well

Great suggestion! While it may still be beneficial to explicitly specify a finite upper bound (e.g., select $k_\mathrm{max} \in \mathbb{N} : k_\mathrm{max} \leq K$ for a finite upper bound $K$), it is certainly possible to also tune $k_\mathrm{max}$. In fact, the RAPS method of [1] does something very similar to this idea (where k is a hyper-parameter for improving set quality, which in this case we would also tune during calibration instead of pre-specifying). It would be interesting to explore this in future work.

[1] Uncertainty Sets for Image Classifiers using Conformal Prediction. Anastasios N. Angelopoulos, Stephen Bates, Jitendra Malik, Michael I. Jordan. 2020.

I also wonder if the $\gamma$ can be tuned jointly with the $\lambda$'s to avoid the union bound?

Yes, this is also another good suggestion! In general, we can use LTT (and more specifically Pareto Testing by Laufer et. al.) to control multiple risks simultaneously. In this case, those risks would be the coverage risk and the false positive risk. $\gamma$ and $\lambda$ can then simply be combined into one configuration, as suggested. That said, as also mentioned in our response to reviewer Sb79, decoupling set construction from component selection makes experimentation and deployment easier (for example, we don't need to redo calibration of components when picking a different $\epsilon$). We found this to be a major practical benefit.

We thank the reviewer for their careful review and thoughtful comments.

We want to first clarify one key misconception in this review: we do not use test set answers as part of our stopping rule.

The stopping rule is only calibrated using labeled examples, so that it provably generalizes to achieve risk control over future samples with high probability (again, without access to test labels). At test time we only use test labels to evaluate how well our predictions perform. Indeed, the "oracle" with 100% coverage reduces to sampling N times with knowledge of the ground truth set, and picking the first answer that is part of it. Of course this is not realistic, and only serves as a point of comparison (i.e., we measure how many "excess" samples our methods take as compared to this oracle).

We now provide answers to specific questions and remarks (quoted) below.

It's not quite clear what the objective is (minimize loss, minimize excess numbers of samples).

$\hat{\lambda}$ must provide valid risk control for $C_\lambda$ (so $\hat{\lambda} \in \Lambda_{\mathrm{valid}}$), but should also be a configuration that is useful empirically. Per our validity constraint, the upper bound of our loss is fixed. We are then left with a multi-objective problem where we want to simultaneously minimize set size (number of responses), and the wasted computational effort it takes to generate the set (excess number of samples). We reduced this to a single weighted objective (Eq. 7), with empirically chosen weights. As also indicated to reviewer Sb79, any choice of $\lambda \in \Lambda_\mathrm{valid}$ can also be used without sacrificing our risk control guarantees.

For the 3-step procedure described in section 4, is it possible this will never terminate?

This is a good question. Simply put, for finite $k_{\mathrm{max}}$, this algorithm will obviously always terminate in finite samples. If $k_{\mathrm{max}}$ is not finite (no sampling upper bound is specified), then with additional assumptions on the underlying LLM and stopping rule (e.g., that the LLM places non-zero probability mass on at least one acceptable answer, which is true for most softmax-based models), we may also show that the algorithm almost surely terminates. However, setting $k_{\mathrm{max}} < \infty$ is more straightforward, and practical.

Finally there's the evergreen concern that this approach might become less important at scale.

We agree with the reviewer that risks on an absolute level will tend to become smaller at larger model scales. That said, performance will always be a combination of the base model being used, the hardness of the task at hand, and the desired controlled risk level. This is why it is an important feature that our algorithm is general in nature, and can apply to any model that follows the specified API (i.e., supports sampling). This supports independent research in improving the underlying LM, in addition to the scoring functions used, while keeping the pipeline the same. In fact, it is great if the underlying LM is better: this will increase the range of achievable risks, and will decrease both the average size of the prediction set, and the number of samples required to generate to derive it.

As the discussion deadline is approaching, we would like to know if we have addressed your comments, or if there is anything else we can help to clarify. Thank you again for taking the time to review our work.

We thank the reviewer for their careful review and thoughtful comments. We provide answers to specific questions and remarks (quoted) below.

The paper does not explain all design choices.

Thank you for highlighting where our design choices were not well explained. We have improved the clarity of our paper with respect to these questions (as detailed below).

Proposition 4.4 is not experimentally validated.

We initially left this out for sake of space; we have now added a plot demonstrating empirical validity---see Figure G.1.

Theorem 4.2 guarantees at least one "acceptable" language model response in the prediction set but does not say much about the individual responses.

This is consistent with the style of guarantees that standard conformal inference / confidence intervals give. It is also good to keep in mind that relative rankings/confidence scores of responses in the prediction set (e.g., by using our "\mathcal{Q}" individual response quality function) can still be computed, though we just don't have formal guarantees on their individual correctness (again, the statements in Theorem 4.2 only apply to the set as a whole). Notably (and different from standard conformal prediction due to the structure of the problem we are dealing with), our component-level prediction does provide guarantees about sub-predictions relevant to individual responses, that hold simultaneously across all responses in the set.

Why is $\hat{\lambda}$ defined as in Eq. 7? Similarly, why is it desirable for $C_{\gamma}^{\mathrm{inner}}$ to be large?

$\hat{\lambda}$ is selected to provide valid risk control for $C_\lambda$ (so $\hat{\lambda} \in \Lambda_{\mathrm{valid}}$), while also being the configuration that is most useful empirically. That means, we want $C_\lambda$ to be precise (contain as few items as is necessary), and we want $C_\lambda$ to be quick to evaluate (not require sampling many responses before the stopping criterion is met). The combined objective we specify for $\hat{\lambda}$ therefore reflects a tradeoff between these two qualities. We have clarified this in the paper.

Meanwhile, $C_\gamma^{\mathrm{inner}}$ identifies the set of subcomponents that our model is very confident in, while controlling for false positives. Ideally, this would contain all correct subcomponents (i.e., we have 100% recall of correct subcomponents). Simply making $C_\gamma^{\mathrm{inner}}$ as large as possible, while subject to our constraint, helps achieve maximum recall. We have also clarified this in the paper.

What is the reason for using a different definition of $C_\gamma^{\mathrm{inner}}$ during calibration?

This decouples set construction from component selection, and makes experimentation/deployment easier (i.e., we don't need to redo component calibration for every different $epsilon$). In practice, we can do either one. We have clarified this in the paper.

The Pareto Testing procedure is used in the proposed algorithm for efficiency. However, the appendix only provides a high-level overview.

We have added a detailed description of Pareto testing to Appendix E.

The achievable risk range for MIMIC-CXR is very high. How can one reduce this for the practicality of the proposed method?

This can be reduced by either increasing $k_{\mathrm{max}}$ (which allows for more sampling effort), or by improving the underlying language model. Our calibration method applies to any base model or $k_{\mathrm{max}}$.

How is the AUC for the set loss plots greater than 0.5?

Thanks for raising this question; we realize that we did not fully explain how we compute the AUC in the paper. Specifically, we compute a normalized AUC as $\frac{1}{b - a}\int_{a}^{b} f(x) dx$, where the limits $a$ and $b$ are set to the minimum achievable epsilon and to the trivial epsilon (the risk of the top-1 prediction), respectively. This normalized AUC can be greater than 0.5. We have clarified this, and have included the values for the diagonal in the plots.

The First-$k$ scoring function does not utilize rejection.

Thanks for the suggestion—we added a variant with rejection. Please refer to our general response.

What is $k_{\mathrm{max}}$ set to in the experiments?

It is set to 20 (Appendix C). We have moved this to the main text.

The data splits to obtain the train, calibration, and test sets aren't well explained in the paper.

We have clarified these details in Appendix F.4.

Additional:

• We have switched to using $\mathcal{Y}$ throughout the paper now for simplicity. We still discuss the structure of $\mathcal{Y}$ in Section 4.1.
• Thank you for catching the typo for $A^c$! We have corrected it.
• We have added more descriptive captions to the tables in Appendix H.
• Thank you for catching the typo in Eq. 20! We have updated it to be consistent with Eq. 7.
• We have fixed the missing definitions and subscripts.