Efficient Conformal Prediction via Cascaded Inference with Expanded Admission
Authors: Adam Fisch
Tal Schuster
Tommi S. Jaakkola
Regina Barzilay
Venue: ICLR 2021 Poster (2021)
Keywords: conformal prediction
uncertainty estimation
efficient inference methods
natural language processing
chemistry

Abstract: In this paper, we present a novel approach for conformal prediction (CP), in which we aim to identify a set of promising prediction candidates---in place of a single prediction. This set is guaranteed to contain a correct answer with high probability, and is well-suited for many open-ended classification tasks. In the standard CP paradigm, the predicted set can often be unusably large and also costly to obtain. This is particularly pervasive in settings where the correct answer is not unique, and the number of total possible answers is high. We first expand the CP correctness criterion to allow for additional, inferred "admissible" answers, which can substantially reduce the size of the predicted set while still providing valid performance guarantees. Second, we amortize costs by conformalizing prediction cascades, in which we aggressively prune implausible labels early on by using progressively stronger classifiers---again, while still providing valid performance guarantees. We demonstrate the empirical effectiveness of our approach for multiple applications in natural language processing and computational chemistry for drug discovery.

Published as a conference paper at ICLR 2021
EFFICIENT CONFORMAL PREDICTION VIA CASCADED INFERENCE WITH EXPANDED ADMISSION
Adam Fisch* Tal Schuster* Tommi Jaakkola
Regina Barzilay
Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology (f tisch, t s, tommi, reg i na @csail mttesail.ii...mm .mit.edu
ABSTRACT
In this paper, we present a novel approach for conformal prediction (CP), in which we aim identify set of promising prediction candidates place of single prediction. This set is guaranteed to contain a correct answer with high probability, and is well-suited for many open-ended classification tasks. In the standard CP paradigm, the predicted set can often be unusably large and also costly to obtain. This is particularly pervasive in settings where the correct answer not unique, and the number of total possible answers is high. We first expand the CP correctness criterion to allow for additional, inferred "admissible" answers, which can substan- tially reduce the size of the predicted set while still providing valid performance guarantees. Second, we amortize costs by conformalizing prediction cascades, in which we aggressively prune implausible labels early on by using progressively stronger classifiers- again, while still providing valid performance guarantees. We demonstrate the empirical effectiveness of our approach for multiple applications in natural language processing and computational chemistry for drug discovery.'
INTRODUCTION
The ability to provide precise performance guarantees is critical to many classification tasks (Amodei et al., 2016; Jiang et al., 2012: 2018). Yet, achieving perfect accuracy with only single guesses is often out of reach due to noise, limited data, insufficient modeling capacity, or other pitfalls. Nevertheless, in many applications, it can be more feasible and ultimately useful to hedge predictions by having the classifier return a set of plausible options-ow of which is likely to be correct.
Consider the example of information retrieval (IR) for fact verification. Here the goal is retrieve snippet of text of some granularity (e.g., a sentence, paragraph, or article) that can used to verify a given claim. Large resources, such as Wikipedia, can contain millions of candidate snippets- of which may independently be able to serve as viable evidence. A good retriever should make precise snippet suggestions, quickly-but do without excessively sacrificing sensitivity (i.e., recall).
Conformal prediction (CP) is a methodology for placing exactly that sort of bet on which candidates to retain (Vovk et al., 2005). Concretely, suppose we have been given examples, (X,, Y2) E X' ), i= 1,... n, as training data, that have been drawn exchangeably from an underlying distribution P. For instance, in our IR setting, X would be the claim in question, Y a viable piece of evidence that supports or refutes it, and y a large corpus (e.g., Wikipedia). Next, let X be new exchangeable test example (e.g., new claim verify) for which we would like to predict the paired y E y. The aim of conformal prediction is to construct a set of candidates C, (X,+1) ) likely to contain Yx+1 (e.g.. the relevant evidence) with distribution ffre marginal coverage at tolerance level e E (0, 1):
P (Yn+1 (X.+1))) 21-c; for all distributions P.
The marginal probability above taken over all the n + 1 calibration and test points {(X,, Y:) 1++ A classifier is considered to be valid if the frequency of error, Ya+1 & (X,+)), does not exceed c. In our IR setting, this would mean including the correct snippet at least e-fraction of the time. Not all valid classifiers, however, are particularly useful (e.g.. a trivial classifier that merely returns all
"quul contribution (author order decided randomly).
Our code is available at https: / /i thub. com/ a www.chhccooosiiaa conforofaaaall cascades.

---

Published as a conference paper at ICLR 2021
Retriever Cascade
Claim: Michael Collins took part in the Apollo mission to the moon.
Apolla
Apalli
2
SS Colie CATVORAND
W WIKIPIDDA
Apedlo II CoO1 EIys
Figure I: A demonstration of our conformalized cascade for m-step inference with set-valued outputs, here on an IR for claim verification task. The number of considered articles is reduced at every reve--red frames are filtered, while green frames pass We only care about retrieving at least one of the admissible articles (starred) for resolving the claim.
possible outputs). A classifier considered to have good predictive efficiency if (Xn+1)l is small (i.e., < D/). In our IR setting, this would mean not returning too many irrelevant articles or in IR terms, maximizing precision while holding the level of recall at 2 1 (assuming Y is single answer). In practice, in domains where the number of outputs choose from is large and the "correct" one is not necessarily unique, classifiers derived using conformal prediction can suffer dramatically from both poor predictive and computational efficiency (Burnaev and Vovk, 2014; Vovk et al., 2016; 2020). Unfortunately, these two conditions tend to be compounding: large label spaces y both (1) often place strict constraints on the set of tractable model classes available for consideration, and (2) frequently contain multiple clusters of labels that are difficult to discriminate between, especially for low-capacity classifier.
In this paper, we present two effective methods for improving the efficiency of conformal prediction for classification tasks with large output spaces V, in which several y E 3' might be admissible-i.e. acceptable for the purposes of our given task. First, in Section 4 we describe a generalization of Eq. an expanded admission criteria. where C, (Xn+1) is considered valid if it contains least one admissible y with high probability. For example, in our IR setting, given the claim "Michael Collins took part in the Apollo mission to the moon," " any of the articles "Apollo 11," "Michael Collins (astronaut), or "Apollo 1I film) have enough information to independently support it (see Figure 1) and are therefore all admissible. When Y,+1 is not unique, forcing the classifier to hedge for the worst case, in which a specific realization of Yn+1 must be contained in C., (Xx+1) 1). is too strict and can lead to conservative predictions. We theoretically and empirically show that optimizing for expanded admission criteria yields classifiers with significantly better predictive efficiency.
Second, in Scction 5 we present a technique for conformalizing prediction cascades to progressively filter the number of candidates with sequence of increasingly complex classifiers. This allows us to balance predictive efficiency with computational efficiency during inference. Importantly, we also theoretically show that, in contrast other similarly motivated pipelines, our method filters the output space in a manner that still guarantees marginal coverage. Figure 1 illustrates our combined approach. We demonstrate that, together, these two approaches serve as complementary pieces of the puzzle towards making CP more efficient. We empirically validate our approach on information retrieval for fact verification, open-domain question answering, and in in-silico screening for drug discovery.
Contributions. In summary, our main results are as follows:
A theoretical extension of validity (Eq. 1) to allow for inferred admissible answers.
A principled framework for conformalizing computationally efficient prediction eascades.
Consistent empirical gains on three diverse tasks demonstrating up to 4.6x better predictive efficiency AUC (measured across all e) when calibrating for expanded admission, with computation pruning factors of up to 1/m, where is the number of models, when using prediction cascades.
2 RELATED WORK
Confident prediction. Methods for obtaining precise uncertainty estimates have received intense interest in recent years. A significant body of work is concerned with calibrating model confidence-
2

---

