Selective Generation for Controllable Language Models
Authors: Minjae Lee
Kyungmin Kim
Taesoo Kim
Sangdon Park
Venue: NeurIPS 2024 spotlight (2024)
Keywords: trustworthy AI
selective classification
conformal prediction
hallucination
LLM
Primary area: safety_in_machine_learning
TL;DR: We propose novel selective generation algorithms to mitigate the hallucination issues of LLMs.

Abstract: Trustworthiness of generative language models (GLMs) is crucial in their deployment to critical decision making systems. Hence, certified risk control methods such as selective prediction and conformal prediction have been applied to mitigating the hallucination problem in various supervised downstream tasks. However, the lack of appropriate correctness metric hinders applying such principled methods to language generation tasks. In this paper, we circumvent this problem by leveraging the concept of textual entailment to evaluate the correctness of the generated sequence, and propose two selective generation algorithms which control the false discovery rate with respect to the textual entailment relation (FDR-E) with a theoretical guarantee: $\texttt{SGen}^{\texttt{Sup}}$ and $\texttt{SGen}^{\texttt{Semi}}$. $\texttt{SGen}^{\texttt{Sup}}$, a direct modification of the selective prediction, is a supervised learning algorithm which exploits entailment-labeled data, annotated by humans. Since human annotation is costly, we further propose a semi-supervised version, $\texttt{SGen}^{\texttt{Semi}}$, which fully utilizes the unlabeled data by pseudo-labeling, leveraging an entailment set function learned via conformal prediction. Furthermore, $\texttt{SGen}^{\texttt{Semi}}$ enables to use more general class of selection functions, neuro-selection functions, and provides users with an optimal selection function class given multiple candidates. Finally, we demonstrate the efficacy of the $\texttt{SGen}$ family in achieving a desired FDR-E level with comparable selection efficiency to those from baselines on both open and closed source GLMs. Code and datasets are provided at https://github.com/ml-postech/selective-generation.

Selective Generation for Controllable Language Models
Minjae Lee"
Kyungmin Kim"
GSAI
GSAI POSTECH
POSTECH
kkm9595955@psstcch ac. kr
Taesoo Kim SCS SCP GaTech taesoo@gatech. edu
Sangdon Park GSAI & CSE POSTECH sangdon@postech.ae ac.
Abstract
Trustworthiness of generative language models (GLMs) is crucial in their deploy- ment to critical decision making systems. Hence, certified risk control methods such selective prediction and conformal prediction have been applied to mitigating the hallucination problem various supervised downstream tasks. However, the lack of appropriate correctness metric hinders applying such principled methods to lan- guage generation tasks. this paper, we circumvent this problem by leveraging the concept of textual entailment to evaluate the correctness of the generated sequence, and propose two selective generation algorithms which control the false discovery rate with respect to the textual entailment relation (FDR-E) with theoretical guar- a direct modification of the selective pre-
Seni antee: SGen Sup and Senn SGen diction, is supervised learning algorithm which exploits entailment-labeled data, annotated by humans. Since human annotation is costly, we further propose a semi- supervised version, SGenSemi which fully utilizes the unlabeled data by pseudo- labeling, leveraging an entailment set function learned via conformal prediction. Furthermore, SGenSeni enables neuro-selection functions, and provides users with an optimal selection function class given multiple candidates. Finally, we demonstrate the efficacy of the SGen family in achieving desired FDR-E level with comparable selection efficiency to those from baselines on both open and closed source GLMs. Code and datasets are provided at htthtt::///g thttbb. com cctp///llppssteccc/eeeeeeeiieeee seapre/ccceeeeeetttveeeeeettttoi generatier
more general class of selection functions,
Introduction
Generative language models (GLMs) 12 3 4 have garnered significant attention for their ability
to generate human-level language primarily due to underlying transformer architectures [6]. However, GLMs raise concerns about generating hallucinated facts [7]. which is an undesirable property when they are used as knowledge retrieval sources. This issue can be mitigated by fine- tuning with human feedback [7] but it remains expensive in terms of training and labeling costs. Certified risk control methods such as selective prediction [9] and conformal prediction (10) are promising cost-efficient alternatives, which have been applied to the hallucination mitigation in various supervised downstream tasks
Equal contribution
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

