Multi-Dimensional Conformal Prediction
Authors: Yam Tawachi
Bracha Laufer-Goldshtein
Venue: ICLR 2025 Poster (2025)
Keywords: classification
conformal prediction
uncertainty quantification
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: A new approach for conformal prediction in multiple dimensions based on several nonconformity scores.

Abstract: Conformal prediction has attracted significant attention as a distribution-free method for uncertainty quantification in black-box models, providing prediction sets with guaranteed coverage. However, its practical utility is often limited when these prediction sets become excessively large, reducing its overall effectiveness. In this paper, we introduce a novel approach to conformal prediction for classification problems, which leverages a multi-dimensional nonconformity score. By extending standard conformal prediction to higher dimensions, we achieve better separation between correct and incorrect labels. Utilizing this we can focus on regions with low concentrations of incorrect labels, leading to smaller, more informative prediction sets. To efficiently generate the multi-dimensional score, we employ a self-ensembling technique that trains multiple diverse classification heads on top of a backbone model. We demonstrate the advantage of our approach compared to baselines across different benchmarks.

Published as a conference paper at ICLR 2025
MULTI-DIMENSIONAL CONFORMAL PREDICTION
Yam Tawachi & Bracha Laufer-Goldshtein
School of Electrical and Computer Engineering Tel-Aviv University
Tel-Aviv, Israel
{y Tyamtawachi@ma @mail, blaufer (tauueeertauxx] taw.aa.................
ABSTRACT
Conformal prediction has attracted significant attention as distribution-free method for uncertainty quantification in black-box models, providing prediction sets with guaranteed coverage. However, its practical utility is often limited when these prediction sets become excessively large, reducing its overall effectiveness. In this paper, introduce novel approach to conformal prediction for classifi- cation problems, which leverages a dialii-dimenionall nonconformity score. By extending standard conformal prediction higher dimensions, we achieve bet- ter separation between correct and incorrect labels. Utilizing this we can focus on regions with low concentrations of incorrect labels, leading smaller, more informative prediction sets. To efficiently generate the multi-dimensional score. we employ a self-ensembling technique that trains multiple diverse classification heads on top of a backbone model. We demonstrate the advantage of our approach compared to baselines across different benchmarks.
INTRODUCTION
Deep learning models become increasingly dominant in almost every domain, ranging from computer vision and natural language processing to speech recognition. However, as deep learning models deployed in safety-critical applications. such healthcare (Lambert et al. 2024) and autonomous driving (Muhammad et al. 2020). is important to certify their reliability and safety. This highlights the need for robust uncertainty quantification methods that can determine when models are uncertain about their predictions and suggest alternative estimates. Conformal prediction offers a powerful, distribution-free, and model-agnostic framework for uncertainty quantification, providing finite-sample guarantees (Vovk et al. 2015) Lei et al. 2013 Barber et al.) 2021 Angelopoulos et al. 2020). Its core principle is transform pointwise predictions from any model into prediction sets or intervals that contain the true value with high probability.
Conformal prediction relies on nonconformity score that quantifies how unusual or atypical new input-label pair is relative to the given data. While conformal prediction guarantees valid coverage for any model and data distribution, of the model and the choice of the nonconformity score (Romano et al. 20200; Angelopoulos et al.) 2020). The efficiency of the resulting prediction sets is typically measured by their size, with smaller sets leading more informative and precise predictions. Consequently, there is active research aimed at developing methods that produce the most efficient and concise prediction sets. This includes proposing new nonconformity scores (Sadinle al., 2019 Romano al. 2020 Angelopoulos et al.) 2020 Huang et al. 2024 [ Luo & Zhou 2024a). training models using loss functions that promote efficiency (Stutz et al. |0.2|2221 Einbinder et al. (222). and combining different
practical effectiveness is influenced by both the performance
models, scores, or data augmentations (Bai et al. 2021 Luo & Zhou 2024b Lu 2023).
The common approach across existing methods is optimize single nonconformity score, while the calibration groeels-generally involving the computation of a threshold based on a quantile of the calibration scores scores-remaite remains unchanged. In this paper, we present a novel perspective that extends the standard conformal prediction framework from one-dimensional score to higher-dimensional space defined by multiple nonconformity scores. The intuition behind this
Our code available at: httpps///ggtthbb..cmm///////////

---

Published as a conference paper at ICLR 2025
Saff-Ensembee
+d443
Computanion
Computtioo
Score
Figure I: demonstration of the proposed multi-score conformal prediction for the 2-dimensional case. On the left, illustration of our proposed self-ensemble model with two classífication heads. We compute nonconformity score for each head. On the right, the 2-dimensional score space presented, where red circles correspond to scores of true labels, and light-blue x-marks correspond to scores of false labels. Selected cells are colored in blue and their centers have black edge color. We that cells with low number of false labels are chosen.
that nigher-dimensional spaces can better separate correct from incorrect labels, potentially leading to more efficient prediction sets with fewer false labels. However, selecting region in this highherdimensional space that guarantees exact coverage while optimizing efficiency is non-trivial, as there are infinitely many ways to partition the space. To tackle this challenge, we propose simple yet effective method that splits the multi-dimensional score space into cells, with cell centers defined by the calibration samples, as illustrated in Fig. [ The cells are ranked bottom-up based on the ratio incorrect correct labels that they contain. Then, we select the top-ranked cells that meet the desired coverage. At test time, the prediction set consists of all labels with scores falling within the selected region. Additionally, we introduce a flexible self-ensembling technique that constructs multi- ditenssiiaan score by combining predictions from multiple diverse classification heads built on top of a single backbone model. We provide theoretical guarantees that this high-dimensional region selection maintains valid coverage and show that it is equivalent optimizing the size of the prediction set, under coverage constraint. Extensive experimental results, demonstrate that our nulti-dimensional framework offers superior efficiency compared baseline methods across various settings.
Our main contributions can be summarized as follows:
1. Propose
multi-dimensional conformal prediction framework that better identify regions with a large amount of true labels and a small amount of false labels. Our approach is parameter- free, requires no optimization procedures. and restricted specific coverage level.
2. Theoretically show that this high-dimensional selection procedure maintains the desired coverage with finite-sample guarantees.
3. Present flexible and cheap self-ensemble approach to obtain multi-diieensooall nonconformity scores by training multiple classification heads, while encouraging diversity.
4. Our experimental results demonstrate the superiority of the proposed method over competing baselines, consistently producing smaller and more efficient prediction sets.
2 RELATED WORK
Enhanced nonconformity scores. Improving the efficiency of conformal prediction has been central focus of recent research. Several studies have derived enhanced nonconformity scores aimed reducing the size of the prediction sets improving conditional coverage (Sadinle et al. 2019;
Romano et al. 2020: Angelopoulos et al., 2020 Huang et al. 2024 Luo & Zhou] 2024a). Another approach involves performing conformal prediction in the feature space, then mapping the intervals from the embedding space back the output space (Teng et al. 2022). Our approach addresses the of multiple nonconformity scores, previous research has demonstrated that combining multi-
2

---

Published as a conference paper at ICLR 2025
ple scores be more efficient than relying single score Yang et al. 2023b). We introduce practical method for generating multiple scores without the need for training multiple models or per- forming additional inference steps. This approach can be applied to any base score and is orthogonal to the advancements in developing improved nonconformity scores.
Improving conformal prediction via training. Although conformal prediction is usually considered as a wrapper around black-box models, recent approaches suggested to directly train models to improve conformal prediction efficiency. [Stutz et al. (202T) introduced differentiable conformal prediction pipeline that optimizes the size of the prediction sets. In (Einbinder et al. 2022]. a regularization term was added to the training loss, encouraging the distribution of the nonconformity scores to match a uniform distribution. Additionally, Bai et al. (2021) explored opti- mizing conformal prediction within broader function classes. These methods rely on differentiable approximations that may not fully align with the actual target objective, and are often designed for a specific coverage level, requiring retraining for each new level. In contrast, our approach avoids optimization altogether and offers greater flexibility by being independent of the coverage level and the base nonconformity score.
Combining nonconformity scores. Several works explore conformal prediction in the context of model fusion and combining nonconformity scores. Ensemble learning methods, which train multiple models on different subsets of the data, have been widely applied to conformal prediction (Linusson et al. 2020). Notable approaches include cross-conformal predictors (Vovk) 2015), bootstrap conformal predictors (Vovk 2015), and out-of-bag calibrated conformal predic- tors Devetyarov & Nouretdinov 2010). Other methods for combining nonconformity scores have also been investigated. For example. Luo & Zhou (2024b) proposed using a weighted average of multiple scores derived from the same output, with weights learned through optimization. Similarly, (023) suggested combining nonconformity scores obtained via test-time augmentations of the same image. A more recent work explored the aggregation of multiple prediction sets, assuming no direct access to the underlying scores (Gasparin Ramdas) 2024). In contrast to existing approaches that focus on combining nonconformity scores via weighted aggregation or majority voting, we propose a general framework that identifies promising regions with low concentrations of false labels in the multi-dimensional score space.
Ensemble methods. Model ensembles have been shown to enhance various metrics for uncertainty quantification beyond conformal prediction efficiency, such calibration error (Hansen & Salamon, 1990 Lakshminarayanan et al. 2017). However, ensembles are often considered computationally expensive, they require training and deploying multiple independent models. To mitigate this, Qendro et al. (2021) proposed an early-exit ensemble, which leverages multiple prediction heads from intermediate layers to improve uncertainty quantification while maintaining a single model.
This approach has been shown to enhance computational efficiency (Cai et al. (0200) and improve adversarial robustness (Qendro & Mascolo, 2022). Building on these insights, we propose a self- ensemble model with multiple classification heads to generate a multi ciltii-dimesionnll nonconformity score without significant additional costs.
3 BACKGROUND - CONFORMAL PREDICTION
E X' represent an input, associated with a label Y E V, where y= {l..... .i.....Qh, Q}. Consider classifier (xx) E [0, 1 that outputs probability distribution over Q classes (e.g., neural network with a softmax layer, producing probabilities for each class). Conformal prediction starts by computing a nonconformity score s : X x S C R. which quantifies the uncertainty of the classifier's s prediction for the pair (X,Y) with respect to existing data. Given set of calibration points {(,,, m we can form a prediction set for a new test point Xm+11 Provided that the points {(X,, } m+ are exchangable, this set is constructed have least 1 1-6 a coverage of the true label, where a E (0, 1) is set by the user. The prediction set is defined as:
Let X
Tx(Xm+1) {y E y: : s(X .) S A},
(1)
where the threshold is set to the quantile of the calibration nonconformity scores:
[[m + 1)(1 - a)].
A = Quantile
(s(X,, m=
(2)
m
3

---

Published as a conference paper at ICLR 2025
144
30
02 26
03 10
(a)
(b)
Figure 2: Binary classification example. (a) P(lyy for y (-1,1) (b) The 2-dimensional score space defined by 81 (3r, y) and $2 y). (c) The set-sizes obtained for different domains based on s0 y). 81 (z, y), 52(2, y) and our multi-score method using both $1 (z, y) and $2 y).
This procedure ensures that the true label Y is included in the prediction set with at least - or probability, as stated in the following theorem.
Theorem 1. (Conformal calibration coverage guarantee) Let {(X,, YJ) be exchangeable data points. For any score function 8 X x y - S and any significance level a E (0, 1), define the quantile X by Eq. and the prediction set T (x (xm+1) by Eq. 47. We have:
P P(Ym+1 E (X(+t))) 2
(3)
Commonly used nonconformity scores are described in Appendix A.I
4 PROPOSED METHOD
4.1 MULTI-SCORE CALIBRATION
We now consider a multi-dimensional nonconformity score s X x - S, constructed by concatenating individual nonconformity scores s(r, y) (Ir, ,,,,,, (z., y)] where S = x ..... x S, C RR.. Before discussing different approaches to handling nonconformity scores and presenting our proposed method, we first introduce toy example to highlight the advantages of using multi-diienssioal score over singledimeensooaa one.
Example 4.1 (Toy setting). Assume a binary classification problem with y {-1,1} and prior probabilities P(Y = 1) and P(Y = -1). The input X is generated from mixture of two Gaussians, with (Y) = (Y, ). In this example, we can compute the posterior P(Y (X) using Bayes rule. Let [P(y/=) = PPY = X x), we consider the following three classifiers:
PP(y(z)) <u(x)= = P(yl=), (x) = 1c.1-c)
if < 0, if 0
=2(2)) : (=,1-)), if < 0.
(4)
Plylz), if 0
where e ~ NO, 1). Here, To(x) is the ideal classifier, while Ti (2) and (2(x) are identical to the ideal classifier over half the range of X, but uninformative over the remaining half. Let (1 y) denote the nonconformity score computed over the i-th classifier, it is clear that performing confor- mal prediction over so(x, y) would be the most efficient, however, using either s (æt, y) or s2(2, y) will lead to suboptimal results in the uninformative regions. Performing conformal prediction in the 2-dimensional space, defined by s(x, v) = [sq (I, $2 v)! , is advantageous as the individual scores provide complementary information for different ranges of the input X. This can be seen from Fig. [ (b), where taking both axes into account can help to identify regions with high density of true points versus false points. Setting = 0.1, we obtain the following average set sizes: 1.05 for so( y), 1.48 for 81 (Ix v), 1.47 for 82 y) and 1.24 for our proposed method. Figure 2 (c) compares the set sizes per z-domiin. As expected, so so y) produces two-element sets, only in the middle region, where the Gaussians overlap. In contrast, $1 (xx y) and $2 (x, y) produce a higher pro- portion of two-element sets in the corresponding noisy regions. Our method, which relies on both scores, closely matches the behavior of the ideal score. Further details are provided in Appendix
We now turn to the analysis of the multi- colli-ddmensionall score space. The construction of such scores discussed in 4.44 In standard conformal prediction, where n 1, the threshold in Eq. (2) divides the real line into regions: scores less than equal to À are included in the prediction
4

---

Published as a conference paper at ICLR 2025
set, while scores greater than À are excluded. This simple thresholding approach is effective because nonconformity scores are expected to be low for true labels, which conform to the patterns in the data, and high for false labels, which deviate from the expected behavior, as explained in $ $E When n > 1, we have a multi-dimensional score. Intuitively, scores that are close to the minimum value in all dimensions correspond the most conforming labels, while increasing any component of s(x, y) leads to less conforming scores. However, unlike the one-dimensional case, it is not immediately clear how to optimally partition the score space S into regions that should be included or excluded from the prediction set.
common approach for handling multiple nonconformity scores is use their weighted sum:
Sw ( y) w48; (v,
where the weights w, are optimized to minimize the size of the prediction set while maintaining the desired coverage level (Bai et al. 2021 Luo & Zhou, 2024b). Geometrically, this is equivalent to splitting the score space S with hyperplane of the form w1 (2,, y) +.... W,,, v) = X, and including only those scores that lie below this hyperplane, i.e. scores satisfying wi (ar, y) +... w,sn(I, y) < X. However, this method imposes rigid structure on the partitioning, which may not align with the optimal regions that yield the smallest possible pre- diction sets. Moreover, it requires tuning the weights for a specific coverage level, making it less flexible and potentially unsuitable for different values of a.
We propose a more flexible approach for managing the multi-dimensional score space that eliminates the need for weight optimization. Our method begins by partitioning the calibra- tion data into two disjoint subsets: Deal Deells U Dre-cat, where Doetls = f(x,, k and k
Dre-cal- = {(X,, space S into distinct regions (cells) and evaluating the quality of each region. Next, the subset Dro-cal is utilized for calibrating the total selection region, ensuring that the resulting prediction sets achieve the desired coverage level. Thus, our method consists of three main stages: (i) partitioning, (ii) scoring and ranking, and (iii) calibration, as detailed below.
with
The subset Deells is used for partitioning the score
(i) Partitioning. We aim to partition the score space S into cells and later decide which cells to include in the prediction sets. Using uniform grid is computationally expensive and not scalable with increasing number of dimensions n. Additionally, the score distribution is typically uneven, with some regions being densely populated and others sparse, making uniform partitioning ineffi cient. Instead, we partition S into l cells, centered at s(X1, Yi),..,,s(( s(X,, Yk) for all samples in Deells. Specificallyy, each point in S is assigned to the closest center:
arg min |s s(X,, K.11 ie ie (1.....,, k}. 13isk
C = E S
(6)
This way, the cell resolution adapts to the score density, with smaller cells in high-density regions and larger cells in low-density areas. Note also that this approach is analogous to standard conformal prediction, where the calibration scores define segments of varying lengths, and the final selected in- terval is the union of all segments to the left of the computed quantile (2). Thus, our cell partitioning method can be seen as a generalization of the standard partitioning process to higher dimensions.
(ii) Scoring and ranking, In the next stage, we determine which cells to include in the prediction sets by computing a ratio that quantifies the balance between false and true labels within each cell.
Let F. = ビ De 1(s(X,,9) E C.}- 1(Y, * 4} and T, = Σ [ss(X,, My) E C,} denote the number of scores with false labels and true labels, respectively. We define the cell scores D; as follows:
D. D. +. F. +1, iE (l.....,,) T,
(7)
T.
This ratio reflects the relative amount of false to true labels within each cell C.. We normalize by the number of true scores in each cell, accounting for the possibility of multiple identical true scores (overlapping cells), though this occurrence becomes increasingly rare as n increases. Note that a definition of D fir results in the same score ordering. However, we keep the definition of Eq. (7) as it is essential for showing the equivalence between our scoring and ranking procedure and solving the set-size optimization problem, described in $ 4.2
5

---

Published as a conference paper at ICLR 2025
In order improve conformal prediction efficiency and obtain smaller set sizes at test time, prioritize regions with a low false-to- true label ratio while avoiding regions with high false-to-true ratio. Let k' denote the number of unique cells, where multiple identical scores are treated single cell. We then rank the sequence of unique cells (2)............. C2))....,CC.. C(r) according to D, from lowest to highest, i.e., D()) P(2) S ....' Daw)
(ii) Calibration. The final step is selecting the regions that will ensure exact coverage. In this stage, utilize the re-calibration set Dre-cal. We start from the cell with lowest D, score, and progressively add cells until the desired coverage is achieved over Dre-cat Formally, we define the selected region C as the union of the top-ranked cells up to index 1y:
C₁
CC.) i=1
The required ry is determined by: 1j" min {1 {I....,k') k'3 Y& C. for least [(1 (r 1)] samples (Xi, Yi) Dre-cal):
(8)
and Cp is the final selected region. is essential to use a separate calibration set rather than reusing Deells This because the cell scores are derived from Deells. and selecting cells based on the same data would introduce bias, ultimately leading undercoverage (see Appendix A for further justification).
At test time, given new test point Xm+1 with an unknown label Ym+1, compute the multi- dimensional score s s(Xm+1.3) v) for each possible E y. We then include only the labels that fall within the selected region Ch yielding the following prediction set:
I Tp (Xm+1) = {y (l..... Q) [[|ss((mm,s)) E Ch'
Our method, Multi-Score Conformal Prediction, is summarized in Algorithm I Unlike the single- score thresholding approach (1) the hyperplane splitting for weighted scores (5), our approach defines an unstructured selection region in the multi-dimensional score space. This flcxibility enables to prioritize regions with fewer false labels, leading to smaller prediction sets. Notably, our method differs from vector quantile regression (VQR), which extends quantile regression to multivariate settings (Carlier et al., 20166; Feldman et al. [2023] Rosenberg et al.) (022). While VQR captures the central 1- a portion of the output distribution, our approach focuses on optimizing the selection region minimize set size while ensuring valid coverage.
4.2 THEORETICAL ANALYSIS
Although our construction seems different from standard conformal prediction, it still provides coverage guarantees, as stated in the following proposition.
Proposition 2. (Multi-score conformal calibration coverage guarantee). Let Deells Ki) and Dre-cal {Xi, =+ be two disjoint datasets, and the sumples {(X,, y=) are ex- changeable. For any multt--iimesional score functionn s X x y + C R" and any significance
level (0, 1). the prediction set I (Xm+1) defined by Eq. 19 satisfies:
IP PPYm+t E (X, 2
(10)
The proof, detailed in Appendix A.3 is based on defining a mapping function from the multi- dimensional score to the corresponding cell ratio score, defined in Eq. 7 By formulating the predicted set in Eq. ( using a thresholding operation over this score, our method is aligned with standard one-dimensione conformal prediction, ensuring valid coverage.
We show now that our approach is similar to previous works, optimizing the set size, subject to a coverage constraint (Stutz et al.] 2021 Bai al. 2021 Kiyani et al. 2024). Since the space of all possible prediction sets is overly complex, the problem must be relaxed. Bai et al. (2021) pro- posed to optimize arbitrary class of prediction sets Te parametrized by A, while Stutz et al. (2021) optimize a parametrized score s0 y). Kiyani et al. (2024) considered structured prediction sets (²)x) = {y E Y|s(x, v) & h(x)) with learned adaptive threshold h. X - R. In contrast,

---

Published as a conference paper at ICLR 2025
Algorithm Multi-Score Conformal Prediction
Definitions: (2z y) is a multi-dimensional score function. Deal is the calibration data of size m. Xm+1 is new test sample, a is the miscoverage level, & is the number of samples for cell- partitioning and scoring, and r
1 the number of samples for re-calibration.
1: function MULTI-SCORE-CA (CteeeCC(((2)))))))) y). Deal, ())
2:
Randomly split Deat to Deells = (X,, Y:) and Dre-cal {(x;, (T))
3:
Compute the scores s(X,, Y), i (1,....,))
4:
Segment S into cells [C centered at (s(X,,
5:
Compute D 2 I,..., according to Eq. 7
6:
Remove duplicate cells C1,C,.....
7:
Rank the cells C()): C(2).... ....).... C(K) according D(1) S D(2) S... S Dao
8: "" minfn {1,.... k} Yú C. for least [(1 a)(r 1)] samples in Drecal)
9: C
C()
return CP
11:
function MUL.II SOUTT-SSOORR--VVAUUUTTONNCC y), X X C
Compute the scores s( (m,,, y E (1....,Q ..... Q}
Construct the prediction I (Xm+1) = y E [I....,Q) Q} ((Xm+1 y) E Ch
14:
return y (Xm-1)
work in the multi-score domain and consider sets defined as a union of cells in Deells i.e. ('(x) {u E (/(((,))) y) E UserC;} with I C 2 We obtain the following relaxed optimization problem:
arg min Lsize = [size(T' (X))] r_2"
S.C.
Leoverage := P (Y r'))) 2 a.
(11)
where size ( (X) = 1/7 E (X))- In the following lemma, we relate this optimization
problem to our defined - scores (see the proof in Appendix [A.4].
Lemma 3. The optimization problem in Eq. 11 admits the following finite sample representation:
[
arg min IC2
Σ Ds SET
S.1. Preoeragg
a.
(12)
It immediately follows that solving Eq. 12) does not require enumerating all possible sets /. Instead, we can rank cells according to D; and select a proportion of -a cells with highest ranks. However, this does not guarantee exact coverage, thus, we perform re-calibration by choosing the top-ranked cells covering [(1 - a)( + 1)] samples of Dre-cal- This is summarized in the following proposition.
Proposition Algorithm 7 is equivalent to solving a finite sample upproximation of Eq. 77 as
defined by Eq. 12 ffollowed by re-calibration stage, ensuring valid coverage (Eq. 10
4.3 ADDITIONAL VARIANTS OF MULTI-SCORE CONFORMAL PREDICTION
In the following, we present two additional variants of our proposed method.
Jackknife+ Multi-Score Conformal Prediction. A limitation of our approach is that uses only part of the data perform the calibration, which may impact efficiency. This especially critical if the sample size m is small. An alternative solution is to adopt a jackknife+ approach (Romano al. 2020 Barber et al. 2021), which computationally more intensive but often provides tighter prediction sets. This approach is summarized in Algorithm[BB B. The key idea is to leverage the entire calibration dataset while sy systematically excluding the äth point from both the set of centers and the score computation in Eq. (7). For each possible label y ) assign it to the nearest center after removing the ith center, and similarly, we compute the assignment for the score s s(X,, Y,). We then compare the ranks of the selected cells and include y in the final prediction if its rank is smaller than [m1-a)(m (m++1) 1)] hold-out calibration ranks. This ensures a theoretical coverage of 1 2a. However, in practice, the achieved coverage is close 1 a, without the adjustment a' a/2.

---

Published as a conference paper at ICLR 2025
Soft Multi-Score Conformal Prediction. We introduce generalized variant of approach, replacing hard assignment to the nearest center with a soft assignment to the b nearest neighbors. This variant, outlined in Algorithm B.2 selects the b closest neighbors and includes point in the prediction set if at least half them belong to the chosen region.
4.4 MULTI-SCORE CONSTRUCTION
Multi-dimensional nonconformity scores can be constructed in several ways. Multiple scores be obtained from a model ensemble, which can be resource- inttereveieesivee. Alternatively, pest-time augmen- tations can be used to generate multiple scores for different input augmentations (Lul 2023). Simi- larly to ensembling, test-time augmentation requires multiple forward passes, and is generally more appropriate for image data. A more efficient approach
derive multiple types of scores from sin- gle model output (Luo & Zhou 2024b). While this requires only single forward pass, all scores are generated from the same output, which may limit their ability to fully capture predictive uncertainty.
Our multi-dimensional approach is applicable to any of the previously mentioned multi-scores. However, we introduce novel method for generating diverse nonconformity scores that capture var- ied perspectives without increasing computational complexity. To achieve this, we attach multiple classification heads, {a, (.))) to the penultimate layer (second-to -oooodtt--lsttttt layer) of the model. Train- ing these heads solely with cross-entropy (CE) loss often leads highly similar outputs, limiting their usefulness for uncertainty estimation. To mitigate this, we adopt the regularization technique from (Qendro al. (002T), encouraging diversity by minimizing similarity among the heads. This crodictions-speciallee for dis-
aligns with the intuition from Example 4.1 where complementary tinct input regions- -anionn--ann can be combined to enhance uncertainty quantification across the entire range. The classification heads are trained using the following loss function:
B
L -
LC n(n
sim (i),
(13)
where LCB(-.) denotes CE loss, sim(...) denotes cosine similarity, and 3 is regularization weight, set to our experiments. While (Qendro et al.) 2021) proposed generating classification heads from various layers and depths of the network, our empirical findings revealed that, as expected, heads from shallower layers tend to be weaker, and thus have minimal contribution in the multi-score setting. By attaching the classification heads to the penultimate layer and applying diversity regularization as in Eq. 113 we achieve robust and diverse classification heads.
5 EXPERIMENTS
5.1 DATASETS AND MODELS
We test method over three image classification datasets, with varying number of classes and difficulty levels: CIFAR100 100 (Krizhevsky et al.) (009). Tiny ImageNet (Le & Yangl 2015). and PathMNIST (Yang et al. (023a).. For all datasets we use ResNet50 backbone model pretrained on ImageNet. We first attach single classification head and fine-tune the full model with CE loss. Next, we add additional classification heads (n heads total), freeze the backbone model, and train the heads using the loss defined in Eq. (33). Based on the heads' output probabilities, we compute the nonconformity scores, where we use either regularized adaptive prediction sets (RAPS) (14) sorted adaptive prediction sets (SAPS) (15) as base scores. We refer to Appendix C for further details on datasets, model architectures, and the training procedure.
5.2 EVALUATION
We compare the proposed multi-scon method to the following baselines:
Best single head (Best head) Conformal prediction is applied independently to each classi- fication head using the entire Deal dataset, opposed to our method that performs calibration only over cat We report the results for the head that achieves the smallest set size among the evaluated heads.
8

---

Published as a conference paper at ICLR 2025
Mutt heoe
30
Coverage
0.91
Optimitzed
25
Mean Sec
20
0.50
0.58
Number Heads
Number Heads
(a) CIFARI00 (a = 0.1)
(b) CIFARIOO (a= 0.1)
0.910
Mothod
Deat hsee!
Uniterm
0:092
Mour Sut So0
0.300
Meen
0.58
0.90
(c) PathMNIST (a = 0.01)
(d) PathMNIST (a- 0.01)
Method
3.815
14
Deed heee
3.010
Newn Diveeage
Norm
2.003
Noae:
3.065
20
2300
3.05
10
2
Number of leads
Number of Heads
(e) Tiny ImageNet (a = 0.1)
(I) Tiny ImageNet (ee 0.1)
Figure 3: Results for RAPS. Empirical coverage (left), and mean set size (right) as a function of the number of classification heads.
Uniform average (Uniform) We average the scores obtained for each head and perform standard conformal prediction on the entire Deal dataset.
Optimized weights (Optimized)- We use the weighted score sw defined in Eq. 5). We perform constrained optimization, minimizing the mean set size with constraint that the empirical mis- coverage does not exceed a. The weights are optimized using Optuna (Akiba et al.) 2019) over Deells with 100 optimization steps. Then, we perform standard conformal prediction over Dre-cal- Norm-based score (Norm)- Conformal prediction is performed over Deal with norm-based score, defined as s2(2, y) ||s(x, 2)ll2
VE (x,
We evaluate the different methods in terms of the empirical coverage Paonl E(XYrEE 1(Y E ](X)} and the mean set size p... E l(X)), computed over the test data Dess- We report the average results and the standard deviation over 10 random splits to calibration and test.
5.3 RESULTS
Varying number of heads. Results as a function of the number of heads are shown in Figs. and D.2 with RAPS and SAPS as base scores, respectively. Results for additional levels are provided in Figs. D.I and D.3 As expected, all methods obtain the required coverage. We observe that the proposed method leads to smaller prediction sets, with decreased sizes the number of
9

---

Published as a conference paper at ICLR 2025
Opeimzes Uniiom text points
Oycimbed
38-
Opcinbed
Uritom
Uriisrm
Thue
points
Rest
best
Nerm
regiors
300
regione
regions
regions
32
10
20
(a) a = 0.2
(b) a 0.1
(c) a 0.05
Figure 4: Selection regions for a 2-dimensional score (n = 2) using RAPS on Tiny ImageNet at different levels. Our method's selected region is shaded in blue, while the unselected region is in orange. Baseline decision boundaries are shown as dashed lines, with selected regions lying to the left of the 'Best head' boundary and below the boundaries for all other baselines. True test points are shown as green circles, while those associated with incorrect labels are marked with purple x-marks. heads increases. Similar trends are observed for both RAPS and SAPS scores. Figure [.7 illustrates how the set size distribution evolves as the number of heads increases, demonstrating the advantage of our method in generating smaller set sizes compared baselines, especially as n grows.
Selection region. Figure demonstrates the results obtained for the 2-dimensional case (n = 2)- We present the region selected by the proposed method (blue area), and the decision boundaries for the baseline methods. In addition, the test scores for true and false labels are presented. We observe that the test scores are concentrated in two distinct square regions: the bottom-left corner, where true labels dominate, and the top-right corner, where false labels are more prevalent. Our method effectively focuses on regions with fewer false labels, whereas the baselines, constrained by their fixed structure, inevitably include areas with a high density of false labels. Figure D.4 illustrates the cell selection order defined by Eq. (7). Here too, we observe that cells near the bottom left corner preferable, as well as cells that have low score in either dimension.
Additional results. We briefly highlight additional results presented in Appendix D Tables D.I and repport the performance in terms of the conditional coverage, with groups defined by either set-size or random projections, respectively. We observe that all methods exhibit similar behav- ior regarding the maximum coverage violation. Figure D.6] presents the set sizes obtained for Thr and APS scores, highlighting the superiority of our method when temperature scaling is applied to spread out the score distribution. Additionally, we conducted several experiments demonstrate the versatility of our approach in other multi-score settings, including: (i) standard ensemble, (ii) test-time augmentation, and (iii) differrnnt score types computed for a single head. Moreover, we conducted experiments on text classification (Tab. D.8). and ImageNet (Tab, D.9) verifying that our method is suitable for other data types and large datasets. We evaluated the two additional variants of our method, presented in $ $4.3 and found that the Jackknife+ version yields smaller sets, while the soft version with b > 1 generally offers no advantage over the basic version with 6 1. We also performed an ablation study over the regularization weight À in Fig. D.11 highlighting the benefit of adding diversity regularization. Furthermore, we show that our method is not highly sensitive with respect the sample size of Deal (Fig. D.12) and Doels (Tab, D.4). and maintains robust performance regardless of the underlying model (Tab. D.7)
7) and the scores hyperparameters (Tabs. D.5 and D.6
6 CONCLUSIONS
We introduce multi-score conformal prediction framework that combines multiple nonconformity scores to select regions in the high-dimensional score space. This approach ensures the desired coverage while minimizing the inclusion of false labels. Unlike existing methods, our technique requires no optimization neither black-bor box nor gradient- level. To achieve this, we construct the score using cost-efficient self-ensemble model with multi- ple classification heads, trained with both CE and diversity losses. Experimental results demonstrate that our multi-score framework outperforms state-of-the-art baselines across multiple benchmarks.
and is applicable to any coverage
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by the Israeli Ministry of Innovation, Science and Technology (Grant No. 1001818518).
REFERENCES
Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. pp. 2623-2663 2631, 2019.
Anastasios Nikolas Angelopoulos, Stephen Bates, Michael Jordan, and Jitendra Malik. Uncertainty sets for image classifiers using conformal prediction. In International Conference on Learning Representations, 2020.
Yu Bai, Song Mei, Huan Wang, Yingbo Zhou, and Caiming Xiong. Efficient and differentiable conformal prediction with general function classes. In International Conference on Learning Representations, 2021.
Rina Foygel Barber, Emmanuel Candes, Aaditya Ramdas, and Ryan J Tibshirani. Predictive inference with the jackknife+. The Annals of Statistics, 49(1):486-507, 2021.
Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han. Once for all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations, 2020.
Guillaume Carlier, Victor Chernozhukov, and Alfred Galichon. Vector quantile regression: An optimal transport approach. The Annals of Statisties, pp. 1165-1192, 2016.
Dmitry Devetyarov and Ilia Nouretdinov. Prediction with confidence based on a random forest classifier. In Artificial Intelligence Applications and Innovations: 6th IFIP WG 12.5 International Conference, AIAI 2010, Larnaca, Cyprus, October 6-7, 2010. Proceedings pp. 37-44. Springer, 2010.
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pp. 4171- 4186, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
Bat-Sheva Einbinder, Yaniv Romano, Matteo Sesia, and Yanfei Zhou. Training uncertainty-ave classifiers with conformalized deep learning. Advances in Neural Information Processing Sys- tems, 2022.
Shai Feldman, Stephen Bates, and Yaniv Romano. Calibrated multiple-output quantile regression with representation learning. Journal of Machine Learning Research, 24(24): 2023.
Matteo Gasparin and Aaditya Ramdas. Merging uncertainty sets via majority vote. arXiv preprint arXiv:2407.0m 09379, 2024.
Lars Kai Hansen and Peter Salamon. Neural network ensembles. IEEE transactions on pattern analysis and machine intelligence, 12(10)9933-001, 1990.
Jianguo Huang, Huajun Xi, Linjun Zhang, Huaxiu Yao, Yue Qiu, and Hongxin Wei. Conformal prediction for deep classifier via label ranking. In International Conference on Machine Learning (ICML), 2024.
Shayan Kiyani, George Pappas, and Hamed Hassani. Length optimization in conformal prediction. In The Annual Conference on Neural Information Processing Systems, 2024.

---

Published as a conference paper at ICLR 2025
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Advances in neural information processing systems, 25, 2012.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles, Advances in neural information processing systems, 30, 2017.
Benjamin Lambert, Florence Forbes, Senan Doyle, Harmonie Dehaene, and Michel Dojat. Trust- worthy clinical ai solutions: unified review of uncertainty quantification in deep learning models for medical image analysis. Artificial Intelligence in Medicine, pp- 102830, 2024.
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015.
Jing Lei and Larry Wasserman. Distribution-fiee prediction bands for non-parametric regression. Journal of the Royal Statistical Society Series B: Statistical Methodology, 76(1):71-96, 2014.
Jing Lei, James Robins, and Larry Wasserman. Distribution-free prediction sets. Journal of the American Statistical Association, 108(501):278-28,, 2013.
Henrik Linusson, Ulf Johansson, and Henrik Boström. Efficient conformal predictor ensembles. Neurocompuliing 397:266-278, 2020.
Helen Lu. Data Augmentation and Conformal Prediction. PhD thesis, Massachusetts Institute of Technology, 2023.
Rui Luo and Zhixin Zhou. Trustworthy classification through rank-based conformal prediction sets. arXiv preprint 240::2400004077 2024a.
Rui Luo and Zhixin Zhou. Weighted aggregation of conformity scores for classification. arXiv preprint arXiv:2407. 10230, 2024b.
Khan Muhammad, Amin Ullah, Jaime Lloret, Javier Del Ser, and Victor Hugo C de Albuquerque. Deep learning for safe autonomous driving: Current challenges and future directions. IEEE Trans- actions on Intelligent Transportation Systems, 22(7):4316-4333 2020.
Lorena Qendro and Cecilia Mascolo. Towards adversarial robustness with early exit ensembles. In 2022 44th Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pp. 313-316. IEEE, 2022.
Lorena Qendro, Alexander Campbell, Pietro Lio, and Cecilia Mascolo. Early exit ensembles for uncertainty quantification. In Machine Learning for Health, pp. 181-195. PMLR, 2021.
Yaniv Romano, Matteo Sesia, and Emmanuel Candes. Classification with valid and adaptive cover- age. Advances Neural Information Processing Systems, 33:3581-3591, 2020.
Aviv A Rosenberg, Sanketh Vedula, Yaniy Romano, and Alexander Bronstein. Fast nonlinear vec- tor quantile regression. In The Eleventh International Conference Learning Representations, 2022.
Mauricio Sadinle, Jing Lei, and Larry Wasserman. Least ambiguous set-valued classifiers with bounded error levels. Journal of the American Statistical Association, 114(525):223-255 234, 2019.
David Stutz, Krishnamurthy Dj Dvijotham, Ali Taylan Cemgil, and Arnaud Doucet. Learning opti- mal conformal classifiers. In International Conference Learning Representations, 2021.
Jiaye Teng, Chuan Wen, Dinghuai Zhang, Yoshua Bengio, Yang Gao, and Yang Yuan. Predictive inference with feature conformal prediction. In The International Conference on Learning Rep- resentations, 2022.
Vladimir Vovk. Cross-conformal predictors. Annals of Mathematics and Artificial Intelligence, 74: 9-28, 2015.
12

---

Published as a conference paper at ICLR 2025
Vladimir Vovk, Ivan Petej. and Valentina Fedorova. Large-scale probabilistic predictors with and without guarantees of validity. Advances in Neural Information Processing Systems, 28, 2015.
Jiancheng Yang. Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. Medmnist v2-a large-scale lightweight benchmark for 2d and 3d biomedical image classification. Scientific Data, 10(1):41, 2023a.
Sherry Yang. Ofir Nachum, Yilun Du, Jason Wei, Pieter Abbeel, and Dale Schuurmans. Foundation models for decision making: Problems, methods, and opportunities. arXiv:2303.04/29 2023b.
A MATHEMATICAL DETAILS
A.1 NONCONFORMITY SCORES
A commonly used nonconformity score is based on the confidence of the predicted probabilities, defined as 5hh 3) = πσ) (Sadinle et al. 2019). However the Thr score can sometimes undercover hard examples and overcover trivial ones. Hence, popular alternative is the adaptive prediction sets (APS) method (Romano et al. 2020). which is based on the cumulative probability > (2) + u T(T).. where u uniform random value that
AAPS (c, = Eg= (()),1 (T()), breaks potential ties between different scores. However, the APS method often results in large prediction sets, which is undesirable. To address this, RAPS score was introduced (Angelopoulos iet al. 2020), which encourages smaller prediction sets by penalizing less likely labels. The RAPS score is defined as:
SRAPS( 1) = Σ x()),1 x(x)g) + (())(x) + v. max(o(2, v) K. 0),
(14)
where o(I, 3/ denotes the rank class y, and y and λ are hyperparameters that control the penalty strength. More recently, alternative scoring methods have been proposed that rely on the relative rank of the prediction (Huang et al. 2024 Luo & Zhou 2024a). For example, the SAPS score is
defined as (Huang et al. 2024):
Tmax (x), (z) + (o(x, y) u) E.
if oz y) 1, otherwise,
SSAPS v) = max
(15)
where & is hyperparameter that controls the weight of the ranking information, and Tama (x) the maximum softmax probability.
A.2 TOY EXAMPLE DETAILS AND ADDITIONAL JUSTIFICATION FOR MULTI-DIMENSIONAL CONFORMAL PREDICTION
Assume binary classification problem with Y E {-1,1} and prior probabilities P(Y = 1) and
P(Y = -1). The input X is generated from a mixture two Gaussians, with P(X = o")
In this example, we can compute the posterior [(Y|X) using Bayes rule:
PP(Y (.)))P(X))) =a)
P(Y x\ P(Y ()P = PP -X)P(XX|Y = -1) -1) a=(-1,1
(16)
We set (Y = 1) IP 1) = 0.5, of = 02, 0.75. Let (P(x. PPY = y|X = x)), consider the following three classifiers:
i 0. To(x)= = F(yla), Ti (2) = (c,1-c), if > 0
P()]z),
(c.1- if 0 P(ylx), if if>0
[2(x)== =
(17)
where e ~ NO, 1). The classifiers are illustrated in Fig. A.1 Here To(2) represents the ideal classifier, and T1 and (2)x)) ideal only in half of the range of and uninformative for the other half. We generate 2000 points based on P(X and use 1000 for validation and 1000 for calibration. We compute the Thr nonconformity score. Results are averaged over 20 random trials.
When Ff((z) = P(Y = y|X = .)) is known, it was shown that the optimal set with minimal size under coverage constraint is given by [*xx)= {y (P((, > qa} (Lei & Wasserman
13

---

Published as a conference paper at ICLR 2025
1,0
1,0
3.5
Probablyy
y
0.5
Probabiltyy
04
myk, 1)
0.4
m. y 31
24
02
02
(a) nO (ar)
(b) m (a)
(c) (2(x)
Figure A.1: The three classifiers the toy example binary classification problem.
2014 Sadinle et al., 2019 Kiyani et al. 2024). This implies that the optimal set a level set of the distribution P(x,, v). Thus, in our toy example, thresholding szz y) = 1 P(x,, y) results in the optimal set. Using only $1 (z, y) and $2 y) the optimal set can be equivalently defined as:
I (x) = {v (1 S 0} s1 (z, y) + 1(x x > 0} 82 w)) - 2a
= (v E yls (z, v) (x) < 1-
where (x) [1 < 0). 1(= > 03O Thus. we obtain that the optimal set function of the 2- dimensional nonconformity score s(x, y). In this example, each classifier specializes on a different subdomain of the input space X'
Another practical case is when classifiers specialize on different parts of the output space y. For example, consider y {0, 1, 2}. and the following three classifiers:
[a(x)= {
F = a|x),
if y a, if (a + 1) mod 3, EE {0, 1,2),
c, Ply a|x) 6,
(18)
if y (a + 2) mod
where é ~ (O, In this case, the optimal set is given by:
(')x) (y V/s" (x, iv()) < qaa
(19)
where (v) [1[y = 13, = 23.1(y TH.. conclude that whenever F(x,, y)
= [0, is non-degenerate function of the multi-score vector, the optimal set relies on sαx v). i.e.:
((s(2, v, y). where o S X x
(x) = fy E Vlo(s(r, y): v) 1 1-
(20)
contrast, relying solely on single score will result in suboptimal solution. Note that, according to Eq. 20), the ideal set corresponds This implics that, general, the decision boundaries in the multi-dimensional score space can be arbitrarily complex, depending the properties of Φ.
level set of ((s(2, v); rather than s(x, y) itself.
We conclude that in practical scenarios, where single score does not provide the full information on the conditional distribution P(y]æz) may appear that optimizing for set size efficiency in the multi-score space exponentially increases the number of possible prediction to be considered, which makes the optimization more challenging compared to the single-dimensional case. However, our cell partitioning and ranking procedure relaxes the problem to convenient structured prediction with simple selection rule that does not require any iterative optimization procedures. Note that the number of cell centers and the summation operation over all scores that fall in the chosen region, remain fixed regardless of the dimensionality of s(x,,). However, n increases the cells move apart from each other, when the scores are nonidentical and provide complementary information. Moreover, each dimension contributes information about the actual conditional distribution IPY)))), we anticipate an improved separation between true and false scores. Consequently, the selected subset of cells is expected to exhibit lower D, values, leading to smaller prediction sets. This is demonstrated in Fig. A.2 presenting the distribution D, for the chosen cells. We observe that as n increases, the values of D, become smaller.
benefit from using dimensiammnni score s(x. y). It
14

---

Published as a conference paper at ICLR 2025
1-head
3-heads
6-heads
Frequency (Log Scale)
10a
400
Selected Deells scores
Figure A.2: Histogram of cell scores D; for the selected number of cells, comparing different num- ber of heads. Values correspond CIFAR100 dataset, RAPS scores and 0.1
A.3 PROOF OF PROPOSITION
Proof. For pair of test input Xm and (candidate) label y y compute the multi-
dimensional score s(Xm11 3) (Xmm,,,, v)...........................v . Sn (Xm+1, 4)17. We define combined score
function Smutti X x R that maps the multi-dimensional score s(x y) into single-dimensional
score 5 mulli (I, y). The mapping is defined as follows:
Smulti (Xm+1, 8) arg min [|s(Xm+1,)) s (() 15jSK'
(21)
where (j) denotes the index of the samples in Deells after sorting according to the ratio values in Eq. ( and eliminating repeating elements, i.e. (X(1): Y(n)).... (X(w). Y(w)) are the centers of the cells ...) C(e)) where D(1) < D(2) .... S D(K)) This way each pair (Xm+1;3) y) is associated with the closet center and the ranking of this cell serves as the one-dimensional score, defined in Eq. 21
The prediction set (Xxm)) is defined in Eq. 9 by including predictions associated with scores that reside in the selected region. This can be equivalently written in terms of threshold operation over Smultis as we can write:
Tg- = v (1....Q) Q} |sXXs
E chi
y E [I...., | s(X
i=1
E (1, (l...., Q} Ü
(((Xm+11)) coll
i=1
(22)
y (1..................... 21 U
arg min (( v) - s(X X
iml
17"
21
y E (1, (I. Q} Ul li 5 mmutti (X (Xm+1,
(y (1, (1...., Q} 1maati (Xm+1, S n))
This formulation is the same as standard one-dimensional conformal prediction procedure, where define the prediction set by thresholding one-dimensional score function. The threshold 17" was
15

---

Published as a conference paper at ICLR 2025
chosen obtain exact coverage over the held-out data Die-cal, therefore:
min E (1....,k') ,K' Yi C. for at least [(1 a)(rr 1)] samples (X;, Yi) E Dre
min(n E (1...., }}} Smuti ,,,, Yi) S 7 for at least [(1 (r + 1)] samples in Dre-cal)
[rr 1)(1 a)l, {smutt (X,, YJ) k=)++
Quantile
Thus, assuming that Dre-cal and (Xm+1, Mm+1) are exchangeable, obtain that:
IP (Y E TT g (Xm+1)) 2 1 -
(23)
following Theorem ①
Note that the split of Deal to two disjoint subsets Deells and Dre-eal is critical here, since we cannot claim that the samples in Dretis and the test pair (Xm+1, Ym+1) are exchangable as Deetls serves for the computation of the score defined in (2I) (in a similar way to the fact that the training data cannot be used for calibration in standard conformal prediction).
A.4 EQUIVALENCE BETWEEN CELL SELECTION AND SET-SIZE OPTIMIZATION
We start by proving Lemma 3
Proof. Let F; = Eq 1(s(),)))))))) E C,} 1(Y, * 9} and T, ( C,} denote the number of scores with false labels and true labels, respectively. Let C 2 denote the set of disjoint cell indexes, removing duplicates. Using these definitions, finite-sample approximation of the expected set-size Liize over Deells, can be written
b Q
Liize
1. E (X,))
j=1 1=1
k
Q
1(S(X,:)) 9) e e.erC)
Q
1(S(3,,)) 2) E UserC
(s((3,,)) CC))
Σ
F.+T.
iE
F
T
T.
Σ iel
Dis
(24)
where the final equality directly follows from the definition of the cell score in Eq. coverage constraint, we obtain:
For the
11 (X)Er'(())) - Σ - 1
Leooeeraee
(25)
k
iel
iET
The proof of Proposition follows directly, now state.
16