Published as a conference paper at ICLR 2021
measured po [xx+1] (Rx+1)-suud such that the true accuracy, Un+1 0n+1. is indeed equal to the estimated probability (Niculescu-Mizl) and Caruana, 2005; Gal and Ghahramani, 2016; Lakshmi- narayanan et al., 2017: Lee et al., 2018). In theory, these estimates could be leveraged to create confident prediction sets Cn (1.+1). Unlike CP, however, these methods are not guaranteed to be accurate, and often still suffer from miscalibration in eeeeeicce-speciaallll for modern neural networks (Guo et al., 2017; Ashukha et al., 2020; Hirschfeld et al., 2020), Selective classification (El- Yaniv and Wiener, 2010; Geifman and El-Yaniv, 2017), where models have the option to abstain from answering when not confident, is similar in motivation to Eq. 1. In fact, it can be considered as a special case in which the classifier chooses to abstain unless (X,+1)
1.
Conformal prediction. As validity is already guaranteed by design in conformal prediction, most efforts in CP focus on improving various aspects of efficiency. Mondrian CP (Vovk et al., 2005) accounts for the fact that some classes are harder to model than others, and leverages class-conditional statistics. Similiarly, several recent studies have built towards conditional as opposed to marginal- coverage through various adaptive approaches, such conformalizing quantile functions or working with conditional distributions that vary with I (see Cauchois et al., 2020; Chernozhukov et al., 2019; Kivaranovic et al., 2020; Romano et al., 2019; 2020, inter alia). Cauchois et al. (2020) also directly model dependencies among y variables for use in multi-label prediction. Our method for expanded admission, on the other hand, aggregates statistics for equivalent single labels by example and across classes. Though we only provide marginal guarantees, the ideas expressed in those related works are complementary, and can be applied here as well. Inductive CP (Pupadopoulos. 2008) is also complementary extension that dramatically reduces the cost of computing C, (Xn+1) in the general case; we make use of here. Most similar our work, trimmed (Chen et al., 2016) and discretized (Chen et al., 201 8) CP trade predictive efficiency for computational efficiency in regression tasks, where the label space is infinite. A key distinction of our method is that we do not force the same trade-off: in fact, we empirically show that our conformalized cascades can at times result better predictive efficiency alongside a pruned label space.
Prediction cascades. The idea of balancing cost with accuracy by using multi-step inference has been explored extensively for many applications (Charniak et al., 2006; Deng and Rush, 2020; Fleuret and Geman, 2001; Jurafsky and Martin, 2000; Li et al., 2015; Rush and Petrov, 2012). Some of these methods use fixed rules with no performance guarantees, such as greedy pipelines where the top predictions are passed on to the next level (Chen et al., 2017; Ferrueci et al., 2010). Closer to work, Weiss and Taskar (2010) optimize their cascades for overall pruning efficiency, and not for top-1 prediction. While they also analyze error bounds for filtering, their guarantees are specific to linear classifiers with bounded L2 norm, whereas our conformalized approach only assumes data exchangeability. Furthermore, they assume a target filtering loss before training- our tolerance level e is defined at test time, which allows for much greater flexibility.
3 BACKGROUND
We begin with brief review of conformal prediction (see Shafer and Vovk, 2008). Here, and in the rest of the paper, upper-case letters (X) denote random variables; lower-case letters (x) denote scalars, and script letters (X') denote sets, unless otherwise specified. Proofs are deferred to the appendix.
At the core of conformal prediction is a simple statistical hypothesis test: for each candidate E y we must either accept or reject the null hypothesis that (Xn+1 1, Yu+1 = y) is correct to serve as the test statistic, where higher value of S reflects that (zn+1.3) 3) is less "conforming" to the distribution specified by dataset D. For instance, S could be computed as - log Po (p/(yee ()) where 0 is a model fit to D.
pairing. Formally, we rely on nonconformity measure S ([In+1. y). D) D)
Definition 3.1 (Nonconformity measure). Let 2 : X' x )' be the space of examples (X, Y), and let 2(-) == Uaz1 (X' x )/ be the space of datasets of examples D, of any size d 2 1. A nonconformity measure S is then a measurable mapping S: 2 x (+) + TR. that assigns a real-valued score to any example (X, Y), indicating how d it is from a reference dataset D. Furthermore, in order to retain exchangeability, is symmetric with respect to permutations of its input data.
To be specific, exact or full CP takes D to be all of the examples seen so far, including the candidate (#n-1. v). Thus, the nonconformity measure S has to be re- re-trained each time. An aiterative-which
"hhe defimition of "different" here is intentionally vague, as any metric will technically work.
3

---

Published as a conference paper at ICLR 2021
use in this paper w.l.ogg-iis the inductive or split CP variant (Papadopoulos, 2008) which assumes that D is a proper training set, independent of any of the subsequent n + exchangeable examples used for CP. Dropping D for ease of notation, denote the score for example (X, Y) as the random variable S(X, Y. The degree of nonconformity can then be quantified using a p-value.
Lemma 3.2 (Smoothed p-value), Assume that the random variables Vi,...,, Vn+1 are exchangeable. We define the smoothed empirical p- p-value pvalue V1n) as
pvalue(Va+1 V1s) := 1 E [1, n]: V, v 11 +
r Hi [1, V; = Vn+1)1+1
(2)
n + 1
where T ~ U (0, Then, for any E (0, 1). we have P( pvalue(Vn-1 V1m) <c) S.
To construct the final conformal prediction, the classifier uses the p-values to include all y for which the null hypothesis-i.c -i.e., that the candidate pair (In+1; 1, y) is conformal-is not rejected.
Theorem 3.3 (CP: Vovk et al. (2005), see also Lei et al. (2018)). Assume that the random variables (X,, Y.) E X' x V. =...... n 1 are exchangeable. For any nonconformity measure S, and e E (0, 1), define the conformal label sel (based on the first n samples) at In E as
Ca(#n+1) == {ur E V: (ralue(S((n41:222 V), S(Z1ms (o01:::)mm) > ej.
(3)
Then (n(())1) satisfies Eq. 1, where P (Yu+1 E (X(+2))) 2 21-6
4 CONFORMAL PREDICTION WITH EXPANDED ADMISSION
We now introduce our strategy for improving the predictive efficiency of CP classifiers. What might it mean for an alternative label to be "good enough?" Among other factors, this depends on the task, the label space }, and even the input For example, in IR, two different texts might independently provide sufficient information for claim x to be resolved. Formally, we pose the underlying setting as a set-valued function f X' + 2", where the ground truth is defined as the expanded set of all admissible answers f.X for input X (e.g., given our notions of semantic equivalence or error tolerance). Unlike ranking or multi-label classification, however, our evaluation only demands retrieving single element of this ground truth set (and without any preference as to which element).
It often the case that this underlying function remains unknown- after all, exhaustively annotating all possible admissible answers can quickly become intractable for many problems. Rather, we assume that what we observe in our dataset are samples, (X, from the underlying ground truth sets f-X,) via some additional observation process (e.g., influenced by which annotator wrote the answer to the question). In this view, the distribution P governing each pair (X,, Y) is an induced distribution from this set-valued function, together with the unknown observation process. We can then use the provided dataset reference Yú to seed label-cxpansion operation, in an attempt to approximate
f(X,). More concretely, for some choice of admission function g: (X' )) x y - {0, 1). construct a set of inferred admissible labels Ay given the seed reference (X- = x, Y = y), i.e.,
Az(x, = {u E V: g(Z,V.0) =1}.
(4)
Assumption 4.1. For any reference label Y e f(X). we have that A, AX, contains Y and is a subset of the full ground truth. That is. AX Y) obeys Y E A, Y) S fX)).
In this work we assume that g is given to us (not learned), and a deterministic function that has no inherent error in its outputs. For many tasks, this is quite natural assumption, as it is often feasible for the user to define a set of rules that qualify label admission-<s e.g., syntactic normalization rules in NLP, or expanding some small 8 d-neighborhood of the original y given some metrie. In Appendix B we discuss a relaxation of this assumption in which A, (X, Y') might have some error.
Given g. x, and y, any prediction that is a member of the derived set Ag is then considered to be admissible, i.., a success. For example, in IR for claim verification, let h be the verification model (or human) that, given the claim and evidence y, outputs a score for the final verdict (that the claim is true or false). The admission might then be defined as g(x, y, 7) == 1 ((h xx) - h( x:] ] & d}. where 5 is a small slack parameter. This then leads us to a helpful definition of expanded admission: Definition 4.2 (Expanded admission). Given any label admission function g and data points ((X,, Y= drawn exchangeably from an underlying distribution P, conformal predictor pro-
4

---

Published as a conference paper at ICLR 2021
Algorithm 1 Cascaded inductive conformal prediction with distribution-free marginal coverage.
Definitions: (St...., Sm) sequence of nonconformity measures. .M is monotonic correction controlling for family-wise wise error, 2n+1 E X is given test point. 21.u E X and yıu y are the previously observed calibration examples and their labels, respectively, y is the label space. is the tolerance level.
I: function PREDICT(2++11 (Zimm Vin).. c)
2: Cn +
b Initialize with the full label set. Conservatively set unknown p-values.
3:
p P2 _... p + 1, E E
4:
for j
m do C% + {
5:
Initialize the current output.
6:
for y E Ch-+1 do
b. Iterate through the previous label
7:
p pvalue (S) (1n+1, v), Sy (y yn.))
P Update the j-th p-value for (Ir+41, y)-
1 + M(p (1)
....,!!!!! ,...,
)
b Correct the current p-values for MHT.
9:
if (p) c) then
Keep y iff the corrected p-value supports it.
10:
C C U [v}
11:
return C
Return the final output of the cascade.
ducing admissible predictions C,, C, (Xn+1) (based on the first points) for exchangeable test example Xn+1 considered to be valid under expanded admission if for any e E (0, 1), C, satisfies
P ((IA)(XntI, 1a+1) n C. 21) 2 1 for all distributions P.
(5)
Recall that by predictive efficiency mean that we desire |c,, (Xnn1)) be small. A CP that simply returns all possible labels is trivially valid, but not useful. By Definition 4.2, we only need to identify least one Yn++1 that is deemed admissible according to g. As such, we propose modification that allows the classifier to be more discriminative-ann produce smaller C., Cx,(Xx1)) testing the null hypothesis that y not just conforming, but that the most conforming admissible y for For each data point (X, = Iú, Y; ys). we then define the minimal nonconformity score as
Smin (xa ys) == min {S(z), D): E Ag(
(6)
and use these random variables to compute the p-values for our conformal predictor.
Theorem 4.3 (CP with expanded admission). Assume that (X,, Yi) E x V, 1,..., + are exchangeable. For any non-conformity measure S, label admission function g, and E (0, 1), define the conformal set (based on the first samples) at Fn+1 E X as
Cmin (xn+1) == { E pvalue (S(In41, v), Smin ( VImm) > >e).
Then Cminn (Xu+1) satisfies Eq. 5. Furthermore, we have E [ (Xm+1)l] S S [[ (Xn+1)))
We present a proof in Appendix A.3. Section 7 we demonstrate empirically that this simple modification can yield large improvements in efficiency, while still maintaining the desired coverage.
5 CONFORMAL PREDICTION CASCADES
We now introduce our strategy for improving the computational efficiency of conformal prediction. As is apparent from Eq. 3, the cost of conformal prediction is linear in [)]] In practice, this can limit the tractable choices available for the nonconformity measure S, particularly in domains where [)] is large. Furthermore, predictive and computational efficiency are coupled, as being forced to use weaker S reduces the statistical power the CP. Our approach balances the two by leveraging prediction cascades (Sapp et al., 2010; Weiss and Taskar, 2010, inter alia), where models of increasing power are applied sequentially. At each stage, the number of considered outputs is iteratively pruned. Critically, clarity of presentation, in this section we return to the standard setting without expanded admission (i.e., where C, (X.+1) satisfies Eq. 1), but emphasize that the method applies to either case.
conformalize the cascade, which preserves marginal coverage. For
5