objective bioycle
C: Where in the Bible does mention Sodon and Gomorrah?
Y
Acas The book of Genests mentions Sodom and Gomorrah.
Dest
LLM
At The objective of tour de Frunce to determine the best cycliit thruug stages challengee.
Selection Function & [Eaect Match))
Selection Function (Entalmmnt)
NO
Ia A.u
Does Á imply Awn??
IDK
don't know))
Fina { wnong! Do whetain] < 0 21-6
Two diffeeent selection function training (ik) rchemee, using sateiing (fett and proposed rightt methods with frozen LLM G01 respectivily.
Inference using an entallment swarn selective genecator, which sefers LLM & seloction function pair.
Figure 1: An overview and qualitative results of our method with GPT-3.5- The crux is to learn entailment-aware selective generator with an abstaining option that controls the rate of hallucination (in a false discovery rate) over generated sequences with a probabilistic guarantee.
The main bottleneck applying such certified methods to language generation tasks is that provided risk control guarantees require correctness labels during the learning process. Specifically, in classification, high-quality correctness labels can be directly acquired by comparing true and predicted labels using exact match (EM). However, this is not the case for language generation tasks, since multiple valid answers can exist for the same question. As correctness metrics such as EM and Fi-score do not account for the multiple valid answers, directly applying them to language generation tasks results in a significant gap between the true and measured correctness, which we call the metric misalignment. Thus, correctness evaluation metric that accounts for multiple answers is required.
In this paper, we resolve the metric misalignment problem by leveraging textual entailment to evaluate the correctness of generated answers and define the false discovery rate with respect to the textual entailment relation (FDR-E). Given two ordered sequences, premise and a hypothesis, we say that the premise entails the hypothesis if the hypothesis is true given the premise. Based on this notion of entailment, we propose two selective generation algorithms, SGen Sup and Seni, which are generalized versions of selective classification [9] control the FDR-E by abstaining from returning an answer when a GLM is uncertain of its answer.
In particular, Sup a direct modification of (9]. is supervised selective generator learning algorithm which requires entailment labels. This necessitates human annotations on textual entailment, where generated answer is the premise and a true answer is the hypothesis. As labeling is expensive and Sup solely relies on entailment-lakee labeled data, we propose a semi-supervised method, SGen Send. which enables the exploitation of deailmmnn--nnlbblee
data in learning selective generator by pseudo-labeling textual entailment using an entailment set function learned via conformal prediction entailment classifier originally developed for the natural language inference problem [15 [6]. the estimated entailment set function approximates a true entailment set function, which returns all entailed answers if true answer is given as hypothesis.
[00. Based
Additionally, SGen introduces the general class of selection functions for selective generation, called neuro-selection functions. In selective prediction, learning a selective predictor is equivalent to learning selection function, which an indicator function to decide whether to abstain from returning a prediction. The standard selective prediction algorithm (9] considers the class of single- threshold indicator functions using a pre-specified confidence-rate function. For the same risk level, the better the confidence-rate function quantifies the model's 's uncertainty, the less likely the selective predictor is to abstain from making a prediction. We refer to this as selection efficiency henceforth. As appropriate confidence calibration for language generation remains challenging, optimizing single-threshon indicator function with a poorly calibrated confidence-rate function leads to low selection efficiency. Instead, generalize the selection function by using multiple- -threshod indicator function with trainable features. Furthermore, SGen Semä provides a user with an optimal class of selection functions among possible candidates in terms of the FDR-E
Finally, we empirically demonstrate the efficacy of SGen over open and closed source GL.Ms, where we consider SGen one of our basclines as it is direct modification of (9). To validate

---

our method and its theoretical guarantee, we create new dataset on textual entailment using the Natural Questions (NQ) dataset [77] for each GLM. Given a question and answer pair, the textual entailment is labeled by letting generated answer as a premise and the true answer in declarative form as a hypothesis. As communities lack human-annotated ontailment-labeles data for language generation, we believe that our dataset contributes to the hallucination evaluation of GLMs. For both open and closed source GLMs, SGen Semi is effective in achieving a desired FDR-E level with better selection efficiency compared to basclines.
1.1 Related Work
We introduce two main research directions to mitigate hallucination in GLMs.
Heuristics for hallucination mitigation. The hallucination in language generation usually refers to the situation where a GLM generates wrong answers with high confidence, which hinders the reliable deployment of GL.Ms. As fine-tuning methods are expensive, heuristics for hallucination mitigation without tuning have been proposed [18] 19]. Notably, [19] proposes a performant hallucination detection method, which quantifies the self-consistency among multiple generated answers for the same question using textual entailment models to detect the hallucination. However, these methods do not provide certified control over the occurrence of hallucinated contents.
Certified methods for ballucination mitigation. Conformal prediction outputs a prediction set that guaranteed to contain a true label with high probability, where a provided coverage guarantee is model-agnostic under a mild assumption on data [10]. Although this property enables the safe
deployment of complex models and has made conformal prediction popular [T0. 12
13 20 21 22
the constructed prediction sets in language generation are often less-informative due to an unbounded
label space, which frequently renders the coverage guarantee ineffective [23] 24] To restrict the
prediction set to a moderate size, [23] constructs the prediction set over answers by sampling them sequentially, while still satisfying the coverage guarantee. Still, post-selection of answers from the prediction set is necessary for final decision making, which may result in the selection bias
[25] 26). [27] (8) decompose generated answers into alignment-labeled sub-claims and return a set of sub-claims that contains no contradiction with high probability via conformal prediction. Even though the post-selection is unnecessary, it requires expensive alignment labels for every sub-claim.
Unlike conformal prediction, selective prediction directly manages target risk at desired level by introducing an abstaining option on unsure predictions. [9] proposes selective prediction method mainly for classification, which learns threshold-based selection function that controls the false discovery rate (FDR) to a desired level. [24] generalizes the selective prediction to language generation. However, their theoretical guarantee is not focused on the target risk to control, but consistency property of a surrogate loss function with respect to a true loss function in optimization process. 22) concurrently published with our paper, proposes certified selective generation method for context-givee language generation which controls the FDR. Unlike [ which takes the number of selected samples as constraint in learning the selection function, 22 set the power constraint. However, as [24] does, they require an additional calibration set for training an entailment scoring function. Importantly, while existing selective generation methods supervised learning methods, we propose a semi-supervised learning algorithm that can fully leverage entailment-unlabelee data.
2 Background
While consider general language generation tasks, we confine our scope the open-ended question-answering task and define the notation accordingly for the sake of clarity and for maintaining consistency in descriptions using a tokenizer, such as Byte Pair Encoding [30], and let W denote token sequence space, defined as W
the experiment. Specifically, let W denote token space constructed
L Wi, Let (x,y) E X' x y be a question and answer sequence pair, where X' = W and y == V refer to the token sequence spaces of questions and answers, respectively. We assume the answer sequence is in a declarative form. Finally, X,.j refers the sub-sequence of from the i-th to the j-th token.
2.1 Language Generation
Given question as input, GLM generates answer through the sequential process called decoding, which we call language generation. Here, we consider the greedy decoding, deterministic generation process described as follows. Let pM X x W + R2 denote a GLM which returns a next-token
3

---

distribution given the input sequence x, where Σ Par x) = for all x E X. A language generator G X + y using greedy decoding sequentially generates tokens from the GLM as follows: ýi == arg maX (M w (x, v1:--)) for i 2 2 and ý1 == arg max weW Pas (w x). The generator G returns a generated answer y == G(x) and terminates the decoding process when the end-of-sequence (EOS) token is returned. Here, the conditional probability of the answer ý is defined as fM (x. f) = (rr x) I ( (x, (1))))))) commonly used as its uncertainty measure.
2.2 Selective Prediction
Selective prediction refuses to make prediction by returning "I don't know" (IDK) if the prediction
is uncertain. In classification, the selective classifier 3 consists of pair of classifier á and
[G(x) if 6(x) = where ((x) ==
selection function $, and is defined follows: S(x) == IDK otherwise
arg max f(x,)) y). Here, f(x. y) refers to an estimated likelihood of the given input x for being a class y, determined by an underlying classification model f. Although the selection function can be of arbitrary form, the common choice is a single threshold indicator function using the maximum likelihood as the confidence-rate function, i.e., $(x) == [(f(x, 8) 2 r). Here, the confidence function is defined to quantify the uncertainty of the model's prediction. Under the independent and identically distributed (i.i.d.) assumption, [9] proposed the certified threshold learning algorithm which controls the false discovery rate (FDR) with respect to the EM metric with the PAC guarantee,
where the FDR is defined as REM == (ū((x) + y S(x) + IDK). Since EM considers the answer (x) to be correct when it is exactly the same as the reference answer y, it is an inappropriate correctness metric for language generation problems that can have multiple valid sequences for the same input. This results in learning too conservative and vacuous selection function for language generation, which is empirically verified by our experiments. Thus, we leverage the textual entailment to evaluate the correctness of the generated sequence to alleviate the metric misalignment problem.
2.3 Textual Entailment
Natural language inference (NLI), also denoted as recognizing textual entailment, predicts whether one sequence implies another. The former refers a premise (p), and the latter refers to hypothesis (h). Since the release of two large-scale benchmarks of ordered sequence pairs labeled with textual entailment [SS [6), a number of transformer- based entailment classifiers have been proposed and shown impressive results. Each pair is classified into one of three categories: entailment if h is true given p: contradiction if h is false given p; and neutral otherwise. In this paper, we define the entailment scoring function as f (G(x), y) == 1 pr. (rroniirudicc p G(x), = y) to estimate and pseudo-label the correctness of Gxx). where y (conttradicc p = G(x), h = y) is the likelihood that (xx) contradicts y. While pseudo-labelin enables the full exploitation of unlabeled data to learn a selection function, controlling the mislabeling error remains as a challenge.
2.4 Conformal Prediction
Conformal prediction (10) outputs a prediction set quantify the uncertainty of given model with model-agnostic correctness guarantee under minimal assumptions on data generating process. Specifically, under the i.i.d. assumption. PAC conformal prediction (1I) incorporates the interpretation of tolerance regions [31] and training-conditional inductive conformal prediction (20) through the
lens of PAC learning theory 322. In this paper, we adopt the PAC prediction set learning algorithm to control the rate of mislabeling error in lseudo-labeled samples used to learn selection function for selective generation. Secction A. for detailed discussion on conformal prediction.
Scalar-parameterized Conformal Set. In this paper, we consider a conformal set C. ~> 2 parameterized by scalar [1] 33 C(x) == (y E y f(x, y) 2 7), where E H is a scalar parameter to learn, H is a hypothesis space (e.g.. H a finely discretized non-negative real numbers), and f X x y + R=0 is called a scoring function. The scoring function corresponds model whose uncertainty is to be quantified, where the softmax output is a common choice in classification. Specifically, (x, 3) measures the likelihood of y as response given x as input.
target
PAC Guarantee. The PAC prediction set learning algorithm outputs conformal set Ć which upper Pty & C(x)) a desired level (0, where the
bounds a miscoverage rate RMc(C) miscoverage rate can be generalized to risk Roi (Ō) = EFffo (C, x,)),, on any indicator losses that are monotonic with respect to т. The algorithm is probably approximately correct (PAC) in

---

the sense that it provides a calibration data-conditionas guarantee at every risk and confidence level. Specifically, controls the risk a desired level irrespective of which calibration data used to learn C with a desired confidence á E (0. 1) as follows: P ((Roi(C) S c} 2 1 ó, where the probability is taken over the calibration set Z ~ DD to learn the conformal set. In this paper, we leverage the PAC conformal set for a pseudo-labeling function such that the guarantee on the labeling quality provides the overall PAC guarantee in semi-supervised selective generator learning algorithm.
Algorithm. The PAC conformal set learning algorithm ABinom (X' x ) + H. [T] 20 34 returns the conformal set parameter f, where H. is finely- dicereddsceetized R20- Specifically, the algorithm
returns f max+EH subject Bimem (Rr: n, 5) E, where k, Li=1 foi (Č. (C,x;, yr). Letting F(k; n. 8) be a cumulative distribution function of a binomial distribution with n trials and success probability 0, UBinom (k; nı, 5) inf (0 E [0, 1] (k;; n. 0) S 83 U (1) is an upper binomial tail bound that satisfies [ (Ō) S Bimoo (ky; n2, 0)}
5, where å the desired confidence. Note that we similarly denote lower binomial tail bound by Binom- If optimization in the algorithm ABinom is infeasible, the algorithm returns & vacuous conformal set. Thus, the algorithm is PAC, and see Section A. for proof.
2.5 Calibration
In classification, calibration aims to adjust the classifier's maximum likelihood response, or confi- dence, to be correct. We say the classifier response ʃ : X2 x ) + R2o is perfectly calibrated with respect to a distribution D over X' x ) and classifier if {y j(x) f(x. (xx)) = t] = for all t E [0, 1] [35 (3). Calibration aims to find the classifier response such that it is perfectly calibrated asymptotically. In this paper, we make an interesting connection between calibration and selective generation. In particular, given the definition of the perfect calibration for a language scoring function fas, we formally provide sufficient condition for selective generator to control the FDR with respect to the textual entailment relation at any desired risk level.
3 Problem: Selective Generation
Let x X' be question and y E Y be answer, assuming that each question has desired answer. Here, we assume (x ~ D', where D' is a data generating process of wnestion-answering pairs. Then, given a generator G X' + V, we consider a selective generator S X + y' {IDK} which refuses to return Gxx) if selection function 8(x, G(x)) E {0, 1} deems uncertain as follows:
[G(x) IDK
if (xx, G(x)) =1 otherwise.
5(x) =
Our main goal is to learn a selective generator $ control generalized false discovery rate (FDR) with respect to a relation R as
RR(S)= = (o(5)=P((GGR) (((((())))))) & R S(x) * IDK
(I)
Here, the probability is taken over examples (x, e, v). where e = I((G(x), E R) an ad- ditional label to be annotated due to unknown R and E 10, is visibility flag of e for semi- supervised learning. For the data generation of (x,y, e, v), we assume that a label e is observed with an unknown success probability of Po. independent of the generative process of (x. e). i.e., (x. y,e,)) v) ~ D = D'. V. D'.V.
where D' a distribution over X' xx)xx x (0, 1} and V = Bernouli(p.)) Note that the definition of e, 'D' varies by generator G even with the same data generating distribution of (x, y). In this paper, we design a learning algorithm A that returns selective generator $ to control the generalized FDR with respect to R within a desired level E E (0. with probability at least 1 - 5 E (0, i.e., PP (AZ)) < =} 2 1 - 8. Here, the probability is taken over calibration set Z ~ D". This guarantee is called a probably approximately correct (PAC) guarantee 32). Among selective generators that satisfies the PAC guarantee, we choose one that minimizes the ratio of IDK-answers with the highest selection efficiency. The main challenge is to find a sample and selection efficient PAC algorithm for any E and 5 along with designing relation R for structured Frequently, we may not obtain a PAC algorithm for any c, so in this
labels, as in intestion-answeriie paper, we use relaxed notion of controllable instead of correct if the algorithm provides minimum achievable risk beoyond a given e.
5

---

4 Semi-Supervised Learning for Controllable Selective-Genrratoo
In this paper, we leverage the textual entailment as the evaluation metric in language generation to consider multiple valid answers in a principled way, and propose two selective generator learning algorithms which control FDR with respect to the textual entailment: SGen and SGen Semi
4.1 False Discovery Rate via Textual Entailment (FDR-E)
textual entailment relation Rg is an ordered subset of y x y where (y', E Rø yf entails y. In canttion-answringg as an example, the generated answer G(x) is correct if the reference answer a logical consequence of G(x).
other words, G(x) is valid if G(x) E E where the true entailment set function Euse: : ) - 2 is defined as follows: (y) = {y' E ) (y', E Rg}. Then, an FDR with respect to the entailment relation R (FDR-E) that we aim to control follows:
RR (5) = P(G(x)= & Eme Sxx) + IDK),
where the probability is taken over labeled examples, ie., (x, D. Here, the label is specifically called entailment label, i.e., G(x) E Fy (y). Then, for any G, D, V. and S, the FDR-E can be decomposed as follows:
D3 [G(x)= & Erme (y)) PD to-v-11 = 1) PP D {e -3 03
P PDg (v 03 PD Po - -},
(A)
(B)
(C)
(D)
(b)
where Pp
= P S(x) * IDK). Note that as (x,y, é) and e are independent, (A), (C), and
(E) in 22 are of the same quantity, which is the target risk that we aim find an upper bound.
4.2 FDR-E Bound for Supervised Learning
We first propose the supervised learning algorithm SGen Sup (Algorithm 8). a direct modification of [ to language generation tasks. In particular, SGen is supervised method in the sense that it solely exploits labeled examples Z == {(x, y. e) (x.y, y, e, v) E Z A U = }} to learn a selective generator that controls the upper bound (C) in (2). Note that for supervised learning, we assume that (B) in (2) is always 1, so we only consider the the upper bound (C) via the binomial tail bound as (9.
4.3 FDR-E Bound for Semi-Superrised Learning
As SGen requires human annotations for entailment labels and makes use of abundant unlabeled examples Zu == {(x y) (x.y.e,v) E 2 A u = 0}, we further propose a novel semi-supervised learning algorithm SGen (Algorithm 5). which fully exploits both Z and Zy while controlling the FDR-E in 2 In particular, we (1) estimate a true entailment set Finu via conformal prediction
with labeled examples Zg and then (2) use the estimated entailment set É to annotate pseudo-labels on Zy Finally, we (3) use both labeled and pseudo-labeled examples learn selective generator. Interestingly, this heuristic-lookii algorithm could be rigorous algorithm that controls the FDR-E of selective generator, which will be described in the following sections.
4.3.1 FDR-E Decomposition
Senn leverages unlabeled examples by esti- mating an entailment set as pseudo-labeling function. However, the estimation error intro- duces wrong pseudo-labels. Here, we consider rigorous way to derive the FDR-E upper bound by controlling the estimation error of the pseudo- labeling function. In particular, two different types of estimation errors of an estimated entail- ment set E are illustrated in Figure 2) i.e., a false negative entailment rate (FNER) and false en- tailment rate (FER). This results in the following decomposition.
26
NER
0
EAEE
FRR
Figure 2: Decomposition of a false discovery rate with respect to an entailment set Euue (FDR-E). Here, 2f. {xx y, e, v) G(x) E E(y)).
Lemma 1. (E) in 2 is decomposed as follows:
PD (e
0} = PD (e = =,, -6=11
PD (e 1, 0) +
PT (ē=0) 0}
(3)
(9)
FER
FNER
NER

---

Here, the first two terms are related to the entailment label estimation error and the last term is the approximate FDR-E using pseudo-labels. As three terms are inter-related, we choose control the FER term to control (E) in ② via conformal prediction in the following section.
4.3.2
Pseudo-labeling via Conformalized Entailment Set Learning
SGen leverages the PAC conformal prediction for the entailment label estimation to control the mislabeling error. Specifically, we estimate the true entailment set function Line via estimated entailment set É using Zg, where use the entailment scoring function fE scoring function, i... Ely) {y' )/ TE(y','' y) 2 TE}. Here, the corresponding loss x,,,x,y, y, e) [ 0 A G(x) E(y)) a monotonically non-increasing function with respect to Tg. so we can use the PAC conformal set learning algorithm. Given a desired risk Eg and confidence óg level, the corresponding algorithm AFER (i.e., Algorithm 1) returns the estimated entailment set function E which controls the false entailment rate (FER) of pseudo-labeled examples REER ()- = p {e 0 A G(x) E E(y) with the following PAC guarantee, where the probability is taken over training examples from Dg.
P ( EE) S E 2 - 6g.
(4)
4.3.3 FDR-E Bound
We then bound the FDR-E for semi-supervised learning, i.e. (E) in (2. via the PAC guarantee by the conformal set learning on Z and the binomial tail bound on ZF and Zy. In particular, the FER is upper-bounded by Sæ, the FNER is lower-bounded by the binomial tail bound using Zr, and NER is by the binomial tail bound using Zy. These bounds hold with high probability, and therefore combined via union bound, as in the following lemma. See Appendix G for proof.
Lemma 2. Let Zg == {(x. e) E ZE S(x) F IDK) and Ze == {(x,)) ) E Zu 15(x) * IDK). For any G. D. V, and S. if == AVER( 2g) satisfies IP,, (RrER( () [E 2 - 8///2, we have
PDfe- = 0} S EE - Limom (h: Zgl, 8',/) + Uiinom (i: (Zull,8)) =: USSL
(5)
with probability at least 1 - 8'r - 8's. where the probability is taken over Z. Here, k L(e E( 1 G(x) & B(y)) and i i= Eixyred 1(G(x) & B(y)).
Notably, each of three bounds holds over a conditional distribution Dg. but Lemma 2 relaxes this to an unconditional distribution D for our final FDR-E guarantee.
papper-prameterre Eg, which controls a trade-off between the FER and other terms. To find a best tradc-off, we optimize Eg to minimize the upper bound ( among Q candidates of g via AUsu described in imAlgorithmm 3 This optimization algorithm can find tighter FDR-E bound, as in the following lemma. See Apepedddi for proof.
Optimizing the FDR-E Bound (5) Lemma 2 introduces
Lemma 3. Let USSI be as in 5 and Q be the Q candidates of Eg- Then, we have
Po(e = =3 S SS. = min USSL
(6)
EEEQ
with probability at least 1 - 52 - /2, where the probability is taken over Z.
Note that for semi-supervised learning, the upper bound of (B), (C), (D), and (E) in (2) should be provided. The upper bound of (E) is provided in (5). which we denote by USSL. The upper bound of (B), (C), and (D) are denoted by WSL. USL, and WSsL. respectively, each of which is computed by the binomial tail bound. See Algorithm 4 and the proof Theorem for details.
4.4 Neuro-selection Functions
The FDR-E bounds for both supervised and semi-supervised learning are crucial for controlling the final FDR-E of selective generator given a selection function $. But, the choice of the se- lection function critical for good selection efficiency and here we discuss better selection function than the standard one, i.e., s(x) == 1 (fax (x, G(x)) 2 TS) for Ts E Rzo. In particu- lar, certified selective classification (9] considers the single-threshold indicator function using the maximum likelihood as the confidence rate function. For the language generation, the conditional probability of the answer y, i.e., J'r, (x. 9). would be a natural and commonly-used candidate. However, it is known to be poorly calibrated 37. an alternative would be self-consistency
7

---

score, ie.. fM, (x, G(x))= = k==1 E fe( G(x)), where yı: are generated answers with the same question x but different random seeds. It empirically shown that the self-consistency score properly quantifies uncertainty when language model is uncertain of an answer [19]. The importance of score calibration with respect to the true entailment relation is demonstrated in [emma 4 which provides the sufficient condition for the selective generation algorithm using the single-threshold indicator function (Algorithm 5) to control the FDR-E at any level. See See Appendixx foor a proof.
Lemma 4. we have access Eise and fM is perfectly calibrated with respect to Euse, the FDR-E is monotonically non-increasing in Tg.
However, as 337 points out, calibrating the language scoring function remains an uneasy task, os is still an active research area. Therefore, we propose general class of selection functions, neuro- selection finnttinss, which is the multiple-threshoe map +b x + R=" as follows: 8(x; Φ W. b) = -== (x), + b; 2 O, where W E " and b Rux1 are linear proejction and bias terms, respectively. In this paper, we only consider two specific sub-classes of neuro-selection functions, where the former reduces to learning the single-threshold selection function using a scoring function (Algorithm 3) and the latter reduces to learning the bi threshold selection function using two scoring functions (Algorithm 6p. Only the bias term b is the learnable parameter for both algorithms, where the others set as hyperparameters. Specifically, W 11. 4 (x) = (x, G(x))]. and b -TS for Algorithm 5 while W 12, (2(x) = [f, (x, G(x)) fM. (x, G( and b = - [TS.1, Ts.2]" for Algorithh 6 if two promising scoring functions exist. Here, developing selection function learning algorithm where W and (b-) are also fully learning parameters is left as future work. In the following section, we introduce our algorithm that chooses the optimal combination of scoring functions via neuro-selection functions.
indicator function using possibly learnable feature
4.5 Semi-Supervised Selective Generator Learning Algorithm with Neuro-Selection
Semi is a ceni-supervised learning algorithm for certified selective generation, which fully exploits unlabeled data in learning selection function via certified pseudo-labeling and uses neuro-selection function for choosing an optimal combination of scoring functions. In particular, SGen solves the following optimization problem over selective generators H such that $ closely satisfies the equality in the constraint, as described in Allgorithmm 7
AsGen : findsen $ subj. to WSLUULL + wSsL uSSLU OPT S Eg,
(7)
Here, S E H. has selection function 8(x; (2 diag(w), b), where w E {[L, OJ" 10,00,,01111 10. and b E R Note that
an additional term U, which is the FDR-E bound given the selective generator S (i.e., Algorithm 4) and informs the infeasibility of the optimization. The proposed Algorithm 7 satisfies the following controllability guarantee. See Appendix I for a proof.
Theorem 1. AsgenSent satisfies the following controllable guarantee on the FDR-E, i.e.,
P(P(((x)= & Emme (y) S(xx) + IDK] S 50) 1-
(8)
where the inner and outer probabilities are taken over (x,y,e, ~ D and Z ~ D", respectively, and ($, Ú) == Seme (Z). Here, 8 == dw + 5s + 8g is desired confidence level, where ow is for the upper bounds on wSl. and WSst. 0s is for (C) in (2) and the NER, and dG is for the FER and FNER.
Here, Astentm is controllable in the sense that it upper-bounds the FDR-E of learned selective generator desired level gg or at least to minimum achievable level Ó with confidence
5 Experiments
We demonstrate the efficacy of our methods in controlling the FDR-E on pre-trained GLMs under various setups. We use two GLMs, GPT-3.5-Turbo and Alpaca-7B alongside the Natural Questions (NQ) dataset to annotate entailment labels for question-answer pairs. Details on model configurations, datasets, and additional experimental results can be found in Secciinn A.3 and (Appendix K
Methods. We consider two heuristic semi-supervised algorithms, SGen H-Sen and SGen gorithm 9) and an unsupervised learning algorithm (9] SGengN (Algorithm 10) as baselines to
AI
show the efficacy of our certified semi-supervised method SGenSent (Algorithm 7). SGenff-Sen Semi and
SGen exploit the unlabeled data by aeudo-labeling textual entailment based on threshold
as hyperparameter without any guarantee mislabeling error. SGen B- Semi additionally filters out
8

---

Table 1: Comparison results of semi comi-supervised methods. Here, Ze and Alpaca-7B 7B. The best results are highlighted in bold and results from methods that do not satisfy desired FDR-E guarantees in learning are underlined.
10K for
Models
GPT-3.5-turbo
Alpaca-7B8 7B
Heuristic
Certified
Heuristic
Certitied
Methods
SGenb.
SGenyri
5Gengy
SGenjeas
SGen Seei
SGenn
Seer
SGenori.
SGengx
SGengoks
SGen Seei
FDR-E efficiency
0.0958
0.0283
0.1338
0.0609
0.1589
0.0231
0.0068
0.0359
0.0359
0.0685
Jan
0.4189
0.1719
0.5495
0.2829
0.7334
0.0915
0.0332
0.1580
0.1580
0.3173
FDR-E
0.1839
0.2002
0.0914
0.1785
0.1589
0.0698
0.0732
0.0549
0.0698
0.0685
fal
efficiency
0.7911
0.8183
0.5332
0.7769
0.7334
0.3207
0.3390
0.2563
0.3200
0.3173
average efficiency|
0.6050
0.4951
0.7334|
0.2061
0.1861
0.3178
Table 2: Qualitative results by Alpaca7B.
Question x
Who is the actor who plays Draco Mal- foy?
When did the movie Benjamin Button come out?
Thomas Andrew Felton plays Draco Malfoy in the Harry Potter movies.
The movic Benjamin Button come out December 25, 2008
Correct Answer y
The movie The Curious Journey of Benjamin Button was released in 2008. (correct)
The actor who plays Draco Malfoy is Tom Felton. (correct)
Generated Answer G(x)
SGengx
rejected
rejected
SGen Semi (ours)
accepted
accepted
pseudo-labeled sample if its entailment score is below specific threshold. SGengx is a certified unsupervised method that takes the EM metric for measuring the correctness. We also report re- sults on SGen (Algorithm 5) for two different scoring functions .fM, and fMg. used in SGen Semi is certified oupi-supe learning algorithm using a single-threshold indicator function given scoring function. We also take SGen Sup (Algorithm 8) as a baseline, since it is a direct modification of [9 to the language generation problem.
SGendors
Scoring Functions. We use the conditional probability of answer as fas, and the self-consistency score 199 as fM, since our goal is to generate the sequence which is not only logically consistent to the true answer but also linguistically correct.
Control Parameters. To control an FDR-E, we use two user-specified parameters (s, where we use (0.25, 0.02) unless specified. For our methods (i.e., SGen SGen and SGen Seni-Sup we have five control parameters (Es, 6g, dg, dw), where we maps follows: Eg E, óg
(8 - Sw )/2 /2 0g = (6 ow) ) 02,ōw = 10 For other methods without using entailment sets, Algorithm 8 Algorithm 9 and Algorithm 10 we use E and d accordingly. Additionally, we use
Q = 5 for Algorithh 3|
our method Senn can overall achieve desired FDR-E guarantees with better efficiency compared baselines. Depending on the quality of scoring functions (e.g.. f',,), our variation SGengeng may not find a selective gen- erator that satisfies a desired FDR-E (denoted in the underlined FDR-E). The heuristic methods, ie., SGeng- and SG do not provide theoretical guarantees on FDR-F In Figure 1 and Table we can correctly predict even with the complicated answers, c.g., which have many equivalent words, because we do not rely on the EM metric. We conducted 100 random experiments for each method to show how well FDR-E is bounded under desired FDR-E. As shown by the green boxes In Figure 4| which are successfully bounded under Ss 0.25, we can see that the FDR-E for learned selective generator is well controlled below Es under the test environment. Among the certified methods with theoretical guarantees, results appear to align well with the expected theoretical basis.
FDR-E Guarantee and Efficiency. As can be seen in Table 1
Why Entailment Labels. As expected and can be seen in Table by comparing SGengw and SGen a metric like EM cannot measure correctness correctly. Unlike classification, generative tasks can have infinite number of true answers so it is not likely to have exact match. Instead, entailment labels provide semantic correctness, so SGen Sup can perform better and more efficient than SGengy.

---

0.25
FDR-E
efficiency
0.25
FDR-E
efficiency
230
630
-0.4
022
3.24
0.22
3.2
120
020
10R5
2.25
0.3
0.50
3.55
0.6
Methods
Methods
(a) SGen Alpaca7B
Send
SGen Alpaca7B
0.25
FDR-E
efficiency
0.25
FDR
affiienccy
330
3375
0.90
1DR6
3730
FDR-E
3768
3.35
-22
3.50
3.000
3.8
3.08
3.000
Methods
Mathhds
SGen GPT-3.5-turbo
(d) SGen GPT-3.5-
Figure 3: Efficiency results over different numbers of unlabeled samples. (a) and (b) use SGen Semi with faz score. (c) and (d) use Seen that has neuro-selection function. Both methods show increasing performance more unlabeled samples Zy are used. For each experiment, the values were measured after averaging 10 random splits and an error bar means standard deviation.
Why Semi-Supervised Learning. We observe that our semi-supervised learning for selective generation is effective. In particular, the fully supervised methods in Table Jcchieess the efficiency of 0.7535 and 0.2959 for GPT-3.5 and Alpaca-7B, respectively, with the entire labeled samples ZE (when they satisfy e-FDR-E guarantee). Compared to these, the proposed semi-supervised method SGen Semi Table achieves the efficiency of 0.7334 and 0.3173 for GPT-3.5 and Alpaca-7B, respectively. by only using 75% of labeled examples. Additionally,
observe that more unlabeled samples are beneficial to achieving better efficiency as can be seen in in/iiguee 3] This implies that
approximate the entailment set well and the size of Zu is enough, we can enjoy our certified pseudo-entailment labeling by the semi-supervised learning even with small Zg.
Why Neuro-Selection. It is hard to manually find well calibrated scoring function. But, given multiple scoring functions, a neuro-selection function learns to choose right scoring functions that achieves desired FDR-E and maximizes selection efficiency. This is empiricially validated in Table as SGen better on average efficiency.
Conclusion
We propose selective generation, a generalized version of (9] for GLMs handle semantic correctness between two structured answers. To this end, we leverage logical entailment to define new entailment-basee based FDR (FDR-E) metric. As obtaining entailment labels are expensive, we propose novel semi-supervised learning for selective generation by using entailment sets as pseudo-labeling function. To enhance the low selective efficiency due to inefficient scoring functions, we propose neuro-selection functions for effectively optimizing scoring functions for better selective efficiency and the FDR-E guarantee. The efficacy of our proposed algorithms Seni and SGen Sup are theoretically and empirically justified.
Limitations. Our algorithm needs the i.i.d. assumption for correctness guarantee, which can be violated in practical situations. We leverage expensive entailment labels, where the labels are obtained by considering logical entailment between a true answer and generated answer. This limitation partially mitigated by proposing the semi-supervised method to propagate entailment-labeled samples samples without entailment labels. Also, our results show the empirical FDR-E is not much closely bounded under especially on Alpaca7B, which implies that we may need tighter FDR-E bound.
10

---

Acknowledgements
This work was supported by Institute of Information & communications Technology Planning Evaluation (IITP) grant funded by the Korea government (MSIT) NNo.RS-2019-1111906 Artificial Intelligence Graduate School Program (POSTECH) (50%); RS-2024-00457882, National Al Re- search Lab Project (25%); RS-2024-00509258, Global AI Frontier Lab (25%)). Also, appreciate valuable comments by NeurIPS reviewers.
References
[1] 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.
[2] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners, 2020.
[3] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thé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.
[4] Rohan Taori, Ishaan Gulrajani. Tianyi Zhang. Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. Stanford alpaca: An instruction-followinn llama model. 2023.
thub. cttm://atss.llbb/sttafor.......
[5] OpenAl Team, Team, ChatGPT. https:/cchat.openai.cmm// 2021.
[6] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[7] Margaret Li, Stephen Roller, Ilia Kulikov, Sean Welleck, Y-Lan Boureau, Kyunghyun Cho, and Jason Weston. Don't say that! making inconsistent dialogue unlikely with unlikelihood training. In Pruceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 4715-4728, Online, July 2020. Association for Computational Linguistics.
[8] Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback, 2022.
[9] Yonatan Geifman and Ran Yaniv. Selective classification for deep neural networks. Advances in neural information processing systems, 30, 2017.
[10] Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic learning in random world. Springer Science Business Media, 2005.
[11] Sangdon Park, Osbert Bastani, Nikolai Matni, and Insup Lee. Pac confidence sets for deep neural networks via calibrated prediction. In International Conference on Learning Representations, 2020.
[12] Stephen Bates, Anastasios Angelopoulos, Lihua Lei, Jitendra Malik, and Michael Jordan. Distribution-free, risk-controlling prediction sets. arXiv preprint arXiv:2101.0270; 2021.
[13] Isaac Gibbs and Emmanuel Candès. Adaptive conformal inference under distribution shift,
2021.
11

---

[14] Sangdon Park, Osbert Bastani, and Taesoo Kim. Acon": Adaptive conformal consensus for provable blockchain oracles, 2023.
[15] Samuel Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. In Proceedings of the 2015 Conference on Empirical Methods in Natural Longuage Processing, pages 632-642, 2015.
[16] Adina Williams, Nikita Nangia, and Samuel R Bowman, A broad-coverage challene corpus for sentence understanding through inference. In Proceedings of NAACL-HLT, pages 1112-1122, 2018.
[17] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:453-466, 2019.
[18] Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering, Transactions of the Association for Computational Linguistics, 9:962 977, 09 2021.
[19] Potsawee Manakul, Adian Liusie, and Mark Gales. Selfcheckgpt: Zero-resource black-box hallucination detection for generative large language models. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
[20] Vladimir Vovk. Conditional validity of inductive conformal predictors. Machine learning, 92(2-3):349-3777 2013.
[21] Adam Fisch, Tal Schuster, Tommi Jaakkola, and Regina Barzilay, Few-shot conformal prediction with auxiliary tasks, 2021.
[22] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets for meta- learning. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[23] Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi S. Jaakkola, and Regina Barzilay. Conformal Language Modeling, June 2024. arXiv:2306. 10193 [cs].
[24] Christopher Mohri, Daniel Andor, Eunsol Choi, and Michael Collins. Learning reject with fixed predictor: Application to decontextuulizaatin., arXiv preprint arXiv:2301.09044, 2023.
[25] Ying Jin and Emmanuel Candès. Selection by Prediction with Conformal p-values, May 2023. trXiv:2210.014000 [stat].
[26) Ying Jin and Zhimei Ren. Confidence on the Focal: Conformal Prediction with Selection- Conditional Coverage, March 2024. 2Xiv:2403300366 [math, stat].
[27] Christopher Mohri and Tatsunori Hashimoto. Language models with conformal factuality guarantecs. arXiv preprint 17X1v.2402.10998, 2024.
[28] John Cherian, Isaac Gibbs, and Emmanuel J. Candès. Large language model validity via enhanced conformal prediction methods, June 2024. arXiv:2406.0977 [cs, stat].
[29] Yu Gui, Ying Jin, and Zhimei Ren, Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees, May 2024. arXiv:2405.10301 [cs, stat].
[30] Philip Gage. A new algorithm for data compression. C Users Journal, 12(2):23-38, 1994.
[31] Samuel S Wilks. Determination of sample sizes for setting tolerance limits. The Annals of Mathematical Statistics, 12(1):91-9, 1941.
[32] Leslie G Valiant. theory of the learnable. Communications of the ACM, 1731111134-1144 1984.
12

---

[33] Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In European Conference on Machine Learning, pages 345-356. Springer, 2002.
[34] Sangdon Park, Edgar Dobriban, Insup Lee, and Osbert Bastani. PAC prediction sets under covariate shift. In International Conference on Learning Representations, 2022.
[35] Morris DeGroot and Stephen Fienberg. The comparison and evaluation of forecasters. Journal of the Royal Statistical Society: Series D (The Statistician), 32(1-2):12 22, 1983.
[36] Bianca Zadrozny and Charles Elkan. Transforming classifier scores into accurate multiclass probability estimates. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 694-699, ACM, 2002.
[37] Yao Zhao, Mikhail Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Peter Liu. Calibrating sequence likelihood improves conditional language generation. In The Eleventh International Conference on Learning Representations, 2022.
[38] Dorottya Demszky, Kelvin Guu, and Percy Liang. Transforming question answering datasets into natural language inference datasets. arXiv preprint arXiv:1809.0292: 2018.
[39] Jifan Chen, Bunsol Choi, and Greg Durrett. Can NLI Models Verify QA Systems' Predictions?, September 2021, 100::2200 [cs].
13

---

A Discussion
A.1 Conformal Prediction
Conformal prediction [TO] provides a promising way to quantify uncertainty of a model with a correctness guarantee under minimal assumptions. Here, consider PAC prediction sets [[T]. an interpretation tolerance region [31] and
inductive conformal prediction [20] in
the lens of PAC learning theory 32 (i.e., learning "good" function within function family from data). This interpretation inspires us to generalize selective generation for GLMs via neural selection functions.
Conformal Set Model. We consider a conformal (prediction) set model Č: + 2 that measures the uncertainty of target model; in conformal prediction, this model is specifically called scoring functioo f ) + R2 that measures the conformity (or likelihood) of for being y with respect to S: thus, f(x,y) y) is called a conformity score. In particular, we consider scalar parameterization
of a conformal set [1] 33 as follows: C(x) = (y E y f(x.y) 2 T) where T E Rzo is scalar parameter.
Conformal Sets and Uncertainty. The output of the conformal model is set of labels, which naturally represents the uncertainty of a scoring function on an example via the size of conformal set. particular, if the scoring function f is unsure on its prediction on x (due to uncertainty on a label distribution of x, i.e., aleatoric uncertainty, and due to uncertainty in the modeling of f, iee, epistemic uncertainty), the conformal set is larger than is when the scoring function is sure on its prediction.
To be precise, consider y" is the true label of æ. In particular, the true conformal set is a minimal set that contains true label and labels with larger scores than the true label score; thus, the size of the true conformal set intuitively measures the uncertainty of a scoring function on the given example, i.e., the scoring function's possibilities on making wrong predictions, instead of the true prediction.
conformal set (*(x) = (y e e f(x,y)
y(x, where
The true conformal set clearly captures the uncertainty, but the true label is unknown in inference time. Thus, the true conformal set is approximated via scalar parameterization [31 as follows:
C(x) = {y y f(x. y) 2 T}
where r E Rzo is a scalar parameter.
Correctness. As we desire to construct a conformal set close to the true conformal set, we define the correctness of the conformal set based its similarity to the true one. In particular, we wish have the smallest (xx)) such that C* (x) C C(x). or equivalently C'(x) needs to have the smallest T while y E (xx). This correctness definition realized into two ways: a coverage guarantee [10 or a PAC guarantee [20].
Assumption. We assume that samples are independent and identically distributed (i.i.d),, i.e., the i.idd. assumption. In particular, all samples for testing and learning prediction sets are independently drawn from the same but known distribution D.
PAC guarantee. Under the i..dd assumption, we learn a conformal set Ô that includes the most true labels (approximately correct). In particular, this means that the miscoverage of È is less than a desired level è E (0, 1), i.e., RMe(C'= == (p & ((x) S E, where the probability is taken over be generalized to be the risk on indicator loss, Ro1(C) = Eploi y). Here, the conformal set Ć is learned from a randomly drawn calibration set, so we desire to construct Ö that has a desired error for the most of random calibration sets (probably approximately correct), i.e., IP (Ro (C) $) > 1 5, where ó E (0, is desired confidence level and the probability is taken over n i.dd. calibration samples ~ D", used to learn
i..dd samples (x,y) D. This risk micoverage
Ć.
34 considers the following algorithm ABinom (X x y)* H. to learn conformal set model C parameterized by f, where H. is finely- -isleddiscretized R>0:
Algorithm. The PAC conformal prediction set method |I
Aginom
f max TEH
subj. to Uiinom (k, < E,
(10)
ABinon returns f if it is infeasible.
14

---

where hr = Lo,,,,
Here, Binom is binomial tail bound, for any C. where Uimom (k:: n,
i.e. P (Roi (C) < Binm (, 8]}
=
inf ( [0, 1] F(k; () {1) and F(k; 0) is cumulative distribution function (CDF) of
binomial distribution with n trials and success probability 0. This algorithm is PAC.
Theorem 2. (12 20 34y) The algorithm Agnom is PAC, for any f. (0, 8 (0,1), 1), and 1, where the probability is taken over i.i.d. labeled
Z20. we have (Ro (C)
examples Z D and Ć ABnom (Z).
Here, we slightly generalize the known PAC guarantee to hold for any risk with indicator loss. See Appendix F for proof. Note that the PAC guarantee generally holds only if an enough number of samples provided (when we know function family including true functtion.. However, we consider PAC algorithms that hold for any number of samples due to the structural property of prediction sets, i.e., prediction set is always correct if r 0 (thus ('xx Y), regardless of the sample size. In other words, if the calibration samples are not sufficient, the prediction set is constructed return y satisfy the PAC guarantee.
A.2 Sample Space Decomposition
Given the generator G and the entailment set function E, the sample space Q = X' x 3 E x V can be partitioned as follows:
Ω {(x,), e, v) G(x) E Emee
| & Ema (y))
(( (xxx)))))))
((x,y,,,,)) l e=
and G(x) B(y) (x,,, e- and G(x) & E(y))U
Sff
SISEE
(x,y,e,v) le and G(x) ((x,,,, e 0 and G(x) E E
9
Ap
f u u O u L
9
Here, the short-hands are defined as follows:
True discovery rate (TDR): P ( Fuse
False discovery rate (FDR): P(D Euse)
True entailment rate (TER): (P(
False non-entailment rate (FNER): P
True non-entailment rate (TNER): P(O
False entailment rate (FER): (
A.3
Experiment Setup
A.3.1
Computing Environment
Our system environment consists of NVIDIA A100 80GB with 128 CPUs.
A.3.2
Models and Datasets
We use two large language models (LLMs), GPT:3.5-Turbo and Alpuca-7B, for language generation. We use deberta-v2 v2- 2-xxlarge-mnni as entailment model.
15

---

For each GLM to annotate entailment labels for each question, answer, and generated answer pair, we annotate entailment labels. Specifically, we consider the open-ended QA task, where the model is prompted to generate the answer in a declarative form given question. To validate our method and its theoretical guarantee on controlling FDR-E, we create a dataset on textual entailment using the Natural Questions (NQ) dataset [17] for each GLM. Based on the transformation method by [88 that converts the question and answer pair in QA dataset into a declarative form, we manually labeled textual entailment by letting the generated sequence as the premise and the reference answer in declarative form as the hypothesis. Similar work can be found in (39], but they label the textual entailment based on the extractive answer from the model. Approximately 7.3k (7,374) and 4.6k (4.595) samples are labeled for Alpaca-78 Ma and GPT-3.5-Turbo respectively, and both are split into calibration and test data at 8:2 ratio. For remi-supervised learning algorithms that exploit unlabeled data Algorithm Algorithm 9), at most 27k and 10k unlabeled samples are used to train a selective generator, varying its size. Besides, semi-supervised learning algorithms only 75% of the labeled calibration data compared to what is used by supervised methods (Algorithm Algorithm 10).
B Semi-supervised Selective Generation Algorithms (Certified)
Algorithm Entailment Set Learning with a False Entailment Rate (FER) Guarantee
1: procedure ES(SE, E, ZE. EE, ōg)
2: Zg f SORT fm (Zg)
(D) In an increasing order of fa G(x:))
3:
(i, + (1, Zzl
4: for i 1 to [log] Z do
5:
k+(+) E(xy,e)E2 1(e (( (V ((4+))))))))
6:
U <- Unioo (1) 12
7:
if U < E then
8:
i < [(i + 2)
9:
else
10:
i f [[i 7)/21
return тø
Algorithm 2 USSL Computation (for Single Eg)
1: procedure COMPUTR-USSLL (fE. Zg, Zu, 8s, E5,EE, 8g)
2:
TE ES(SE, ZE EE, 6g/2)
3: E+ Lixya)eZz [ = 1, fx < TE)
4: k Eixy)ezo ((JE(G(x),)) < TE)
5: USSI. E Liinom (e; E 0F/2) + Uinom (k, /Zur, 8s/2)
6:
return USSI.
Algorithm 3 Optimal USSL Search
1: procedure COMPUTE-UORT SSL SF. ZE, Zu 8s. Q. 8F)
2:
Zg +- SORT fæ (Zg)
(D) In an increasing order of fe(y,, G(x,))
3:
7 + IZll
4:
l(e = 0 Emax Σ E(xyye)EZz
5: HE + {E1 = Emax .., EQ = 1/1Q Emax
6:
USST. f- x
7:
for i in {l,.... Q} do
(:()) + Compute-U Usstte--Ussshhe (fE. Ze, Zu, 0,,
8:
if U7( (5) UOPT then
9:
USPT + (1)
10:
SSL
return /OPT
16

---

Algorithm 4 FDR-E Bound Computation
1: procedure FDR-E B-BOUNDDfFFFF. g. Zg. Zu, 6s. Q, dg dw)
2: WSt. x Binam Z Z2 + /zu,, 0w/2)
(>) Upper bound of (B) in
3: kst. _(xxy,))22 [(e 0)
4: USL <
Binom KSL: |Z 0s/2)
Upper bound of (C) in
5: WSSL UBinom Zu ZE + Zu dw (2) UOFT
Upper bound of (D) in
6:
< Compute OPT (f JE Z E Zu 8s 2, Q 8F/2)
Upper bound (E) in
7: U <- USI. USI. + Wsst. U
8:
return U
Algorithm 5 Semi-supervised Selective Generator Learning "Single-threshold Selection Function) fE, G, ZE, Zu, Es, 8s. Q, òg. dw, return_bool = False)
1: procedure
2: ZU,E +- Zu U ZE
3: ZU,E + SORT JM (Zu,E)
(D) In an increasing order of fMr G(x,)
4:
(i, + ZU,)
5:
Umin 00; Tmin NULL
6:
for = 1 to Togg Zu,El do
7:
Tg
(i)
G(x ((x(11))1)))
Z E ((x,y,e) Ze [M G(x))
8:
TS
9:
DU ((x,y) Zu fas (x, G(x))
2 Tg
(i)
10:
U + FDR-E-BOUND(JE, E
Z
Q, TTgg
6Gc
kw [log
Tog, Z0
Zu.e
Zu
11:
if U < Umin then
12:
Umin + U0); Tmin + TS
if (1) < E5 then
14:
i it [[i 0)/27
else
16:
i - [(i + 0)/21
(8)
17:
Ts
T3
18:
if Umin S Egg then
19:
Ú - (
20:
Bounded +- Success
21:
else
22:
U 5 Umin
23:
Ts t Timin
24:
Bounded +- Fail
25:
return (Ts, Ú, Bounded) if return_bool else (Ts, 0).
17

---

Algorithm 6 Semi-supervised Selective Generator Learning (Double-threshold Selection Function)
procedure SGEN- (GEN-SEMI2(fM. fal.- fE, G. Zg, Ze. ES. ds. Q. òg, ów. return_bool
False)
2:
ZU + Zu UZE ZE
3: ZUI,E. -- SORTORRA JAC, (ZU,E)
(D) In an increasing order of fM, (y:, G(x)) (D) In an increasing order of (y,, G(x,)
4:
EU + -SOTTT/UR 12 (Z
5:
Umin + -0; Tiin
NULL
6:
i (1, [1,1Zu,,E5)
7:
[ogg2 Zu.El
8:
for i = 1 to [log2 Zu, do
(1) +- fas, (x (x(4))/22) ((x
9:
(-61 +- 00; min
10:
NULL
min
11:
(j,3) t (1, Zuz )
12:
for j = 1 to [loge Zuuell do
T5 < fMz (x (6-+1/22 ((x11)+)2)))
14:
((1) < ((x,y,e) e) E Zz 8(x; G, JM,, M2
Tg -8 = 1}
(8) (1)
15:
Z < ((x,y) E Zu [(x: G. fM, fazz
T
55 = 1}
U(i)) FDR-E-BOUND(F2)
Z (id)
Z (1.3)
59
Q T
Aw
F
U(())) I ( then ((() + U(d)); min - (T$, (i)
17:
18:
min
TT
19:
if ((s)) < Es then
20:
j - [[] + 22
21:
else
22:
i - T)/2
23:
if (()
min S U then
Unin [(O). Tmin
(2)
24:
min
25:
if * [log, Zu.El then
if ((()) < Es then
26:
27:
[(i + 1)
28:
else
29:
i [[i + 7)/21
30:
else
(2) (1) Ts (TS ,7
31:
32:
if U min
S E. then
33:
Ú (1,d)); Bounded Success
34:
else
35:
Ô + Umini Ts f- Tmin; Bounded +- Fail
36:
return (Fs, U, Bounded) if return_bool else (Ts, 0)
18

---

Algorithm 7 Semi remi-supervisede Selective Generator Learning with Neuro-Selection
1: procedure SGEN- GGEN-SEMI-MS((M, fMai fE. G, Zg, Zu ES, ds, Q, d5 ow:)
2:
MSccess = 0: MFail (
3: (rs, Bounded,) ) (ouunded) SGen Semi(fa,. fE. G. Ze. Zo. es. 6s/3. 13/3.00 Q. 8g/3, 6w. return_boo True)
4: (r8,, Cr Bounded,) + SGen-Semi(/n.. Jas, G. Zy, Ze. Es. 65/3. Q. / ów /3, return True)
5:
(78, Cg Bounded,) SGen-Seni2(Arr JMN f8s G. Zo. Ze. 63/3. Q. 6,/3. 5w /3, return_bool True)
6:
((TS. U1 $1 Bounded;), ), (TS2. U2 82, Boundedg). (TSa: U3. 83, Boundeds)]
7:
(D) refers to the scoring function(s) used in each algorithm.
8:
for (Ts, Ú, Bounded) in MM do Bounded Success then
9:
10:
Msuccess Msuccess U ((TS,Ü,s) else
11:
12:
MFail Mpa Ü,T, if M MSccesss = O then
13:
14:
return (Ts, s) + arg min a) Ú
15:
else
return (Ts, Ü,s) +- arg maggax (r, 0 M
19

---

C
Supervised Selective Generation Algorithms (Certified)
Algorithm 8 Supervised Selective Generator Learning with R Rg (5) Control
1: procedure SG-SUP(fM. G, Zg,,,,0
2: (i, + (1, [Ze|)
3: for i to logg Zel | do
4:
T + fai /2 (( G ((+7/22)))
z + ((x,y,)) e) E Ze fM (x, G(x)) 2 Tg (0)
5:
6:
MO -- ((xy,)) [ = 0)
7:
UO Binom (x) 1 1 1, 6/ [log [ell)
8:
U < E then
9:
i - [(i + 0)
else
11:
i + [(i + 0)/21
(8)
12:
TS
TS
13:
Ú U
14:
return TS. 0
20

---

D Semi-supervised Selective Generation Algorithms (Heuristic)
Algorithm 9 Semi- Semi-suupr Selective Generator Learning with Pseudo-entallment Labels
1: procedure EG-PSL-H-SEMIIE fE, G, ZE, Zu, E, TLL. FILTER)
2: FILTER = TRUE then
3:
Zu {(x, y) /x(((x),)) 2 TH. (x)((x)))) 2 mp.) (x, E Zy,ē= ()) 2 TL))
4:
Zu + y( é)
5:
Zg ((x, é)
c. E -Zu,ē=)
6:
ZU,E + SORT fM
(Zg ZZ)
7:
(L, +- (1, [ZEzel
8:
for
1lgg2 Zu do
(i) fas (x ((
9:
Tg
U.E ((x,)) E ZUZE [xx(x, G(x)) 2 )
11:
1O + E(xx)))ZZ 1(==0)
12:
U0) + Uninom (1: Zu 8/llog2 [e,
Uf < E then
14:
i < [(2 + i)/2]
else
16:
i < [(2 + i)/2]
(8)
Tg
5 Tg
18:
Ú- U
19:
return TS. U
E
Unsupervised Selective Generation Algorithms (Certified)
Algorithm 10 Unsupervised Selective Generator Learning with (S) Control
1: procedure SG-EM(JM. G, Zg, Zu, e, 8)
2: ZU,E + Zy ZE
3: ZU.E + SORT fM (Zu,e)
4:
(i, (1, (Z,,E)
5:
for
[log2 Zu do
6:
Tg fasl (x G(x
(i)
ZUE y(x,)) E ZuzE [x,(x, G(x)) 2 )
7:
8:
100 + E(xriEZ!) 1(G(x) Fy)
9:
U0) < UBinom (A:
| 8/ /loo Zc,ell)
if < then
11:
i < [( i)
else
13:
i <
[(i + f)/21
(8)
T8
Tg
15:
Ú- (
16:
return Ts. Ú
21

---

Proof of Theorem 2
Let C be prediction set with a parameter T, He == {T H Roi > E), and T" = inf He.
where H finely-discretized non-negative real values. Then, we have
(k+; P P2RRi (Aiiom (2)) > { S PP Fr E He, Uiiomm ( n, 8) S
PP Uiiomm (k: in,
(1I)
$ P Roi (Cr-) 8 Uimoo (ki--;n, _e
$ P
Roi (or(C > UBinom (ky. n, 8) S 5..
(12)
where the last equality in (11) holds as 1 (y & C+(x) and Up are non non-decreasing in (i.e., Lemma in and the last inequality in [12 is due the property of the binomial tail bound Binom
G Proof Lemma 2
Since (E) in decomposed into three terms in Lemma we first find upper bounds each of the terms and take the union bound as follows. This will return a single upper bound on (E) in (2). which we denote USSL.
FER Bound. First, recall that
REER ()) = PD, fe = 0 G(x) E E(y)}.
Learning É via AFER is equivalent to the PAC prediction set learning algorithm that considers the optimization problem in (10), where the indicator loss is foz (,, e)) 1(e -A G(x) E(y))
and the target model is the entailment scoring function fE. Therefore, by Theorem 2 for any
n |E,, have
BE
IZE RREER(E) (B)
S EE
Pzz
(EER(E) SEE |6g = m
IPZ { [ = m
m=1
ng
8/p/2)
PZE 1ize m)
(13)
1 //
(14)
Note that 13 holds as the PAC guarantee for conformal prediction holds for any number of samples.
The same bound holds with respect to Specifically, letting EFER (ZE Zu) 1 (ReER (E) EF), we have
/ &EE (Zg. Zu) dIP(Z)
Pz REER S cg
/ 1FER (ZE Zo) dIp(Zz dPP())
(1 - 8'g/ (L)
8/
(15)
where the second equality holds due to the i..d. assumption on the calibration data and the inequality holds due to (14.
FNER Bound. Recall
RENER (É) = I'D le I
22

---

Since our goal is to upper-bound -RENER (E), we consider a lower bound RENER(E) as follows for any R
Zzl:
Pze
RENER (E) 2 Limomm (k: (2al.88//21 8xr/2))
n
Pe ReNER(E) Linom (k: 12...88/22 [2gl = mm Pz ( = m)
m=1
ng
82)/2) 12z [Z m)
82
(16)
where the inequality holds due to the binomial tail bound. The same bound holds when the probability is taken over Z. First, let
(NNER Ze Zu) = 1 (RENER (B) 2 Linom (k:; 12,1,
Then,
/ (FNER(2A) Zz:)dI(())
Pz RRNNER (B) Liinom (k: (2,)))8/221
/ (INEE (Z Zy.) dPP ddP (Zv)
2 / (1 8'E/2)dP
=1 82g/2,
(17)
where the second equality holds due to the i..d. assumption and the inequality holds due to (16).
NER Bound, Recall
RNER (E) = PD. - 0} PD3 (G(x) E(y)).
Then, upper bound RNER (E) follows for any vur Zull:
{ RNERR ()- < U Rinom (1; 12rl, d's)
Pzo
Σ Pzu { (RAEE( (f) S U Uinoom (1: (2ull,05) |2vl m) Prz (120l = m)
12
Σ (1 (1-8')
8's) Pz, (12y m}
8's.
(18)
where the inequality holds due the binomial tail bound, Again, the same bound holds when the probability is taken over Z. First, let
EEER (Z Zu) 1 [RRNER < Uninom
(f; (f: (1:1Zo1,6')
Then,
/ LNER (NER(ZE: (Zg, Zu (Z)
Pz RNER (E) < UBinom (i:12u,,,
/ ENTE FZ, Zui ) (Zv )dP (Z)
8's )dP (Z
8's.
(19)
where the inequality holds due to Finally, taking the union bound of
18
15
and
19
completes the proof.
23

---

H
Proof Lemma 3
Let USS) be USst. for the i-th candidate e in Algorithm
SSL
Due to Lemma
the following holds:
Pz(Poyfc=00 03 ~ S (6% + 8s)/Q.
( SSL we have
Since USLL
min (E[Q]
Pz (2 fe 0} >
SSI.
- P2 P ( 03 > ((1
SSL
$ Σ Pz PD (c f== 0) US$
$ 8 + 8/s:
where the second inequality is due union bound. This completes the proof.
Proof of Theorem
Let H. be the calibration set-dependent hypothesis space of selective generators, where nı = [H] always calibration set independent. Letting (1() be the FDR-E bound computed given the i-th selective generator S; in H. we first describe how derive upper bound of the FDR-E for a given hypothesis S..
Since an upper bound of (E) in 22) is proved in Lemma 3 the remaining parts are (i) to derive upper bounds on the others and (11) to take the union bound. For proportions of the visibility of textual entailment labels, i.e. (B) and (D) in (2). and the FDR-E for the supervised case only using
Mntailment-labelee examples, i.e., (C) in (2). the followings hold due the binomial tail bound:
Pz PDS, (u = 1} < U Binom (1Zzl: Zg 1u.l 8w (2 1mD)
12 x 17();
(5)
Pz PDS. {u = 0} < Binom | |:10::011 7g +
Zo. 8w 8w/(w//222 x [P()) } 11 - 8w/(2 x 17();
w
(4)
P'z D' le 0} < U Binom (|2g
10=0 Žøl 0s/(2 12 x (H1)) } 221- 0s/(2 x 171),
(
where 7g and Zy are defined same as Lemma does, and 2 = y, 2g = 0}. Note
that the binomial tail bound is applied to filtered sets by the given selective generator (e.g., Zg) but we can use the same bound for the non-filtered set Z, by using the same marginalization technique over the size of filtered set, in, egg., (15).
Thus, by taking the union bound along with Lemma 3 when 8' = 55 and 8'3 85/22
(ZE(R < U() 2 (ōx + 6g + 5w fw)////1
(20)
(1) ((()) + ussi SSL. where U, = wst ST.
UP is the computed FDR-E bound given selective generator S,
Here, T refers to the smallest FDR-E bound of (E) in given the i-th selective generator.
Since 20p holds for all S, E H. and the final bound Ú chosen among them, this completes the proof by taking union bound, i.e.
24

---

Pz { RE(() > 0} = Pz (3S; H. R > U.}
dP (3E; E H. (S() > UR [H] k}
Pz (3S; E (HR > U, | [7|| = k)) Pz (12) = k}
k=
Pz (S.) Us 1 H4| k} Pz [ = k}
k=
6g + ôs + dw
Iz {1H) k}
k= i=1
6F 8g + d.w.
Proof of Lemma 4
We say fu is perfectly calibrated with respect to D, G, Euve if
Pp(G(x) E Exue(y) (x G(x)) = +}} = t, vt.
(21)
The true discovery rate with respect to Eune conditioned on fas (x, G(x)) 2 Ts, iee. FDR-E, is as follows:
P(((() E (y) (x((x 2 TS}
St. P(G(x) E Emee | fxr(x, G(x)) = ()P[[M( G(x)) = t)dt
S/. P(fNr( G(x)) dt
(P G(x))) = tt
(22)
Sig P(MM(x = 1jdl'
where and 22 holds as fM is perfectly calibrated, i.e., (1
Letting lut)) = P(fM(x, G(x)) t}. H() = ft (tt')(()e )d''''d'', i(t) = (x, G(x)) t). and
Si (())
I(I) = ft i(t')dt', since we have TS <
Trg (()) 1, the following holds:
- - (Fss) 2 -
Therefore,
d drs
d I(1) I(TS)
P[G(x) e (y) (M G(x)) 2 Ts}
drs
H(1) - (TTS)
-h((s) ((((s)) ((4) ((s))
(H (Ts)))²
0.
This completes the proof.
Note that the classification problem can be reduced from the special case, Le, Func(y) FEM(U).
where y = W and (EM(y) = {y} = arg maxwew IPY = w X = x).
25

---

=.25.
6s 025
0.20
0.0
0.25
TER1
118
0.00
025
0.30
Sten
Sterk
S0and
Sounbial
Merthd
(a) supervised methods
(b) unsupervised and semi-supervised methods
Figure 4: FDR-E box plots of methods for GPP--3.5-turbe We randomly split the calibration ad test set 100 times for box plots. For supervised methods (a), we use all entailment labels, i.e. Z | For (b), which includes an unsupervised method (SGenæx) and semi-supervised methods, we use All methods except for Seen JM, as score function. The methods that do
[e = 0.75 g not control FDR-E in learning at least once are drawn using red boxes but otherwise using green boxes in Figure 4(a) and Figure 4(b) We draw the whisker plot to indicate 1005% and 100(1 6)% quantiles. In both (a) and (b) with green boxes, the top of the whisker is below of the dotted line, we can see that the FDR-E is well controlled with probability at least 8, í.e., they satisfy the PAC guarantee. The numbers of iterations that satisfy Es FDR-E in learning while running 100 iterations H-Semi = 100, are (a) SGen 0, SGen Sup 100, SGengoos Sup 100 and (b) SGen It-Semi_ 100, SGenøeL SGen 18, SGen Sems 100.
K Additional Experiments
Table 3: Comparison results of fully supervised methods. Here, we use all entailment labels, i... [Zg| ! for GPT-3.5-turbe and Alpaca-7B. The best results are highlighted in bold, GPT-3.5-ture
results from methods that do not satisfy desired FDR-E guarantee are underlined. and Alpaca-78 7B, the best efficiency values among methods that satisfy desired FDR-E guarantee are 0. 7575 and 0.2959, respectively, which serve as the best achievable efficiency results of semi- supervised methods.
Models
GPT-3.5-turbo
Alpaca-7h 7B
Methods
SGen Sup
SGen
Sein--Su
SGen
SGen
Semi-Sup
FDR-E
0.1697
0.1066
0.0400
0.0231
fM.
efficiency
0.6474
0.4657
0.1769
0.0922
FDR-E 0.2209
0.0914
0.0983
0.0827
fM²
efficiency
0.8596
0.5408
0.4149
0.3675
average efficiency
0. 0.7535
0.5033
0.2959
26

---

Table 4: Comparison results of semi-supervised methods. Here, Zol 10K for GPT-3.5- S-turbo and Alpaca- 7B. The best results are highlighted bold and results from methods that do not satisfy desired FDR-E guarantee underlined. We used QA2D dataset, filtered with only SQuAD, where human transformed QA sentences exist. E = 0.15.
Models
GPT-3.5-turbo
Heuristic
Certified
Methods
SGen Semi
SGen
SGengx
SGen Semi
SGen Semi
FDR-E
0.0000
0.0000
0.0213
0.0962
0.0918
fM efficiency
0.0387
0.0227
0.4775
0.8608
0.8502
FDR-E
0.0053
0.0039
0.0831
0.0169
0.0918
fMz2
efficiency
0. 0.1300
0.1025
0.4862
0.2156
0.8502
average efficiency
0.0844
0.0626
0.5382
0.8502
Table 5: Comparison results of fully supervised methods. Here, we use all entailment labels, i... |Zel a for GPT-3.5- and Alpaca-7B. The best results are highlighted in bold, results from methods that do not satisfy desired FDR-E guarantee underlined. We used QA2D dataset, filtered with only SQuAD, where human transformed QA sentences exist. E = 0.15.
Models
GPT-3.5-turbo
Methods
SGen
SGen
Semi Sup
FDR-E
0.1116
0.0454
JM1
efficiency
0.8956
0.6525
FDR-E 0.0459 0.3185
0.0082
JMa
efficiency
0.1532
average efficiency
0.6071
0.4029
NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA]-
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include it (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No] ", it is perfectly acceptable to answer "[No] providedd a proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA] is not grounds for rejection. While the questions are phrased acknowledge that the true answer often more nuanced, so please just use your best judgment and
27

---

write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The theoretical guarantee and the proposed algorithm are illustrated in Sec- tion Detailed proofs and algorithmic deseriptions can be found in the appendix. Experi- mental results are illustrated in Section 5
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations due assumptions made for the theoretical guarantee and the expensive data labeling process are illustrated in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
28

---

While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
We provide the correct and complete proofs with full set of assumptions made for each theoretical result, which are illustrated in detail in the appendix. Furthermore, the limitations of the theoretical guarantees induced by the assumptions are stated in Section 6
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Datasets, models, and hyperparameters used in implementing proposed algo- rithms are all described in detail. See Section 5
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
29

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will provide the code to train and evaluate the proposed algorithm, which reproduces the experiment results the paper after the rebuttal process.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: http:/ubbbllilguuddd//eeeeeueuue
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide the details of our experiments including generation.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
30

---

Justification:
This paper includes holdout experiments to assess statistical significance and provide error bars for the reported results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report I-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative eтror rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification:
We wrote the details in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp///paarrrs...c//o////hhcca
Answer: [Yes]
Justification:
The research is conducted with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative socictal impacts of the work performed?
31

---

Answer: [Yes]
Justification: The paper can measure the uncertainty of generative large language models, which is crucial for decision making problems.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: This paper poses such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: This paper cite the original papers such as dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
32

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperssw thcode, www.comm/aaa.oo dateetsss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's ' creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
This paper will release code for running experiments and it is well documented.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the datasct/cod//model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing research with human subjects.
Guidelines:
33

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "t3AG4IS7GU", "reviewer": "Reviewer_7eme", "summary": "The paper looks at a selective generative language system, meaning one which can produce a I-Don't-Know label rather than an answer, and calibrating it such that some guarantees on the precision of the system can be made. \nThe paper expands upon citation [1] on selective generation, to improve the efficiency by not requiring an exact match metric on the answer in order to be able to say whether it is correct or not. This is important for language generation tasks where there are endless possibly valid answers. It does this via the use of entailment measures, ie saying whether a candidate question+answer pair have positive/negative or neutral entailment. \nThe paper reports theoretical analysis of when the proposed method can be learnt within given error margins, doing so under reasonable assumptions of the data being IID. This may not truly be the case for say actual question-answer datasets, but is a required assumption for the theoretical statements that are presented. \nThe paper also presents empirical results on a question-answer dataset (Natural Questions), comparing against other selective generation methods with exact matching (rather than entailment), and with entailment sets (from labels or inferred). \nThe proposed method which learns the selective threshold is shown to have the best false-discovery-rate (ie the inverse of precision on the generated answer).", "questions": "* In figure 2, are the SG-EM and SG-ES systems scoring 0? I'm not familiar with the prior literature, but with this paper being strongly influenced by [1] where SG-EM is from, it seems surprising these 2 baselines are so poor.", "limitations": "* The theoretical analysis relies on the IID assumption, which won't hold on real world language datasets. This is noted by the authors.\n* Not clear how many language problems this is applicable to.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The requirement of having labels for answer correctness is clearly a large limiting factor in language generation tasks given the large number of possible correct answers. Relaxing this via entailment is therefore well motivated. \nThorough theoretical analysis given, albeit under", "weaknesses": "* Say more about what language problems this could and could not be applied to. The key appears to be in being able to have an accurate entailment function. For how many types of language-generation problems is such obtainable? \n\n* Some data on rates of IDK generation on the test set would be useful to see. \n\n* Minor suggestion: an algorithm box showing the steps for the whole proposed approach would be helpful for the reader. \n\n* The paper would benefit from an editor / proofreading. It doesn't impact understanding, but there are several small typos (lines 34, 69, 367 as some examples)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Say more about what language problems this could and could not be applied to. The key appears to be in being able to have an accurate entailment function. For how many types of language-generation problems are such obtainable?\nThanks for raising a nice point. We expect our method can be generalized to a variety of language generation problems, but we currently consider open-ended QA due to the limitation of the entailment classifier that we rely on.\n* In particular, as you have mentioned, the key point is whether we have access to an accurate entailment function for the given language generation problem. Specifically, as can be seen in Algorithm 1, the accuracy of the entailment function depends on the performance of the entailment classifier. Therefore, the applicability of our algorithm depends on the choice of the entailment classifier and its quality on the specific type of language-generation problem we consider. In this paper, we consider the transformer-based textual entailment classifier which is originally trained on the NLI dataset. Since the NLI dataset consists of pairs of premises and hypotheses in a declarative form of moderate length, the entailment classifier would not perform well on pairs of long sequences (e.g., summarization). For such cases where the pretrained entailment classifier provides inaccurate predictions, extra data are needed to train an entailment classifier from scratch [R1], or to finetune the base model [R2].\n    * [R1] Yu Gui, Ying Jin, and Zhimei Ren. “Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees.” ArXiv, 2024.\n    * [R2] Christopher Mohri, et al. “Learning to Reject with a Fixed Predictor: Application to Decontextualization.” ICLR, 2024.\n\n> Some data on rates of IDK generation on the test set would be useful to see.\n* Rates of IDK generation correspond to 1 - efficiency, which refers to the ratio of data selected in the test set. Efficiency is reported by figures and tables in our response.pdf (or the paper).\n* If you want some data examples of IDK generation, we sampled three examples of GPT3.5 that NSEGen says IDK, in addition to Table 2 of the paper.\n* Question: who sang there she was walking down the street\n    * Correct Answer: Manfred Mann\n    * Generated Answer: The Beatles sang “There she was walking down the street”\n* Question: how long is the ferry ride from cape may to lewes\n    * Correct Answer: 80 minutes\n    * Generated Answer: The ferry ride from Cape May to Lewes is approximately 1 hour and 15 minutes.\n* Question: what is the first book in the hive series\n    * Correct Answer: Institute of Villainous Education\n    * Generated Answer: The first book in the Hive series is “The Hatching” by Ezekiel Boone.\n\n> Minor suggestion: an algorithm box showing the steps for the whole proposed approach would be helpful for the reader. \n* Thank you for your suggestion. We will add the algorithm box on the final manuscript.\n\n> The paper would benefit from an editor / proofreading. It doesn't impact understanding, but there are several small typos (lines 34, 69, 367 as some examples) \n* Thank you for your suggestion. We will proofread over the draft and fix typos and errors for better readability.\n\n> In figure 2, are the SG-EM and SG-ES systems scoring 0? I'm not familiar with the prior literature, but with this paper being strongly influenced by [1] where SG-EM is from, it seems surprising these 2 baselines are so poor. \n* The main reason for the small FDR result of SG-EM is that it does not consider semantic correctness of answers (i.e., it only considers the answer is correct only if it is exactly the same as a given true answer). Thus, to achieve a desired FDR rate, [1] finds a conservative selective generator (i.e., $\\tau$ is close to one thus mostly saying IDK), resulting in low FDR to achieve a desired FDR rate.\nThe main reason for the small FDR result of SG-ES is due to the not-performant scoring function, i.e., a scoring function $f_{M_1}$ usually does not have high scores on correct answers. In this case, Algorithm 3 does not tightly achieve a desired FDR rate, it finds a conservative selective generator (i.e., $\\tau$ is close to one thus mostly saying IDK), resulting in low FDR to achieve a desired FDR rate (as the SG-EM case).\n* The reason why the score is exactly '0' is because we did not report the scores on the figure when the methods cannot be bound under $\\epsilon_S$, for the reasons above. (In this case, $\\tau$ is the largest value in the calibration data which is ~= 1). \n* We will add this analysis in the paper and to avoid such confusion, we will use Table to annotate the cases where $\\epsilon_S$ guarantees are not satisfied.", "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": "NOhdsqd6kQ", "reviewer": "Reviewer_abKP", "summary": "This work presents a method for selective generation from language models for question answering. Their approach functions as a secondary decision function on top of an existing language model, determining whether to accept the language model's generation or to abstain. Their method is approach is based on constructing an entailment set of correct answers to a given question. The entailment set is defined as all answers that imply or textually entail the ground truth answer. They then design their secondary decision function such that it satisfies bounds on the correctness of accepted, generated answers based on whether it is within the constructed entailment set, or the answer not being in the ground truth entailment set. The authors then demonstrate that their method satisfies correctness guarantees based on conformal prediction, and demonstrate the efficacy of using their entailment set approach to identifying correctness empircally through experiments on open-domain question answering (NaturalQuestions) and with two language models (Alapaca7b and GPT3.5)", "questions": "The presentation of the experimental details could benefit from additional explanation. Clearly defining what the baselines are and how their implemented (not just the algorithms in the appendix) would greatly improve readability. This applies to the experimental results and metrics as well.\n\nEvaluations could be designed in a way that (1) more clearly describe each methods efficacy and performance in the end task (QA in this case) and (2) allow for direct comparison against other methods also designed for calibration and selective generation.", "limitations": "The authors address that they do not report statistical significance.", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The goal of this work, selective generation for language models to prevent hallucinations and erroneous outputs is sounds and well motivated.\n\nThis work provides theoretical guarantees on the efficacy of the selective generation approach, builds upon insights from prior works on the efficacy of using textual entailment to aid in calibrating QA predictions.", "weaknesses": "Relying on single-directional textual entailment as a method for determining correctness of an answer is susceptible to accepting generations that produce that untrue fact or hallucinations in addition to the correct answer. [1] is a very relevant work (that was not cited) that similarly uses entailment to determine equivalence between two answers; however, in their work they rely on bi-directional entailment to ensure answer equivalence.\n\nThe baselines used in this work lack clear descriptions, and are not in line with current simple and effective methods for selective generation and calibration of language models [1, 2, 3]. [2] and [3] both do not require additional entailment training data and [1] takes a related approach using entailment to determine answer equivalence among a set of generated answers. [1] also does not require domain-specific entailment data.\n\n[1] Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation\nLorenz Kuhn, Yarin Gal, Sebastian Farquhar\nICLR 2023\n\n[2] Self-consistency improves chain of thought reasoning in language models.\nX. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou.\nICLR 2023 \n\n[3] Language Models (Mostly) Know What They Know\nSaurav 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, Jared Kaplan\nArXiv 2022", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Relying on single-directional textual entailment as a method for determining correctness of an answer is susceptible to accepting generations that produce that untrue fact or hallucinations in addition to the correct answer...\n- We agree that the bi-directional entailment is the best choice in terms of evaluating the \"equivalence\" of two sequences. However, for open-ended QA problem, GLM is prompted to generate a sequence in a free-form that often includes extra explanation. Therefore, considering the single-direction entailment as a correctness metric may be preferred. \n- Furthermore, the problem set-up that our algorithm considers is general since it can take any type of entailment $R$ as a correctness metric (Eq. (1)). Taking paraphrase generation as example, it is appropriate to let $R$ be the bi-directional entailment, and FDR-E is defined as $P${$G(x)\\notin E_{\\text{true}}(y)\\wedge y\\notin E_{\\text{true}}(G(x))$}. Then, the implementation of our algorithm is exactly the same as we did with the open-ended QA problem. \n- Additionally, we conducted experiments using bi-directional entailment and compared them with the result from single-directional entailment in the open-ended QA problem using proxy labels, showing similar results. For GPT3.5, NSEGen can bound FDR-E to 0.1659 (where efficiency is 0.9804) when using single-directional entailment, while to 0.1594 (where efficiency is 0.9653) using bi-directional entailment. Other baselines showed similar trends.\n\n> The baselines used in this work are not in line with current simple and effective methods ... [R1, R2, R3].\n- We appreciate constructive suggestions on related work. Suggested papers [R1-R3] are mainly to design better uncertainty measures for the generated sequence (=a good “scoring function”). It is a very important issue in the NLP literature, and the efficiency of our algorithm implicitly depends on a given scoring function. However, “given” a scoring function, what our algorithm does is to learn a selective generator which refuses to generate the sequence based on a scoring function value. Therefore, designing a scoring function is out of our scope. [R1-R3] can be used to define the scoring function, and our algorithm provides a theoretical guarantee on FDR-E, irrespective of the choice of scoring functions.\n\n> [R2] and [R3] both do not require additional entailment training data and [R1] takes a related approach using entailment to determine answer equivalence among a set of generated answers. [R1] also does not require domain-specific entailment data. \n- We agree. But we also want to highlight that an extra entailment-labeled training set is necessary to “guarantee” the rate of hallucinations (Theorem 1). \n- Besides, it is also true that [R1] does not require “domain-specific” entailment data, where the transformer-based entailment classifier that [R1] utilizes is trained on the NLI dataset. While the classifier can be applied to arbitrary pairs of sequences, it underperforms on some language generation problems where the pair comes from different distribution.  For such cases, extra calibration data are needed to train an entailment classifier from scratch [R4], or to finetune the base model [R5].\n   * [R4] Yu Gui, Ying Jin, and Zhimei Ren. “Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees.” ArXiv, 2024.\n   * [R5] Christopher Mohri, et al. “Learning to Reject with a Fixed Predictor: Application to Decontextualization.” ICLR, 2024.\n\n> The baselines used in this work lack clear descriptions…\n\n> Clearly defining what the baselines are and how they are implemented ... would greatly improve readability. This applies to the experimental results and metrics as well.\n- We clarified descriptions on baselines (SG-EM, SG-EL, SG-ES) along with extra baselines (SG-ES-Sup, SG-PL, SG-PFL) for clear comparisons. \n   * Supervised Baselines\n      * SG-EM: A supervised method that uses exact match metric\n      * SG-EL: A supervised method that uses semantic correctness encoded in the entailment label instead of exact match\n      * SG-ES-Sup: A method that uses same entailment set algorithm in SG-ES, where $Z_U = \\emptyset$\n   * Semi-Supervised Baselines\n      * SG-PL & SG-PFL: They exploit the unlabeled data by pseudo-labeling entailment based on a threshold. Both algorithms are heuristics, since they do not control the mislabeling error.\n   * Metrics\n      * FDR-E refers to the ratio of whether a generated answer does not entail the true answer for a test sample.\n      * Efficiency refers to the ratio of data selected in the test set.\n\n> The presentation of the experimental details could benefit from additional explanation.\n- We employ two large language models (LLMs), GPT-3.5-Turbo and Alpaca7B. We create a dataset on textual entailment using the Natural Questions (NQ) dataset [43]. Based on the transformation method by [44], we convert the (q, a) pair into a declarative form for each model. Besides, semi-supervised learning algorithms use only 75% of the labeled data compared to what is used by supervised methods.\n- To control an FDR-E, we use two user-specified parameters $(\\epsilon, \\delta)$, where we use $(0.25, 0.02)$ unless specified. For our methods (i.e., SG-ES, NSEGen, and SG-ES-Sup), we have four parameters ($\\epsilon_S, \\epsilon_E, \\delta_S, \\delta_E$) which are mapped as follows: $\\epsilon_S = \\epsilon$, $\\epsilon_E = 10^{-4}$, $\\delta_S = \\delta/2, \\delta_E = \\delta/2$. For other methods without using entailment sets, we use $\\epsilon$ and $\\delta$ accordingly.\n\n> Evaluations could be designed in a way that (1) more clearly describe each method's efficacy and performance in the end task (QA in this case) and (2) allow for direct comparison against other methods also designed for calibration and selective generation.\n- We have compared methods in attached files (Table 1, 2).\n\n> The authors address that they do not report statistical significance.\n- See Figure 1 in attached files.", "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": "GCgg3QSGHB", "reviewer": "Reviewer_KeFc", "summary": "The paper investigates the trustworthiness of generative language models in critical decision-making systems, identifying deficiencies in current uncertainty learning methods, such as selective classification and conformal prediction, which fail to address metric misalignment in GLMs. The authors propose an entailment-based false discovery rate  by leveraging logical entailment to define the relationship between true and generated answers. They introduce a supervised selective generation approach using entailment labels to control the FDR and a semi-supervised method to mitigate the high cost of obtaining these labels. This method employs an entailment set for pseudo-labeling and neuro-selection functions to enhance data space learning, reducing FDR. The neuro-selective entailing-generation algorithm  is theoretically validated, meeting the PAC guarantee on the desired FDR. NSeGen demonstrates improved efficiency and reliability in achieving a desired FDR level compared to baseline models, highlighting its practical applications.", "questions": "See my weaknesses. esp. \n\n3. It would be great to get a practical understanding of how much data would be needed to train a good enough selective algorithm. This is important especially in low resource scenarios (both language and application areas) as the space of application of where such an algorithm such as yours might be used is highly likely in places were there is not much data. So ablation", "limitations": "The work covers their limitations well and this was very appreciated. A practical guide for researchers might have been great in terms of knowing how much data is needed to help the psuedo labelling.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The work works to provide good grounding of both the problem and proposed path to the solution. With the proposed path, the authors work well to highlight the deficiencies both with current approaches, as well as their chosen approach and then incorporate fixes that make the deficiencies less of a problem. The work to do psuedo labelling and also deal with entailment is important as well as showing the theoretical guarantees.", "weaknesses": "1. There is a bit of repetitiveness in the Experiment section when describing the GLMs and Datasets. \n2. It should be made clear that your approach deals with the generation results from the underlying model. For example, when reading table 1 earlier I thought you were comparing Alpaca to your method, but later got it as you have different ways to deal with the selective generation. \n3. It would be great to get a practical understanding of how much data would be needed to train a good enough selective algorithm. This is important especially in low resource scenarios (both language and application areas) as the space of application of where such an algorithm such as yours might be used is highly likely in places were there is not much data. So ablation studies on sizes of the training set would have been great.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There is a bit of repetitiveness in the Experiment section when describing the GLMs and Datasets.\n* Thank you for your suggestion. As you mentioned, there are redundancies in our descriptions of GLMs and datasets. The following is our revised version in a concise but detailed manner, and we will update it in our final manuscript.\n    * Models and Datasets. We use two large language models (LLMs), GPT-3.5-Turbo and Alpaca-7B, for language generation. Specifically, we consider the open-ended QA task, where the model is prompted to generate the answer in a declarative form given a question. To validate our method and its theoretical guarantee on controlling FDR-E, we create a dataset on textual entailment using the Natural Questions (NQ) dataset [43] for each GLM. Based on the transformation method by [44] that converts the question and answer pair in QA dataset into a declarative form, we manually labeled textual entailment by letting the generated sequence as the premise and the reference answer in declarative form as hypothesis. Approximately 7.3k (7,374) and 3k (3,000) samples are labeled for GPT-3.5-Turbo and Alpaca-7B, respectively, and both are split into calibration data at an 8:2 ratio. For semi-supervised learning algorithms that exploit unlabeled data, at most 27k and 10k unlabeled samples are used to train a selective generator, varying its size. Besides, semi-supervised learning algorithms use only 75% of the labeled calibration data compared to what is used by supervised methods.\n\n> It should be made clear that your approach deals with the generation results from the underlying model. For example, when reading table 1 earlier I thought you were comparing Alpaca to your method, but later got it as you have different ways to deal with the selective generation.\n* Thank you for your suggestion. We agree that there should be a clarification that our approach depends on generation results of the underlying GLM we consider, even with the same dataset. We will update it in our final manuscript, which is the revised version of descriptions on GLMs and datasets from the above question.\n\n> It would be great to get a practical understanding of how much data would be needed to train a good enough selective algorithm. This is important especially in low resource scenarios (both language and application areas) as the space of application of where such an algorithm such as yours might be used is highly likely in places where there is not much data. So ablation studies on sizes of the training set would have been great.\n* Thanks for your advice. We conducted the ablation study on NQ dataset while maintaining the ratio of $|\\mathbf{Z}_E|$ and $|\\mathbf{Z}_U|$. We simply multiplied the sizes of $|\\mathbf{Z}_E|$ and $|\\mathbf{Z}_U|$ by 1, 0.7, 0.5, 0.3, and 0.1. To set initial data sizes of each model similar in ratio, the sizes of GPT-3.5 were set to about (2.4k, 10k) and Alpaca7B to (5.9k, 2.7k). $\\epsilon$ was set to 0.25.\nBased on the representative NSEGen, FDR of GPT-3.5 was reported as (0.1561, 0.1478, 0.1146, fail, fail), and FDR of Alpaca7B was reported as (0.0251, 0.1478, 0.1146, fail, fail), respectively.\n* Two models show different FDR-Es on the NQ dataset. Considering this fact with the results, although Alpaca7B's $|\\mathbf{Z}_U|, |\\mathbf{Z}_E|$ on NQ dataset are larger, when the size is reduced, Alpaca7B fails to bound earlier than GPT-3.5, where other methods show similar trends.\n* Thus, for a stable bound, the certain size of $|\\mathbf{Z}_E|$ seems to be needed proportional to the FDR(which is dependent on the model and data).\n* We will add this ablation studies by using plots in Appendix of our final manuscript.", "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": "MQOqmfBRUW", "reviewer": "Reviewer_UCLF", "summary": "This paper introduces Neuro-Selective Entailing-Generation (NSEGen), a novel approach to enhance the trustworthiness of generative language models. The method extends selective classification to language generation tasks, utilizing textual entailment to measure semantic correctness between generated and true answers. NSEGen employs a semi-supervised method that leverages both labeled and unlabeled data by learning an entailment set, addressing the challenge of expensive entailment labeling. The authors introduce neuro-selection functions to optimize feature selection for minimizing false discovery rate and provide theoretical guarantees on false discovery rate control. The approach aims to control the entailment-based false discovery rate while maximizing selection efficiency.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a new framework for improving GLM trustworthiness that addresses limitations of existing methods. This is particularly important because it tackles the metric misalignment issue in GLMs, where conventional metrics like exact match fail to capture semantic correctness. By introducing selective generation and leveraging textual entailment, the authors provide a more nuanced and accurate way to evaluate language model outputs.\n- The approach is supported by thorough theoretical analysis and guarantees. The authors provide a detailed proof for the correctness guarantee of their algorithm (Theorem 1) and establish conditions for achieving monotonicity in precision (Lemma 3).", "weaknesses": "- The method introduces several new components and parameters, which may make it challenging to implement and tune. For instance, the algorithm involves learning an entailment set, designing neuro-selection functions, and tuning multiple parameters. This complexity could make it difficult for practitioners to adopt the method.\n- Experiments are conducted only on Natural Question with two models (GPT-3.5 and Alpaca-7B). While these experiments do demonstrate the method's effectiveness, they leave open questions about its generalizability. Especially if the method claims to adapt uncertainty learning methods to generation tasks. It would be valuable to see how the method performs on a wider range of language generation tasks (e.g., summarization, translation, or open-ended text generation and so on).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The method introduces several new components and parameters, which may make it challenging to implement and tune. For instance, the algorithm involves learning an entailment set, designing neuro-selection functions, and tuning multiple parameters. This complexity could make it difficult for practitioners to adopt the method.\n- We thank you for valuable comments on practical use of our algorithm. Even though the algorithm may seem complex at first glance, we want to highlight that there are only a few user-specified parameters that the user should take care of to run our algorithm, all of which have intuitive interpretations.\n- Here, we provide (1) a detailed description of how to choose the user-specified parameters and (2) additional guidelines for the practical use of our method. First, we would like to start with (2). The following is a list of configurations that practitioners need to choose before running our algorithm, which may vary based on the language generation problem they aim to solve. Since we assume the configurations are easy for practitioners to choose, we distinguish them from what we call “user-specified parameters”.\n   * Generator $G$: Target GLM that we aim to control the rate of hallucinations for the specific language generation task\n   * $Z_E, Z_U$: Calibration data with and without labels on textual entailment\n   * $f_{M_1}, f_{M_2}$: Language scoring functions to quantify the uncertainty of the generated sequence on a given problem\n   * $f_E$: Entailment classifier to predict the textual entailment\n- The remainder provides a detailed description of choosing the user-specified parameters: $\\epsilon_S, \\epsilon_E$, and $\\delta(=\\delta_E+\\delta_S)$. \n   * For $\\epsilon_E$, we newly propose an automatic $\\epsilon_E$-searching algorithm for convenience. We hope to add this algorithm in our final manuscript, since we believe this would make our algorithm more accessible to users. \n      * $\\epsilon_E$: The target level of mislabeling error made in the pseudo-labeling process. Unlike $\\epsilon_S$ which specifies the target rate of hallucinations (FDR-E), we thought that letting the user choose $\\epsilon_E$ may not be easy. Hence, we propose a $\\epsilon_E$-searching algorithm which automatically chooses $\\epsilon_E$ among possible candidates. Specifically, we find the smallest $\\epsilon_E$ that returns a non-vacuous entailment set among candidates. If a detailed algorithmic description or a modified version of proof is needed, we will additionally provide them via an anonymized file. \n   * The following are guidelines for choosing the remaining user-specified parameters. Although they may not seem straightforward to choose, they have intuitive interpretations that make them easy to specify.\n      * $\\epsilon_S$: As mentioned above, $\\epsilon_S$ is the target rate of hallucinations (FDR-E) chosen by the user, which is straightforward. Based on the type of language generation problem or the user’s preference between the rate of hallucinations and the number of abstained answers, he/she can select $\\epsilon_S$.  \n      * $\\delta ( = \\delta_S + \\delta_E )$: $\\delta$ is related to the confidence of the guarantee on FDR-E. Specifically, irrespective of which calibration set $(Z_E, Z_U)$ we use, our algorithm controls the FDR-E with probability $1 - \\delta$ (Theorem 1). This can be chosen based on the degree of confidence that the user thinks appropriate (e.g., 90% of confidence). \n\n> Experiments are conducted only on Natural Question with two models (GPT-3.5 and Alpaca-7B). While these experiments do demonstrate the method's effectiveness, they leave open questions about its generalizability. Especially if the method claims to adapt uncertainty learning methods to generation tasks. It would be valuable to see how the method performs on a wider range of language generation tasks (e.g., summarization, translation, or open-ended text generation and so on). \n- Thanks for raising concerns on the generalizability of our method. We think it would be great to verify and further generalize the applicability of our method to a wider range of language generation tasks and these would be very interesting future work. Although we have conducted an experiment only on the open-ended QA problem, we want to note that our problem and algorithm are designed in a general manner.\n- As of generalizability, one of technical issues is concerned with the choice of the entailment classifier. Specifically, the success of our semi-supervised version, a label-efficient version which exploits the unlabeled data set via pseudo-labeling, depends on whether we have access to an accurate entailment set for the given language generation problem. Specifically, as can be seen in Algorithm 1, the accuracy of the entailment set depends on the performance of the textual entailment classifier. Therefore, the applicability of our algorithm depends on the choice of the entailment classifier and its quality on the specific type of language-generation problem we consider. In this paper, we consider the transformer-based textual entailment classifier which is originally trained on the natural language inference (NLI) dataset. Since the NLI dataset consists of pairs of premises and hypotheses in a declarative form of moderate length, the entailment classifier would not perform well on pairs of long sequences. For such cases where the pretrained entailment classifier provides inaccurate predictions, extra calibration data are needed to train an entailment classifier from scratch [R1], or to finetune the base model [R2].\n   * [R1] Yu Gui, Ying Jin, and Zhimei Ren. “Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees.” ArXiv, 2024.\n\n   * [R2] Christopher Mohri, et al. “Learning to Reject with a Fixed Predictor: Application to Decontextualization.” ICLR, 2024.", "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:
We appreciate reviewers’ valuable feedback and constructive comments. In this global response, we delineate the structure of our responses. 
* We provide individual responses to questions of each reviewer.
* We provide pdf, including requested experiment results.
* We also suggested an improved method due to a request – We can provide a proof (also a slight variation of the original proof) on the correctness of the improved method if required.

Meta-review: The paper presents an entailment-based false discovery rate by leveraging logical entailment to define the relationship between true and generated answers for GLMs. They introduce a supervised selective generation approach using entailment labels to control the FDR.  The paper also reports theoretical analysis of when the proposed method can be learnt within given error margins.  Any major concerns from reviewers seem resolved in the rebuttal/discussion.
Decision: Accept (spotlight)