---

Published as a conference paper at ICLR 2025
Algorithm B.1 Jackknife+ Multi-Score Conformal prediction
Definitions: s( y) is a caali-ddmeenional score function. Deal is the calibration data of size m. Xm+1 is new test sample, a is the miscoverage level, & is the number of samples for cell- partitioning and scoring, and r m k: the number of samples for re-calibration.
1: function MULTI-SCORU C- y). Deat. a))
2: Compute the scores s(X,, s. Yi), i (1.....,, ..)
3: Segment S into cells {C, 1 == centered at {(X;, Y:)
4: Remove duplicate cells Ci, Ci,.,,
5:
for i E (1....,k) do
6:
Compute D -j = ,,..,, 1, ,,..., k'' using Eq. 7 excluding the i-th point Rank the cells C(1), Ci)....................... C (w-1) according (1i) (2) S .... D
7:
8:
E t arg min (1...... [|, Y.) s(X Yo)i
9:
Ey) + arg min jll.... (' |s(Xm+1))) s(X (o))|| eEY
10:
T JJK+ (Xm+1) = {y e .1.,............. Q} Em 1 E (y) < (1 - am + 1)}
return 1 11:
Proof. Lets first assume that there are no duplicates, i.e. T, 1, sis Let I denote the (1 at) proportion of cells with the smallest D; values, we obtain that:
L D coverage
aa
(26)
By construction, I* has the smallest empirical set size compared to any other set 1 with [
||] = =1 -1-0
Lun - D. - D
D. Lg
(27)
SET' EES
Thus, when there are no duplicates, the solution to the optimization problem in Eq. (12) is obtained by ordering the cells according D; and selecting the top-ranked a proportion of cells. When duplicates exist, it can be interpreted as selecting the same cell T; times. In this case, the solution to the optimization problem in Eq. (12 obtained by ordering the cells according to D, and selecting the top-ranked cells until a a proportion of k is selected, subject to the constraint that all dupli- cates must be selected together. different T; values, which would make it ambiguous to determine which cell to select first. However, this will only make difference when approaching the selection limit and since, anyway, duplicates are rare in dimensions higher than one, this ambiguity has negligible effect.
possible for some disjoint cells to have the same D, scores with
Finally, re-calibration over Dre-cul, as defined in Eq. 8), guarantees exact coverage, as follows from Proposition 2
B ALGORITHMS
The jackknife+ variant, described in Section D.6 is provided in Algorithm B.1 while the soft centers variant, as detailed Section D.6 presented in Algorithm B.2
C IMPLEMENTATION AND DATASET DETAILS
Datasets and Implementation. The details of each dataset and the corresponding data splits are summarized in Table C.I where Tiny ImageNet, CIFAR100 and PathMNIST are used in our main results while ImageNet and Newsgroups are used for the additional experiments. described in $ The calibration data is split into half for cell computation, and re-calibration.
17

---

Published as a conference paper at ICLR 2025
Algorithm B.2 Soft Multi-Score Conformal Prediction
Definitions: ( y) is multi-dimensional score function. Deal is the calibration data of size m. Xm+1 is new test sample, a is the miscoverage level, & is the number of samples for cell- partitioning and scoring, and r m k is the number of samples for re-calibration and is the number of neighbors.
1: function SOFT MULTI-SCORE-CP(sSal v). D a,b)
2:
Randomly split ceal to D Deells = {X;, Y,) 1-11 and Dre-cal = {(X,, ())
3: Compute the scores s(X,, s, Y),, i E {1..... .......
4:
Segment S into cells {C, ] ==1 centered {(X, 1))=
5:
Compute D; ,...., k Remove duplicate cells according to Eq.
6:
7:
Rank the cells C(1). C(2),... ,a,, according to D(1 S D(2) S S DKk)
8:
(1) b nearest cells of s(X,, Yi) in (C() iE (k 1....,,)) m}
9:
"' min {1)
Σ Ei
EL (T)(1) S C 00.5 [0.5. b1 2 [(1 a)(r+
10:
CM U. C())
11:
return CØ
function SOFT MULT-SCOR--VALUUATINNE
y). X Xm+1 C Compute the scores s(Xm+1, v), E (1...., Q} WK
13:
14:
(v)) + b nearest cells of s s(Xm+1, in (C() 1==1 h= yEY To (X {UED' Ei-n (T(()) C })
15:
[0.5 b1
16:
return , (Xm-1)
Table C.I:
Datasets Details
Dataset
Classes
Train
Validation
Calibration
Test
Average Accuracy
Tiny ImageNett
200
71,500
11,000
16,500
11,000
0.58
CIFARI00
100
39,000
6,000
9,000
6,000
0.69
PathMNIST
69,667
10,718
16,077
10,718
0.94
20 Newsgroups
20
9,800
2,499
3,298
3,299
0.87
ImageNet
1,000
1,281,184
10,000
20,000
20,000
0.71
For the first three datasets used ResNet50 model with pretrained weights on ImageNet. Each head a 3 layer feed-fo neural network with, BatchNorm, ReLU activation and dropout with p 0..1.
In the first stage, the full model with a single classification head was fine-tuned on each task with 20, 100 and 200 epochs for Tiny ImageNet, CIFAR 100 and PathMNIST, respectively. In the second stage, we freeze the backbone model and train only the classification heads for 20 epochs, using the loss defined in Eq. (1).. In both stages,
Adam optimizer with cosine annealing scheduler, momentum decay of 0.95, weight decay of le 5, and batch size of 16.
5, and for the SAPS score For the computation of the RAPS score we used 0.05 and set & = 0.3. Performance with respect to other parameter values is reported in Tables D.5 and D.6 for RAPS and SAPS, respectively.
D ADDITIONAL RESULTS
D.1 EVALUATING OTHER PERFORMANCE ASPECTS
Conditional Coverage. We assess performance in terms of conditional coverage, evaluated using size-stratified coverage violation (SSCV) and worst-slice coverage (WSC). For SSCV, we define a set of disjoint strata (S,))=1 where S/ (1, (1,...,Q) Q). We partition the data into groups with
18

---

Published as a conference paper at ICLR 2025
0.52
Best heoe
Mutti aulooscono
10
Coveraze
0.81
Mean Set Size
0.50
0.79
0.77
Number Heads
Number Heads
(a) CIFARI0O (a = 0.02)
(b) CIFARIOO 0.02)
Mathod
3.5
0.085
3.0
Mean Cevero
2.5
0:580
Mener St6
03/5
0970
0.5
0.0
Number Heads
Number Heads
(c) PathMNIST (a 0.02)
(d) PathMNIST (ax 0.02)
2.500
Method
2.15
head
2.10
Unieen
20
Moen Cove age
Ootinizzd
2,000
Norm
2,500
Meen See
2.900
2.80
3.80
2
Numbur of Frudda
Namber of Heads
(c) Tiny ImageNet (a = 0.2)
(f) Tiny ImageNet (a 0.2)
Figure D.1: Conformal prediction with RAPS as a function of the number of classification heads. Results compare multi-score conformal prediction and the baselines (Best head, Optimized, Uni- form, and Norm) across two metrics: empirical coverage (left column), and mean set size (right column), over: CIFARI00, Tiny ImageNet and PathMNIST.
equal numbers of samples. Let وj- = Quantile (4: (IT(X, Y.)D)) j= 0,... J. denote the 4-th quantile of the set sizes. The jth group is then defined as G. = fi: -;- < [1 Xi)l S gj } for
j E JT. Accordingly, the SSCV is defined as (Angelopoulos et al. 2020
[i: Y, E T(X,, Y,), i E 93Hl (1 a)
SSCV(1S)))=)) = sup
(28)
For this evaluation, we divided the data into J = 10 groups. The results, summarized in Table D.I indicate that all methods achieve similar SSCV scores, with no method showing clear advantage over the others.
Additionally, we evaluate the WSC, defined in (Romano et al. 2020), which quantifies the worst- case coverage along a random projection within a local region of the distribution. The results, summarized in Table D.2 indicate that the multi-score method performs comparably to the baselines in terms of WSC, contirming that the proposed approach maintains conditional coverage.
Results with SAPS scores. To examine the robustness of the multi-score method with respect to the choice of nonconformity scores, we compare the results achieved using the SAPS nonconformity score across different levels of and datasets. The results presented in figs D.2 and D.3 As
19

---

Published as a conference paper at ICLR 2025
35
Methed
30
Cooorge
0.93
Unitorms
Optim Loed
25
Notm
20
0.00
0.50
0.88
Number Heads
(a) CIFAR10O (a = 0.01)
(b) CIFARIOO (a = 0.01)
Mathod
0.334
Toor Sut $:00
0.90
Meah
0:886
0.84
Number Heads
Number Heads
(c) PathMNIST (a 0.01)
(d) PathMNIST (a 0.01)
Method
3.915
2.910
besd head
Unilden
Covernn age
3,805
Ootieiized
Norm
0.008
2.00
3.86
10
3.80
2
Numbur of Faada
Namber of Heads
(c) Tiny ImageNet (a = 0.1)
(f) Tiny ImageNet (a 0.1)
Figure D.2: Conformal prediction with SAPS as a function of the number of classification heads.
Results compare multi-score conformal prediction and the baselines (Best head, Optimized, Uni- form, and Norm) across two metrics: empirical coverage (left column), and mean set size (right column), over: CIFAR100, Tiny ImageNet and PathMNIST.
expected, all methods achieve the required coverage. The proposed multi-score calibration produces smaller prediction sets, with significant improvements as the number of heads increases.
Results with Thr and APS scores. In general, our proposed method can be applied over any type of score. However, we have seen that is not fully optimal for Thr and APS. The reason is that for these scores the values are more concentrated on specific levels, while for SAPS and RAPS the values are more spread. In order to improve this behavior we use temperature scaling, i.e. we divide the logits by 7 before applying Softmax(). As T increases the entropy of the probabilities increases and they become more spread, as illustrated in Fig. [D.5] Figure D.6 presents the set sizes obtained for all methods with respect to different temperatures. We see that the efficiency the proposed method greatly improves as T increases for both Thr and APS, while the performance of the baseline methods is less effected by T. For RAPS and SAPS the proposed method outperforms the baselines regardless of the temperature due to the inherent spread of these scores.
The distribution of set sizes. Figure D.7 illustrates how increasing the number of heads (from 1 to 7) shifts the set size distribution toward smaller values, indicating more samples with smaller set sizes. Notably, the multi-score method responds more effectively to the increase in heads compared
20

---

Published as a conference paper at ICLR 2025
0.53
12
Mutt-
Best heoe Uniform
Coverage
0.81
Optiiitzed
Mean Set Size
0.80
0.78
Number Heads
Number Heads
(a) CIFARI00 (a = 0.02)
(b) CIFARIOO (a = 0.02)
0.0075
Mathod
3.6
0.0050
3.0
Mean Coveege
Mene St6 Stn
2.6
0.0900
2.0
0.975
0.8790
08722
0.9700
0.5
0.9675
0.0
Number Heads
Number Heads
(c) PathMNIST (a 0.02)
(d) PathMNIST (ax 0.02)
0.02
Method
25
head
Meatn Coverage
Unieeen
Opterizzdd
North
10
0.78
0.77
2
Nambar of Huada
Numbbr of treach
(c) Tiny ImageNet (a = 0.2)
(f) Tiny ImageNet (a 0.2)
Figure D.3: Conformal prediction with SAPS function of the number of classification heads. Results compare multi-score conformal prediction and the baselines (Best head, Optimized, Uni- form, and Norm) across two metrics: empirical coverage (left column), and mean set size (right column), over: CIFAR100, Tiny ImageNet and PathMNIST.
to the baselines, achieving set size values in smaller range (2 41) while for the other methods the sizes range from 11 - 41. This highlights again that our multi-score method leads to more efficient and precise sets.
D.2 RESULTS WITH OTHER TYPES OF MULTIPLE SCORES
Standard Ensemble. We conduct an experiment with a standard ensemble, consisting of multiple different models that are trained separately on the same dataset. We use ImageNet dataset for evaluation with an ensemble of 5 models pretrained on ImageNet: VGGI6, Incep- tion, ResNet50, ResNet152 and DenseNet161. Results are shown in Fig. D.8 for RAPS score and 10.03, 0.05, 0.1]. Similarly method obtains the smallest prediction set sizes. This indicates that our method can be applied to self-ensemble models well regular ensembles.
main results with self-ensemble, here too the proposed
21

