Conformal Language Modeling
Authors: Victor Quach
Adam Fisch
Tal Schuster
Adam Yala
Jae Ho Sohn
Tommi S. Jaakkola
Regina Barzilay
Venue: ICLR 2024 poster (2024)
Keywords: conformal prediction
uncertainty estimation
language models
generative models
confidence
prediction sets
sampling
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: This paper introduces a new extension of conformal prediction that is tailored towards generating provably performant generations from large language models.

Abstract: In this paper, we propose a novel approach to conformal prediction for  language models (LMs) in which we produce prediction sets with performance guarantees. LM responses are typically sampled from a predicted distribution over the large, combinatorial output space of  language. Translating this to conformal prediction, we calibrate a stopping rule for sampling LM outputs  that get added to a growing set of candidates until we are confident that the set covers at least one acceptable response. Since some samples may be low-quality, we also simultaneously calibrate a rejection rule for removing candidates from the output set to reduce noise. Similar to conformal prediction, we  can prove that the final output set obeys certain desirable distribution-free guarantees. Within these sets of candidate responses, we also show that we can also identify subsets of individual components---such as phrases or sentences---that are each independently correct (e.g., that are not ``hallucinations''), again with guarantees. Our method can be applied to any LM API that supports sampling. Furthermore, we empirically demonstrate that we can achieve many desired coverage levels within a limited number of total samples when applying our method to  multiple tasks in open-domain question answering, text summarization, and radiology report generation using different LM variants.

Published as a conference paper at ICLR 2024
CONFORMAL LANGUAGE MODELING
Victor Quach ++
Aaam Fisch'.. 1.
Tal Schuster
Adam 3,4
Jae Ho Sohn
Tommi Jaakkola'
Regina Barzilay'
CSAIL, MIT
Google Research
UC Berkeley
UCSF
ABSTRACT
In this paper, we propose novel approach to conformal prediction for language models (LMs) in which we produce prediction sets with performance guarantees. LM responses are typically sampled from a predicted distribution over the large, combinatorial output space of language. Translating this to conformal prediction, we calibrate a stopping rule for sampling LM outputs that get added to growing set of candidates until we are confident that the set covers at least one acceptable response. Since some samples may be low-quality, we also simultaneously calibrate a rejection rule for removing candidates from the output set to reduce noise. Similar to conformal prediction, we can prove that the final output set obeys certain desirable distribution- free guarantees. Within these sets of candidate responses, we also show that we can also identify subsets of individual components- such as phrases or sentences ttat are each independently correct (e.g., that are not "hallucinations"), again with guarantees. Our method can be applied to any LM API that supports sampling. Furthermore, we empirically demonstrate that we can achieve many desired coverage levels within a limited number of total samples when applying our method to multiple tasks in open- -omainn question answering, text summarization, and radiology report generation using different I.M variants.
INTRODUCTION
Language models (LMs) have emerged powerful tools for solving natural language processing (NLP) tasks. Given an input prompt, LMs generate a response from some predicted distribution over output text sequences. For modern models, these generations are often coherent and contextually relevant. At the same time, these generations can still contain mistakes, and lack certain aspects of robustness and reliability in terms of providing accurate, trustworthy predictions (Jones and Steinhardt, 2022; Krishna et al., 2021; Lin et al., 2022a; Mallen et al., 2022; Srivastava et al., 2022; Wang et al., 2023). Unfortunately, quantifying the uncertainty in LM outputs has remained a major challenge.
Conformal prediction is a popular model-agnostic and distribution-free method for creating prediction sets that contain the correct answers with high probability (Angelopoulos et al., 2023; 2021a;b Bates et al., 2020; Lei et al., 2018; Romano et al., 2019; Vovk et al., 2005). Applying conformal prediction to generative models such as LMs, however, challenging due to (a) the unbounded nature of their output space (i.e., all possible text sequences), and (b) the limited available (tractable) mechanisms for exploring all possible predictions. In particular, LMS can typically only approximately search or sample candidate responses. Furthermore, while several possible responses might be acceptable (e.g., correct or factual), small differences can result abrupt changes in coherence or meaning.
In this paper, we propose an extension of conformal prediction that is tailored specifically to generative LMs. We only assume that the (potentially black-box) LM that is given to us can be used to sample diverse output sequences, together with their evaluated model likelihoods (i.c., the output token sequence logits). Like conformal prediction, our method offers a rigorous coverage guarantee by constructing prediction sets that, in case, provably contain at least one acceptable response with high probability. Unlike conformal prediction, however, we do not enumerate the entire output space (which is impossible). Instead, derive a calibrated stopping rule for sampling different outputs from the LM that get added to growing output set of candidates, until we are confident that the
"Equal contribution. AF is Google DeepMind. Correspondence adamf i sch 50gma com.

---

Published as a conference paper at ICLR 2024
L-J Cardlomegay moderatc. There mild pulmonary
inderstiial adimss Hiar con congestion mild [-]]
Reject?
Regenerate?
Ys [.J The heart appoars mikily oniarged. There hiler congestion. There frank ederns, (-)
Cj0Ktest) = biy2s
Language Model
Reject?
AOt) -
y: [-J Mild to moderate entargement the cardias alhoustie [-]] There is no puimonary edems, ]-]]
Agg) =
yy heart is midy Tentanged The lungs are deear No Lagrn of adima [-]
Roject?
X
@ Regenenate?
Figure I: Our conformal procedure samples candidate outputs from some blackbox LM until stopping rule is reached. Each sample is added to the output conformal set if it meets both minimum estimated quality and diversity criterion. The procedure is calibrated candidate from the conformal set is admissible (A(y) 1) with high probability. In this example, samples y/1 and y/2 are in-admissible because they hallucinate the presence of "edema" (in orange) and "hilar congestion" (in magenta), respectively. The minimal output set includes ys, which is admissible.
stop when least one
output set is sufficient. Since not all samples from the LM may be high quality (e.g., some may be redundant, incoherent, have lower confidence), also simultaneously calibrate rejection rule for removing candidates from the output set-whin still ensuring that our coverage bound is not violated. This gives the benefit of making our output sets not only accurate, but also precise (i.e., small).
To more concretely describe the exact type of guarantee that we provide, suppose we have been given a calibration set Deal (X,, E X' A, I,..., n of independent and identically distributed (i.i.d.) prompts and "admission" functions (see also (Fisch et al., 2021a)). Here, Aü is binary random function that measures whether or not generation y E y for prompt X, is "good enough" (i.e., (v()) 1). Note that randomness in A; can come from implicit random covariates such as relying on a random annotated reference, Y.re to compare the candidate y to. Figure illustrates a setting where X, is an X-ray to automatically analyze and produce report for, while A; extracts individual findings from each generated report and checks if they correspond to those given by an expert radiologist. Let Xeest be new i.i.d. test prompt. Using Deal guide our choice of hyper-parameters E A, for any e, E (0, 1). our goal to generate a set of samples Cx (X C 2) that satisfies
P (P By Cx(eeet)) Areat (b)
Deal) > 1 21- 2 8.
(I)
The outer and inner probabilities are over the draws of Deal and (Xuust- Atest), respectively, e is our error tolerance, while 5 controls for the sensitivity of our algorithm with respect to calibration data.
While Eq. (1) stipulates the existence of at least one "acceptable" generation in (X ), it does not tell us much about individual responses, y E C2 (Xesss) Additionally, longer generations are often composed of multiple statements. In our radiology setting, report may contain multiple findings, such as "Cardiomegaly is moderute. There is mild pulmonary interstitial edema." " We futher identify subset of confident components that would independently be categorized being correct (given other admission function Afests this time operating over generation fragments). For example, we might predict that "Cardiomegaly moderate." is correct, but perhaps not "There is mild pulmonary inter- stitial edema." " This can not only be useful in catching incorrect statements, but can also help identify independently correct parts of larger generation, even when the overall quality of the full generation is poor. Like Eq. (I), we calibrate this process such that it gives accurate results with high probability.
Contributions. In summary, main results are as follows:
We bridge the gap between conformal prediction and LMs by calibrating the sampling of output sets, rather than enumerating and selecting candidate responses directly from the output space;
We extend multi-label conformal prediction to identify confident components of long generations;
Though limitations apply, we demonstrate valid risk control on multiple diverse tasks with different LMs, while still retaining meaningful output sets that are efficient and precise compared baselines.
2

---