---

Published as a conference paper at ICLR 2021
and corresponding p-value is com- puted for every candidate E J Different y, however, might be much easier to reject than others, and can be filtered using simple metries. For example, in IR, wholly non-topical sentences (of which there are many) can be discarded using fast key-word matching algorithms such as TFIDF or BM25. On the other hand, more ambiguous sentences sentences-pprhaps those the same topic but with insufficient information-
When constructing C, (Xn+1) via Eq. 3. nonconformity
require a more sophisticated scoring mechanism, such as a neural network.
Assume that we are given a sequence of progressively more discriminative, yet also more computa- tionally expensive, nonconformity measures (S),...,S,,, When applied in order, we only consider
y C₁ (Xn+1) as candidates for inclusion in C,++ (Xn+1). Thus, C, (Xn+1) S C Cm--1 (Xn+1) S S (Xn+1) S Y. In this way, the amortized cost of evaluating m measures over parts of ) can be lower than the cost of running one expensive measure over all of it. For example, IR, we can use BM25 (S)) to prune the label space passed to neural model (S2). Furthermore, combining multiple nonconformity measures together can also lead to better predictive efficiency when using complementary simila ensembling (Toccaceli and Gammerman, 2017).
Naïvely applying multiple tests to the same data, however, leads to the multiple hypothesis testing (MHT) problem. This results in an increased family-wise error rale (i.e., false positives), making the CP invalid. Many corrective procedures exist in the literature (c.g., see Liu (1996)). Formally, given m p-values (P1 (Pi..... Pm) for pair (X, Y), denote as .M some such correction satisfying
p M (P1 Pm.) P (P <cc Y is correct) S.
(8)
Furthermore, we require M to be element-wise monotonic*, i.e. (where s operates element-wise):
M (PI,..,,Pall x P
Pm)) S M (PI...., .m
We consider several options for M, namely the Bonferroni and Simes corrections (see Appendix E). In order to exit the test early at cascade before all the p-values (i.e., for measures k: > j) are known, we compute an upper bound for the corrected p-value by conservatively assuming that Ps 1, vk > j. The full procedure is demonstrated in Algorithm I, and formalized in Theorem 5.1.
exchangeable. For any sequence of nonconformity measures (S)...., .S)) yielding p-values (Pi...., Pm.,, and e (0, 1), define the conformal set for step j (based on the first n samples) at In41 E X as
Theorem 5.1 (Cascaded CP). Assume that (X,, Y;) E X'
.....,
(I := { (y p(a) >
(10)
where p(u) is the conservative p-value for candidate y at step j. M(P(U) ...... P(M) .1..... 1). with ply) 1. Then Vj [1, m), C₁ (Xn+1) satisfies Eq. and CT (Xn+1) S Cj
We present proof in Appendix A.4. Theorem 5.1 also easily extends to the setting of Eq. 5. An important result is that early pruning will not affect the validity of the final result, C.P.
EXPERIMENTAL SETUP
We empirically evaluate method on three different tasks with standard, publicly available datasets. In this section, we briefly give a high-level outline of each task and our conformalized approach to it. We also describe evaluation methodology. We defer the technical details for each task, such as data preprocessing, training, and nonconformity measure formulations, to Appendix C.
6.1 TASKS
Open-domain question answering (QA). Open-domain question answering focuses using large-scale corpus 2 to answer arbitrary questions via search combined with reading comprehension. We use the open-domain setting of the Natural Questions dataset (Kwiatkowski et al., 2019). Follow- ing Chen et al. (2017), we first retrieve relevant passages from Wikipedia using a document retriever, and then select an answer span from the considered passages using document reader. We use Dense Passage Retriever model (Karpukhin et al., 2020) for the retriever, and a BERT model (Devlin
Note that we are unaware of any common M beyond contrived examples satisfying (8) hut not (9).

---

Published as a conference paper at ICLR 2021
et al., 2019) for the reader. The BERT model yields several score variants cascade (see Table C.1). Any span from any retrieved passage that matches any of the annotated answer strings when lower-case and stripped of articles and punctuation is considered to be correct.
multiple in our
Information retrieval for faat verification (IR). As introduced in $1, the goal of IR for fact verification is to retrieve sentence that can be used support refute given claim. We use the FEVER dataset (Thorne et al., 2018), in which evidence is sourced from a set of ~40K sentences collected from Wikipedia. A sentence that provides enough evidence for the correct verdict (true/false) is considered to be acceptable (multiple are labeled in the dataset). Our cascade consists of (1) a fast, non-neural BM25 similarity score between a given claim and sentence, and (2) the score of an ALBERT model (Lan et al., 2020) trained to directly predict if a given claim and sentence are related.
In-silico screening for drug discovery (DR). In-silico screening of chemical compounds is a common task in drug discovery/repurposingg, where the goal is to identify possibly effective drugs to manufacture and test (Stokes al., 2020). Using the ChEMBL database (Mayr et al., 2018), we consider the task of screening molecules for combinatorial constraint satisfaction, where given specified constraint such as "has property A but not property B", we want to identify at least one molecule from given set of candidates that has the desired attributes. Our cascade consists of (1) the score of a fast, non-neural Random Forest (RF) applied to binary Morgan fingerprints (Rogers and Hahn, 2010), and (2) the score of directed Message Passing NN ensemble (Yang et al., 2019).
6.2 EVALUATION METRICS
For each task, we use a proper training, validation, and test set. We use the training set to learn all nonconformity measures S. We perform model selection specifically for CP on the validation set, and report final numbers on the test set. For all CP methods, we report the marginalized results over 20 random trials, where in each trial we partition the data into 80% calibration (I1:n) and 20% prediction points (n++1) ). In order to compare the aggregate performance of different CPs across all tolerance levels, we plot each metric as function of e, and compute the under the curve (AUC). In all plots, shaded regions show the 16-84th percentiles across trials. We use the following metrics:
Predictive accuracy. We measure the accuracy rate as the rate at which least one admissible prediction is in C.. i.e., [A, (Xn+1, Y1+1) n (x,+ 2 1 (see Eq. 5). To be valid-the key criteria in this work-a classifier should have an accuracy rate
e, and AUC > 0.5. Note that more is not necessarily better: higher success rates than required can lead to poor efficiency (i.c., the size of C,, can afford to decrease at the expense of accuracy).
Predictive efficiency (L). We measure predictive efficiency as the size of the prediction set out of all candidates: |C,,1 1 The goal is to make the predictions more precise while still maintaining validity. Lower predictive efficiency is better (1), as it means that the size of C, is relatively smaller.
Amortized computation cost (1). We measure the amortized computation cost as the ratio of pvalue computations required to make cascaded prediction with early pruning, compared to this work we
when using a simple combination of CPs (no pruning, same number of measures). do not measure wall-clock times as these are hardware-specific, and depend heavily on optimized implementations. Lower amortized cost is better, as it means that the relative number of p-value computations required to construct C.a (for given m) is smaller.
7 EXPERIMENTAL RESULTS
In the following, we address several key research questions relating to our two combined conformal prediction advancements, and their impact on overall performance. In all of the following experiments, we report results on the test set, using cascade configurations selected based on the validation set performance. The QA and IR cascades use the Simes correction for MHT, while the DR cascades uses the Bonferroni correction. Additional results, details, and analysis are included in Appendix D.
Predictive efficiency of expanded admission. We begin by testing how deliberately calibrating for expanded admission affects predictive efficiency. That is, we use minimal admissible nonconformity scores {Stin (X,, Y)) for calibration (Eq. 6) to create (X,+1) using Eq. 7. Figure 2 shows the predictive efficiency of our min-calibrated CPs with expanded admission across all c, while Table I shows results for select values of c. We compare both eascaded and non-cascaded CPs, as Theorem 4.3 applies to both settings. The non-cascaded CP uses the last nonconformity measure
7

---

Published as a conference paper at ICLR 2021
1.0
1.
1.0
00:03111
CP (9:064
249)
Pedioove Eftciec)
0-8
Cascaded (949)) 01391
0.5
Cascadec
(0.0334)
Prefrowe Ent.eeeeeeeeee Effeceec
0.
Cancaded (0.250)
02411
Cascadied
06-
04-
6.
0.4
044
0.0
0.0
06
0.0
0.7
0.0
0.2
0.0
0.6
1-c
1.0
1.0
1.0
0.0
0.0
0.0
0.6
2:0.
0.0
0.4
GA
0.4
CP 71.00
(9 1600
(0.01:0
02
Cascaded (9.54))
Min CP (0.593)
02-
Cencadied (0.553)
Mn (0.498)
0.2
Concaded (0-201)
Min 895)
Cascaded Min 10.530)
Cascadio Min (0.533)
Cascoded Cn (0.348)
0.0
0.0
0.0
0.
1.0
10
0.0
02
1.
1-c
1-c
1-2
(a) QA
(b) IR
(c) DR
Figure 2: Does calibrating using minimal admissible nonconformity scores ($4) improve predictive efficiency? We show predictive efficiency and success rates function of e. The efficiency of the min-calibrated CPs (both cascaded and non-cascaded) is significantly better (i.e., lower) than standard CP across all tasks, especially at critical values of The min-calibrated CP's accuracy hugs the diagonal, allowing it to remain valid, but be far less conservative (resulting in better efficiency).
Baseline CP
min-CP
Cascaded min-CP
Task
Target Acc. (1 e)
Acc.
C..
Acc.
(mmin)
Acc.
[
Amortized cost
0.90
0.98
1245.7
0.90
198.0
0.90
235.1
0.59
0.80
0.94
453.5
0.80
58.7
0.80
57.7
0.50
QA
0.70
0.91
227.8
0.70
22.1
0.70
20.6
0.45
0.60
0.87
127.8
0.60
10.6
0.61
9.5
0.42
0.99
1.00
33.6
0.99
17.8
0.99
18.0
0.92
0.95
1.00
20.9
0.95
7.4
0.95
7.4
0.79
IR
0.90
0.98
13.8
0.90
4.0
0.90
3.8
0.73
0.80
0.95
6.7
0.80
1.7
0.80
1.6
0.63
0.90
0.99
429.8
0.90
84.1
0.91
147.8
0.84
0.80
0.97
305.8
0.80
42.7
0.81
62.1
0.79
DR
0.70
0.96
216.6
0.70
28.1
0.71
37.3
0.75
0.60
0.94
145.6
0.60
19.3
0.63
24.6
0.72
Table CP results for specific tolerance levels e. Each line shows the empirical accuracy (Acc.) and the (raw) size of the prediction set for our two methods compared to regular CP, per target accuracy rate (1 c). The amortized computation cost of the cascade, consequence of pruning, is also given.
of the cascaded CP. Across all tasks, the efficiency of the min-calibrated CP is significantly better than the baseline CP method, and results in tighter prediction sets -os--iiinn up to 4.6x smaller AUC. Naturally, this effect depends on the qualities of the admission function g and resulting admissible label sets Ay. For example, the most dramatic gains are seen on QA. This task has relatively large variance among admissible label nonconformity scores (i.e., some admissible answer spans are much easier to identify than others), and thus calibrating for the most conforming spans has large impact.
Validity minimal nonconformity calibration. As per Theorem 4.3, we observe that our min- calibrated CP still creates valid predictors, with an accuracy rate close to 1 1- average. We see that the min-calibration allows the predictor to reject more wrong predictions (lower predictive efficiency, which is better) while, with high enough probability, still accept at least standard CP methods, however, are more conservative and result in prediction sets and accuracy rates larger than necessary. This effect is most pronounced at smaller (e-g., < 0.2).
that is correct. The
8

---

Published as a conference paper at ICLR 2021
1.0
3.4
1.0
0.8-
D.E-
0.0
Amortbed Cost
Amartbbd Cost
Amorrtzed Cozt
0.0
64
144
02
Min (1.00)
04
Nin 12.00]
02
Min (C-C0)
Cascaded Nat
Conratted Min (0.38))
Cancadie Nix TOR)
84
60
0.7
0.
04
0.0
02
0.4
0.0
6.2
0.6
DG
1-
1-c
1-c
(a)
QA
(b) IR
(c) DR
Figure 3: How effective is cascaded conformal prediction ($5) at pruning the candidate space? Incorporating early rejection via the CP cascade reduces the fraction of required p-value computations. Larger tolerance levels (e) allow for more aggressive pruning rates.
Computational efficiency of conformalized cascades. Figure shows the amortized cost, in terms of percentage of p-value computations skipped, achieved using our cascaded CP algorithm. Our method reduces the number of p-value computations by up to factor of 1/m for an m-layer cascade. The effect of conformalization clear: the more strict an we demand, the fewer labels we can prune, and vice versa. To simplify comparisons, In practice, however, the benefits of early pruning will generally grow by layer, as the later p-values assumed to be increasingly expensive to compute. Again, exactly quantifying this trade-off in we leave for future work.
metric gives equal weight to all p-value computations.
terms of absolute cost model- and implementation-speaiee
Conservativeness of conformalized cascades. A limitation of the cascade approach is the con- servative nature of the MHT-corrected p-value (i.e., the Bonferroni effect), which can reduce the statistical power of the CP as the number of cascade layers grows. This effect is especially present if the cascaded measures are highly dependent. In general, however, in both Figure and Table 1, we see that the benefits of combining complementary cascaded models largely make up for this drop in statistical power, as our cascaded min-calibrated CPs nearly matches the predictive efficiency of our non-cascaded models. Importantly, this is achieved while still improving computational efficiency.
Relation to heuristic methods. For completeness, in Appendix D.2 we also compare CP to common heuristic methods for producing set-valued predictions namely. taking the top-k predictions and taking all predictions for which the model's score exceeds threshold т. We show that while CP is more general, it can be (practically) reduced to each of these methods with the appropriate choice of nonconformity measure. In some cases, the flexibility of CP even allows for better predictive efficiency, even while those heuristics do not amortize cost or guarantee coverage in finite samples.
CONCLUSION
Conformal prediction can afford remarkable theoretical performance guarantees to important ap- plications for which high accuracy and precise confidence estimates are key. Naively applying CP, however, can be inefficient in practice. This is especially true in realistic domains in which the correct answers are not clearly delineated, and in which the computational cost of discriminating between options starts to become limiting factor. In this paper, we proposed two novel methods that provide two more pieces of the puzzle. Our results show that (I) calibration using expanded admission consistently improves empirical predictive efficiency, and (2) conformal prediction cascades yield better computational efficiency-
and and thereby enable the use of more powerful classifiers.
ACKNOWLEDGEMENT
We specially thank Ben Fisch for his helpful comments and discussion on this work, in addition to Kyle Swanson for help in running the chemprop models. We also thank the MIT NLP group for valuable feedback. AF is supported in part by the National Science Foundation Graduate Research Fellowship under Grant #11 123244 Any opinion, findings, conclusions, or recommendations expressed this material are those of the authors and do not necessarily reflect the views of the the NSF or the U.S. Government. TS is supported in part by DSO grant DSOCL 18002. This work is also supported in part by MLPDS and the DARPA AMD project.