---

Published as a conference paper at ICLR 2025
52 y)
34
02
06
51 y)
Figure D,4:
Visualization of cell selection order over CIFAR100 with RAPS score and a = 0.1. Darker cells were selected earlier in the sequence while lighter cells are selected later stage.
Table D.1: SSCV measure for 100 with RAPS score
a
Head
Methods
Multi-score
Best head
Uniform
Optimized
Norm
0.174
0.034
0.174
0.159
0.174
2
0.167
0.108
0.114
0.194
0.141
3
0.240
0.104
0.066
0.162
0.277
0.1
0.298
0.204
0.178
0.167
0.264
5
0.106
0.155
0.167
0.200
0.252
6 0.131
0.153
0.172
0.308
0.125
0.056 7
0.159
0.062
0.191
0.175
1 0.190
0.037
0.190
0.157
0.190
2 0.362
0.249
0.292
0.221
0.330
0.342
0.200
0.132
0.187
0.098
0.2
4
0.379
0.206
0.167
0.166
0.279
5
0.361
0.192
0.159
0.209
0.331
6
0.220
0.180
0.071
0.274
0.276
0.186
0.203
0.200
0.171
0.245
Test-Time Augmentation. We evaluate our method on test-time augmentations (Lu 2023). We use ImageNet dataset with Inception-V3 V3 model. We use simple common test-time augmentation policy (Krizhevsky et al. 2012), which consists crop and a horizontal flip. The random crop pads the original image by 4 pixels and takes 256x256 crop the resulting image. draw five augmentations using this policy. Figure D.9 presents the results for RAPS score and [0.03, 0.05, 0.1]. Our method outperforms the baselines in terms of prediction set size. We conclude that test-time augmentation can serve as a possible alternative for generating multiple nonconformity scores within multi-score conformal prediction framework.
score that is formed by
random
Multiple scores computed over single head. We examined a setting where instead considering multiple classification heads,
single head and compute different conformity scores: Thr,
22