Published as a conference paper at ICLR 2024
2 RELATED WORK
Conformal prediction and risk control. Our work adds to the rich collection of tools for uncertainty estimation and risk control for machine learning algorithms (Angelopoulos et al., 2023; 2021 a;; Barber et al., 2021: Bates et al., 2020; Fisch et al., 2022; Gupta et al., 2020; Lei et al., 2013; 2018; Vovk, 2002; Vovk et al., 2015; 2017, inter alia). These techniques were previously extended and applied in the language domain to classification with finitel-maany classes (Fisch et al., 202 1021abb; Jones and Steinhardt, 2022), to token-level predictions (Dey et al., 2022; Ravfogel et al., 2023), and to reliably accelerate LMs Slaufer-Goldsttiin et al., 2023; Schuster et al., 2021b; 2022b). Here, we address the emerging challenge of providing reliable prediction sets for unbounded, free-text generation-which previous methods are unequipped for. The distribution-free, finite-sample performance guarantees that we derive are similar to those given by prediction sets or regression intervals in standard conformal prediction (Angelopoulos et al., 2023: Papadopoulos et al.. 2002; Vovk et al., 2005), but with slightly relaxed "correctness" criterions (Cauchois et al., 2022; Fisch et al., 2021a). In particular, we build on the groundwork set by Angelopoulos et al. (2021a), which provides general methodology for calibrating any risk function that is controllable via some low-dimensional hyper-parameter configuration. We extend their framework to handle sampling-base can effectively be used for LMs, and that, critically, do not require enumerating the full output space (which is intractable in our case). Most relevant to our work in LMs, other recent approaches have built on conformal principles to construct confidence intervals for generative diffusion models over images (Horwitz and Hoshen, 2022; Teneggi et al., 2023). These methods do not directly translate to LMs, however, as they only provide non-combinatorial confidence intervals at the pixel-level.
algorithms that
Uncertainty estimation in LMs. As the use of LMs in-the-wild quickly grows, there is increasing interest in obtaining and expressing meaningful confidence estimates for each output. Recent studies show that the logits of out-of-the-box LMs tend to exhibit overconfidence, even when wrong (Desai and Durrett, 2020; Kadavath et al., 2022; Miao et al., 2021; Vasconcelos et al., 2023). Recent alignment techniques degrade this even further (Kadavath et al., 2022; OpenAI, 2023). Most current mitigation approaches focus on introducing linguistic cues (Lin et al., 2022b; Zhou al., 2023) or post-hoc logit calibration (Jiang et al., 2021: Kadavath et al., 2022; Mielke et al., 2022; Zablotskaia et al., 2023). this work, we develop similar techniques to improve the output of the underlying LM. Our methods are model agnostic and provide rigorous guarantees. Our conformal component selection ($4.4) also relates to recent self-consistency work that builds on the empirical observation that repeated similar samples are more likely to be correct (Mitchell et al., 2022; Wang et al., 2023), and cross-sample entailment can approximate uncertainty (Kuhn et al., 2023). Unlike previous work that uses fixed number of re-samples and compares full outputs, we (a) introduce dynamic stopping rule to reduce the number of samples, (b) extend this concept to semantically compare sub-components of long text outputs, and (c) conformalize the process provide formal guarantees.
Reliable generation. It is common practice to post-hoc apply classifiers and filters on top of LM generations for various quality goals such as preventing toxicity (Gehman et al., 2020; Rauh et al., 2022: Welbl et al., 2021), verifying grounding against sources (Bohnet et al., 2023; Liu et al., 2023; Yue al., 2023). or re-ranking the set of decoded outputs (Jiang et al., 2022). Our work provides systematic and reliable approach for filtering or flagging poor-quality outputs- both at a full generation and component level-and can also readily incorporate additional signal from auxiliary classifiers. For example, we demonstrate in our experiments using off-the-shelf natural language inference (NLI) models (Bowman et al., 2015; Khot et al., 2018; Schuster et al., 202 la; Thore et al., 2018; Williams et al., 2018; Zhang et al., 2019) to help guide the selection of individual, confident components in text summarization (i.c., sentences that are fully entailed by the larger text (Fabbri et al., 2022; Honovich et al., 2022; Laban et al., 2022; Schuster et al., 2022a)).
3 BACKGROUND
We begin with a review of conformal prediction and risk control (see also (Angelopoulos and Bates, 2022)). We use upper-case letters (X) to denote random variables; lower-case letters (x) to denote constants, and script letters (X') to denote sets, unless otherwise specified. Proofs are in Appendix D.
Given new example x, for every candidate label y 3 standard conformal prediction either accepts or rejects the null hypothesis that the pairing (a. y) is correct. The test statistic for this test is a nonconformity measure, M((x, v), D), where D is a dataset of labeled examples. Informally,
3

---

Published as a conference paper at ICLR 2024
lower value of MM reflects that point (z,, y) "conforms" to D, whereas higher value of M reflects that (z, y) does not. For example, a practical choice for M could be the model-based negative log likelihood, - log Po (y æ), where A are parameters fit to D. Split conformal prediction (Papadopoulos, 2008) uses a separate training set Drrain to learn a fixed M that is not modified during calibration or prediction. To construct prediction set for the new test point x; the conformal classifier outputs all for which the null hypothesis (that pairing (z, y) is correct) is not rejected. This is achieved by comparing the scores of the test candidate pairs the scores computed over n calibration examples.
Theorem 3.1 (Split conformal prediction (Papadopoulos, 2008; Vovk et al., 2005)), Let (X,, Y;), i i= L,..... + 1 be exchangeable random variables. Let random variable V = (X,,, Y,) be the nonconformity score of (X,, Yi). where M is fixed. For E E (0, 1). define the prediction (based on the first n examples) al x X
C,(x) == {y E y: M(x. v) S Quantile(1 - e; Vin U {0o1)}
(2)
Then P(Y,+1 (((+))))) 2 c.
Note that the coverage expressed in Theorem 3.1 is marginal over the draw of calibration and test data. The recent Learn Then Test (LTT) framework of Angelopoulos et al. (2021a) extends conformal prediction to control the expectation of any loss function (conditional on the draw of calibration data) by reframing hyper-parameter selection as multiple hypothesis testing problem.
Specifically, let L + IR be any random function using a hyper-parameter configuration À in some space A. For example, we might have L(A) {(X, Y; A) for some fixed loss function & with random inputs (X, Y). Unlike conformal prediction, however, can be multi-dimensional (e.g., consist of multiple thresholds). Let L,, i = ,...., be an i.i.d. calibration set Deal of random functions, and Liest a random test function. Let E IR be a tolerance for the test risk, Liest (A) S e. LTT then iden- tifies random (depending on Deat) subset of parameters, Avalid C A, with the goal of guaranteeing
IP
sup AgAvali
I[[Lust (A) | Deal] S
2 1 1
where the outer probability is over the draw of Deal. and the inner expectation is over draws of Lreat This then implies that any X E Avalid can be selected to control the risk of Lreat. In short, this is achieved by associating the null hypothesis HA: [E [A)] > to each X E A. For each null hypothesis, we then use the calibration set to compute super-uniform p-value PA using concentration inequalities. Any multiple testing algorithm Tpx X E A) that controls the family- wwse error rate (FWER) can then be used to identify the subset of non-rejected X, i.e. Avalia.' Note that it is possible that Avalid = Ø, in the case that we fail to identify any statistically valid solutions (and the desired risk may not even be achievable with any A). In this situation, set À null, and either reject the task, or provide a trivial solution (c.g., a classifier that provides all possible labels )).
Theorem 3.2 (Learn Then Test (Angelopoulos et al., 2021a)). Suppose px is super-uniform under HA for all X. Let T be any FWER contocongoolling algorithm at level 8. Then Avalid satisfies Eq. (3).
Defining (x)x) == {y E y: M(z, v) S A and L(A) := 1(Y & Cx(X)) recovers a crite- rion similar to that of conformal prediction (though not marginal over Deat). Unfortunately, in either instantiation (LTT vs. conformal prediction) iterating over E y is intractable for LMs, regardless of whatever calibration technique is ultimately used. Instead, in $4, introduce our method for generating uncertainty sets by casting À as configuration of sampling algorithm, rather than a filter on the output space y. We then show that this randomized algorithm can still be calibrated with LTT.
4 CONFORMAL LANGUAGE MODELING
We now introduce our method for generating uncertainty sets for LMs. At a high level, our procedure consists of three main steps to sample and return an collection of plausible output predictions:
1. Sample. new candidate response y is sampled from our language model.
'A FWER FWER-controlinng algorithm at level 5 is any procedure that accepts or rejects null hypotheses Hy, while ensuring that the probability of falsely rejecting any HA. AA E A, is less than 8.
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Conformal sampling with rejection
Definitions:
is an input prompt, FF is our set-based confidence function, S is our text similarity function, 2 is our sample quality estimator, À is our threshold configuration, and kimax is our sampling budget. po(y 2)) is the conditional output distribution defined by our language model.
1: function SAMPLE(2, J, S, 2, X, maxx
2: CA x 0
b Initialize empty output set.
3: for = 1,,,.... kmax do
4:
1/k. 1-=- (y x).
Sample new response. > Reject if its estimated quality is too low.
5:
if Q(xx y/) < 22 then
6:
continue
7:
if max (max(S(yx: us): Us E EC,) > A then continue
D Reject it is too similar to other samples.
8:
9:
CA = Cx if F((x) 2 A3 then
> Add the new response to the output set. D Check we are confident enough stop.
1I:
break
12: return Cx
Accept or reject. The sample y is added to the growing output set, as long as it is diverse (e.g.. maximum overlap with any other element is S A1) and confident (e.g., the LM likelihood is 2 A2).
3. Stop or repeat. Using a set-based scoring function, we check if the confidence in the current set is 2 A3. it is, then we stop and return the current set. Otherwise we return to Step 1.
= (Ai, 22 >g) is a configuration that we calibrate to find a valid setting, A = (A,, 22 Ag), that controls the risk of our output sets. In the following, we more carefully define our setting and notation 164.1), and then describe our sampling ($4.2) and calibration algorithms (84.3). Then, in $4.4, we provide an additional extension for highlighting confident generation components iee. subsections of our full generations that are independently likely to be correct, even if the full generation is not.
4.1 FORMAL SETTING AND NOTATION
Let V be an alphabet (a non-empty, finite set of tokens such as ("aa", "c","c...... from which all possible output strings, y. are composed, i.e. y := U V". We assume that we are given a generative model po x) that defines a conditional probability distribution given some input prompt E X which we can sample from to obtain output strings, poly x). Following Fisch et al. (2021a), for every input prompt x, we also further assume access to some "admission" function A: y + {0, 1} that is used to measure the acceptability of given sample y. Intuitively, A tells us if an output is "good enough". We explore different tasks and admission functions in our experiments in $5. See Appendix A for extended discussion of this setting and its assumptions. Given sampled calibration set Deat, our goal is then to derive a configurable algorithm with input parameters for constructing a prediction CA that we can calibrate satisfy Eq. (1). In the framework of LTT (refer to $3), this is equivalent to defining (((A) = 165y E (X.): Ac(y) = 1}, and using Deat to find a value Å such that L (Å) S with probability at least - 5 over the draw of Deal-
A
4.2 CONFORMAL SAMPLING WITH REJECTION
Let F; 23 HR be set-based function that, for any set C E 2", gives set confidence score for the event 1{3y E: Aly) = 1). F should not depend on Deal- Furthermore, let S: y ) + R be text-based similarity function (e.g., BLEU or ROUGE) that we use detect duplicates and preserve measure of an individual
diversity in C, and @: X x ) - IR an conutttondiiinall response's quality- suchlity-suchaae as the LM's likelihood function, po(y 2).. We define and test different instances of these functions in $5.2. We then adopt a sampling- based procedure that grows an output set, C1 C C2 C ... C by repeatedly taking samples yk po x:), and updating
Ck-1UP (vk)
if max 3j): My E Cc-1) $ d
C₁ =
and Q(x, yb)) 2 X2. otherwise.
(4)
Ck-1
5

---

Published as a conference paper at ICLR 2024
until the confidence after k samples, F(Cx), 2 A (or some sampling budget kmax is reached).
As an intuitive, but toy, example, suppose we modeled ys: ~ py z), k = 1, as Bernoulli process, where each ye has the same probability of success p that we assumee (albeit unrealistically) that we know. For Xiest "success" is determined by the admission function, Atest The confidence that our current set Cş contains at least admissible answer (without rejection) then follows ge- ometric distribution, Gco(p): all that remains is to compute the minimum number of samples to take such that Eq. (1) satisfied. This achieved by taking F(Cx) = k and Xa [log(e)/ log(1 p)].
Of course, in reality we do not know the probability of success p for test examples. Furthermore, the samples ys are not independent, and since
also able observe their values, better strategies 1. Therefore, we allow JF to be any set-based function-
may exist to conditionally estimate Ayyx) that we also pair with similarity function S, and sample quality function 2, for handling rejections. Pseudocode is given in Algorithm 1. We derive, calibrate, and test different variations of F, and Q in $5 and $6, respectively. Using À (A1, A2, As), we write (Xess) to denote the final output set.
4.3 CALIBRATION WITH LEARN THEN TEST
Let A be finite set of configurations. For example, if searching for a value of X = (A1, As) [0, 1]3 we might consider the evenly-spaced set A = { i I.....K}* ,*3 for some finite x E N. For each À E A, LTT then requires computing valid p-value Px where px is super-uniform random variable under Hx. Here, we can obtain valid p-values from the empirical risk on Deal,
R = 1 Σ L((A), where L((A) = 1f E Cx(,)) A.))) = 1])
(5)
Lemma 4.1 (Binomial tail bound p-values). Let (A) be the empirical risk in Eq. (5), and let Binom(n, e) denote a binomial random variable with sample size n and success probability e. Then
BT = P(Binom((ne)) S nnRx())) PX
(6)
valid p-value for Hx: [aast (A) >6
When paired with any selecting all configurations for hypotheses HA that are rejected by T À E A). If Avalid is empty, then we abstain (i.e., return null). Otherwise, we are free to use any configuration in Avalid- We then select the one that empirically minimizes weighted combination of the average final set size (after rejection) as well as the relative number of "excess" samples taken from our model (i.c., how many extra samples our algorithm takes after the first admissible answer has already been surfaced, proportional to the total number of samples). Specifically, let Sx(x) be the total number of samples taken, S* (2: be the oracle sample index j of the first admissible generation (where A(y;) = 1), and Cx (x) be the final prediction set. Then, reusing Deat, we take
algorithm T at level we obtain the set Avalid S A by
1 (x)Cs(X))1 P2
(Sx(X.) - -Xx())]+++
Å = argmin XEAustid
SA(X,)
where ,1, P2 R220 are hyper-parameters and [+] - max(:;
0). We choose P1 = P22 0.5. As con- sequence of LTT, the chosen À (which is a random variable that depends on Doat) is risk-controlling.
Theorem 4.2 (Sampling-ae based LTT). Let & be defined according to Eg. (7). Then the prediction C₁ (Xtest) computed by Algorithm I satisfies Eq. (1).
Remark 4.3. Given a finite kmax. Algorithm is guaranteed to terminate. Smaller kimax will, however, shrink the range of achievable (i.e.. with À & null). See Appendix C for additional discussion.
To efficiently search and test the higher dimensional x (A1, Xg Ag). we use the Pareto Testing proce- et al. (2023). Pareto Testing exploits structure in A by first using propor-
dure from tion Deat to find A's Pareto-optimal frontier, and then iteratively validates promising configurations using Fixed Sequence Testing (Holm, 1979) the remaining calibration data. See Appendix E.

---