---

Published as a conference paper at ICLR 2021
REFERENCES
Dario Amodei, Chris Olah, Jacob Steinhardt, Paul Christiano, John Schulman, and Dan Mané. Concrete problems in ai safety. arXiv preprint arXiv:1606.06560 2016.
Arsenii Ashukha, Alexander Lyzhov, Dmitry Molchanov, and Dmitry Vetrov. Pitfalls of in-domain uncertainty estimation and ensembling in deep learning. In International Conference on Learning Representations (ICLR), 2020.
Evgeny Burnaev and Vladimir Vovk. Efficiency of conformalized ridge regression. In Conference on Learning Theory (COLT), 2014.
L. Carlsson, M. Eklund, and Norinder. Aggregated conformal prediction. In AIAI Workshops, 2014.
Maxime Cauchois, Suyash Gupta, and John Duchi. Knowing what you know: valid confidence sets in multiclass and multilabel prediction. arXiv prepring: arXiv 2004. 10181, 2020.
Eugene Charniak, Mark Johnson, Micha Elsner, Joseph Austerweil, David Ellis, Isaac Haxton, Catherine Hill, R. Shrivaths, Jeremy Moore. Michael Pozar, and Theresa Vu. Multilevel coarse-to- fine PCFG parsing. In Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2006.
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes Reading Wikipedia answer open- domain questions. In Annual Meeting of the Association for Computational Linguistics (ACL), 2017.
Wenyu Chen, Zhaokai Wang, Wooseok Ha, and Rina Foygel Barber. Trimmed conformal prediction for high-dimensional models. arXiv preprint: arXiv 16/1.09933, 2016.
Wenyu Chen, Kelli-Jean Chun, and Rina Foygel Barber. Discretized conformal prediction for efficient distribution-free inference. Stat, 7(1):e173, 2018.
Victor Chernozhukov, Kaspar Wuthrich, and Yinchu Zhu. Distributional conformal prediction. arXiv preprint: arXiv 1909.07889, 2019.
Yuntian Deng and Alexander M. Rush. Cascaded text generation with markov transformers. arXiv preprint: arXiv 2006.01111 2020.
Jacob Devlin, Ming-Wes Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter the Association for Computational Linguisties: Human Language Technologies (NAACL-HLT), 2019.
Jay De Young, Sarthak Jain, Nazneen Fatema Rajani, Eric Lehman, Caiming Xiong, Richard Socher, and Byron C. Wallace. Eraser: A benchmark to evaluate rationalized nlp models. In Annual Meeting of the Association for Computational Linguisties (ACL), 2020.
Ran Yaniv and Yair Wiener. On the foundations of noise-free selective classification. Journal of Machine Learning Research (JMLR), 11553): 2010.
David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya A. Kalyanpur, Adam Lally, J. William Murdock, Eric Nyberg, John Prager, Nico Schlaefer, and Chris Welty. Building watson: An overview the deepqa project. Al Magazine, 31(3):59-79, Jul. 2010.
Francois Fleuret and Donald Geman. Coarse-to-fine face detection. International Journal of Computer Vision, 41(1-2):85-1
2001.
Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In International Conference on Machine Learning (ICML), 2016.
Yonatan Geifman and Ran EI- Yaniy. Selective classification for deep neural networks. In Advances 2017.
in Neural Information Processing Systems (NeurIPS), pages
10

---