---

Published as a conference paper at ICLR 2025
Table D.2: WSC Results on CIFARI00 and TinyImageNet (10 trials)
Dataset
Score
Method
Multi-score
Best head
Uniform
Optimized
Norm
RAPS
0.901
0.905
0.903
0.905
0.901
CIFARI00
SAPS
0.903
0.908
0.906
0.895
0.894
0.1
RAPS
0.905
0.903
0.896
0.896
0.892
TinylmageNet
SAPS
0.900
0,902
0.900
0.901
0.909
RAPS
0.801
0.801
0.797
0.799
0.803
CIFARI00
SAPS
0.812
0.819
0.800
0.813
0.817
0.2
RAPS
0.796
0.791
0.801
0.800
0.802
TinyImageNet
SAPS
0.808
0.802
0.808
0.806
0.807
1.0
1.0
0.8
0.8
0.6
True
0.9
Fest palnts
Thei ports
Sitx v)
Sifx.v
(a) Thr (1' 1)
(b) APS (7' 1)
1.0
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
The
Tue poinr
0.9
Taxt partts
0.0
pants
0.0
0.2
0.1
1.0
0.0
0.2
0.1
0.6
0.8
1.0
(c) Thr (T"
(d) APS (T 5)
Figure D.5: Demonstration of APS and Thrt scores's distribution with different Temperatures on CIFAR-100 and = 0.1.
APS, RAPS and SAPS. To ensure all scores are comparable and fall in the range between [0, 1]. apply Softmax)) over each score. Table D.3 summarizes the results for all datasets. We see that combining multiple scores improves the results compared to the best single score, and that the proposed method obtains the smallest prediction sets in almost all cases. The advantage of this score fusion that does not require any additional modifications to the model or further fine-tuning iterations.
23

---

Published as a conference paper at ICLR 2025
Veehods
Melhade
30
Meld Soure
Best Head
Sol 580
Mill Surro
Best Head
Listfom
Unittrm
Cafiniiedd
Qufinicoo
25
2.0
2.0
(a) ThR
(b) APS
Mothods
Mothods
32.5
30.0
Optimizod
Optinizod
Nom
Nom
Sct Bize
17.5
15.
10
1.5
2.0
2.5
3.0
3.5
4.0
4.5
5.0
10
1.5
2.0
2.5
3.0
3.5
4.0
4.5
50
(c) RAPS
(d) SAPS
Figure D.6: Set size as a function of the temperature for different nonconformity scores. Results are shown for CIFAR 100 with 7 heads and 0.1
Servie
Grde
(a) Multi-score
(b) Best head
(c) Uniform
(d) Optimized
(e) Norm
Figure D.7: Histograms of the set size distribution across different numbers of classification heads with RAPS score on Cifar100 and a=0.1. Rows represent 1, 2, and 7 heads, while columns corre- spond to different methods.
D.3 ROBUSTNESS TO HYPERPARAMETERS
Influence of training with diversity regularization. We conducted ablation study examine the affect of adding diversity regularization to the loss used for training the classification heads, defined in Eq. (13). We use the same fine-tuned model in the first training stage and change only
24

---

Published as a conference paper at ICLR 2025
Mall-woce (ptrecco)
Mam Sac
224
0.32
0.0
Figure D.8: Results for ImageNet with standard ensemble of five different models, using RAPS score.
100
Nethod
Uiibora
1.4
Veec
2.50
2.0
060
683
OLS
6-1
Figure D.9: Results for ImageNet with test-time augmentations, using RAPS score.
Table D.3: Set-size comparison for a single classification head and multiple types of scores.
Method
Dataset
Multi- score
Best head
Uniform
Optimized
Norm
CIFARIO0
33,90
35.12
35.32
34.96
35.54
0.1
TinylmageNet
58.08
61.62
62.96
62.70
78.45
CIFAR100
18.33
27.88
28.12
27.52
28.18
0.15
TinylmageNet
35.84
48.55
49.47
49.48
55.75
CIFAR100
8.25
9.34
9.19
8.35
13.02
0.2
TinylmageNet
19.99
24.94
27.49
26.94
34.49
0.01
PathMNIST
6.26
6.69
6.67
6.5
6.56
0.02
PathMNIST
3.31
4.56
2.98
2.96
3.07
the second stage to optimize the regularized loss in Eq. 113 with different values of X, controlling the strength of the diversity regularization. Figure 1.10 shows the similarity between heads with and without the diversity regularization. As expected, the similarity between heads is smaller for the model trained with the regularized loss. Figure [.II compares the set sizes obtained for different values of X, demonstrating that adding the regularization results in smaller sets. The optimal value of À is around 0.8, after which an increase in set size observed, apparently due the fact that increasing head diversity comes the cost of decreasing the accuracy of each head.
Influence of the of size Deat- We examine how the performance is affected by the size of the calibration data. Here, we vary the proportion p of samples from Deal that are actually used, i.e. select a subset D S Deals where [D' = -p- |Deall- Then, as before, D is split into half for cell computation, and re-calibration. Figure D.12 presents the set sizes for different values of p. It can be seen that the proposed method is almost always preferable, with its advantage becoming more pronounced the size of the calibration data increases.
25

---

Published as a conference paper at ICLR 2025
1e0 18633 Houe Hear
OCT
091
093
690
HANT meal 19X3
47
107
089
0.76
00
A0L
6G2
679
00L
00
00
001
602
122
Headd
IMBE
ledd)
Hlead
lead
leed?
HHBC
1862
(led))
leed5
leads
Hind
Figure D.10: Similarity matrix between prediction heads for heads trained with (left) or without (right) diversity regularization on CIFARION dataset.
0-0002 02
15
Sai Size
0.2
08
1.4
Figure D.11: Set size function of the regularization parameter À for CIFAR100 with RAPS score and 7 heads.
(a) CIFARI00
(b) Tiny ImageNet
(c) PathMNIST
Figure D.12: Sensitivity of the results to the size of D We select subset Dr C Deat. where DD' cal = p- [Deal The set sizes obtained for different values of are reported for RAPS score on heads. Upper row for 0.1 and lower row for 0.2.
Influence of the of size Dealss- We investigated the effect of k. the size of Deeliss on the results.
the definition of the cells in Eq. (6) and the computation of the ratio-based scores in Eq. (7). In this experiment, the dataset is divided, as before, into three fixed
Recall that Doelss is responsible
subsets: Deells: Dre cal, and Drea. We vary the proportion p of samples from Deelis that actually
26

---

Published as a conference paper at ICLR 2025
Table D.4: Sensitivity of the set-size the size of Deelss We select a subset cells Deelss where [D settss p- [Peets]. The set sizes obtained for different values of are reported for CIFAR100 dataset and heads.
Method
Score
Proportion
100%
95%
90%
85%
80%
70%
60%
50%
25%
10%
0.1
15.32
15.66
15.68
15.69
15.92
16.26
16.68
17.32
19.04
22.13
RAPS
0.2
2.33
2.33
2.34
2.35
2.37
2.49
2.54
2.64
3.09
4.16
Multi-score
0.1
15.46
15.46
15.76
15.72
15.88
16.04
16.32
16.91
19.01
22.17
SAPS
0.2
2.36
2.36
2.37
2.41
2.42
2.54
2.6
2.64
3.09
3.61
0.1
22.47
22.27
22.04
22.09
21.85
21.71
22.47
22.52
23.4
24.2
RAPS
0.2
6.53
6.31
6.21
6.3
6.73
6.49
6.14
6,55
6.54
7.21
Optimized
0.1
21.8
21.83
21.71
21.68
21.51
21.63
21.55
21.66
23.24
25.11
SAPS
0.2
6.8
6.45
6.4
6.45
6.31
.6.14
5.93
5.93
7.4
8.611
used, i.e., we select subset D C Deells. where !D p [Deell]-- The set sizes obtained for different values of p presented in Table D.4 As expected, the set size increases However, the overall behavior remains stable, with only 9.4 13.3% increase in set size for 50% reduction in the number of samples Deells- In addition, we compare the Optimized bascline, where the set D cells, is used for optimizing the weights for combining the scores. We see for all values Multi-score advantageous over Optimized.
decreases.
Influence of the nonconformity score's parameters. We examined the influence of the different parameters of the non-conformal RAPS and SAPS scores on the methods performances The re- sults for the RAPS score are detailed in Table D.5 while those for the SAPS score are presented in Table D.6 Overall, our findings indicate that the Multi-Score method remains consistently advanta- geous, regardless of the parameter settings.
Inftuence the underlying model. conformal prediction (CP) regardless of the underlying model, we conducted experiment using a more powerful ViT model Dosovitskiy et al. (2020) Results are presented on table D.7 showing similar trends to those observed in main results.
To demonstrate that our method improves the efficiency of
D.4 RESULTS ON OTHER DATASETS
Results on text data classification. To show that our method can be applied across different types of data, we conducted an experiment with a text classification task. We use the 20 Newsgroups dataset, which comprises newsgroup posts 20 topics. We use BERT-base model (Devlin et al.) 2019). and attach additional classification heads a similar way to the other models. The results on Table D.8 show that Multi-Score outperforms all the baselines. Here, the norm baseline is the closest in the performance to the proposed method.
Results for ImageNet. Table D.9 presents the results obtained for ImageNet. Here the classification heads consist of a single linear layer, and are all initialized by the weights of the pretrained model. the benefit of the proposed method over the baselines.
Here too
D.5 ADDITIONAL BASELINES
L1 Norm baseline. We examined additional baseline, where the LI norm instead of the L2 norm. Table D.10.compare compares the two baselines for CIFAR-100 dataset and RAPS score. We observe that both baselines obtain similar performance.
Set-size comparison to vanilla baseline. We examined vanilla baseline, where the CP procedure performed over the original classification head, without the addition of multiple classification heads. We observe that the results are similar to the Best head baseline defined above. Table D.II summarizes the results
27

---

Published as a conference paper at ICLR 2025
Table D.5: Set-size comparison between the baselines for different values of x and X, used in RAPS score, CIFARI00, 0.1 and 7 heads.
Method
K
0.001
À 0.01
0.1
1.0
12.79
14.83
15.10
15.45
12.84
14.26
15.11
15.53
Multi-score
3
12.88
14.29
15.30
15.54
12.81
14.45
15.36
15.53
5
12.80
14.44
15.51
15.70
32.04
32.11
32.11
32.11
24.41
24.00
24.00
25.00
Best head
23.01
23.02
23.04
22.79
4
20.77
21.12
21.63
22.70
20.32
21.21
23.60
22.60
24.38
24.76
24.91
24.96
2
24.41
23.59
24.87
25.05
Uniform
23.10
23.75
25.44
26.14
4
21.20
21.84
23.26
23.33
5
20.40
21.41
22.63
22.75
24.45
24.89
25.26
25.84
24.52
24.00
24.76
25.10
Optimized
3
23.09
23.32
24.64
25.07
20.82
21.20
22.30
22.70
5
20.34
21.40
22.80
22.60
18,01
19.62
19.80
22.59
18.01
22.99
24.53
24.66
Norm
22.82
23.05
27.74
28.50
4
20.80
21.21
21.75
23.60
20.34
21.21
23.86
25.04
Table D.6: Set-size comparison between the baselines for different values of &, used in SAPS score, on CIFAR100, a 0.1 and heads.
Method
{ 0.01
0.05
{ 0.1
0.1
{
0.5
{ 1.0
Multi-score
14.70
16.17
16.28
16.89
17.06
Best head
34.49
35.11
35.21
35.43
35.48
Uniform
19.15
21.73
21.91
22.55
22.57
Optimized 18.51
21.00
21.60
21.90
22.07
Norm 18.61
21.31
23.12
24.56
24.59
Table D.7: ResNet
VIT model set size comparison CIFAR100 with 0.1 and 7 heads.
Method
Model
Acc.
Score
Multi-score
Best head
Uniform
Optimized
Norm
RAPS
4.34
22.11
16.21
15.93
5.51
VIT
0.8
SAPS
2.33
12.77
2.43
2.45
2.60
RAPS
15.32
35.29
22.37
22.47
22.49
ResNet50
0.69
SAPS
15.46
35.41
22.05
21.80
22.79
28

---

Published as a conference paper at ICLR 2025
Table D.8: Set-size comparison across different methods on the 20 Newsgroups dataset, with heads, using the BERT-base model fine-tuned for news topic classification.
Method
Score
Multi-score
Best head
Uniform
Optimized
Norm
RAPS
1.46
9.61
9.58
9.49
1.5
0.08
SAPS
1.47
10.66
2.09
2.18
2.35
RAPS
2.29
10.1
10.01
10.07
2.32
0.05
SAPS
1.97
10.9
2.4
2.46
2.62
RAPS
4.28
11.73
11.73
11.47
4.36
0.02
SAPS
3.28
11.57
3.45
3.34
3.65
Table D.9: Set-size comparison across different methods on the ImageNet dataset, with heads, demonstrating the performance with huge-nnumbr-of classes.
Method
α
Score
Multi-score
Best head
Uniform
Optimized
Norm
RAPS
4.1
4.36
13.47
14.63
13.47
0.1
SAPS
4.94
5.36
13.85
14.99
13.85
RAPS
1.82
2.4
2.1
2.1
0.2
SAPS
1.57
1.68
2.04
2.06
2.04
Table D.10: Set-Size comparison between LI and L2 Norm methods on CIFAR100 and heads.
Method
Score
L1
L2
Multi-score
RAPS
22.98
22.49
15.32
0.1
SAPS
22.25
22.79
15.46
RAPS
6.75
7.51
2.33
0.2
SAPS
7.62
7.85
2.36
Table D.11:
Set-size comparison between the vanilla baseline and the multi-score methods on CI- FAR100, with RAPS score and 7 heads.
Set Size
αt
Multi-score
Vanilla RAPS
Best head
0.1
15.32
39.27 8.09
35.29 9.37
0.2
2.33
D.6 VARIANTS OF MULTI-SCORE CONFORMAL PREDICTION
Jackknife+ Multi-score conformal prediction. We compare split version in Algorithm to the jackknife+ version in Algorithm B.I We obtained that the required 1-a coverage is achieved in both settings, and the set sizes are summarized in Table D.12 As expected jackknife+ obtains smaller set sizes. However, the improvement appears to be insignificant this case and may not justify the additional computational cost.
29

---

Published as a conference paper at ICLR 2025
Table D.12: Comparison between Jackknife+ and Multi-score methods on CIFARI00 and 7 heads.
Method
Score
Multi-score Jackknife+
Multi-score
RAPS
14.85
15.32
0.1
SAPS
14.61
15.46
RAPS SAPS
2.26
2.33
0.2
2.22
2.36
Table D.13: Comparison of soft centers approach with different number of neighbors b on CIFAR100 and heads.
Method
Score
b= 200
b 100
b b= 50
10
Multi-score 1)
RAPS
23.68
22.73
19.32
16.48
15.32
0.1
SAPS
23.53
22.44
19.12
17.14
15.46
RAPS
3.01
2.89
2.75
2.26
2.33
0.2
SAPS
3.04
2.87
2.81
2.29
2.36
Soft Multi-score conformal prediction. We evaluate the soft version of our proposed approach. The set sizes obtained for different number neighbors are summarized Table D.13 We observe that in almost all cases 6 1 (Algorithm T is preferable.
30


Reviews:
[{"review_id": "AhzROnSprf", "reviewer": "Reviewer_4GpN", "summary": "This paper studies a multi-dimensional non-conformity approach to conformal prediction. They introduce a novel method to identify high probability regions with low low false-to-true labels ratio, which requires to carefully design a calibration procedure with multiple stages, including partitioning the space, ranking different partitions, and selecting the high quality partitions.", "questions": "I have no further questions. Might ask more once I see the authors response.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper is very well-written and has a very clear flow. The multi-dimensional CP looks like a promising avenue of research. They provide a novel perspective of finding conformalized regions by ranking the false-to-true ratio and they also show sufficient experimental results to back up their claim about improving efficiency.", "weaknesses": "I believe this is a very good paper. Although I do have some suggestions to further improve both the theoretical and algorithmic perspectives.\n\n- You break the dataset in two parts and then use the second part as a recalibration to ensure coverage. A natural way to improve the efficiency of your method and use all the data together is to use a leave-one-out method. At each time, you can use all the data but one (say X_i, Y_i), go through the partitioning and ranking and then find the smallest threshold (rank) such that the selected regions include the left-out sample (X_i, Y_i). Lets call that threshold (rank) tau_i. Then you can take (1-\\alpha))-quantile of the ranks and use that as the final threshold (rank) to make the regions. There are some subtleties to make this work, you might want to look at https://arxiv.org/abs/1905.02928 for more details. \n\n- For the case of scalar scores there are some theoretical underpinnings that shows the optimal (think of it as the tightest possible) prediction sets are of the form of level-sets of a scalar function. (i.e., thresholding a scalar score) These results are considered classic in CP (look at https://www.stat.cmu.edu/~jinglei/LeiW14.pdf) and they have been also recently generalized to the more advanced case of CP with conditional coverage requirements (look at https://arxiv.org/pdf/2406.18814). These results and their insights also heavily contributed in the line of research around designing better scores. Therefore, I believe it is important to discuss whether a multi-dimensional score design has any fundamental theoretical underpinnings or not. For instance, it would be nice to think of a scenario where (in the population regime) the optimal prediction sets are actually characterized by a multi-dimensional score. Or maybe trying to show that in a (perhaps simplified) scenario the multi-dimensional perspective is provably a better approximation of the optimal prediction sets. These kind of results and discussions are more than just an effort for having some theory in the paper, but rather can bring useful insights for follow-up works in this line of research.\n\nI am willing to increase my score in case of a satisfactory response.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jKL5PVlBvk", "reviewer": "Reviewer_3FMy", "summary": "This paper proposes an extension to conformal prediction for classification tasks. Standard conformal prediction constructs prediction sets with guaranteed coverage by thresholding a nonconformity score, which measures the disagreement between the model and the ground truth class label. This work has two main contributions: (a) a variant of conformal prediction that is compatible with multidimensional nonconformity scores, and (b) a self-ensembling method for producing these multidimensional nonconformity scores using diverse classification heads. The proposed method partitions the multidimensional space and then selects a set of cells to include in prediction sets by thresholding the cells based on the relative frequency of false labels. The proposed approach is shown experimentally to lead to smaller prediction sets.", "questions": "- Please see the first point under the weaknesses section about. How would the proposed approach compare to a vanilla RAPS/SAPS baseline with one classification head (i.e. before the six additional heads are attached)?\n- In Figure 4, the nonconformity scores appear to be distributed in a pattern resembling a square. Would an L1 norm perform better than an L2 norm in this case?\n- What is the effect on the algorithm as the dimensionality increases? Is there a curse of dimensionality effect here?\n- In Algorithm 1 (line 6), when do the duplicate cells occur?\n\nMinor comments:\n- The cells in Figure 1 are difficult to understand.\n- Figures 2 and 3 are small and therefore hard to read.\n- Since Section 3.1 discusses background work, it should probably be moved out of Section 3, which is title \"Proposed Method\".", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths of the paper include the following:\n- The main claims are supported with evidence. Theoretical justification for the proposed procedure is provided in Appendix A.1. Smaller prediction set sizes are also demonstrated in Figure 2 and Figure 3. However, see weaknesses below regarding multiple classification heads.\n- There is a good amount of exploration performed, even beyond what is reported in the main paper. For example, results on standard ensembling, test-time augmentations, and size of $\\mathcal{D}_\\text{cells}$ are all useful.\n- The paper is well-written. I thought the related work section in particular explored a good amount of relevant literature.", "weaknesses": "Weaknesses of the paper include the following:\n- The empirical evidence provided in the paper is overall good, but the role of the multiple classification heads is still unclear. The best head baseline uses a network trained with multiple heads. How would the proposed approach compare to a vanilla conformal prediction baseline trained with a single head (i.e. the network prior to attaching the six additional classification heads)?\n- The contribution of the paper is fairly solid in terms of theoretical and empirical justification. However, from a practical perspective, it seems more likely that rather than investing time into using multidimensional nonconformity scores, a practitioner would likely simply focus on improving the underlying model generating the nonconformity scores. The cases in which the multidimensional approach succeed are those where the model is suboptimal, and fixing the model will remove the need to use multidimensional scores. This limits the significance of the proposed work.\n- The benefits of the proposed approach are empirical in nature. There does not seem to be a way to know beforehand whether multidimensional nonconformity scores will help or not. In some sense, this is a modeling question that depends on the distribution of nonconformity scores in the multidimensional space. There will be some datasets where the modeling assumptions proposed here (analogous to a KNN variant with $K=1$) will be beneficial, and others where it will not be.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2QGRcpSLE8", "reviewer": "Reviewer_52ya", "summary": "In this paper, the authors aim to improve the efficiency of conformal prediction sets with multiple non-conformity scores. In particular, they propose a multidimensional framework of conformal predictions, which uses a single score in one of the dimensions. They provide a theory to show the desired coverage can be guaranteed through the multidimensional selection. To obtain multiple diverse nonconformity scores, they employ a multi-head model and train it with a diversity regularization. The proposed method is validated on a CIFAR100, Tiny ImageNet, and PathMNIST to show the effectiveness.", "questions": "In figure 2, are all the compared methods employed on the multi-head model trained by the loss in Equation (11)?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 1, "presentation": 4, "contribution": 2, "strengths": "1. The method is novel. To the best of my knowledge, this is the first work to utilize ensemble predictions as multidimensional score.\n2. The empirical improvement is significant. The proposed method can produce smaller prediction sets compared to other baselines.", "weaknesses": "Major:\n1. Why the multi-score conformal calibration can work better is not explained. The authors only provide a theorem to ensure the valid coverage of the proposed method, but do not elaborate about how it leads to efficient prediction sets. It could be better if they can provide convincing explanation in this aspect.\n\n2, The multi-score setting seems different from previous works. Previous multi-score works aim to utilize multiple score functions to obtain better performance, but this work proposes the method to generate multiple scores with ensemble models. In my view, this problem should be CP for ensemble models instead of the multi-score setting. So it might be better for authors to rewrite the motivation (subsection 3.2) for avoiding misunderstanding. (Or the authors can show the method can also improve the setting of multiple score functions.)\n\n3. The empirical comparison is not extensive. The authors should include ImageNet in the experiments, or it is hard to evaluate the effectiveness of the proposed method in large number of classes. \n\nMinor:\n1. presentation: it is hard to read the information from Figures 2 and 3. Maybe the authors can simply provide tables to show the results.\n2. It might be better to put some results in Appendix B in the main part, as there is almost one page left as blank.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lVN5eMyUnJ", "reviewer": "Reviewer_UGXT", "summary": "This paper tends to combine several different conformity score functions aiming to reduce the prediction set size. In short their approach is to combine different score functions per $(x, y)$ forming a vector of scores. Dividing the calibration set into two separate sets of re-cal and tuning set, they use the tuning set as the basis (centroids) in the mutli-dimensional scores space. They assign a rating to each of these centriods based on the proportion of false labels inside that area (this means 1 + set size if there is only one point at the place). During calibration they deactivate regions in decreasing order to the number of false predictions, as long as the $1 - \\alpha$ coverage is satisfied. Each calibration point is assigned to the closest centriod. Similarly during test. they check the closest centiod and add the label to the prediction set if the centriod is active.\n\nThe propose different methods to build multi-dimensional score including using different classification heads, to simply using different score functions.", "questions": "Please see Weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is simple yet effective. The paper is also easy to read and “to the point”. I do not see any major flaw or discouraging point in it. I also see that the authors tried to include a comprehensive evaluation by comparing with best head, uniform average and optimized weights.", "weaknesses": "1. Why the authors did not report worst slice coverage which is metric of adaptivity? \n2. Why the authors used an unnecessarily large calibration set? I don’t think the evaluation setup is realistic with 16500 calibration points to predict 11000 test points. What is the gain of this large calibration set? Is there any statistical efficiency results that are missing?\n3. Related to the previous problem, a fair comparison is to report paper’s best method in comparison with the normal best method where the tuning set is also added to the calibration set. The results are not expected to be significantly different but still this is important to be reported.\n4. Why the authors did not report their result with APS and threshold prediction sets? Although there are adaptivity and efficiency constraints, still those result are important to be reported. RAPS and SAPS are ignoring informations in the logit space either by penalty, or just reporting the rank, and intuitively in a perfect classifier this should cause inefficiencies.\n5. Is there any preference to have 0-1 assignment to the zones?, the author could also try soft probability assignment to each region and optimize for that. It is not a must, but either trying soft centroid assignment, or showing that the optimal is happening with the current 0-1 assignment would make the work stronger.\n\nI would increase my score if a convincing answer to these two questions is provided.\n\n1. Why the calibration set is very large in all experiments. Are there any limitations? What would the result be with smaller calibration set (e.g. 2000 points)\n2. Why threshold prediction sets (softmax score) and adaptive prediction sets are not evaluated. The authors could have similar results with these score functions as well.\n3. An ablation study on the number of centroids is important. How the results would change with very limited number of centriod (e.g. 200)?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oZF0ewimsi", "reviewer": "Reviewer_9Lus", "summary": "The paper introduces a multi-dimensional conformal prediction method for classification problems. A nonconformity measure is defined depending on the multiple scores, which leads to finer separation between correct and wrong labels. The proposed procedure mainly includes three steps: first, partitioning the score space into cells using $D_{cells}$; second, scoring and ranking the cells according to the ratio of false to true labels; and third, calibration-achieved by progressively adding top-ranked cells until the desired coverage level is reached.", "questions": "How sensitive is the method to hyperparameter choices, such as the number of classification heads or diversity regularization? And how do different configurations affect set size?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized. The problematic and approach are well introduced, and the concept concisely presented. The proposed method successfully extends conformal prediction into a multi-dimensional setting with enhanced separation between correct and incorrect labels, and it appears sufficiently general.", "weaknesses": "1. The experiments mainly focus on image classification datasets (e.g., CIFAR100, Tiny ImageNet, PathMNIST), limiting the demonstration of the other data types, such as text or tabular data.\n\n2. While the paper is claimed to be cost-efficient, it still involves training and managing multiple classification heads, which could be computationally expensive for large-scale datasets or resource-constrained environments. Could you provide more insights into the computational cost? Specifically, how does it compare to other baseline methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)