Published as a conference paper at ICLR 2024
Algorithm 2 Conformal component selection
Definitions: Cx is prediction set, & is an algorithm for splitting candidates y into components, F is a confidence estimator for individual components, is our threshold configuration.
1: function SELECT(CA, F,,
2: Cinner (
Di Initialize an empty output set. D Iterate over full predictions.
3: for CC do
4: for e E E(y) do
P Iterate over individual components.
6: if (e) 2 then Cinner
5:
City
{e}
Keep only high-confidence components.
?
Cinner 7: return Cy
4.4 CONFORMAL SELECTION OF INDIVIDUAL COMPONENTS
caveat of language generation is that LM responses can be verbose, and composed of multiple components. We consider a "component" to be a logically defined subpart of a larger response, such as series of phrases or propositions. For example, a radiology report like "The heart mildly enlarged. The lungs are clear." can be broken down into two findings: "The heart is mildly enlarged." " and "The lungs are clear." While Theorem 4.2 guarantees that complete, admissible generations do exist within our prediction sets, we cannot use it to make statements about the relative reliability of individual components within each response contained within that prediction set. Let E: y + 2n be deterministic function that takes text string and breaks it down into components. We implement to be a simple sentence splitter. For every input I, we assume access to some component-ban based admission function A y - {0, 1} that is used to judge individual components for correctness. For example, A may check if e is entailed by another component e' E E where yoe is a human reference. Let Fc; score for the event (e) = 1. We then define the subset of components Cinner C 2 as
R be function that, for component
Y, gives a confidence
Cinner (x) =
={{E (EE U
(7)
(8)
yECx(*)
Using Deal, seek calibrate 7 r, such that for test pair (Xtest, Abost) and a, 6 E (0,1),
P ((P( (4 (c) = 1, Ve E Ci (Xuest) Deal) 1 21 21-5.
The outer and inner probabilities are over the draws of Deal and (Xust, Afest) respectively. The new parameter a can be interpreted as the maximum rate of making any false positive predictions in which we select component that not fact acceptable. Like Cx, we calibrate Ciuner using L.TT, but seek to make Cinner as large as possible, in order to maximize recall of correct components. Concretely, let T2(7) = (3e E Cianer: (e(e) 0) and let r valid be the set of non-rejected configurations found by LTT (again using binomial tail p-values). During calibration define Cinner (X;) using an upper bound to C2 (X,), by simply taking the first kmax samples, {B1,.... Minas }. This will allow to conveniently decouple component calibration from set calibration. We then use the configuration that empirically maximizes the average number of confident components (where we again reuse Deat):
4 argmax TET valid
Σ (X,))
(10)
12
Proposition 4.4 (Component- LTT), Let be defined according Eq. (10), where C, (X,, uses Cx(), = (yr..... Memaa Y during calibration. Then the prediction set of components, Cs (Xtest) computed by Algorithm 2 paired with any Cx at test time with sup,, Cx(x)) < kmax satisfies Eq. (9).
By the union bound, Eq. (1) and Eq. (9) hold simultaneously with probability 1-28 28.
5 EXPERIMENTAL SETUP
In this section, we briefly describe our experimental setup, including tasks, scoring functions, and metrics. We set kmax 20 for all experiments. See Appendix F for additional task and model details.
7

---

Published as a conference paper at ICLR 2024
5.1 TASKS
Radiology report generation. As motivated in $1, we apply our method to chest X-ray radiology report generation using the MIMIC-CXR (Johnson et al., 2019) dataset. For our LM, we fine-tume an encoder-decoder architecture based on a pretrained ViT (Dosovitskiy et al., 2021) 1) image encoder and GPT2-small (Radford et al., 2019) text decoder. To judge admission, we
the popular Clinical Efficacy metric (Liu et al., 2019; Nicolson et al., 2022) to check if the 14 labels predicted by an auxiliary CheXbert (Smit et al., 2020) model on the generated report exactly match the labels predicted by the same CheXbert model for a reference report from a radiologist. Similarly, a component (here sentence including a finding) is defined to be admissible if it has ROUGE-L (Lin, 2004) score 2 0.4 (picked empirically), when compared to any component directly extracted from the reference.
News summarization. We also apply our method news article text summarization using the CNN/DM (Hermann et al., 2015) dataset. For our LMM, we finetune a T5-XI. (Raffel et al., 2020) model. We define a candidate generation to be admissible if has a ROUGE-I. L, score 2 0.35, when compared to all available reference summaries from human annotators. Like MIMIX-CXS define a component to be admissible if has a ROUGE- L score 2 0.4 when compared to components extracted from human summaries. These thresholds are picked through manual validation.
Open-domain question answering. Finally, we apply our method to open-domain QA using the TriviaQA (Joshi et al., 2017) dataset. Here sample answers from LLaMA- 13B (Touvron et al., 2023) in the few-shot setting (A = 32), without any additional fine-tuning. Since answers are limited one or few tokens, candidate output generation is acceptable only if exactly matches an annotated reference answer (after removing articles, casing, and punctuation). Furthermore, since the expected answers are short and fairly atomic, we do not evaluate component-level confidence for this dataset.
5.2 SCORING FUNCTIONS
Our method can support different quality functions Q, similarity functions S, and set scoring functions F. We show that a straightforward approach is to simply use transformations on the model likelihoods (from token logits). We define Q(I, y) = (y x) using the likelihood function of the base LM, with length- normaliaaomliiiiinn (Wu et al., 2016). We use ROUGE-L for S. For F, we experiment with:
FIRST-K. K. As baseline, corresponds to the number of samples taken, and follows the intuition from our toy example in $4.2.
by its size, (FR IC], and do not use rejection. This
FIRJT-K+REJECT. This variant uses our duplicate rejection component ($4.2), but like FIRST-K. K. scores set by the total number of samples taken so far (where the number of samples is now 2 [C]).
MAX. The FMAx scoring function stems from the intuition that a set is only as good as its best clement, and defines (C) = max Q(y): y E C).
SUM. Alternatively, we also the sum of item-level scores: (C) = Eyec Q(v).
5.3 METRICS
Our main motivation is to produce valid confidence sets that are also precise. To reflect this, we measure both the loss of our sets (which is guaranteed to satisfy our prescribed limits), as well as both (a) the relative number of "excess" samples taken from our model (including rejected samples, see also Eq. (7)), and (b) the ultimate output size of the prediction set (after rejection). Both metrics are important, as over-sanpling wastes computation (or expensive API calls), while large output sets can be unwieldy to and overall less helpful as an uncertainty quantification tool. We measure results and compute the normalized AUC over the range of achievable or a (using a fixed 0.05), excluding trivial values (e.g., that policy that always returns the first generation would satisfy).
6 EXPERIMENTAL RESULTS
We now present our main results. In all plots, solid lines give the mean over 100 trials and shaded re- gions show +/- the standard deviation. Additional experimental results are reported in Appendix G.
SSpecifically, we compute AUC(f: a, -in St [e)dee where (a, b] the range of evaluated e (or o).
8

---

Published as a conference paper at ICLR 2024
(0,05)
0.80
rejees (0.04)
0150
0.78
Sum
daggnnll
diagonal
Sett
0.30
0.00
0.20
0.25
0.33
0.00
0.0
0.75
0.00
0.00
0.30
0:35
0.00
0.15
0.20
0.25
0.30
0:33
Hikk Level
Risk Level (d)
Risk Level (c)
0.35
0.30
FiSE (0.15)
Fint reject in 18
Rolackve Excess Samples
reject
023-
Sam (D.32)
Max 12)
020
0.4
0.35
0.00
Nelecvve
frrt K.t..ol K.04411
Arrtt - reject (D:41)
0.-
0.65
0.00
0.80
8.70
0.75
0.85
0.1
Vwc (0-23
Sum (0.
6:50
0.0
0.15
0.30
0:35
0.0
Hist (0.50)
Hist reject 10
Frost K0 22)
Fisst K reject 10 231
Firt K reject 10 07)
First i 211
Nax 0..33
Max 201
Max (o 1.0
0.0
5.m 10.30 32
Sum 10 20.20)
Sun 10.00
Sine:
0.4
0.4
0.-
02-
0.33
0.00
2.05
0.70
0.75
3.50
0.85
0.25
0.30
0.35
0.40
3.35
0.20
0.23
0:30
0.33
Risk Level (c)
Risc Level lo
Risk Level
(a) MIMIC-CXR
(b) CNN/DM
(c) TriviaQA
Figure 2: Conformal sampling results for Cx a function of E. We report the loss, relative excess samples, and overall size (normalized by kmax). We also report the AUC over achieved/non-triie e.
Validity of conformal sampling with rejection. We demonstrate in Figure 2 that our conformal sam- pling approach matches our theory in practice, as the average set loss often matches but never exceeds the target risk level. Methods that have access to the model logits (MAX, SUM, TIRRST---RJJEAE are close to, but still below, the diagonal line, indicating that they are valid, but not conservative.
Prediction efficiency. The likelihood- based approaches outperform the uniform FIRST-K K baseline across all three tasks. For example, as Figure 2c shows, the AUC of expected set size of MAX and SUM are both less than half the AUC of FIRST-K K in the QA task. In tasks with longer output texts, FIRST-K K produces competitive set sizes across all achievable c. However, on the relative number of excess samples metric, the MAX scoring function largely outperforms SUM and FIRST-K. achieves similar size efficiency to the other rejection algorithms, but still lacks sampling efficiency.
Individual components. We evaluate two scoring functions Fe for conformal component selection. SPAN-LOGITS extracts the likelihood of a component using the hase language model. However, as that likelihood is also conditioned on previous context, it may underestimate the score of a correct component that follows an incorrect component. We therefore also test an application-specific RANDOM baseline
CLASSIFIER to assign a conformity score to each component. We compare which attributes a random score to any (zz e) pair. Figure G.1 shows that by modeling components independently, we produce better (larger) sets. We include additional results Appendix G and H.
7 CONCLUSION
Reliably using language models (LMs) in real-world tasks inevitably requires meaningful uncertainty quantification. this paper, we introduced an approach to conformal prediction that allows user to sample prediction sets from generative LMs with infinite, combinatorial output spaces, while retaining desirable statistical guarantees. Our method bridges the gap between standard conformal prediction and LM inference by calibrating a stopping rule for algorithm that iteratively grows an output prediction set by sampling new generations (with rejection). Moreover, we can separately identify confident answer subcomponents. This can help users better understand the quality of long responses, which often include both correct and incorrect aspects. Empirically, we demonstrated that can obtain efficient prediction sets, both in terms of size and total required samples.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
Code is available at https: //ghttttss.. com camp://aaall/ccotoooaaaaaaaaaeee
The codebase includes implementations of Algorithms 1 and 2. pre-processing code for tasks, and functions for computing the metrics and producing all our plots and tables. In Section 5 and Ap- pendix F we descrihe in detail all the datasets, language models, and scoring and admission functions we used, with references to downloading the public data and models, and all our
REFERENCES
Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction conformal prediction and distribution-free uncertainty quantification, 2022.
Anastasios N. Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control, 2023.
Anastasios Nikolas Angelopoulos, Stephen Bates, Emmanuel Candès, Michael I. Jordan, and Lihua Lei. Learn then test: Calibrating predictive algorithms to achieve risk control. ArXiv preprint: 2110.01052, 202
Anastasios Nikolas Angelopoulos, Stephen Bates, Jitendra Malik, and Michael Jordan. Uncertainty sets for image classifiers using conformal prediction. In International Conference Learning Representations (ICLR), 2021b.
Rina Foygel Barber, Emmanuel J Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507, 2021.
Stephen Bates, Anastasios Nikolas Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution free, risk controlling prediction sets. ArXiv preprint: 2101.02703, 2020.
Bernd Bohnet, Vinh Q. Tran, Pat Verga, Roee Aharoni, Daniel Andor, Livio Baldini Soares, Massimil- iano Ciaramita, Jacob Eisenstein, Kuzman Ganchev, Jonathan Herzig, Kai Hui, Tom Kwiatkowski, Ji Ma, Jianmo Ni, Lierni Sestorain Saralegui, Tal Schuster, William W. Cohen, Michael Collins, Dipanjan Das, Donald Metzler, Slav Petrov, and Kellie Webster. Attributed question answering: Evaluation and modeling for attributed large language models, 2023.
Samuel R. Bowman, Gabor Angeli, Christopher Potts, and Christopher D. Manning. large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 632 642, Lisbon, Portugal, September 2015. Association for Computational Linguistics. doi: 10. 1..1865//1/D15-1077 URL https: //aclantho 1 wwwhhhoooooogoogoo.oooo wtt//15-111111
Maxime Cauchois, Suyash Gupta, Alnur Ali, and John Duchi. Predictive inference with weak supervision, 2022.
Shrey Desai and Greg Durrett. Calibration of pre-trained transformers. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 295-302, Online, November 2020. Association for Computational Linguisties. doi: 10.18653/v1/200 emnlp-main.21, URL https: /taps//acaaatttota aaclanthology orgg 2rgg22020.0m emn monll-mmiie mamin... 21.
Neil Dey, Jing Ding, Jack Ferrell, Carolina Kapper, Maxwell Lovig, Emiliano Planchon, and Jonathan P. Williams. Conformal prediction for text infilling and part-of-speech prediction. The New England Journal of Statistics in Data Science, 1(1):69-8) 83, 2022. ISSN 2693-7166. doi: (0.51387/22-NEISDSS.
Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2021.
10

---

Published as a conference paper at ICLR 2024
Alexander Fabbri, Chien-Sheng Wu, Wenhao Liu, and Caiming Xiong. QAFactEval: Improved QA- based factual consistency evaluation for summarization. In Proceedings of the 2022 Conference of the North American Chapter the Association for Computational Linguisties: Human Language Technologies, pages 2587-2601, Seattle, United States, July 2022. Association for Computational Linguistics. doi: 10. http:///.222222mmaaiiia 187. URL https: aaccc anthology, org/ 2022. naacl
Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Efficient conformal prediction via cascaded inference with expanded admission. In International Conference Learning Representations (ICLR), 2021a.
Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Few-shot conformal prediction with auxiliary tasks. In International Conference on Machine Learning (ICML), 2021b.
Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay. Conformal prediction sets with limited false positives. In International Conference on Machine Learning (ICML). 2022.
Samuel Gehman, Suchin Gururangan, Maarten Sap, Yejin Choi, and Noah A. Smith. RealTox- icityPrompts: Evaluating neural toxic degeneration in language models. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3356-3369, Online, November 2020, Association for Computational Linguisties. doi: 20.18633/112020
http:///////20..ninnnggem/////// findings-emnlp.301.. URL https::///// /tttps::/aclae http///aaaaattttooce/ee htwpsooogooorrooooooooooo 2020 findings-emnlp... 301.
Chirag Gupta, Aleksandr Podkopaev, and Aaditya Ramdas. Distribution-free binary classification: prediction sets, confidence intervals and calibration. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Su- leyman, and Phil Blunsom. Teaching machines to read and comprehend. In C. Cortes, N. Lawrence D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28, Curran Associates, Inc., 2015. URL https: /ptp//eeeocccecepee/eeeepee neurips. cc/ http://///..eeeeeeeeeeeeeooeeoe/ 474 Fd0f399-Paaarrrrrrer.roo paper.pdf.
Sture Holm. A simple sequentially rejective multiple test procedure. Scandinavian journal of statistics, pages 65-70, 1979.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. International Conference on Learning Representations (ICLR), 2020.
Or Honovich, Roee Aharoni, Jonathan Herzig. Hagai Taitelbaum, Doron Kukliansy, Vered Cohen, Thomas Scialom, Idan Szpektor, Avinatan Hassidim, and Yossi Matias. TRUE: Re-evaluating factual consistency evaluation. In Proceedings of the Second DialDoc Workshop on Document- grounded Dialogue and Conversational Question Answering, pages 161-175, Dublin, Ireland, May 2022. Association for Computational Linguistics. doi: 1111166/1112222.iaaei org/ 2022 dialdoc-1.19,
1.19. URL
https: http:///alaahthhhcccoo
Eliahu Horwitz and Yedid Hoshen. Conffusion: Confidence intervals for diffusion models. 2022.
Dongfu Jiang, Bill Yuchen Lin, and Xiang Ren. Pairreranker: Pairwise reranking for natural language generation, 2022.
Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How know when language models know? on the calibration of language models for question answering. Transactions of the Association for Computational Linguistics, 9:962 977, 2021. doi: 10.1162/tacl a0007 URL https: http:///aaaaaahhhaaeo wwtp:/rggg.//// t.cl-1..1
Alistair EW Johnson, Tom Pollard, Nathaniel R Greenbaum, Matthew Lungren, Chih-ying Deng, Yifan Peng, Zhiyong Lu, Roger G Mark, Seth Berkowitz, and Steven Horn. Mimic-cxr-jpg, large publicly available database of labeled chest radiographs. arXiv preprint arXiv:1901.07042. 2019.
11

---

Published as a conference paper at ICLR 2024
Erik Jones and Jacob Steinhardt. Capturing failures of large language models via human cognitive biases. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. http: http::/pp///ppeeeie..... http:/viiiweeefft...t.aee
Ld=fc09Cgn-X- R-R..
Mandar Joshi, Eunsol Choi, Daniel S. Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension, 2017.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, Scott Johnston, Sheer El-Showk, Andy Jones, Nelson Elhage, Tristan Hume, Anna Chen, Yuntao Bai, Sam Bowman, Stanislav Fort, Deep Ganguli, Danny Hernandez, Josh Jacobson, Jackson Kernion, Shauna Kravec, Liane Lovitt, Kamal Ndousse, Catherine Olsson, Sam Ringer, Dario Amodei, Tom Brown, Jack Clark, Nicholas Joseph, Ben Mann, Sam McCandlish, Chris Olah, and Jared Kaplan. Language models (mostly) know what they know. 2022.
Tushar Khot, Ashish Sabharwal, and Peter Clark. Scitail: A textual entailment dataset from science question answering. In AAAI Conference on Artificial Intelligence, 2018.
Kalpesh Krishna, Aurko Roy, and Mohit lyyer. Hurdles to progress in long-form question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computaaionnl Linguistics: Human Language Technologies, pages 4940-4957, Online, June 2021. Association for Computational Linguistics. doi: 10.18653/v1/200 https: htt////aaaaatlooo/o//e/o org/ nwacl-aalnnnmmm ma iiaiini.. 393.
htw.////....aallll... main.393. URL
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation. In The Eleventh International Confer- ence on Learning Representations, 2023. URL httt:::://peerevieww wwt.ilewwweee/eeeeeeme seee/forume forumiide VD-AYtPOdve.
Philippe Laban, Tobias Schnabel, Paul N. Bennett, and Marti A. Hearst. SummaC: Re-visiting NLI-based models for inconsistency detection in summarization. Transactions of the Association for Computational Linguistics, 10:163-177, 2022. doi: 10.1162/tacl a_00553. URL https: // faclanthology.... org/ tac1-1.10.
Bracha Goader--oldshtein, Adam Fisch, Regina Barzilay, and Tommi S. Jaakkola. Efficiently controlling multiple risks with pareto testing. In The Eleventh International Conference Learning Representations, 2023. URL http::tt///// /ttttps://ppereeiiiie
net/ forum? wtte://oooommmmoooee/ee id==cggYX___y_3
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):27--887, 2013.
Jing Lei, Max Gelll, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113(523); 1094-1111, 2018.
Chin-Yes Yew Lin. ROUGE: A package for automatic evaluation of summaries. Text Summariza- tion Branches Out, pages 74-81, Barcelona, Spain, July 2004. Association for Computational Linguistics. URL https::////. aalllannhhogggg wwgg..rrg//w.. wwt///0-1100000
Stephanie Lin, Jacob Hilton, and Owain Evans. TruthfulQA: Measuring how models mimic human falsehoods. In Proceedings of the 60th Annual Meeting of the Association for Com- putational Linguistics (Volume 1: Long Papers), pages 3214-3252, Dublin, Ireland, May 2022a. Association for Computational Linguistics. doi: 10. 1116:///1/2222..cllloog....22.2 URL https: / /acl antho wontnhhhoooyy...ooooo..o log org/
22.9. Stephanie C. Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. ArXiv, abs/2205. 14334, 2022b.
Guanxiong Liu, Tzu-Ming Harry Hsu, Matthew McDermott, Willie Boag, Wei-Hung Weng, Peter Szolovits, and Marzyeh Ghassemi. Clinically accurate chest x-ray report generation. In Machine Learning for Healthcare Conference, pages 249-269. PMLR, 2019.
12

---

Published as a conference paper at ICLR 2024
Nelson F. Liu, Tianyi Zhang, and Percy Liang. Evaluating verifiability in generative search engines, 2023.
Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Hannaneh Hajishirzi, and Daniel Khashabi. When not to trust language models: investigating effectiveness and limitations of parametric and non-parametric memories. arXiv preprint, 2022.
Mengqi Miao, Fandong Meng, Yijin Liu, Xiao- Zhou, and Jie Zhou. Prevent the language model from being overconfident in neural machine translation. 2021.
Sabrina J. Mielke, Arthur Szlam, Emily Dinan, and Y-Lan Boureau, Reducing conversational agents' overconfidence through linguistic calibration. Transactions of the Association for Computational Linguistics, 10:857-872, 2022. doi: 10.1 1a2/hhallaa00442066 URL https: //t:://acc acc/lacllcoo cellanhhologg org/202/
Eric Mitchell, Joseph Noh, Siyan Li, Will Armstrong, Ananth Agarwal, Patrick Liu, Chelsea Finn, and Christopher Manning. Enhancing self-consistency and performance pre-trained language models through natural language inference. In Proceedings of the 2022 Conference Empirical Methods in Natural Language Processing, pages 1754-1768, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. URL https:ttp//.oo /acl//aclleeee// aclaanhooogyy org/2022. emn 1p-ma i n. 115.
Yasuhide Miura, Yuhao Zhang, Emily Bao Tsai, Curtis Langlotz, and Dan Jurafsky. Improving factual completeness and consisteney of image-to-ters to-text radiology report generation, 2021.
Aaron Nicolson, Jason Dowling, and Bevan Koopman. Improving chest x-ray report generation by leveraging warm-starting, 2022.
OpenAl. Gpt-4 technical report. 2023.
Harris Papadopoulos. Inductive conformal prediction: Theory and application to neural networks. In Tools Artificial Intelligence, chapter 18. IntechOpen, Rijeka, 2008
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Leurning, pages 345-356. Springer, 2002.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. 2020.
Maribeth Rauh, John Mellor, Jonathan Uesato, Po-Sen Huang, Johannes Welbl, Laura Weidinger, Sumanth Dathathri, Amelia Glaese, Geoffrey Irving, lason Gabriel, William Isaac, and Lisa Anne Hendricks. Characteristics of harmful text: Towards rigorous benchmarking of language models, 2022.
Shauli Ravfogel, Yoav Goldberg, and Jacob Goldberger. Conformal nucleus sampling. 2023.
Yaniv Romano, Evan Patterson, and Emmanuel Candès. Conformalized quantile regression. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Tal Schuster, Adam Fisch, and Regina Barzilay. Get your vitamin C! robust fact verification with contrastive evidence. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 624-643, Online, June a. Association for Computational Linguistics. doi: 10. 10.18653/v1/200 nnacc--mai. 52. URL https:ttp..... / a aallanthology org/ 2021 naacl .
Tal Schuster, Adam Fisch, Tommi Jaakkola, and Regina Barzilay. Consistent accelerated inference via confident adaptive transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages
Online and Punta Cana, Dominican Republic, November 2021b. Association for Computational Linguistics. doi: 10. 1..18863/11222 1/2021.emnlp main. 406. URL https: / /acl aoooooooooooyo....ooooooooooooo org/ 22021 emn 406.
13

---

Published as a conference paper at ICLR 2024
Tal Schuster, Sihao Chen, Senaka Buthpitiya, Alex Fabrikant, and Donald Metzler. Stretch- ing sentence-pair NLI models to reason over long documents and clusters. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 394-412. Abu Dhabi, United Arab Emirates, December 2022a. Association for Computational Linguistics. URL https: htt///allatttt www.caannnoooooo..o wtt.ollooyyyoo2/2211//
1 28.
Tal Schuster, Adam Fisch, Jai Gupta, Mostafa Dehghani, Dara Bahri, Vinh Q. Tran, Yi Tay, and Don- ald Metzler. Confident adaptive language modeling. In Advances in Neural Information Processing Systems, 2022b. URL https:::p...............: /oppeeeeeeeeeeeeeeeeeeeeeeeeeeee net / forum? d=uLNc41.3881
Abigail See, Peter J. Liu, and Christopher D. Manning. Get to the point: Summarization with ceenter-generator networks. CoRR, abs/1704.04368, 2017. URL 1704.08 04368.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost, 2018.
Akshay Smit, Saahil Jain, Pranav Rajpurkar, Anuj Pareek, Andrew Y. Ng, and Matthew P. Lungren. Chexbert: Combining automatic labelers and expert annotations for accurate radiology report labeling using bert, 2020.
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R. Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, and et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models, 2022.
Jacopo Teneggi, Matthew Tivnan, J. Webster Stayman, and Jeremias Sulam. How to trust your diffusion model: convex optimization approach to conformal risk control. ArXiv, abs/2302.03791, 2023.
James Thome, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal. FEVER: large- scale dataset for fact extraction and VERification. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long Papers), pages 809-819, New Orleans, Louisiana, June 2018. Association for Computational Linguisties. doi: (0.18653/1/N18--0774 URL https:// Saanthology.or//Wuee 10744.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. Llama: Open and efficient foundation language models, 2023.
Helena Vasconcelos, Gagan Bansal, Adam Fourney, Q. Vera Liao, and Jennifer Wortman Vaughan. Generation probabilities not enough: Exploring the effectiveness of uncertainty highlighting in ai-powered code completions. 2023.
Vladimir Vovk. On-line confidence machines are well-calibrated. In The 43rd Annual IEEE
Symposium on Foundations of Computer Science., 2002.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning Random World. Springer-Verlee Berlin, Heidelberg, 2005.
Vladimir Vovk, Ivan Petej, and Valentina Fedorova. Large-scale probabilistic predictors with and without guarantees of validity. In Advances in Neural Information Processing Systems (NeurIPS), 2015.
Vladimir Vovk. Jieli Shen, Valery Manokhin, and Min-ge Min-ge Xie. Nonparametric predictive distribu- tions based on conformal prediction. In Proceedings of the Sixth Workshop on Conformal and Probabilistic Prediction and Applications, 2017.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023. URL https:/ https://openres: http://pppeeviiieeeee net wtwprreewweeeeeeeeoorrrieeeo
14

---

Published as a conference paper at ICLR 2024
Johannes Welbi, Amelia Glaese, Jonathan Uesato, Sumanth Dathathri, John F. J. Mellor, Lisa Anne Hendricks, Kirsty Anderson, Pushmeet Kohli, Ben Coppin, and Po-Sen Huang. Challenges in detoxifying language models. ArXiv, abs/2109.07445, 2021.
Adina Williams, Nikita Nangia, and Samuel Bowman, A broad-coverage challenge corpus for sentence understanding through inference. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lan- guage Technologies, Volume (Long Papers), pages 1112-1122, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/w1/N18-11100 URL www.t/hhhhoooooo./...... org/N18 1101.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, R' R'emi Louf, Morgan Funtowicz, and Jamie Brew. Huggingface s transformers: State-of-the-art natural language processing. ArXiv preprint: 1910.03771, 2019.
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V Le, Mohammad Norouzi, Wolfgang Macherey. Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Google's neural machine translation sys- tem: Bridging the gap between human and machine translation. arXiv preprint arXiv: 1609.66044444 2016.
Xiang Yue, Boshi Wang, Kai Zhang. Ziru Chen, Yu Su, and Huan Sun. Automatic evaluation of attribution by large language models. arXiv preprint arXiv:2305.06: 1,1,1,1 2023.
Polina Zablotskaia, Du Phan, Joshua Maynez, Shashi Narayan, Jie Ren, and Jeremiah Liu. On uncer- tainty calibration and selective generation in probabilistic neural summarization: A benchmark study. 2023.
Yuan Zhang, Jason Baldridge, and Luheng He. PAWS: Paraphrase adversaries from word scrambling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pages 1298-1308 -008, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10. 10.18653/v
URL https: accc///claaa. anthologyhooo org 91131.
Kaitlyn Zhou, Dan Jurafsky, and Tatsunori Hashimoto. Navigating the grey area: Expressions of overconfidence and uncertainty in language models. ArXiv, abs/2302. 13439, 2023.
A ASSUMPTIONS
For clarity, we provide some additional discussion on our assumptions, and their implications. Assumption 1. Input prompts x are ii.d. for both calibration and testing.
The inputs to our LM are considered to be randomly sampled from some fixed distribution. This is reasonable assumption for many standard scenarios, such the ones that explore in experiments, i.e.: questions for question answering, articles for summarization, and X-rays for radiology report generation. Importantly, however, this does not include multi-tura dialogue where successive prompts are dependent, or when there is distribution shift between calibration and testing. Additional modifications of distribution shift (c.g.. by defining new p-values that remain super-unifona under the target distribution using weighting), although we do not evaluate this direction in this work.
be done extend
calibration procedure handle certain types
Assumption 2. We can sample po(y x) using a language model API that accesses pe.
No other assumptions placed on the LM itself its sampling process. That said, two additional LM qualities also affect the performance of our method in practice:
QI. There exists good response that is expressible by the LM, i.e., By E V* s.t. A(y) = 1. This simply to say that all inputs are not impossible to answer appropriately.
Q2. The LM places high enough probability mass on good responses such that good responses are sampled within tractable number of calls sufficiently often (i.e., fraction of the time).
15

---

Published as a conference paper at ICLR 2024
Without qualities QI and Q2, some settings of kmax and may be unachievable, and our algorithm will fail to return a risk- controliig configuration. Nevertheless, this does not affect the validity of our algorithm; it only affects its application. See Appendix C for a discussion on kmax.
Assumption 3. The admission function A is good proxy for assessing generation quality.
Our guarantees are based on bounding the expected value of A on future outputs. For this to be meaningful, A(y) 1 should reflect that y is a good sample. In our experiments, we manually design A by using similarity metrics that compare possible responses to human references. For example, in our radiology report generation task, x is the X-ray, y is the report, and po(y æ) our image-to-text LM. Given y and a "ground truth" report y written by radiologist (from the MIMIC-CR dataset), we use the popular Clinical Efficacy metric (Liu et al., 2019; Nicolson et al., 2022) as a proxy for "admissibility", where we check if all of the 14 labels predicted by auxiliary CheXbert (Smit et al., 2020) model given y exactly match the labels predicted by the same CheXbert model given y"
The admission function is flexible, however, and need not be automatic. For example, the most reliable admission function is to directly use real users to assess whether a generated sample is acceptable or not (or the majority vote of one more human annotators, when given clear, consistent guidelines). Such a user-based calibration set would be ideal, but also often costly to obtain.
When automatic admission functions are needed, here we show that it is also sufficient only require access to a conservative admission function, A: V + {0, 1], where Vy E V we have Aly) S A(y). For instance, Á might measure exact match on word-for-word basis between y and y", instead of accounting for differences in dictation. We show that À remains valid with respect to the "true" (but inaccessible) Atest if conservative admission functions A; were used during calibration.
Corollary A.1 (Conservative sampling- based LTT). Suppose that over Deal we let L,(A) 1 (By e (X,): (y) 1} where A(y) S A(y). Vy V*. Then Cj (Xtstt still satisfies Eq. (1).
Proof. The following proof is analogous to that of Propostion 4.4. Let
Σ(A)= = 1 E Cx(x): A=1}
(11)
For all y E V", have Atest (v) This implies that for any choice of Deal
Aceet(y) (v) 1, which implies that L(A) L(A) for all A.
L et (Å) Deat) 2 EL (\) Deall.
(12)
Applying Theorem 4.2 gives that the left hand side is S w.p. 2 6.
B LIMITATIONS
Our work aims to provide rigorous, yet useful, uncertainty estimates for language models. This has important implications for the safety and reliability of deployed models that make decisions with real consequences. At the same time, definite limitations do exist for the algorithms presented here, in particular (a) the assumption of i.i.d. data, (b) an appropriate admission function A, and (c) having resulting Cx that are not too large or expensive to obtain (e.g.. requiring many samples). In the same vein, if kmax. the maximum number of samples drawn, is too low, then many levels of will be unattainable, and the method will fail to find valid configuration (it will return null). Finally, important to emphasize that the guarantees presented here are probabilistic in nature- and also do not necessarily hold when conditioned on particular type of input. While setting 5 and to low values possible and decreases the changes of failures, it will also make the algorithm more conservative and potentially less useful. The admission function A also requires careful construction. Nevertheless, these results can be improved by (a) plugging in better language models, (b) using higher signal con- fidence metrics (e.g., as opposed to raw logits), and (c) obtaining larger samples Deal for calibration.
C EFFECTS OF TRUNCATED SAMPLING (kmax)
To be useful, it is critical to ensure that our sampling algorithm terminates in a reasonable number of steps. For this reason, we use kmax as a hard stop on the total number of samples we take from po(y æ). Naturally, this also effects the achievable coverage that can guarantee, certain LMs
16

---

Published as a conference paper at ICLR 2024
may require more than kmax samples get correct response for certain input examples. For each Emax there is therefore band of achievable (non-trivial) c, that ranges from the error rate at first-1 to the error rate first-kmax (where first-k denotes the strategy of always taking the first le samples for a fixed k). In our experiments, we set kmax = 20, although the best practice is to empirically choose mmxx using development set along with an idea for how many samples one is willing to take in the worst case, which is primarily determined by the one's 's computational budget.
D PROOFS
D.1 PROOF OF LEMMA 4.1
Proof. Let (nnommn, e) and = =n,, (A), which also has distribution (inomm e'), for some unknown success probability e', as L;'s are binary. We write F'x (x) and (y) to denote the CDFs of X and Y. respectively. Under the null hypothesis Hx: Lestest I (A)l > e (or equivalently, Hx e' c).
Y stochastically dominates X, i.e., Fx Fu) 2 (u), Vu. Let Z = BT FY Then
P(Z S 2) = PXFx(() 2)
(13)
S (YF 5)
(14)
= =P(Y S (z))
(15)
= =FyFy (2)
(16)
=.
(17)
Therefore since px super-uniform, is valid p-value.
D.2 PROOF OF THEOREM 4.2
Proof. Since sampling is performed independently for each (i.i.d)) input prompt X; and admission function A,, the set losses (A) are also i.i.d. According to Lemma 4.1, px super-uniforn under Hx: [[[rest()) > Given T, FWER-controlling algorithm at level 6, we can apply Theorem 3.2 to identify Avalid such that
IP sup AEAvali
E[ (A) Deal Se) 21
(18)
i.c.
P(Py Cx(Xtest): Arest = Deal 1 21- 22 21 5.
P inf AEAvalia
(19)
Therefore, Equation 1 holds for any À E Avalid- In particular, it holds for selecting Å by Eq. (7).
D.3 PROOF OF PROPOSITION 4.4
Proof. Let
[((r) = Be E U A = =0}
Wemax
(20)
1=1
Since (x)x C ......., Memar for any X by definition, we have ['()) 2 (*()) for all This implies that for any draw of Deul.
E L Lest (7) Deal] 2 E[ (9) Deal)
(21)
Similar to the proof of Theorem 4.2, since (7) is also binary, we can use Lemma 1 to show that p is valid p-value, and apply LTT to show that the left hand side
w.p. 2 1 8.
17

---

Published as a conference paper at ICLR 2024
E PARETO TESTING
We briefly review the Pareto Testing method for configuration selection, but refer the reader to naufer-Goldshtein et al. (2023) for full details. Pareto Testing is a computationally and statistically efficient procedure that improves Fixed Sequence Testing (Holm, 1979). a common procedure, by optimizing the ordering of configurations to test. The method consists of two stages:
Stage 1: Constructing the Pareto frontier
First we solve unconstrained, multi-objective optimization problem in order to recover an approxi- mate set of Pareto-optimal configurations, i.e., settings for which no other configuration exists that is uniformly better in all respects. Some of these objectives are meant eventually be constrained (e.g.. controlled to be S e), while others are meant to be optimized (e.g., find the smallest set).
Specifically, suppose that there are e objectives we seek to control and & objectives that we seek to optimize. In our setting, c = 1 (we would like to control coverage) and k = 1 (we would like minimize a weighted combination of the number of samples and the size per Eq. (7)). Let A ê A1 x.....X,, Xmm (here m 3) be a be a map from À to the values of the objective functions (both constrained and unconstrained), i.e.
configuration space, and let q()) : A Retk
(A) @ (A),..., Q (2)
(22)
where Q."" is the empirical average of the objective evaluated over a split of data, Dopt (c.g., the empirical coverage). Generally speaking, there is typically single value of À that minimizes all objectives simultaneously. Instead, we find the Pareto frontier of all points that are not dominated (i.e., there exists another X E A that is better in all respects):
Apur f A X' < <
(23)
Apar then represents set of configurations with optimal trade-offs (at least, according to the empirical values computed over Dopt). Let [a1..... acl be list of our target constraints for the first e constrained objectives. We then sort Apar by estimated p-values
(A, = max p(Q.PM (A); 1gige
(24)
which compute over D Dopt (the same used find the Pareto frontier, but separate from testing data). Different p-values can be used, see Angelopoulos et al. (2021a). Intuitively, this defines a sequence of configurations that are Pareto-optimal, ordered by the likelihood of them being able to satisfy all of our constraints. Since in this work we only have one constraint (coverage), this reduces to finding the sequence of Pareto-optimal configurations ordered from most least likely to result in valid coverage.
Stage 2: Fixed sequence testing
The second stage is simple. Given the sequence of configurations identified in Stage 1, Stage applies Fixed Sequence Testing. Concretely, given calibration data Drat, we sequentially test each configuration by checking if the maximum p-value for constrained objectives greater than 8, i.c.,
() a) = max p(Q)aal (A); 2 5,
(25)
ISi5o
and stopping the first configuration for which this inequality holds. The set of evaluated À for which Eq. (25) does not hold is then taken to be Avalid It can be shown that this procedure is FWER-controlling level 8. and often powerful, as the constructed sequence of À generally allows for identifying a Avalid with high-recall (i.c., we recover many of the valid configurations).
F ADDITIONAL EXPERIMENTAL DETAILS
In this section, we provide additional details regarding the experiments conducted for the three tasks discussed in Section 5. Our code will be released after the review process.
18

---

Published as a conference paper at ICLR 2024
F.1 RADIOLOGY REPORT GENERATION
Dataset For the radiology report generation experiment, we utilized the labeled MIMIC-CXI and MIMIC-CXR-IIP datasets (Johnson al., 2019). The MIMIC-CK, dataset can be accessed at http://ionetoog//ootte//miieieee
under the PhysioNet Credentialed Health Data License 1.5.0. Similarly, the MIMIC-CXR-JPG dataset available at https///phyiionet...r/cmmmmmnmni exr-jpg/2.000/ under the same license.
We start with the standard splits preseribed in MIMIC-CXR-JGG. However, we further divide the training set into a train set and a dev set using a 0.9/0.1 I ratio. The train set is used for training the model, using the validation set for early stopping. We then exclusively use the dev set for conformal prediction experiments, Subsequently, we filtered the dataset to include only anterior to posterior (AP) or posterior to anterior (PA) views and retained only one image per report. Furthermore, we removed examples where the report did not start with the phrase "FINAL REPORT" as these reports often contained summary of the findings at the beginning, inadvertently leaking the answer we aimed to generate with the model. Table F.l provides an overview of the resulting dataset.
Split
Train
Dev
Validation
Test
Number of Images
176,078
19,658
1,594
2,799
Number Studies
176,078
19,658
1,594
2,799
Number of Patients
54,482
6,053
463
286
Table F.1: Dataset statistics for preprocessed MIMIC-CXR. The splits and preprocessing scripts are available within our code release. The train and validation split is used for to train the encoder-deocder model with early stopping. The dev set is used for conformal prediction. The test set is unused.
Each image was resized and cropped resolution of 224x224. Following prior methodology (Miura et al., 2021), we split each report into a prompt part and a findings part (which may also contain the impressions section) by identifying one of the following phrases: "FINDINGS AND IMPRESSION". "FINDINGS" or "IMPRESSION".
Model The image encoder used in our experiment was a Vision Transformer (ViT) model pretrained ImageNet-21k google/ve e/vittiiitie ceait--bae-ppacch. et al., 2019). The text decoder model with a batch size of 128 distributed over 8 GPUs, resulting in a batch size of 16 per GPU. The AdamW optimizer was employed with 81 0.9, 83 0.999, and e 10-8, The learning rate was set to 5 x 10-5, The training process consisted of 10 epochs, and the total training time on 8 RTX A6000 GPUs was approximately 11 hours.
utilized the model available in the Transformers library (Wolf GPT2-small model (gpt.2 HuggingFace). We trained the
resolution of 224x224. Specifically,
Generations Candidate reports were sampled from the model using default arguments from the Transformers library, i.e. top == 50, top_p = 1.0 and temperature = 1. Each generated report is then evaluated using trained CheXbert model (Smit et al., 2020). The CheXbert model is available at https:/ssanfordmediiiin wwwpeeeiiiieeee...oo.o www.com//cccccoooococcccooo under the Stanford Academic Software License. The CheXhert model lahels each report for 14 conditions, assigning of the following labels: "Blank," "Positvee." "Negative," " or "Uncertain."
To determine the admission of a candidate report, we compare with a reference (human) report from the MIMIC dataset. If the candidate report matches all 14 labels of the reference report, the admission function returns 1; otherwise, it returns
We define a component as sentence delimited by period. The component-level admission function is defined based on how well a sentence aammst matches" one of the reference sentences. Two sentences sentence almost matches a reference sentence, the component-lewe admission function returns 1; otherwise, it returns O.
Components
considered "almost match" if their ROUGE score is above 0.4. If
19

---

Published as a conference paper at ICLR 2024
Answer these questions
Q: Which American-born Sinelair the Nobel Prize for Literature in 1930?
A1 Sinclair Lewis
Q: Where in England was Dame Judi Dench born?
A: York
Q: which decade did Billboard magazine first publish and American hit chart?
A: 30s
Q: From which country did Angola achieve independence in 1975?
A: Portugal
Q: Which city does David Soul come from?
A: Chicago
Q: Who won Super Bowl xx?
A: Chicago Bears
Q: Which was the first European country to abolish capital punishment?
A: Norway
Q: which country did he widespread use of ISDN begin 1988?
A: Japan
Q: What is Bruce Willis' real first name?
A: Walter
Q: Which William wrote the novel Lord of The Flics?
A: Golding
Q: Which innovation for the car was developed by Prince Henry of Prussia in 1911?
A: Windshield wipers
Q: How is musician William Lee Conley better known?
A: Big Bill Broonzy
Q: How Joan Molinsky petter known?
A: Joan Rivers
Figure F.1: Truncated replication of the prompt used to generate answer on the TriviaQA dev set. The actual prompt contains 32 question-answer pairs.
F.2
QUESTION ANSWERING
We use the TriviaQA (Joshi et al., 2017) dataset available at www.:ip.....assiittoooocom under the Apache License Version 2.0. To generate candidate responses, used LLaMA-13B (Touvron et al., 2023). We considered the closed-book setting, where the model does not have access supporting text for answering the questions. We performed experiments in the few-shot setting by providing 32 example crestion-answee pairs sampled from the training set. A truncated prompt used for generating answers on the TriviaQA dev is reproduced an illustration in Figure F.1. Please note that the actual prompt used in the experiment contains 32 question-answw pairs.
For generating answers in the open-domain question answering task, parameters reported in the previous section. We extract an answer by considering the text until the first line break, comma. or period is encountered. We then normalize the answers: this involves con- verting the generated answers to lowercase, removing articles, punctuation, and duplicate whitespace. Generated answers are then compared using the exact match metrie: an answer is considered correct only if it matches the provided answer exactly.
the default Transformers
F.3 NEWS SUMMARIZATION
We use the CNN/DM dataset (Hermann al., 2015; See et al., 2017) that includes news articles from CNN and the Daily Mail paired with their human written summaries, and is available at under MIT License. We use the standard train set for finetuning, the validation set for selecting the best checkpoint, and the test set for all reported conformal experiments.
We T5 1.1 XL model, which includes roughly 3B parameters, and further pretrained for 100k steps with multilayer objective (Schuster et al., 2022b). We finetune the model on the train set for 200k steps with batch size of 128 using 64 TPUv4 chips for approximately 40 hours. We use
20

---

Published as a conference paper at ICLR 2024
the Adafactor (Shazeer and Stern, 2018) optimizer with deacy rate of 0.8, initial learning rate of 0.001 and Ik warm-up steps.
To generate candidate responses, use Nucleus sampling (Holtzman al., 2020) with top-p set to 0.95, temperature 0.7, and maximum output length set 256 tokens.
To get the response components nent. As a classifier for evaluating the correctness of each component, we use an independent T5 XXL model trained on mixture of NLI datasets (Honovich et al., 2022; Schuster et al., 2022a). Specifi- cally, we leverage the model used in the TRUE benchmark (Honovich et al., 2022) and is available at https//hugginggacee http://hgggng..c....o/oogoog//// xxl __te__uee_i_i___________________ lalinnniiiiia mil_mmieeeee.. This model was trained SNLI (Bowman et al., 2015), MNLI (Williams et al., 2018), FEVER (Thorne et al., 2018), SciTail (Khot et al.. 2018), PAWS (Zhang al., 2019), and VitaminC (Schuster al., 2021a) make binary prediction of whether an hypothesis sentence is entailed by the given premise (in three-way datasets, the neutral class was merged with the negative class). We query the model with each component as the hypothesis, and the source summary as the premise, and measure the tog-probability of predicting "entailment".
simple sentence spliter and treat each sentence compo-
F.4 DATASET DETAILS
Dataset
Standard split
Size
Purpose
Train
176,078
Train the generative model
Dev*
19,658
Calibration experiments
MIMIC
Validation
1,594
Early stopping Unused
Test
2,799
Train
138,384
Prompt LLaMA (32 samples)
TriviaQA
Validation
18,669
Calibration experiments
Test
17,210
Unused
Train 287,113
Train the generative model
CNN/DM
Validation 13,368
Early stopping
Test
11,490
Calibration experiments
Table F.2: We use the standard splits each dataset and reserve unseen data for our calibration exper- iments. The only exception is for MIMIC where validation and test data are too small, so we reserve a subset of the official train set as unseen data for calibration. The asterisk marks that exception.
Dataset MIMIC
Split
Size
Calibration train
2,000
Calibration val
2,000
Calibration test
15,658
TriviaQA
Calibration train
2,000
Calibration val 2,000
Calibration test 14,669
CNNDM
Calibration train 2,000
Calibration val 2,000
Calibration test 7,490
Table F.3: Additional splits for calibration experiments
For each dataset, we use the standard splits shown in Figure F.2 and further split the data reserved for calibration experiments, as described in Figure F.3. The calibration "val" set was used in our earlier experiments to compare scoring functions. Some scoring functions required training (e.g. Platt scaling) and we used an additional calibration "train" set for that purpose. For final evaluation, 100 trials. For each trial, the calibration test data split as follows: 10% is used to compute the Pareto frontier, 20% is used for Fixed Sequence Testing. The remaining 70% is used measure test metries (validity and efficacy).
used the calibration "test" set
21

---

Published as a conference paper at ICLR 2024
25
25
Number of compenents
Classifier (7.01)
Number of components
Classifier (5.75)
Span logits (3.57)
Span logits (1.96)
20
20
Rardomm 64)
Random (2.13)
15
10
5-
5-
0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Risk Level (a)
Risk Level (a)
(a) MIMIC-CXR
(b) CNN/DM
Figure G.1: Conformal component selection results for Cinner as a function of a. We report the number of components in Ciyner, which we want to maximize. We also report the AUC over a.
Classifier
logits (0.48)
Szan logits (0.47)
Component LOSS
Random (0.44)
Component Loos
Random (0.47)
diagonal (0.50)
d agonal (0 (0.50)
0.8
0.6
0.4
0.4
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Hisk Level (4)
Kisk Level (s)
0.6
0.8
Classifier (0.25)
Classifier (0.21)
Span logits (0.17)
Span logits (0.15)
0.6
Random (0.08)
0.4
Random (0.10)
Recail
Recall
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.4
0.6
0.8
1.0
Risk Level (a)
Risk Level (a)
(a) MIMIC-CXR
(b) CNN/DM
Component selection results for Cinner as a function of a. First row: validity curves. Second row: recall achieved by Cinuer, which we want to maximize. We also report the AUC over a.
Figure G.2:
F.5 LENGTH-NORMMALIZATIO
For all tasks, we apply length-normalizinn normalizaiaiiinnn (Wu al., 2016) to the model logits, i.c. we compute:
log po Ip(ux)
Qxx, yv) = cxp
where
(p(y) (5 + 1y))
(5 1)0.6"
22

---

Published as a conference paper at ICLR 2024
G ADDITIONAL RESULTS
We describe another metric useful to characterize the effectiveness of the components identified by component selection method.
Given an input x' and a component set Cy.mmerr (z), we compute the recall by counting the number of reference sentences that "almost match" least one element in Cylnner (I:). We then divide this count by the total number of reference sentences for that particular example. This gives us a measure of how much of the human reference covered by the selected components. To obtain the expected recall, we average the recall values over all examples. The expected recall is reported in Figure G.2.
In particular, observe that component sets generated using scoring functions based on an auxiliary CLASSIFIER outperform uncertainty measures based solely on the span logits provided by the model.
H QUALITATIVE RESULTS
We present qualitative results for radiology report generation and news summarization. In this section, we use the SUM method and consider (C) Σyec Qgy). The choice of a and e is reported in Table H.7. We use 30% of the dev dataset (chosen uniformly at random) to determine Å as described in $4.3, and reserve the remaining 70% of the dataset for qualitative inspection. The corresponding values of À and
reported in Table H.7. Notably, the method produces X2 -oo for the CNN/DM task, indicating that individual summaries are not rejected based on their quality but only for redundancy reasons.
In Figure H.I, an X-ray example is shown, depicting left basilar opacities while the rest of the X-ray appears normal. Table H.1 indicates that our method terminates the generation process after producing three samples. The third generation correctly identifies "apical scarring"; however, it mistakenly attributes it to the right lung instead of the left lung. This highlights a limitation of using CheXbert as the basis for the admission function, as its label granularity does not differentiate between left and right. Our component selection method accurately identifies several sentences that align with the reference report. These sentences are displayed in bold. Notably, our method avoids emphasizing low-confidence findings such as "right apical scarring" and instead focuses on the absence of an acute cardiopulmonaty process.
more challenging example is described in Figure H.2. The report mentions an enlarged heart, signs of cardiomegaly, and edema. Samples 4 and correctly capture these findings but considered incorrect due to the inclusion "effusion." " The conformal selection of components chooses not to highlight any sentences since none of them meet the confidence threshold defined by e.
In Tables H.3-H.6, we illustrate how our method continues sampling candidate summaries until the produced set is deemed acceptable. Specifically, Table H.3 demonstrates that the component selection process highlights the main idea while excluding minor ideas, which exist in multiple variations. Table H.4 exemplifies that the method stops after Sample not because Sample has the highest score, but because the sum of the scores collectively exceeds the target threshold of X3 = 1.02. Indeed, as shown in Table H.5, a higher individual score does not necessarily imply that generation is more acceptable than one with a lower score. Finally, Table H.6 reveals a model failure, where the scores indicate high confidence Sample 2, but the proposed generations are missing some main ideas from the reference summary.
23

---

Published as a conference paper at ICLR 2024
AP and lateral views of the chest. Streaky biapical and left basilar opacities are most compatible with scarring, The lungs are clear of confluent consolidation. There is no effu- sion. Cardiomediastinal silhouette is within normal limits. No acute osseous abnormalities detected. IMPRESSION: No definite acute cardiopulmonary process.
Figure H.I: Chest X-ray and reference radiology report for study id 55663120
Table H.l: Example prediction sets for study 55663120, at = 0.7, e 0.7. Bolded sentences are sentences that are chosen by the component selection process. Here see that several phrases common all generations, such as "AP and lateral views of the chest", are high confidence (and also correct). The finding about the cardiomediastinal silhouette is also confident. A completely correct generation, however, is not achieved until the third sample (after which the algorithm stopped).
Text
Score 1,45e-05
Label
Sample
AP upright and lateral views of the chest provided. There is chronic left lower lobe atelectasis. There is no focal con- solidation concerning for pneumonia. No large effusion or pneumothorax. The cardiomediastinal silhouette normal. Imaged osseous structures are notable for a mild compression deformity of an upper lumbar vertebral body. Degenerative change seen in the right acromioclavicular joint. IMPRESSION: No acute intrathoracic process.
False
Sample 2
AP and lateral views of the chest. Diffusely calcified pleu- ral plaques are identified bilaterally suggesting prior asbestos exposure. There is no pleural effusion. The cardiomediasti- nal silhouette is within normal limits. No acute osseous abnormalities detected. Surgical clips project over the up- per abdomen. IMPRESSION: No definite acute cardiopul- monary process.
1.98e-05
False
Sample
AP and lateral views of the chest. There is right apical scarring. Elsewhere, the lungs are clear. The cardiomedi- astinal silhouette is within normal limits. Atherosclerotic calcifications noted at the aortic knob. No acute osseous abnormality detected. IMPRESSION: No acute cardiopul- monary process.
5,36e-03
True
24

---

Published as a conference paper at ICLR 2024
In comparison with the study of there is continued enlargement the cardiac silhouette with increasing fullness and indistinctness of central pulmonary vessels, consistent with worsening pulmonary edema. Mild asymmetry at the left base could represent developing aspiration or even infectious
Figure H.2: Chest X-ray and reference radiology report for study id 55770135
Table H.2: Example prediction sets for study id 55770135, at 0.7, 0.7. No sentences are selected by the component selection process. As a symptom low component confidence, most generations have low overlap in exact phrasing and findings. In this case, the sampling process failed to produce a correct response (though the probability of this happening overall is 0.3).
Text
Score
Label
Sample
In comparison with the study of there is little overall change. Again there is enlargement of the cardiac silhou- ette with elevated pulmonary venous pressure and bilateral opacification is consistent with developing pulmonary edema or pneumonia in the appropriate clinical setting. The naso- gastric tube again extends at least to the lower body of the stomach, where it crosses the lower margin of the image. Compared to chest radiographs ate pulmonary edema is exaggerated due to the low lung volumes, but is new, including mild interstitial edema and engorgement of the mediastinal veins. Mediastinal veins are still engorged, but not large. Pleural effusions are presumed, but not large. Indwelling right subclavian line ends in the low SVC.
1.96e-05
False
Sample 2
through
Moder-
7.10c-08
False
Sample 3
Compared to chest radiographs through ate pulmonary edema is improving, although heart remains moderately enlarged and mediastinal veins are substantially dilated due to volume status. Bilateral pleural effusions are presumed, but not large. No pneumothorax. NOTIFICA- TION: discussed the findings with the referring physician by telephone Compared to chest radiographs
Moder-
2.42c-07
False
at 3:08 PM.
Sample 4
through to severe pulmonary edema has worsened. Moderate car- diomegaly is chronically large, exaggerated by lower lung volumes. Pleural effusions are small if any. No pneumotho-
Moderate
2.35e-04
False
Sample 5
No previous images. The cardiac silhouette is enlarged and there is some indistinctness of pulmonary vessels consistent with mild elevation of pulmonary venous pressure. In view of the prominence of the pulmonary vasculature, it would be difficult to unequivocally exclude superimposed pneumonia, especially in the absence of lateral view.
4.69e-04
False
25

---

Published as a conference paper at ICLR 2024
Table H.3: Example prediction sets for example from CNN/DM dataset, 0.3,
0.7. Bolded
sentences are sentences that are selected by the component selection process. Missing sample indices represent samples that were rejected. Here observe that component selection highlights the main idea, while excluding minor details, which are lower confidence. A fully correct sample is not obtained until the 19th draw.
Text
Score
Label
Ref
Debris from boat to be dried, inspected and taken to landfill. The debris contained fish normally found in Japanese waters.
The earthquake and tsunami hit Japan in March 2011. Section of boat believed be from 2011 Japan tsunami found off Oregon coast. Biologists say the environmental threat is small
Sample
3.62e-01
False
Sample
Ship debris found off Oregon coast suspected to be from 2011 Japan tsunami. Biologists say the invasive species threat is small.
2.63e-01
False
Sample 3
Ship fragment found off Oregon coast. It's suspected to be from 2011 Japan tsunami. Yellowtail jack fish were found inside the boat.
1.71e-01
False
Sample 7
Ship debris found off Oregon coast may be from 2011 Japan tsunami. Yellowtail jack fish were found inside the vessel
2.76e-01
False
Sample 12
Ship debris found off Oregon coast and towed to harbor. Biologists say it poses threat to the environment. Section of boat found off Oregon coast suspected to be from 2011 Japan tsunami. Biologists say the boat fragment will be taken to a landfill Yellowfall jack fish, normally found in Japanese waters, will be taken an aquarium. Section of boat found off Oregon coast may be from 2011 Japan tsunami. Biologists say the environmental threat small
1.22e-01
False
Sample 13
2.63e-01
False
Sample 16
3.62c-01
False
Sample 19
Section of boat found off Oregon coast suspected to be from 2011 Japan tsunami. Biologists say the environmen-
1.40e-01
True
tal threat posed by the boat is small.
26

---

Published as a conference paper at ICLR 2024
Table H.4: Example prediction sets for example from CNN/DM dataset, at 0.3, = 0.7. Bolded
sentences are sentences that are selected by the component selection process. Of note is how this example demonstrates that the method stops after Sample 9, not because Sample has the highest score, but because the sum of the scores collectively exceeds the target threshold of X 1.02.
Text
Score
Label
Ref
Jordan lbe showed off the impressive dance move on his Instagram. The Liverpool star has broken into the first team during this campaign. lbe is currently on the sidelines after suffering knee injury. CLICK HERE for all the latest Liverpool news.
Sample
Jordon lbe has been key player for Liverpool this season The 19-year-old winger has been sidelined with knee injury Ibe has been performing the moonwalk while recovering from the injury He posted video Instagram of him performing the move Liverpool face Newcastle their next Premier League game
2.63e-01
True
Sample 2
Jordon Ibe has been key player for Liverpool this season The 19-year-old winger has been sidelined with a knee injury Tbe took to Instagram to show off his skills performing the moonwalk.
1.60e-01
False
Sample 3
Jordon lbe has been key player for Liverpool this season The 19-year-old is currently out with knee injury But lbe showed off some impressive moves his Instagram account
2.63e-01
True
The Liverpool winger posted a video of him performing the moonwalk.
Sample 5
Jordon lbe has been key player for Liverpool this season
2.27e-01
True
The 19-year-old took to Instagram to show off his dance moves. lbe is currently out with knee injury but is expected to return in the next few weeks..
Sample
Jordon lbe has been key player for Liverpool this season The 19-year-old took to Instagram to show off his moves. He posted a video of him performing the moonwalk. Ibe is currently out with a knee injury but is expected to return soon
3.89e-01
True
Sample 8
Jordon lbe has broken into the Liverpool first team this season The 19-year-old took to Instagram to show off his skills performing the moonwalk. Liverpool face Newcastle in their next Premier League game.
3,89c-01
True
Sample
Jordon lbe posted a video on Instagram of him perform- ing the moonwalk The Liverpool winger is currently out with a knee injury But Tbe is expected return in the next few weeks. Liverpool face Newcastle in the Premier League on Sunday
2.92c-01
False
27

---

Published as a conference paper at ICLR 2024
Table H.5: Example prediction sets for example from CNN/DM dataset, at a 0.3, e = 0.7. No sentences are selected by the component selection process. Here we also that higher individual score does not necessarily imply that a generation is more acceptable than one with a lower score, which highlights why calibration critical. Note that this example also highlights case in which a finer-grained component splitter might be useful: though no complete sentence is confident, certain topies, like "hormone therapy" appear to be.
Text
Score
Label
Ref
Craig Lister, 54, from Watford, is on hormone therapy for prostate cancer. This starves cancer cells by reducing levels of testosterone in the body. One side-effect is hot flushes: 'I have about ten to flushes a day'
Sample 1
Hormone therapy for prostate cancer starves cancer cells by reducing levels of testosterone in the body and has the side-effect of hot flushes It can't 't cure the cancer, but help keep it under control The majority of prostate cancers rely on the hormone grow Lowering the amount the body means it's less able to spread.
5.11e-01
True
Sample
Hormone therapy is usually given in the form of regular injections implants It can't cure the cancer, but can help keep under control. The majority of prostate cancers rely the hormone to grow Lowering the amount in the body means it's less able to spread.
9.10e-01
False
Table H.6: Example prediction sets for example from CNN/DM dataset, at = 0.3, c = 0.7. Bolded
sentences are sentences that are selected by the component selection process. This example reveals model failure, where the scores indicate high confidence in Sample 2, but the proposed generations are missing some main ideas from the reference summary.
Text
Score
Label
Ref
Independent Commission for Reform in Cycling (CIRC) con- cluded that the UCI colluded with Lance Armstrong to cover up allegations. Hein Verbruggen was criticised as events occurred under his leadership. Verbruggen has revealed he having the report analysed by lawyers.
Sample
Hein Verbruggen is unhappy with the CIRC report ver- dict The former head of international cycling has sent the report to lawyers. Verbruggen claims the report is "character assassination'
5.18e-01
False
Sample 2
Hein Verbruggen is unhappy with the CIRC report dict. The former head of international cycling has sent the report to lawyers. Verbruggen says he is having the report analysed by Swiss lawyers.
6.67e-01
False
Table H.7: Choice of e, and corresponding X, y for qualitative results presented in Appendix H.
Dataset
CNN/DM MIMIC-CXR
0.7
0.3
0.7
0.7
A (similarity)
7.37c-1
8.67c-1
A2 (quality)
2.47e-10
-00
Ag (set score)
2.82e-4
1.02
Y (component threshold)
2.04e-1
9.88e-1
28


Reviews:
[{"review_id": "taapsELmKl", "reviewer": "Reviewer_Sb79", "summary": "This paper extends the conformal prediction framework to language models (LMs). The aim is to construct prediction sets of LM responses such that at least one is \"acceptable\" with a desired probability.\n\nThis goal is achieved by sampling responses repeatedly from the LM and adding them to the prediction set until a stopping rule occurs: either (i) an upper bound $k_{\\max}$ on the number of samples drawn from the LM, or (ii) a lower bound $\\lambda_{3}$ on the prediction set confidence score, quantifying how good it is. Additionally, samples are removed from the prediction set (to reduce noise) based on a rejection rule: either (i) a lower bound $\\lambda_{2}$ on the individual response's quality, or (ii) an upper bound $\\lambda_{1}$ on the response's similarity with others in the set. $\\lambda = (\\lambda_{1}, \\lambda_{2}, \\lambda_{3})$ is a configuration that is picked via the Learn Then Test [Angelopoulos et al. 2021a] framework; $k_{\\max}$ is fixed by the user. Note that not all desired errors are achievable. The paper also proposes an extension to identify individual components of the responses (for instance, sentences from paragraphs) that are each independently \"acceptable\" with desired probability.\n\nThe paper goes on to provide empirical results to corroborate its methodology. Experiments on open-domain question-answering, text summarization, and radiology report generation empirically verify the proposed algorithm and its statistical guarantees.", "questions": "1. Design choices:\n    1. Why is $\\hat{\\lambda}$ defined as in Eq. 7? Similarly, why is it desirable for $C^{\\text{inner}}_{\\gamma}$ to be large ($\\hat{\\gamma}$ in Eq. 10)? Explicitly explaining these would help the reader. Are there alternative definitions that might be advantageous?\n    2. What is the reason for using a different definition of $C^{\\text{inner}}_{\\gamma}$ during calibration?\n    3. The Pareto Testing procedure is used in the proposed algorithm for efficiency. However, the appendix only provides a high-level overview. Can the authors include more details and explain how this procedure helps efficiency?\n\n2. Experiments:\n    1. The achievable risk range for MIMIC-CXR is very high. How can one reduce this for the practicality of the proposed method?\n    2. How is the AUC for the set loss plots greater than 0.5? The diagonal should have an AUC of 0.5, and since all the curves are under this, their respective AUCs should be lower than 0.5.\n    3. The First-$k$ scoring function does not utilize rejection. As a result, the likelihood-based approaches have better prediction efficiency. Did the authors try First-$k$ with the rejection scheme for a more apples-to-apples comparison?\n    4. What about the set loss in the individual component case? Experimental results on that would corroborate the theoretical result in Proposition 4.4.\n    5. What is $k_{\\max}$ set to for the experiments?\n    6. The data splits to obtain the train, calibration, and test sets aren't well explained in the paper (appendix included). For example, the authors use a dev set for the conformal prediction experiments, but in what way? Can the data splits be explained more succinctly for the datasets used?\n\n3. \"While Eq. 1 stipulates the existence of at least one \"acceptable\" generation in $C_{\\lambda} (X_{\\text{test}})$, it does not tell us much about individual responses, $y \\in C_{\\lambda} (X_{\\text{test}})$\" (Section 1). Is there any remedy for this? This paper discusses individual components (for example, sentences) but not the whole LM responses.\n\nClarifications:\n\n1. It would be helpful for the reader to highlight why admission functions $A_{i}$ are used rather than labels $Y_{i}$ in Section 1 (where the setup is explained).\n2. Shouldn't the function $A^{c}$ be a mapping $\\mathcal{Y} \\mapsto \\\\{0, 1\\\\}$ instead of $2^{\\mathcal{Y}} \\mapsto \\\\{0, 1\\\\}$ (Section 4.4) as it acts on individual components?\n3. $\\mathcal{Y}$ and $\\mathcal{V}^{*}$ are used interchangeably. Making it consistent would help the reader.\n4. It would be helpful for the reader to add more descriptive captions for the tables in Appendix H. For example, the authors can highlight what the findings are not just in the text but in the table captions as well.\n5. Should Eq. 20 be replaced with Eq. 7?\n6. Missing definitions:\n    1. $\\mathcal{Y}$ is not defined in Section 1 but is used right before Eq. 1.\n    2. $L_{\\text{test}} (\\lambda)$ is not defined but is used right before Eq. 3.\n    3. $F_{X} (u), F_{Y} (y)$ are not defined in Appendix D.1.\n7. Missing superscripts:\n    1. The superscript $c$ in $A^{c}_{\\text{test}}$ is missing in the text before and after Eq. 9.\n    2. The superscript $c$ in $\\bar{L}^{c} (\\gamma)$ is missing in the text after Eq. 22.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. This paper tackles an important research area of providing statistical guarantees on the output of language models.\n2. These statistical guarantees are provided by leveraging the conformal prediction framework and extending it to language models, which is a generative task.\n3. The proposed algorithm is easy to interpret: sample responses from the language model as long as the rejection and the stopping rules are not triggered.\n4. The theoretical results are corroborated experimentally on 3 tasks.", "weaknesses": "[Details in the Questions section]\n\n1. The proposed algorithm is easy to interpret. However, the paper does not explain all design choices.\n2. The experimental results support Theorem 4.2. However, Proposition 4.4 is not experimentally validated.\n3. Theorem 4.2 guarantees at least one \"acceptable\" language model response in the prediction set but does not say much about the individual responses. While the paper considers components of the responses, the response as a whole is not.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SkqVztrsrn", "reviewer": "Reviewer_zQVz", "summary": "This paper proposes a different kind of sampling for LMs. The idea is to extend ideas from Conformal Prediction to produce solution sets that contain diverse outputs. Generation follows a three step process involving sampling, accepting (if the answer is sufficiently high probability), and then possibly resampling if there aren't enough diverse answers in the set yet.\n\nEvaluation is done on a few tasks and LMs -- chest Xrays with a GPT2 small LM + ViT, news summarization on CNN/dailymail with T5-XL, and Open-domain QA on triviaQA sampled from LLaMA-13B. To the best of this reviewer's understanding the evaluation is done assuming access to the ground truth set of references, and so early stopping is done if the prediction set contains the answer already.", "questions": "for the 3-step procedure described in section 4, is it possible this will never terminate? To this reviewer, it seems a little bit sketchy to use ROUGE or BLEU to score diversity.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "To this reviewer, the application of conformal prediction to LMs could be interesting. Sampling in a way that preserves diversity and quality; and that returns a variety of different generations at the sequence level, could be a solid contribution. There's a lot of math here (mostly beyond the understanding of this reviewer, who is not an expert on conformal prediction in particular) but that could be helpful to people working in this space, for how to extend these ideas to LMs where the solution space is vast.", "weaknesses": "To this reviewer, it's a bit unclear what the benefit of this approach is (ie what problem it's solving). There's a worked example but it's a bit hard to follow as I'm neither an expert in conformal prediction nor cardiology. I guess my confusion comes down to this part:\n\n\"Like conformal prediction, our method offers a rigorous coverage guarantee by constructing prediction sets that, in our case, provably contain at least one acceptable response with high probability. Unlike conformal prediction, however, we do not enumerate the entire output space (which is impossible). Instead, we derive a calibrated stopping rule for sampling different outputs from the LM that get added to a growing output set of candidates, until we are confident that the output set is sufficient\"\n\nThis seems reasonable to this reviewer, but it also seems like from the experiments, the stopping rule involves having access to the test set answers, which seems not realistic. It's not quite clear what the objective is (minimize loss, minimize excess numbers of samples).\n\nI think this paper would also benefit from some stronger yet simpler baselines that don't follow conformal prediction. E.g. sampling N times and checking whether any of the samples is in the ground truth.\n\nI think this paper would benefit from comparison with other types of ways of controlling diversity, e.g. Stochastic Beam Search https://arxiv.org/abs/1903.06059 or NeuroLogic sampling https://aclanthology.org/2022.naacl-main.57/ . A worry I have with this approach (that I asked in the 'questions' field) is that the procedure in Sec 4 might never terminate because the LM might keep returning the same kind of answer over an over again (or at least a sufficiently strong LM might); maybe lexically constrained decoding would fix this.\n\nFinally there's the evergreen concern that this approach might become less important at scale; comparing e.g. GPT2small vs GPT2-XL could help here.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cDbsS3x76n", "reviewer": "Reviewer_7gqi", "summary": "This paper studies inference of responses generated by large language models (LLMs), \nleveraging ideas of conformal prediction. The specific aim is to construct a set of \nresponses for a given prompt $x$, such that at least one response in the set is \n``acceptable'' (compared with an expert response that we do not get to observe).\n\nThe main technical component is from [1], where the Learn then test (LTT) method is \ntailored for this specific setting. The authors evaluate the proposed method on the task \nof radiology report generation, news summarization, and open-domain question answering.\n\n[1] Angelopoulos, Anastasios N., et al. \"Learn then test: Calibrating predictive algorithms to achieve risk control.\" arXiv preprint arXiv:2110.01052 (2021).", "questions": "1. I wonder how the computational time (or relative excess samples) changes with regard to the choice of $k_\\max$?\n2. In the proposed method, $k_\\max$ is fixed. As pointed out by Remark 4.3, the choice of $k_\\max$ does not affect \nthe coverage guarantee, but could result in uninformative results. I wonder if it could be possible to treat $k_\\max$ as a tuning \nparameter as well, e.g., $\\lambda_4 = k_\\max$, and we can then optimize over all ``valid'' k_\\max.\n3. For the individual component pruning, I also wonder if the $\\gamma$ can be tuned jointly with the $\\lambda$'s to avoid the \nunion bound?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The paper is very written: it contains sufficient details and is easy to follow. \n2. This work provides an interesting application of the LTT framework. From my understanding, the major \ncontribution includes formulating the task as a risk-controlling problem, specifying the tuning parameters, \nand identifying the optimization problem that fits practical goals. \n3. The paper also provides abundant numerical evidence supporting the validity and efficiency of the proposed method.", "weaknesses": "I do not see obvious weaknesses of this work, but a few questions regarding some details (they are in the question section).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hT8ZxGE4Vw", "reviewer": "Reviewer_1uqq", "summary": "This paper proposes an extension of the learn-then-test framework which could help generating responses from language models with risk control. It proposes a sampling pipeline which involves adding generations to a prediction set until the set-level confidence score is above a threshold. The whole pipeline involves using LTT to search for viable configs of three hyperparameters (for the quality of single generation, the rejection/diversity of single generation, and the quality of the prediction set). The experiments were carried out on three medical and benchmark datasets, suggesting that this pipeline generally is able to find feasible hyperparams.", "questions": "1. How are the thresholds 0.4 and 0.35 for ROUGE-L determined? What does \"These thresholds are picked through manual validation\" mean exactly?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a first (yet quite solid) step forward in conformal prediction in NLG. It proposes a general framework to sample responses from language models with some given criteria (admission function), and allows independent research to improve the various scoring functions (quality estimate, diversity rejection criteria, etc.) in the pipeline. Breaking down the full generation into different components is also a nice way to address the question of UQ for longer texts.", "weaknesses": "The main weakness is the use of ROUGE-L as a proxy of the quality of the generation. This only captures the the lexical similarity between the generation and the reference, which undermines the experiments quite a bit, in the following sense:\n1. the LTT framework might return null hyperparameters, which might happen more often should the admissible function by the human be stricter than ROUGE\n2. ROUGE was also used in the pipeline (detecting duplicate) so it's kind of \"being its own judge\"\n\nAnother 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)