Published as a conference paper at ICLR 2021
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In International Conference on Machine Learning (ICML), 2017.
Lior Hirschfeld, Kyle Swanson, Kevin Yang. Regina Barzilay, and Connor W. Coley. Uncertainty quantification using neural networks for molecular property prediction. arXiv preprint: arXiv 2005.10036, 2020.
Robert A. Jacobs, Michael Jordan, Steven J. Nowlan, and Geoffrey E. Hinton, Adaptive mixtures of local experts. Neural Computation, 3(1):79-87, March 1991.
Heinrich Jiang, Been Kim, Melody Guan, and Maya Gupta. To trust not to trust a classifier. In Advances in Neural Information Processing Systems (NeurIPS), pages 5541-5552. 2018.
Xiaoqian Jiang, Melanie Osl, Jihoon Kim, and Lucila
Calibrating predictive model estimates support personalized medicine. Journal of the American Medical Informatics Association, 19(2):263-274, Mar-Apr 2012.
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus, 2017.
Daniel Jurafsky and James H. Martin. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall PTR, USA, 1st edition, 2000. ISBN 0130950696.
Vladimir Karpukhin, Barlas Oğuz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen tau Yih. Dense passage retrieval for open-domain question answering. arXiv preprint: Xrxiv 2004.04900 2020.
Danijel Kivaranovic, Kory D. Johnson, and Hannes Leeb. Adaptive, distribution-free prediction intervals for deep networks. In Silvia Chiappa and Roberto Calandra, editors, Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pages 4346-4356, Online, 26-28 Aug 2020. PMLR.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming- Wei Chang, Andrew Dai, Jakob Uszkoreit, Quoe Le, and Slav Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association of Computational Linguistics, 2019.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In Advances in Neural Information Processing Systems, pages 6402-6413. 2017. 2017.
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference Learning Representations (ICLR), 2020.
Kenton Lee, Tom Kwiatkowski, Ankur Parikh, and Dipanjan Das. Learning recurrent span representations for extractive question answering. arXv preprint: arXiv 1611.01433 2016.
Kimin Lee, Honglak Lee, Kibok Lee, and Jinwoo Shin. Training confidence-calibrated classifiers for detecting -uitor-diitributtin samples. In International Conference on Learning Representations (ICLR), 2018.
Jing Lei, Max G'Sell, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113(523): 1094-1111, 2018.
Haoxiang Li, Zhe Lin, Xiaohui Shen, Jonathan Brandt, and Gang Hua. A convolutional neural network cascade for face detection. In Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
Henrik Linusson, Ulf Norinder, Henrik Boström, Ulf Johansson, and Tuve Löfström. On the calibration of aggregated conformal predictors. In Proceedings of the Sixth Workshop on Conformal and Probabilistic Prediction and Applications, 2017.

---

Published as a conference paper at ICLR 2021
Wei Liu. Multiple tests of non non-hierarchical finite family of hypotheses. Journal of the Royal Statistical Society. Series B (Methodological), 58(2):555 461, 1996.
Andreas Mayr, Günter Klambauer, Thomas Unterthiner, Marvin Steijaert, Joerg Wegner, Hugo Ceulemans, Djórk-Amé Clevert, and Sepp Hochreiter. Large-scale comparison of machine learning methods for drug target prediction on chembl. Chemical Science, 9, 06 2018. doi: 10.1039/C&SC00148K
Alexandru Niculescu-Mizil and Rich Caruana. Predicting good probabilities with supervised learning. In International Conference on Machine Learning (ICML., 2005.
Yixin Nie, Haonan Chen, and Mohit Bansal. Combining fact extraction and verification with neural semantic matching networks. In AAAI Conference on Artificial Intelligence (AAAT), 2019.
Harris Papadopoulos. Inductive conformal prediction: Theory and application neural networks. In Tools in Artificial Intelligence, chapter 18. IntechOpen, Rijeka, 2008.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-lear:: Machine learning in Python. Journal of Machine Learning Research (JMLR), 12:2825-2888 2830, 2011.
Pranav Rajpurkar, Robin Jia, and Percy Liang. Know what you don't know: Unanswerable questions for SQuAD. In Annual Meeting of the Association for Computational Linguistics (ACL), 2018.
Radim Rehūřek and Petr Sojka. Software Framework for Topic Modelling with Large Corpora. In LREC 2010 Workshop New Challenges for NLP Frameworks. ELRA, 2010.
David Rogers and Mathew Hahn. Extenned-coomectiitty fingerprints. Journal of chemical information and modeling, 50:742-54, 05 2010.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
Yaniv Romano, Rina Foygel Barber, Chiara Sabatti, and Emmanuel Candès. With malice toward none: Assessing uncertainty via equalized coverage. Harvard Data Science Review, 4 2020.
Alexander Rush and Slav Petrov. Vine pruning for efficient multi-pass dependency parsing. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT). 2012.
Einar Andreas Rødland. Simes' procedure is 'valid on average'. Biometrika, 93(3):742-746. 2006.
Benjamin Sapp, Alexander Toshev, and Ben Taskar. Cascaded models for articulated pose estimation. In European Conference on Computer Vision (ECCV), 2010.
Sanat K. Sarkar and Chung-Kuei Chang. The simes method for multiple hypothesis testing with positively dependent test statistics. Journal of the American Statistical Association, 92(440): 1601-1608, 1997.
Tal Schuster, Darsh Shah, Yun Jie Serene Yeo. Daniel Roberto Filizzola Ortiz, Enrico Santus, and Regina Barzilay. Towards debiasing fact verification models. In Conference on Empirical Methods in Natural Language Processing and the International Joint Conference Natural Language Processing (EMNLP-IJCNLPP, 2019.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. Journal of Machine Learning Research (JMLR), 9:371-421, June 2008
R. J. Simes. An improved Bonferroni procedure for multiple tests of significance. Biometrika, 73(3): 751-754, 12 1986.
Jonathan Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz Nina Donghia, Craig MacNair, Shawn French, Lindsey Carfrae, Zohar Chiappino- Peppe Ahmed Badran, Ian Andrews, Emma Chory, George Church, Eric Brown, Tommi Jaakkola, Regina Barzilay, and James Collins. A deep learning approach to antibiotic discovery. Cell, 102.e13, 02 2020.
Victoria Tran, Anush
12

---

Published as a conference paper at ICLR 2021
James Thome, Andreas Vlachos, Christos Christodoulopoulls, and Arpit Mittal. FEVER: large- scale dataset for fact extraction and VERification. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), 2018.
Ryan J Tibshirani, Rina Foygel Barber, Emmanuel Candes, and Aaditya Ramdas. Conformal prediction under covariate shift. In Advances Neural Information Processing Systems (NeurIPS). 2019.
Paolo Toccaceli and Alexander Gammerman. Combination of conformal predictors for classification. In Sixth Workshop on Conformal and Probabilistic Prediction and Applications, 2017.
Vladimir Vovk, Alex Gammerman, and Glenn Shafer. Algorithmic Learning in a Random World.
Springer-Veriee Berlin, Heidelberg, 2005.
Vladimir Vovk, Valentina Fedorova, Ilia Nouretdinov, and Alexander Gammerman. Criteria of efficiency for conformal prediction. In International Symposium on Conformal and Probabilistic Prediction with Applications Volume 9653, 2016.
Vladimir Vovk, Ivan Petej, Ilia Nouretdinov, Valery Manokhin, and Alexander Gammerman. Compu- tationally efficient versions of conformal predictive distributions. Neurocomputing, 397:292 308, 2020.
David Weiss and Benjamin Taskar. Structured prediction cascades. International Conference on Artificial Intelligence and Statistics (AISTATS), 2010.
Kevin Yang, Kyle Swanson, Wengong Jin, Connor Coley, Philipp Eiden, Hua Gao, Angel Guzman- Perez, Timothy Hopper, Brian Kelley, Miriam Mathea, Andrew Palmer, Volker Settels, Tommi Jaakkola, Klavs Jensen, and Regina Barzilay. Analyzing learned molecular representations for property prediction. Journal of Chemical Information and Modeling, 59(8)33370-3388, 2019.
13

---

Published as a conference paper at ICLR 2021
Appendix
A PROOFS
A.1 PROOF OF LEMMA 3.2
Proof. This is a well-known result; we prove it here for completeness (see also Tibshirani al. (2019) for a similar proof). It is straightforward to show that for P pvalue(Vn+1) Vin),
P Vn is ranked among the [e (n + +1] largest of V1,... Vn+1- c
According to our exchangeability assumption over the n + variables, the right hand side event occurs with most probability [e (n 1)]//m+11) c.
A.2 PROOF OF THROREM 3.3
Proof. Once again, this is well-known result: we prove it here for completeness (see also Tibshi- rani et al. (2019) for similar proof). For notational convenience, let random variable V; be the nonconformity score ((,,, Y,). Since the nonconformity scores Vi are constructed symmetrically, then
((X,, (Xa+1, Y x++)) & ((Xo(1)) Ya())..... (Xx()))....((((x)) Yo(n+1)))
(V...... 12+1) _ (Vo(1)...., Vo(n+1))
for all permutations (o(1). ... o 1)). Therefore, if ((x, Y exchangeable, then their nonconformal scores [V:)a=+
By the construction of C. (x we have
Yn-1 $ (x(xn+)) + pvalue (Va+1, Vin) S. Then, using Lemma 3.2, P( (Xm+)) = P(Yn-1 Cx((n+1)) 21 -
A.3 PROOF OF THEOREM 4.3
Proof. (1) First we prove that Cminn Cxin((ns (Xn+1) satisfies Eq. 5. We begin by establishing exchangeability of the minimal nonconformity scores, Smin (X,, Yi), as defined in Eq. 6. We simplify notation once again by letting V; == S(X,, Yi), and M, = Smin X,, Y;). To denote S(X;, Y) for general random Y E V, we write V v(Y) By the same argument as Theorem 3.3, we have that the base {Vi) 1++1 are exchangeable. Since the label expansion and subsequent min operator are taken point-wise over the V,, we retain symmetry, and therefore
(Vi, Va+1) _ (Vo(i).... Vo(n+1)) = (M, Ma+1) & (Mo().... ................................ Mo(n+1))
for all permutations (a(1), ... o + 1)). Thus the (M,
1++1 are also exchangeable.
Next, we want to prove that C.nin satisfies Eq (1Ag((nnt Yn-1) (min(Xn+1)l 1) 2 1-c.
Let (X Xn+1)l = k. where (x(N++1, Xn+1) = (Y.t....., y 1 Then:
(1Ag(X (Xn+1, Ynt1) n 2 1) P
U C
Cmin
max (P (Pi Cmiin
..... (Yx E &Cmiu))
max [P (pvalue (P()) Mim) > E) ,...,, (vaalue (PPt) (P*) n+1 M > })}
P
c)
where (i) by construction of M.+1 (assuming w.l.o.g. that it is unique in the case of the random tie-breaking in pvalue), and (ii) comes from applying Lemma 3.2 to the exchangeable {M)
14

---

Published as a conference paper at ICLR 2021
(2) We now prove the second part of Theorem 4.3: that E ||cT (Xx+1)l E (ICn Again, to simplify notation, we drop the dependence on (I2, where obvious.
Let {ys E C
be the indicator random variable that yi E y included C.. Then:
D
31
D
E ||
R
Σ [ye E c.)
Σ
E (v E C..)
Σ P (vvalue(V(
otll Vin) >
By the same derivation we also have E ||cHiu|| = E (pvalue v(u) n+1 (Mm) > z).
Since M, E [1, + 1] by definition, we get that Vn+1 S M, - Vn+1 S V,, and the easy to see from the definition of the pvalue (see Eq. 2) that this leads to P(pvalue ((() h-11 Mim) >
S [P(pvalue(Vat) a+1 Vin) > e). Vy E V. Therefore, it follows that E [[enin]] < E [[c,]]-
A.4 PROOF OF THEOREM 5.1
Proof. We restate assumption that M is valid multiple hypothesis testing correction procedure that properly controls the family-wise error rate,
P = M (P1,
Pm)) s.t. (P Se
is correct) Se
and that it is element-wise monotonic*
(P,,..., Pm) < (PI.....
where P: are p-values produced by different nonconformity measures for the same point (X. Y). and operates element-wise. First show that all C constructed via Eq. 10 satisfies Eq. 1 when all p- values are known and no pruning has been done. .M operates element-wiss over examples, therefore exchangeability is conserved and all basic individual p-value computations from nonconformity scores are valid as before. Then, by the construction of C, (Xn+1) we have
Yut1 & C. (X = PSC
and therefore,
P (Yn+1 E CT. (Xn+1)) = P (Yn+1 $ C (Xn+1))
= =1 - P P 2 c-
where the final inequality comes from the first assumption on M. Next, we want to prove that early pruning does not remove any candidates y that would not be removed from C. When all p-values after step j are not yet known, we set PEyj to 1. Using the clement-wise monotonicity of M, we have M (P)....,
1) (P ..... Pm). Therefore.
y y: p(0) > 2 2 2 yyv: p(y) >E).
yielding y E C. (Xn+1) = Cj by E V. We finish by using the earlier result for C (X,+1) ) to get IP (Y E CX 2 P(rY+1 E cm (x (xm+1)) 116,, E m1. Li
B APPROXIMATE EXPANDED ADMISSION
Assumption 4.1 states that g is a deterministic criterion that always produces a subset of the full ground truth, i.e., Y.+1 AX Yu+1) C f(X,+1). As stated earlier, for many tasks, this is reasonable assumption. For example, g( g(X, YYY, might be the outcome of sampling random human annotator, applying a fixed set of valid syntactic normalization rules, or checking if falls within some n-neighborhood of Y. Then, by design, 9 has no error when identifying admissible answers.
In other cases, we may wish to learn an approximation 9 of the true admission criterion g. For example, for QA, might be interested in learning "semantic equivalence" function based auxiliary paraphrase pairs. This inherently introduces some error, i.e., (x. y, g) + g(x, y, D) w.p.
As noted in the main text, though we formally require this condition, unaware of any common M heyond contrived examples satisfying Eq. but not Eq. See Appendix for common MHT corrections.
15

---

Published as a conference paper at ICLR 2021
In the following, we sketch process for accounting for this error while retaining valid predictions. We leave a more thorough analysis, formal proof, and experimentation for future work.
As the true error rate of 9 is unknown, we can instead bound it on a small set of labelled ii.d. data," by measuring the empirical false- sille-positve rate ý over m samples:
Σ
arg min S(r,. 3) & Ag(as. (E
(1I)
Y
The empirical error follows a binomial distribution.
Borrowing from the proof of Theorem 4.3, let Ma+1 be the minimal nonconformity score of the approximated admissible answers. We then want to bound P(M,+1 S T, E Ag(nn++1 ( where ÿ" is the most conforming approximate admissible answer used to derive Ma+1 and r is some threshold. If we assume that these joint events are non-negatively dependent (i.e., that our most-conforming labels tend to be ones that the approximate classifier does not make errors on), then we can bound IP PM S T, E Ag(xXn,,,,,,m Yn+1)) by IP S -)"I((" E (g ( 12).)).
The first term can then be bounded in similar manner as in Lemma 3.2, and the second by binomial confidence intervals for the true error rate 7, given the observed 5. Then T can be set to be the corresponding quantile that allows this probability bound to exceed
C IMPLEMENTATION DETAILS
Multiple labeled answers. When multiple answers are given (i.e., Un+1 is set) we take Ag(xx+1 11+1) as the union of all the admissible answers, along with any additional answers expanded by g. For the standard conformal prediction baseline, we calibrate on one of the answers at a time, chosen uniformly at random. Note that this is important to preserve equivalent sample sizes across min-calibrated CP and standard CP.6
Open-Domain QA. We use the open-domain setting of the Natural Questions (NQ) dataset (Kwiatkowski et al., 2019). In this task, the goal is to find short span from any arti- cle in Wikipedia that answers the given question. Questions in the NQ dataset were sourced from real Google search queries, and human annotators identified answer spans to the queries in Wikipedia articles (we use the short answer span setting, and only consider answerable, non-boolean questions).
We use the open-source, pre-trained DPR model for retrieval (i.e., the document retriever) and the BERT model for question answering (i.e., the document reader) provided by Karpukhin et al. (2020). To summarize briefly, the DPR model is trained maximize the dot-product similarity between the dense representations (obtained via BERT embeddings) of the question and the passage that contains the answer. For candidate passages, we use the Wikipedia-basee based corpus processed by Karpukhin et al. (2020), where each article is split into disjoint passages of 100 words, resulting in total of 21,015,324 passages. The DPR model pre-computes dense representations for all passages and indexes them with FAISS (Johnson et al., 2017) for efficient retrieval. At test time, relevant documents for a given dense question encoding are retrieved via fast similarity search. The reader model is standard BERT model with independent span prediction head. This model encodes the question and passage jointly, and therefore, the representations cannot be pre-computed. For each token, the model outputs independent scores for being the start or end of the answer span. We also follow Karpukhin et al. (2020) by using the output of the [CI.S] token to get a passage selection score from the reader model (to augment the score of the retriever). For ease of experimentation, we only consider the top 5000 answer spans per question- -taken as the top 100 passages (ranked by the retriever) and the top 50 spans per passage (ranked by the reader). In order be able to evaluate all E (0, 1) we discard questions whose answers do not fall within this selection. We retain 6750/8757 questions from the validation set and 2895/3610 from the test set.
We compose the cascade for this task using four metrics: the retriever score, followed by the reader's s passage selection score, the "span start" score, and the "span end" score. For the non-cascaded models, we take the sum of the span start and span end scores as a single metric.
'We must slightly strengthen our assumptions from simply exchangcable data to i.i.d. data. "Another possibility would be to calibrate on all the given answers, but we found this generally does worse.
16

---

Published as a conference paper at ICLR 2021
Task
Metric
Description
retriever
1. similarity score of the question and paragraph by the retrieval model.
passage
logit of the passage selection score by the BERT reader.
QA
span start
-1- logit of the answer's first token by the BERT reader.
span end
-1- logit of the answer's last token by the BERT reader.
span sum
span start + span end.
BM25
1- BM25 similarity score between query and candidate.
IR
CLS logit
1- logit of the claim-evidence pair by the ALBERT classifier.
RF
1- score of the candidate by the Random Forest model.
DR
MPNN
1- score of the candidate by the directed Message Passing Neural Network.
Table C.I: Nonconformity measures used in our experiments.
IR. We use the FEVER dataset for evidence retrieval and fact verification (Thorne et al., 2018). We focus on the retrieval part of this task. Note that the retrieved evidence can then be used to verify the correctness of the claim automatically (Nie et al., 2019; Schuster et al., 2019), or manually by a user. We follow the dataset splits of the Eraser benchmark (De Young al., 2020) that contain 97, 97,957 claims for training, 6,122 claims for validation, and 6,111 claims for test. The evidence needs to be retrieved from set of 40, 133 unique sentences collected from 4,099 total Wikipedia articles.
We compose the cascade using two metries: an efficienct non-neural BM25 model, and a neural sentence-pair classifier. Our BM25 retriever uses the default configuration available in the Gensim library (Rchûřek and Sojka, 2010). We perform simple preprocessing the text, including removing punctuation and adding word stems. We also add the article title to each sentence. Our neural classifier (CLS) is built top of ALBERT-Base and is trained with BCE on (claim, evidence) pairs. We collect 10 negative pairs for each positive one by randomly selecting other sentences from the same article as the correct evidence. For shorter articles, we extend the negative sampling to also include the top (spurious) candidates indentified by the BM25 retriever.
DR. We construct a molecular property screening task using the ChEMBL dataset (see Mayr et al., 2018). Given a specified constraint such as "is active for property A and property B but not property C². we want to retrieve at least one molecule from a given set of candidates that satisfies this constraint. The motivation of this task is to simulate in-silico screening for drug discovery, where it is often the case where chemists will searching for new molecule that satisfies several constraints (such as toxicity and efficacy limits), out of pool of many possible molecular candidates.
We split the ChEMBL dataset into a 60-20-20 split of molecules, where 60% of molecules are separated into a train set, 20% into validation set, and 20% into test set. Next, we take all properties that have more than 1000 labeled molecules (of which at least 100 are positive and 100 are negative, to avoid highly imbalanced properties). Of these ~00 properties, combinations that have at least 100 molecules with all K properties labelled (ChEMBL has many missing values). We set K to 3. For each combination, we randomly sample an assignment for each property (i.e., (active, inactive) sets. The molecules for each of the combinations are only sourced from their respective splits (i.e., molecular candidates for constraints in the property combination validation split only come from the molecule validation split). Therefore, at inference time, given a combination we have never seen before, on a molecules we have never seen before, we must try to retrieve at least one molecule that has the desired combination assignment.
take all N choose K
We keep 5000 combinations for each of validation and test
Both our random forest (RF) and the directed Message Passing Neural Network (MPNN) were implemented using the chemprop repository (Yang et al., 2019). The RF model based on the Scikit library (Pedregosa et al., 2011) 1) and uses 2048-bit binary Morgan fingerprints (Rogers and Hahn, 2010) of radius 2 to independently predict all target properties (active or inactive) for a given molecule. The RF model is fast to run during inference, even on a single CPU. The MPNN model uses graph convolutions to learn a deep molecular representation, that is shared across property predictions. Each property value (active/inactive) is predicted using independent classifier head. The final prediction is based on an ensemble of 5 models, trained with different random seeds. Given combination assignment (7 21,..., Z 2ạ), for both the RF and MPNN models, we take
17

---

Published as a conference paper at ICLR 2021
the nonconformity score the model's negative log- liliiiiiehhod,,, where the likelihood is computed independently, i.e. Po(Z) = 21...., ,, Zk = 2x) = [Ipo(22 Z2 = 21).
D ADDITIONAL EXPERIMENTAL RESULTS
We provide supplemental experimental results to those shown in $6. In D.1 we show example of closed-domain QA task where cascading multiple measures actually boosts the predictive efficiency to the extent that it outweighs the conservative MHT correction factor. In D.2 we compare our method to hcuristic methods at fixed efficiency levels, as described in $7.
D.1 COMPLEMENTARY CONFORMAL CASCADES FOR CLOSED-DOMAIN QA
The primary motivation in this work for conformalized cascades is to improve computational efficiency by allowing cheaper models to pre-filter the candidate space prior to running more expensive and more powerful models. Though not guaranteed, in some cases it is also possible that combining different nonconformity scores together has an overall synergistic effect that outweighs the generally conservative effects of the MHT corrections. This is similar in theory to ensembles or mixtures- of-experts (Jacobs et al., 1991), and similar results have been reported for combined conformal prediction (Carlsson al., 2014; Linusson et al., 2017: Toccaceli and Gammerman, 2017).
While the tasks in $7 focus on cascades that are designed primarily for efficiency, here we also explore cascades for the smaller-scale task of closed-domain questions answering the SQUAD 2.0 dataset (Rajpurkar et al., 2018). This task isolates the documen! reader aspect of the open-domain QA pipeline, in which relevant passage is already given. We cascade two primary models: (1) a span extractor (EXT) that gives independent scores for the start and end positions of the answer span, and (2) more expensive answer classifier (CLS) that considers the entire candidate span (i.c., models the start and end jointly). We briefly outline the implementation details before giving the results below.
The EXT model uses the ALBERT-BE Base QA model (Lan et al., 2020). It is trained to maximize the likelihood of the answer span 51. where p(start = i, end j) is modeled as p(start = i)p(end = j). During inference, the model computes all (n²) start and end position scores, and predicts the pair with the highest sum. We use the start and end position scores two separate nonconformity measures. The CLS model is also built on top of ALBERT-Base, and is similar to Lee et al. (2016). Instead of scoring start and end positions independently, representations at tokens (start) and j (end), and score them jointly using an MLP. We then train with binary cross-entropy (BCE) over correct and incorrect answers. We limit the number of negative samples (incorrect answers) to the top 64 incorrect predictions of the EXT model.
concatenate the corresponding hidden
The authors keep the original test set hidden; for ease of CP-specific evaluation we re-split the development set randomly by article. This results in 5,302 questions in our validation set, and 6,571 questions in our test set. The average length of paragraph in the evaluation set is 127 words. Together with the "no answer" option, a question for a paragraph of that length will have 8, 129 candidate answer spans. For the purposes of experimentation, we filter out questions for which the EXT model does not rank the correct answer within the top 150 predictions (so we can compute the full (0, 1) range of c tractably). This discards less than 0.5% of questions.
Our results across several values of epsilon are given in Table D. As in the tasks in $7, the min- calibrated CPs greatly improve over the baseline CP. In this case, however, the cascaded CP also consistently outperforms the CP with only single measure.
CP
min CP
Cascaded min CP
Suce.
[C..]
Suce.
Suce.
[
Amortized cost
0.99
1.00
17.69
0.99
6.68
0.99
6.31
0.50
0.95
0.98
5.14
0.95
3.14
0.96
2.45
0.42
0.90
0.95
3.09
0.90
1.98
0.92
1.76
0.40
0.80
0.86
1.66
0.80
1.31
0.83
1.24
0.38
Table D.I: CP results on the SQUAD 2.0 dataset.
18

---

Published as a conference paper at ICLR 2021
D.2 HEURISTIC METHODS
In addition evaluating our improvements over regular conformal prediction, we compare our conformal method to other common heuristics for making set-valued predictions. Specifically, we consider baseline methods that given some scoring function score y) and threshold to define the output set of predictions B at z E X' as
B r) = {y E y: score( y) 2 7
(12)
where T then tuned on the calibration set to find the largest threshold for the desired accuracy:
n
:e sup
[y B(z, r)} 2 +)))))2221 2-1
(13)
The prediction for the test point In+1 is then B(In+1, T.). We consider two variants: (1) fixed top-k, where score := -rank -rank(metri(((n411 v)) according to some metric, and (2) raw thresholding, where score := metric((n+1: V). i.e., some raw, unnormalized metric. Top-k simple and relatively robust to the variance of the metric used, but as it doesn't 't depend ø, it also means that both easy examples and hard examples are treated the same (giving prediction sets that are too large in the former, and too small in the latter). Raw metric thresholding, dynamically-sized prediction sets, but is more sensitive to metric variance. We emphasize that these baselines do not provide theoretical coverage guarantees for potentially non-i.i.d. finite samples.
the other hand, gives
When ignoring smoothing factors and restricting ourselves to a single, non-cascaded metric, it is straightforward see that choosing the nonconformity measure be S = rank(metric(z, or simply S == metric((,, y) makes the set C,2 (Zn+1) equivalent to B( where
F. = Quantile (1 F ((S(21, V))...,,((E,,, vo ) (
(14)
We write F(V) to denote the empirical distribution of set V. For large enough n, F. becomes nearly identical to - Note, however, that this comparison only applies to the split (i.e., inductive) conformal prediction setting. Metrics computed without relying on a held-out calibration set (as full CP is able to do) must treat the n + data points symmetrically. key feature of CP. Our methods extend to multiple cascaded metrics, finite n, and the full CP setting.
We compare predictive efficiency results when using top-k and threshold heuristics versus our CP methods in Figure D.1 and Table D.2. As expected, with large enough n, the baseline CP and Threshold methods are nearly equivalent. In some cases, top-k outperforms the threshold- and CP-based methods that use raw scores (this is likely due to variance in the densities of high scoring candidates across examples). When applying optimizing for admissible answers, our min-calibrated CP improves over all three methods. Note that optimizing for admissible answers is also applicable for the heuristic methods, in which case the trends will be similar to that of the bascline CP.
E MULTIPLE HYPOTHESIS TESTING
As we discuss in $5, naively combining multiple hypothesis tests will lead to an increased family-wise error rate (FWER). For visual example, see the uncorrected cascaded CP (blue dashed lined) in Figure 1. It demonstrates that combining nonconformal measures without using a MHT correction can result in accuracies smaller than e (i.e., invalid coverage).
Several methods exist for correcting for MHT by bounding the FWER (with different assumptions on the dependencies between the hypothesis tests). We experiment with the Bonferroni and Simes procedures. We test the corrections and IR, but not to hold for DR (See Figure E. Therefore, we use the Bonferroni correction for DR and Simes for the other two tasks. For completeness, briefly describe the two methods and the assumptions they rely on below (extensive additional details can be found in the literature).
each task's 's validation set and find Simes to work well for QA
E. BONFERRONI PROCEDURE
The Bonferroni correction is easy to apply and does not require any assumptions the dependencies between the hypothesis tests used (c.g., independent, positively dependent, etc). However, it is generally very conservative. The Bonferroni correction scales e by factor of 1/m, and uses the
19

---

Published as a conference paper at ICLR 2021
1.0
14
1.0
Protictiv EnfoOncy
0.8
0.5
4.0
Prodiction EfIE
predictive EIR
0.2
0.2
040
00
07
06
0.7
1.0
000
0.7
04
6.7
09
0.0
0.0
02
04
06
64
1-1
AccurC0
Threshole span score 10.728) 726)
Threstold CLS 882)
Thecs rold SIMaNN 513)
los seon score (0.0010.77) 773)
To CLS (9:569)
To K MPPNN (0.994) (0.214) Win 400)
7301
10 59.5981
00.422)
Vin 00.490
00
0.
0. Ub 00
U.F.
08 19
0.
2.
0.2
U.5
94
05
U. 0.7
10
0. 0.1 02
94
0.4
U.
08 09
(a) QA
(b) IR
(c) DR
Figure D.I: How does our conformal method compare to non-conformal baselines? We show predictive efficiency and accuracy across various target accuracies (values of c). As expected, with large enough calibration set, the performance of the threshold heuristic is similar to CP. The top-k: threshold is harder to tune, resulting in lower than the desired accuracy for some values IR, and sometimes in unnecessary large prediction sets. Specific values of compared in Table D.2.
Threshold
Top-
Baseline CP
min-CP
Task
Target Ace.
Acc.
[
Acc.
[3
Acc.
|Cn]
Acc.
Ca
0.90
0.98
1243.8
0.98
1041.7
0.98
1245.7
0.90
198.0
0.80
0.94
452.8
0.95
390.5
0.94
453.5
0.80
58.7
QA
0.70
0.91
228.8
0.92
203.3
0.91
227.8
0.70
22.1
0.60
0.87
128.4
0.89
120.5
0.87
127.8
0.60
10.6
0.99
1.00
33.6
1.00
41.0
1.00
33.6
0.99
17.8
0.95
1.00
20.9
0.95
29.8
1.00
20.9
0.95
7.4
IR
0.90
0.98
13.8
0.89
18.7
0.98
13.8
0.90
0.95
6.7
0.78
6.7
0.95
0.80
1.7
0.90
0.99
429.5
1.00
652.9
0.99
429.8
0.90
84.1
0.80
0.97
305.8
1.00
525.1
0.97
305.8
0.80
12.7
DR
0.70
0.96
216.8
0.99
398.3
0.96
216.6
0.70
28.1
0.60
0.94
145.7
0.98
266.5
0.94
145.6
0.60
19.3
Table D.2: Non-CI baseline results on the test set for different target accuracy values. We compare the predictive efficiencies of the CP methods (IC,,) and (Cmiil) to those of the baseline methods ((3)).
union bound on the p-values (PI,..., Pm) to get:
PP PV & CT (X = UURS
P:
6 m
1=1
We achieve the same result by scaling each p-value by m, and take the final combined p-value to be the minimum of all the scaled p-values. It is easy show that this correction is monotonic.
E.2 SIMES PROCEDURE
The Simes procedure (Simes, 1986) allows a stricter bound on the FWER when the measures are multivariate totally positive (Sarkar and Chang, 1997). which usually holds in practice (Rødland, 2006). To apply the correction, we first sort the p-values in ascending order, and then perform an order-dependent correction where the correction factor decreases as the index of the p-value increases.
20

---

Published as a conference paper at ICLR 2021
14
1.5
10
0.5
0.-
0.0
0.6
0.4
044
94
depornl
deporsl
0.2
bontemont
(0.205)
0.2
borrersont (3.400)
02
benferan (0.500)
(9.290)
(9:100)
04
14 04
0.7 0.4
04
0.
1.0
1-6
1-c
QA
(c) DR
Figure E.1: Success rate against tolerance thresholds with different methods for MHT correction
(validation set). Not applying any correction leads a in-valid classifier (the success rate below diagonal). The Bonferroni method is conservative, leading to a valid classifier, but sometimes with higher accuracy rate than necessary (a result of having excessively large C,).. The Simes correction works for the QA and IR tasks and provides tighter bound for them. The Simes correction does not work for the DR task, likely due to a violation of its MTP2 assumption, but the Bonferroni method provides relatively tight correction there especially for small
Specifically, if (P()).... P(m)) are the sorted p-values (P1.... Pm)) in an m-level cascade, we modify the p-values be pSim PGe We take the final combined p value to be the minimum of the corrected p-values. is easy show that this correction is monotonic.
21


Reviews:
[{"review_id": "i3cS6nJPPZV", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper presents two advances in conformal prediction, a field with information retrieval applications in which a set of candidate responses to a query is presented and the objective is to return a small set of responses with at least one of the responses being the correct response.  The first contribution is a method in which the possibility of several admissible responses is modeled (rather than there being just one response) with the system being calibrated against the odds that a particular response is the \"most admissible\", i.e. most conforming to the joint query/response distribution being learned from data. The second contribution is a cascaded prediction system in which simpler and less computationally expensive models are used for initial filtering and then more sophisticated and more expensive models are used downstream to further refine the response set. Rigorous statistical adjustments are used to account for multiple-hypothesis-test issues arising from using the cascading system.\n\nPros:\n\nReasonably thorough experimental results demonstrating performance gains in terms of sensitivity/specificity as well as in terms of computational cost are presented.\n\nThe paper is mostly well written and the theory is presented with a good amount of rigor. \n\nCons:\n\nI feel that the cascading technique is only of moderate significance. It's a good idea and there's some value in promoting it, but it also feels like a solution that might get arrived at by a savvy, practical-minded machine learning engineer in industry rather than a particularly profound ML research concept. The rigorous multiple hypothesis corrections (Bonferroni , etc) are certainly appreciated and are something which a less sophisticated practitioner might not know to apply, so that aspect of it feels more like an academic-paper-level contribution, but the basic idea of cascading feels like an applied, industry systems solution that someone with common sense might arrive at on her/his own.\n\nFurther suggestions:\n\nI strongly suggest changing the definition of \"predictive efficiency\" on page 6.  Defining it such that lower \"efficiency\" is better will confuse many readers. Efficiency has a well-established common-language meaning as something which is desirable. Why not define the efficiency as (for instance) the percentage of the entire candidate Y set which is eliminated, so that higher efficiency is better?\n\nI also think that it would broaden the appeal and accessibility of the paper to spend more time relating conformal prediction to more widely known information retrieval concepts like precision and recall and maybe also learning-to-rank. I suspect far more readers will be familiar with basic information retrieval, precision, recall, etc than with conformal prediction. I acknowledge that one of the appendices connects conformal prediction back to some of these concepts. I think maybe some of that appendix content belongs in the main paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "T3yBURy7e5t", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper propose a conformal prediction (CP) approach in which the prediction output is not necessarily unique; and will be assumed to belong to a finite set. Then, the authors analyze how the classical CP set can be modified wrt to a relaxed requirement that it is sufficient to contains an admissible answer. This lead to a smaller set in expectation and a coverage guarantee is established, proving the validity of the method. Authors also provide a computational methodology to screen out non promising candidate. The paper is well written and provide practical numerical experiments that demonstrate usefulness of the introduced CP in \"real\" world.\n\n- Assumption 4.1 should be probabilistic since $A_g(X, Y)$ is a random set. Is the inclusion required *almost surely*? Note also that ${\\bar Y^j}$ is not defined here. It is also unclear how the sequence of admissible answers $(\\bar Y_{i}^{j})_{j \\in [k], i \\in [n]}$ is included in the datasets (both training and testing). This leads to the following confusion\n\n- In Eq. 1, P is the distribution of $(X, Y)$. However in Eq. (5), it seems that P is the distribution of $(X, {\\bar Y^j}_{j \\in [k]})$ (whose sample is assumed exchangeable).\n\n- Computational complexity of CP:\nThe comment in the beginning of section 5 seems inexact: the cost of computing CP is not linear in $|\\mathcal{Y}|$ otherwise it would be impossible to compute in regression case where $\\mathcal{Y}$ is the real line $\\mathbb{R}$.\n\n- How this cascade strategy could be used in regression setting? For instance, despite the limitation of statistical estimator that can be used, full conformal prediction set can be computed by using parametric programming (without loss in the coverage guarantee): \n(J. Lei 2019): Fast exact conformalization of Lasso using piecewise linear homotopy.\n(Ndiaye and Takeuchi, 2019): Computing Full Conformal Prediction Set with Approximate Homotopy. For instance in the latter, one could consider cascade parameterized by the optimization error. How this cascade approach can improve the computational efficiency of full CP in regression?\n\n- In section 2, CP paragraph, these two papers might be relevant:\n(Chernozhukov etal 2019): Distributional conformal prediction. And (Kivaranovic etal 2019): Adaptive, distribution-free prediction intervals for deep neural networks\n\n- In section 3, the notion of conformity measure is not well defined (S must be symmetric wrt permutation of the data).\n\n- epsilon in (0, 1) in the introduction.\n\n- Given g, *x and y*, any prediction that is a member ...\n\n- Is Eq. 5 equivalent to $P(\\exists j \\in [k]: \\bar Y_{n+1}^{j} \\in C(X_{n+1})) \\geq 1 - \\epsilon$? (which seems more explicit)", "extra_scores": {}, "extra_text": {}}, {"review_id": "NyF2vfnPZGn", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Conformal prediction (CP) allows for the selection of a set of candidate answers guaranteed to contain the correct answer with some probability. The authors propose two extensions to CP, 1. To extend validity for all admissible answers, 2. Using prediction cascades to improve computational efficiency. The authors show that their approaches provide similar guarantees on accuracy like CP but with lowered predictive efficiency and computational cost.\n\n\nReasons to accept: \n1.  The approaches are simple, novel, and interesting and they come with theoretical guarantees \n2. The proposed methods allow for CP to be extended to some realistic tasks\n3. Impressive results showing lowered predictive efficiency and computational cost\n4. The paper was well written and the approaches and experiments seem technically sound\n\nOverall, I believe that this would be a useful paper for the community, and based on the reasons given above I would recommend acceptance. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an approach for conformal prediction where, in its standard paradigm, a set of prediction candidates is identified as opposed to a single one.  The authors advance the CP framework by presenting a rigorous methods that allows for a smaller set of admissable predictions with a covergae quarantee. Their further contribution is a methodolgy based on cascading that filters out non promising candidates.

After the discussion period, _all_ the reviewers are in favour of accepting the manuscript with the average being marginally above acceptance.  My recommendation is therefore to accept the paper. 

Strong points:
The advance of a smaller set of admissible predictions in the CP framewrok is quite useful especially in scenaria where the set can grow (expensively) large. 
Thorough experimental analysis with good presentation of performance gain and usefulness in real world data. 

Weak points:
Lack of novelty in the techniques make the work a weaker candidate compared to the rest of submissions. 
Decision: Accept (Poster)