Improving the Statistical Efficiency of Cross-Conformal Prediction
Authors: Matteo Gasparin
Aaditya Ramdas
Venue: ICML 2025 poster (2025)
Keywords: Conformal Prediction
Exchangeability
Randomization
Primary area: probabilistic_methods

Abstract: Vovk (2015) introduced cross-conformal prediction, a modification of split conformal designed to improve the width of prediction sets. The method, when trained with a miscoverage rate equal to $\alpha$  and $n \gg K$, ensures a marginal coverage of at least $1 - 2\alpha - 2(1-\alpha)(K-1)/(n+K)$, where $n$ is the number of observations and $K$ denotes the number of folds. A simple modification of the method achieves coverage of at least $1-2\alpha$. In this work, we propose new variants of both methods that yield smaller prediction sets without compromising the latter theoretical guarantees. The proposed methods are based on recent results deriving more statistically efficient combination of p-values that leverage exchangeability and randomization. Simulations confirm the theoretical findings and bring out some important tradeoffs.

Improving the Statistical Efficiency of Cross-Conformal Prediction
Matteo Gasparin'
Aaditya Ramdas 2
Abstract
requires one to train the model for every possible value of the response, and this procedure is usually computationally burdensome. To alleviate this problem, split conformal pre- diction (Papadopoulos et al., 2002; Lei et al., 2018) has been proposed as a solution. The procedure involves a random partition of the data into two subsets: the first subset is used to train the prediction algorithm, while the remaining part used to calibrate the predictions and obtain the prediction interval. Although this variant proves to be computationally efficient, it suffers from reduced efficiency in terms of the width of the resulting prediction set; this is due to the fact that only a fraction of the data is used to train the model.
Vovk (2015) introduced cross-conformal predic- tion, a modification of split conformal designed improve the width of prediction sets. The method, when trained with a miscoverage rate equal to a and n. >> K, ensures marginal coverage of at least 1 - 2a - 2(1 - a)(K - 1)/(n + K), where n is the number of observations and K denotes the number of folds. A simple modification of the method achieves coverage of at least 1 2o.. In this work, propose new variants of both methods that yield smaller prediction sets without compromising the latter theoretical guarantees. The proposed methods are based on recent results deriving more statistically efficient combination of p paluue that leverage exchangeability and ran- domization. Simulations confirm the theoretical findings and bring out some important tradeoffs.
Several "hybrid" solutions have been proposed in the liter- ature, which can be considered between split conformal prediction and full conformal prediction. Examples in- clude cross-conformal prediction (Vovk, 2015; Vovk et al., 2018) 8), multi-split conformal prediction (Solari & Djord- jilović, 2022), the jackknife+ (Barber et al., 2021) and out- of-bag conformal prediction (Linusson et al., 2020; Gupta et al., 2022). These techniques generally result in smaller prediction intervals compared to split conformal prediction and involve less computational effort than full conformal prediction. However, one of the main drawbacks of these methods is the reduced marginal coverage guarantee, which is less than the usual 1 - level.
1. Introduction
Conformal prediction has emerged as a general and versatile framework for constructing prediction sets in regression and classification tasks (Shafer & Vovk, 2008). Unlike tradi- tional methods, which often depend on rigid distributional assumptions, conformal prediction transforms point pre- dictions from any prediction (or black-box) algorithm into prediction sets that guarantee valid fiiie-ssaple marginal coverage. Originally introduced by Saunders et al. (1999), it has become increasingly influential, with numerous methods and extensions being proposed since its introduction.
In this work, we focus the attention on cross- cross-conformal prediction and we prove that the method can be improved without altering the coverage guarantee. In other words, we are able obtain smaller prediction sets while ensuring the same (worst-case) miscoverage rate. Starting from modification of the method (Vovk et al., 2018; Barber et al., 2021), the new results are obtained using recent findings on the combination of dependent p-values derived in Gasparin et al. (2025). Importantly, these results are obtained in a fully general manner, and do not need any specific prediction model or ensemble method to be used.
In particular, full conformal prediction by Vovk al. (2005), demonstrates favorable properties regarding the coverage and the size of the prediction set. However, these advantages are counterbalanced by substantial computational cost, which limits its practical application. In fact, the method
The structure of the paper is as follows. In Section 2 we illustrate the problem setup and related work. In Section 3 cross-cofformal prediction is described while the new meth- ods and results are presented in Section 4. Section 5 presents some empirical results. In particular, Section 5.1 contains some simulation results, while an application a real-world dataset is presented in Section 5.2.
'Department of Statistical Sciences, University of Padova, Padua, Italy Department of Statisties and Data Science, Camegie Mellon University, Pittsburgh, PA, USA. Correspondence Mat- teo Gasparin <mtttoo, smaateo.gaspparn. I @ und.uiiid..ts..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
2. Problem Setup and Related Work
et al. (2019), Prinster et al. (2022), Barber et al. (2023) and Stutz et al. (2023). Our work is based on the cross- conformal prediction method introduced in Vovk (2015) and later extended in Vovk et al. (2018). We refer to Fontana et al. (2023) and Angelopoulos & Bates (2023) for an overview of conformal prediction and its extensions.
Assume we have independent and identically distributed (iid) training samples Z; = (X,, Y.) E X V, i = ,,...,7, n,, drawn from a probability distribution Q, where X' represents the feature space and y' the response space. Using these training data, our goal is to obtain prediction set for the response variable 11+1 based on the covariates Xn+1, under the assumption that the test pair (X++1, Yn-1) is independently sampled from the same distribution Q. In what follows, the results will be shown to hold more gener- ally under the assumptions of exchangeability of the n + data points with the iid assumption as special case. A typical scenario involves applying prediction algorithm to the training data in order to find a prediction for the response value. In particular, let j : X' + y" be regression function obtained by applying an algorithm A to the training points, where y" is the prediction space (in regression problems we usually have X' Rp and y y" RR. Formally, A is mapping from 1d21 (X x ))dd (the set of all possible training datasets of any size d 2 1). to the space of func- tions X' + y" Starting from the regression function f., we aim to construct a prediction set ((X++1) that contains the point - with high probability. Since no assumptions are made about the distribution Q, the method is said to be distribution-free
The solutions proposed here are based on recent results on the combination of p-values that exploit exchangeability and randomization (Gasparin et al., 2025). The combination of p-values is not new in the statistical literature and dates back at least to Fisher (1948). Fisher's 's method is based on the assumption of independence among the p-values, an assumption frequently violated in practical applications. Other works propose combination rules valid for arbitrar- ily dependent p-values; some examples are Rüger (1978), Morgenstern (1980), Rüschendorf (1982), Vovk & Wang (2020), and more recently Vovk et al. (2022b). Clearly, these rules valid under arbitrary dependence come with price in terms of statistical power. In other words, these methods for combining p-values are usually conservative since they have to protect against the worst-case scenario of dependence. The results in Gasparin et al. (2025) are able improve these rules valid under arbitrary dependence exploiting the exchangeability of the starting p p-values and/or randomiza- tion. Their results are derived using extensions of Markov's s inequality introduced in Ramdas & Manole (2025).
Before proceeding with the remainder of the paper, we define the score function s = s((x, ;); D), which quantifies the non-conformity of a point in the sample space with respect to the dataset D E (X' x 2 used to train the prediction model. In particular, we assume that the score function 8 adheres to a symmetry property:
In the framework of conformal prediction, the combination (or ensembling) of p-values is used in Carlsson et al. (2014), Toccaceli & Gammerman (2017) and Linusson et al. (2017). Their empirical results indicate that Fisher's method is not valid rule for combining p-values obtained from differ- ent splits or algorithms, whereas using rules valid under arbitrary dependence tends to be generally conservative. In particular, Linusson et al. (2017) provides some intuitions suggesting that the empirical coverage of cross-conformal prediction depends on the degree of dependence between the conformal p-values (that it is strictly related to the stability of the underlying prediction algorithm). In a similar spirit, the solutions in Cherubin (2019) and Solari & Djordjilović (2022) aim to combine dependent conformal prediction sets (rather than p- p-values) derived from different random splits or prediction algorithms. In particular, their approach relies on majority vote strategy. Gasparin & Ramdas (2024) further extended their approach by introducing a weighting system and incorporating randomization. Other works aim to select or combine conformal prediction sets; see for example Yang & Kuchibhotla (2024) and Liang et al. (2024).
s ((z, D): = s(x,, ((..)) D*),
(1)
where i is any permutation of the indices [d] := (L...., d} and DtdT refer to the dataset whose elements are permuted by o.. For example, when considering residual scores ly [x(x)] in regression problem, the symmetry of the score function is satisfied if the prediction algorithm is symmetric, which means that A(D) = A(D)). In addition, we denote the dataset containing the observations the set as D,
(Z,+ : i I).
2.1. Related Work
As outlined in the Introduction, conformal prediction was first introduced and formalized by Saunders et al. (1999) and Vovk al. (2005). Several influential contributions to the framework include the works of Lei et al. (2018), Romano et al. (2019), and Barber et al. (2021). Extensions and generalizations of the methods have been proposed by Kim et al. (2020) and Gupta et al. (2022), among others. Other works extend conformal prediction to settings where the standard assumptions may not hold, such as Tibshirani
3. (Modified) Cooss-Conformal Prediction
This section will recap two methods: cross-conformal pre- diction, and modified cross-conformal prediction. We let K denote the number of folds, and we focus on the (prac-
2

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
tical) case when K is small like K or K 10. We will always assume that m n/ K" is an integer, which is achievable by only throwing away less than K points from the original dataset. However, we point out in Appendix C that both methods have guarantees without this assumption (which is new to the best of our knowledge, though minor).
(3) with the cross-conformal p-values in (5). In particular, point y is included in Caross (aak,a((x++) (Xn+1) if and only if
K
--1 +
K P
(6)
The multiplicative factor of two in the coverage statement in (4) arises from the fact that the average of arbitrarily dependent p-values remains p-value up to factor of 2
3.1. Gross-Conformal Prediction
Cross-conformal prediction, introduced by Vovk (2015), is a method to obtain distribution- free prediction intervals. can be considered as a combination of split conformal prediction (see Appendix A) and volss-vali,,,on. works as follows: data are divided into K disjoint subsets (or folds) .i...., I of size n K. The are defined as:
(Rüschendorf, 1982; Vovk & Wang, 2020):
K Pa(Ktt))
1 K
IP
5a S 2a.
scores
This implies that the statement in (4) can be proved by com- bining the results in (6) and (7). For a detailed discussion on cross-conformal prediction see, for example, Chapter 4.4 of Vovk et al. (2022a).
SPV =8 ((X,, (xx, (():
i=
n,
Remark 3.1. The coverage statement in (4) is meaningless when K is large. In fact, Barber et al. (2021) proves a different bound for the miscoverage rate valid for large K. However, in practical applications, the number of splits is usually small if compared with the number of observations (e.g., K = 5 or K = 10) and the bound in (4) is the one that applies. We discuss the two different bounds and the connection with the CV+ method by Barber et al. (2021) in Appendix B.
where Tx()) is the subset containing the i-th data point. The cross-conformal prediction set is simply defined as
Coroes Kn (Xu+1) = VEV:
1+ EE 1 1ss
(Xx+1.)): D Pin]Vacc)
S SCV]
a
n +41
Remark 3.2. In a regression setting, there are no guarantees that Eeross (Xn+1) will be interval; in fact, there particular cases where it can be union of intervals. This property is shared by other "hybrid" methods mentioned in Section 1. One can avoid having a union of intervals by taking the convex hull of the set (the interval formed by the furthest endpoints) as explained in Gupta et al. (2022). In addition, when the residual score is chosen as score function, the prediction set Éyross (X.+ is subset of the CV+ set that is guaranteed to be an interval (see Appendix B).
Vovk et al. (2018) proves that the interval in (3) is such that
p Yut E Cicross
n,K,a (Xxt1)
(4)
1/K 2 1- 2a 2(11 aa) n/K +1'
where the probability is marginal and is computed with respect to (X,, Y,). (X.+1. Y.+1). In particular, when K is small compared to n (that is, >> K), the additional term is negligible and the coverage is essentially at least 1 2a. To prove the result in (4), it is useful to define for each subset, & E [K], the quantity
3.2. Modified Cross-Conformal Prediction
It is clear from the previous section that we can obtain set with coverage at least equal to 1 - 2a using modification of the cross-conformal prediction set defined in (3). We define the modified cross-conformal prediction interval (the same name is used in Barber et al. (2021)) as
Pv(v)= = 1+ Eien 1l (s ((X=+1 v); D (n))))) S SPCV
m
K
Cm (Xa+1) y E y
Σ
Pa(x) > a
K
that is discrete p-value if computed using the response
k=1
(8)
test value Yx+1 and if data (X,, Yz), In + 1], are iid or at least exchangeable (i.e., (( < a) < a).
Using the result stated in (7), we have
This is due to the fact that the scores in 4 U In +1++1 1} are exchangeabl,, since the prediction algorithm is trained only
P (Ynt1 E Emod-crross K,K.a
(o (Xn+1) 2 20.
on the training points in [n] \ Lt. so (5) can be seen as a rank-based p-value. is possible to relate the set defined in
The intervals defined in (3) and (8) usually have inflated coverage. In other words, with typically employed levels
3

---

the sample Improving the Statistical Efficiency of Cross-Conformal Prediction
of a, the coverage obtained using these methods often flue- tuates between the levels 1 a and 1. This is due to the fact that the rule in (7) is valid under arbitrary dependence and it has to take into account the "worst-case" scenario of dependence, which typically differs from the scenario observed in the data. However, in some situations where the regression algorithm is unstable or with some particular distribution Q. the coverage can oscillate between the guar- anteed level 1 2a and 1 a. Linusson et al. (2017) offers some empirical observations regarding the miscalibration of the average of p-values obtained from different folds. In particular, since the p-values are dependent, the distribution of the averaged p-values is in between the Bates distribution and the uniform distribution, and this strictly depends on the stability of the underlying algorithm.
(cross-conformal) p-values obtained using data Z, (X,, Yi), i [n- [n+ + 1), then P1 P2(Yn+1);- ............ (Yn+1) are exchangeable, meaning that P. _ P", where = represents equality in distribution, P = (Pi(Yx+)):.... ...,, Px (nn+))), pr = (Ynn))(r+t))....... (((k)((nz))) (Yn+1)) and π [K] + [K] is any permutation of the indices.
A formal proof of the result is based on the following lemma and is provided in Appendix F.
Lemma 4.2 (Dean & Verducci (1990); Kuchibhotla (2020)).
Suppose W (Wi...., W,) E W is a vector of ex- changeable random variables. Fix transformation G WM + (W"))" for each permutation there exists a permutation T2.
: [m] - [m] [Tx] - [n] such that
TT G/G(w) = G(Tzw), for all w W",
Since p-values take discrete values, in order to avoid having noninformative sets identical to Y³ the inequality 1 < a(m+ 1) must hold. A slightly improvement can be obtained using randomized p-values Pi (Yn+1;T)..... Px (Yn+157) defined by
then G(-) preserves exchangeability.
Remark 4.3. The assumption that n/K = is crucial to prove the result in Proposition 4.1. In fact, if the subsets 11...., 1k have different sample sizes, then the result in Proposition 4.1 does not hold. Notice that the p-values in (5) take discrete values (1/m, 2/m,.... 1}. sizes differ, then the p-values assume values in different grids of values, and therefore the marginal distributions of Pi (Y ..... Px (Yn+1) are different. This implies that p-values cannot be exchangeable. In addition, with different sample sizes the proof of the result breaks down and a permutation т2 that satisfies the condition in Lemma 4.2 does not exist. In Appendix C, we will see how to extend the result to the case where the folds have different sizes using simple trick.
P&(y:T)= =
T+ Eien 71l {s ((xn+1.0) ()): (mnl)e)) S.V]
m
Eier 1 ((Xnt.,)));
(() < <
m m+1
(9)
where T is a uniform random variable in the interval (0, 1) drawn independently from the data. In this case, the p- values (for y 11+ are uniformly distributed in the interval (0, 1), rather than taking discrete values. However, the dependence among the p-values obtained from different folds is not broken.
An improved version of the set in (8) can be defined as:
Ge-mod-eross (Xx+1))) = { O,KKa
y::: min EE[K]
Pk(U) a
4. New Variants of Cross Coofs-Conformal Prediction
(10)
In this section, we improve the prediction set in (8) using recent results regarding the combination of p-values. In particular, the combination rules that will be used are more powerful than the combinations valid under arbitrary de- pendence of the p-values. The results are obtained in a completely general manner and do not require the use of expensive computational procedures (Carlsson et al., 2014) or the use of specific models (Boström et al., 2017).
where, for given y. the combination of the different Px is asymmetric and depends on the order of the p- p-values.
Theorem 4.4. It holds that Õo-mod-eross (Xn+1) S n, Emed (x In addition, if data are exchangaable,
P (Yn+1 E -re-uod--roo cross (Xn+1)) 2 21 21-20 2a.
(11)
The proof of this and subsequent results provided in Ap- pendix F.
4.1. Exchangeable Modified Cross-Conformal Prediction
The theorem indicates that one can derive a set smaller than the modified cross-conformal prediction set while maintain- ing the same coverage guarantee. The same results hold if the valuee in (9) are used. Specifically, the randomized p- values are still exchangeable if common across the folds.
The interval in (8) can be improved using recent results on the combination of exchangeable p-values. Before proceed- ing, we state a useful result.
Proposition 4.1. Let Pi (F Pk (Yu+1) be the
4

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Indeed, conditional on the p-values are exchangeable due to Proposition 4.1. In particular, using the p-values in (9) we obtain a smaller set since ()) I Pa (y) almost surely.
Čmodd-eross (X++1), In addition, if data are exchangeable, K,K
TP (Y E Cn K,K,ax (X (Xn+1) 2 - 22..
(13)
Remark 4.5, Once K exchangeable (or more generally de- pendent) p-values are obtained, there are several methods to combine them. The proposed solution is to use the mini- mum (over ?) of the mean obtained using the first I p-values, which is related to the valid combination rule "twice the aver- age" used by Vovk et al. (2018: 2022a) to prove the coverage guarantee of cross-conformal prediction. However, similar results apply to other merging functions like quantiles (for example "twice the median" is also valid combination rule) and generalized averages (e.g., geometric mean har- monic mean). However, it is important to emphasize that, as explained in Section 6 of Vovk & Wang (2020), the mean is an effective method of combining strongly dependent p-values, which is often the case for rank-based p-values ob- tained by coos-connoomal prediction. Other merging rules, such the Bonferroni method, are more appropriate near independence. For instance, Lei et al. (2018, Section 2.3) shows, under some assumptions, that the Bonferroni rule is overly conservative in the context of multisplit conformal prediction.
Even in this case, the guaranteed marginal coverage remains at least 1 - 2a, but the set size is enhanced using a simple result based on randomization.
4.3. Exchangeable and Randomized Modified Cross-Conformal Prediction
The results in Section 4.1 and in Section 4.2 can be "com- bined" in order obtain a prediction set that improves the one defined in (10). In this case as well, the exchangeability property outlined in Proposition 4.1 is crucial.
We define randomized improvement of the conformal prediction set defined in (10):
Óeu-mod-croes (Xn+1) K,
Y ::V:
(14)
{
min 2 P1()), min Epau >
1 &
EE[K] Rm
4.2. Randomized Modified Cross-Conformal Prediction
where U is uniform random variable in the interval (0, 1) independent of all the data.
In the previous paragraph, we leveraged the exchangeability of p-values to obtain a smaller set. In this section, we move in different direction and improve the set (8) using a sim- ple "randomization trick" (introducing a uniform random variable). Indeed, in this case, the exchangeability of the p-values is not necessary. As before, the improvement does not alter the marginal validity of the set, but the new result is obtained in a different way. Although randomization is avoided in some statistical applications due to the extra ran- domness introduces, in this case, it does not pose a major issue. Indeed, cross-conformal prediction is. by definition, randomized method. More precisely, data are randomly divided into K different subsets in the first step, which means that the procedure inherently includes randomness (see Remark 4.8 for further discussion).
Theorem 4.7. It holds that Own mndd (Xn+1) S
Go (X.+1) S. Cn Xnt1). In addition, if data are exchangeable,
K,K,a
P PYn+1 E K,K,a
Grn-mond-cross (Xn+1) 21-22 2a.
(15)
The set in (14) can be considered an improvement of the set described in (10) but not of the (randomized) set in (12), since only the first p-value of the sequence is randomized. Remark 4.8 (Randomization and "interval sicervallhacking),. A direct use of external randomization is present in both pro- cedures described in Section 4.2 and Section 4.3. The use of randomization is often avoided in statistical methods, it can pose challenges to the reproducibility of results. Clearly, randomization becomes problematic when a human is in the loop and runs the procedure multiple times until the desired result is achieved (for example, in the described cases, one can sample U many times until it reaches a value close to zero). Some recommendations aimed at solving this prob- lem are proposed, for example, in Ramdas & Manole (2025, Section 10). Actually, in the data pipeline of split and cross- conformal prediction methods, randomization comes into play in different parts: by default in the division of data into their respective folds; to smoothen p-values as described in (9); and potentially to improve the conditional cover- age as described in Hore Barber (2024). In particular,
We can define a "randomized" improvement of the interval in (8) as follows:
Ou mnd cross K.K.a
(Xn+1)= =
1 K Pa(v)
> )
(12)
VEY: 2 U
K
where U is a uniform random variable in the interval 10 independent of all the data.
Theorem 4.6. It holds that
Cu-mod-ccross (Xn+1)
K.K.a
C
5

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
there exists a trade-off between reproducibility and statis- tical efficiency, and it is not always evident which should be prioritized. In other words, randomized procedures tend to be more efficient than standard procedures but may lack in terms of reproducibility, and vice versa. For instance, our methods may be particularly well-suited in industrial settings, where hundreds or thousands of predictions are made daily, and efficiency may be more important.
as:
8 ((z, y): = by - An(x),,
(16)
where AD is the regression function obtained by applying the regression algorithm A on D.
The code to reproduce the experiments is available at gittob..coocmaattoggggg//CCCoo.t
5.1. Simulation Study
4.4. Improving Conso-oofo Prediction
We examine the performance of the proposed methods on simulated data using least squares as our regression algo- rithm. Data simulated as in Barber et al. (2021, Section 6) in particular, the number of observations is n 100 and we let the number of regressors vary p {5, 10, 200 The training data points are iid from
The improvements proposed in the previous subsections are valid for modified cross-conformal prediction; particular, the new variants are able to produce smaller prediction sets while preserving the same marginal coverage. Specifically, the marginal coverage does not depend on the number of folds K and the number of observations n. When the folds have the same size, the techniques can be used to enhance cross-conformal prediction ( (Vovk, 2015); in particular, by examining (6), one can observe that it is possible to improve cross-conformal prediction simply by replacing the thresh- old with (1 (K - 1)/(K + n)) in the prediction sets defined in (10), (12), and (14).
X, Ip) and Y, X N(X 3.1),
where the vector of coefficients is drawn as B == TO v for a uniform random unit vector o IRP. Ordinary least squares is employed regression method (if the linear system is underdetermined, then we take the solution that minimizes the 2n-nom)). Formally, given the training data Y,), i [n], we estimate the regression function pizx) = B, where 3 = -Xinat Yvee is the response vector, Xmma is the matrix of covariates of dimension n p and denotes the Moore-Penrose inverse. The nominal miscoverage rate equals a 0.1, the number of replications (for each p) is 1000 and for each replication, we generate a single test point (X,-1. 1 The number of folds for cross-conformal prediction and its extensions is K = 5.
Theorem 4.9. It holds that
Comoddccross C K, Cn-mod--roos C K,K
Ccroos n, K
K,
Öeuypad-cccss On,Kaa
C n,K,a'
(e-mod-cross C
Ccroos
K,K,av
where a' = aa a1+(1- al)a)((K -))(K)) + n). If data are
exchangeable, the marginal coverage of the conformal pre- diction sets Ön-modreross (Xn+1). Cu-mod-crosa K,K.a
'.K (orooos((nn (Xn+1) and
From Figure/ 1, we can see spike in the size observed at p 80. This is due to the fact that the prediction algorithm is unstable when the number of training points is equal (or almost equal) to the number of covariates (Hastie et al., 2022). Since the number of folds equals 5, the peak is observed at p = 80.
Crungod-erooss (Xx+1) (i-))a is at least - 2n'. n,K.a"
In practice, when n Creoes (Xx+1) and Cuppherrse (Xm+1) are similar. How- ever, for moderate values of n, we will see that the sets defined in (10), (12), and (14) are typically narrower than Ceross "..K..X (Xx+1), even though Õeross K,K (Xa+1) assures theo- retically lower coverage guarantee. Clearly, the proposed improvements are valid as long the marginal coverage level 1 1a2a' is meaningful, which in practical applications is the most common case. It follows that the improvements are not valid, for example, in the extreme case of leave-one-out conformal prediction (the case K- = n).
K. the prediction sets
The smaller size often observed by the exchangeable and randomized variant of cross-conformal prediction. Cross-conformal prediction (Vovk, 2015), is usually over- conservative, and in some cases, its coverage is closer to one rather than to the guaranteed level. This behav- ior is not shared by the proposed e-mod-cross and eu-mod-cross. The coverage of these methods lies be- tween the levels 1 - 2a and - a, and remains essentially constant with respect to the number of covariates p. The cov- erage of the randomized variant u-mod-cross depends p and exhibits behavior similar to that of standard cross- conformal prediction. In general, our proposals outperform standard cross-conformal prediction in terms of set size.
An experiment using the threshold a' is reported in Ap- pendix E.
5. Empirical Results
We study the effectiveness of the proposed methods through a simulation study and real data examples. In all experi- ments, the score function used is the residual score, defined
For additional comparisons, we evaluate our proposed eu-mod-cros: method with split conformal prediction
6

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Averaged prediction set size
(coomnd in)
Empliiaa coverage
Aversged prediction size
(coomed in)
Emprical
14
Coverage
200
200
wwww
Cr0Ss 9-Htod-oo CrOSs
au-medd-cross mod-crosa u-mod-oross
au-nod-croaa modicroos 2plt spll((2))
Figure I. Simulation results, showing the size and coverage of the predictive sets for cross-conformal prediction and its vari- ants. In the left plot, peaks are observed at 404, 102, 286, 100 and 307 for mod-cross, e-mod-cross, u-mod-cross, eu-mod-cross and cross, respectively. The parameter is set to 0.1. The smaller sets are often obtained using eu-mod- cross that has coverage hetween 1 2a and a. The randomized method cross-conformal prediction.
Figure 2. Simulation results, showing the size and coverage of the predictive intervals obtained using 4 methods. The parameter a set to 0.1. Split conformal prediction is trained at levels and 2a and it is compared with mod-cross and eu-mod-cre cross. The modified cross-conformal prediction method always overcovers and tends to produce large prediction sets. Its exchangeable and randomized variant gives good results in terms of size. When E [25, 60), the average size of the eu eu-mod- crosssss method is smaller than that of the split conformal prediction method trained at level 2o.
performs similarly to
trained at levels a and 2a. In particular, we note that the marginal coverage of the exchangeable and randomized variant is at least - 2a. From Figure 2, we can observe that for some values of p E [25, 60), when the prediction algorithm is not stable for the split conformal prediction method, the average length of the eu-mod cross sets is smaller than that of split conformal prediction trained at level 2a. Described differently, both techniques ensure the same coverage level. However, there is no single method that performs best for all values of p. When p is sufficiently small compared to and the algorithm is stable, split con- formal prediction trained at level a performs well, although it uses half the points to train the model.
Conformal prediction methods are applied to 10.000 data points randomly sampled without replacement; while other 2500 observations chosen at random from those not part of the training set are used as the test set. The miscoverage rate is set to a = 0.1 and the procedure is repeated 100 times to remove the randomness of the split. The method used are cross-conformal prediction and its variants (with K = 10) and split conformal prediction. In particular, split conformal prediction is trained both at levels a and 2a. The averages over 100 trials are reported as results in Figure 3 and Table 1.
From Figure 3, it is possible to note that cross cross-conformal pre- diction and its modified version give very similar results in terms of size and are usually slightly better than split confor- mal prediction trained at level The randomized methods u t--ood-oe mod-cross and eu gu-mod--o mod-cross show significant improvement in terms of size. The improvement is not as evident for the e e-mod-crr be slightly better than the modified method. The smaller sets are obtained using split conformal prediction trained at level 2a. The level of coverage of cross-conformal prediction (and mod-cross. is around 1 a and the two methods tend to overcover (indeed, they guarantee miscoverage rate smaller than 2a). The e-mod-crae ccros method ex- hibits similar performance to cross-conformal prediction in terms of coverage; while the coverage of u-mod-cross and eu-mod-cross is between the levels - 2a and a. Clearly, there exists a direct relationship between
Additional results, comparing the proposed variants with other conformal prediction methods, such as jackknife+ and full conformal prediction, are reported in Appendix D.
5.2. Real Data Application
We apply the proposed methods to the "Online News Popu- larity" dataset (Fernandes et al., 2015). The dataset contains information on n = 39 797 articles published by the online news blog Mashable. After some preprocessing operations, the number of covariates is p- 55 and the covariates con- tain information about the text of the article. The goal is to predict the number of times the article was shared on logarithmic scale. Three different regression algorithms are used, specifically: linear regression (as described in Sec- tion 5.1), lasso regression with penalty parameter set to 0.2 and random forest with 200 trees grown for each forest.
method, which turns out to
7

---

Improving the Statistical Efficiency of Cross-oonformal Prediction
LM
Lasso
Random Forest
2.75
2.75
2.75
2.50
2.50
2.50
Size
Size
Size
2.25
2.25
2.25
2,00
2.00
1.75
1.75
1.75
mad-cross
e-mod-oross
u-med cross
eu-mod-crass
cross
split
spli((2a)
mad mod-eross
e-mod-cross
u-mod u-mod-crass -rood-
el-madd-rooss
cross
spiit
spla((20)
mad--cross
e-mod-cross
u-mod--ross
eu-mod-crass
pross
spiit
spl)(2a)
Figure 3. Empirical size obtained using different regression algorithms and different conformal prediction methods. The methods mod-cross and cross give similar results. The variants that use randomization (u-mod-crose and cu-mod-cross) have smaller size with respect the other methods trained level a. The smaller are obtained using split conformal prediction trained level 2o.
Table 1. Empirical coverage for the News Popularity Dataset using different regression algorithms and different conformal prediction methods. The a-level set 0.1. Mod-cress and cross have empirical coverage around a (while guaranteeing a coverage level of least 1 2a). The coverage for the randomized methods lies between 2a: and The e-mod-cross variant has coverage 11-1--1 a. Coverage variability is reported through the minimum and maximum values across the 100 replications, together with their difference.
Method
Metric
mod-cross
c-mod-cross
u-mod-cross
eu-mod-cross
cross
split
split(2a)
Mean
0.902
0.896
0.851
0.852
0.901
0.900
0.801
Min
0.884
0,876
0.834
0.826
0.884
0.885
0.777
LM
Max
0.917
0.915
0.874
0.881
0,916
0.916
0.831
Range
0,032
0.039
0.040
0,055
0.032
0.030
0.054
Mean
0.901
0.896
0,851
0.845
0.900
0.900
0.800
Min
0.888
0.872
0.831
0.826
0.887
0.884
0.772
Lasso
Max
0.916
0.914
0,870
0.876
0.915
0.915
0.822
Range
0.028
0.042
0.039
0.050
0.028
0.030
0.050
Mean
0.903
0.892
0.853
0.847
0.903
0.900
0.801
Min
0.885
0.870
0.832
0.815
0.885
0.882
0.778
RF
Max
0.918
0.915
0.875
0.881
0.917
0.918
0.819
Range
0.032
0,045
0,042
0.066
0.032
0.036
0.042
set size and coverage, with smaller prediction sets attaining coverage values closer to 1 - 2a. The coverage of split conformal prediction is essentially equal to the target levels a or 1 (see Appendix for further details on the coverage properties of the method). As a final remark, the eu eu-mod- cross method demonstrates higher degree of variability in coverage, while the remaining methods exhibit
comparable and more stable variability levels.
Additional experiments on real-world datasets are reported in Appendix E.
8

---

We present new variants of cross-conformal prediction that can achieve smaller prediction sets while maintaining valid coverage guarantees. The achievements are based on recent results on the combination of dependent and exchangeable p-values (Gasparin et al., 2025). In particular, starting from a target miscoverage rate equal to a, the new methods guar- antee a marginal coverage of least coverage is guaranteed by other methods, such as the jack- Improving the Statistical Efficiency of Cross-Conformal Prediction
Table Comparison of the properties of different conformal prediction methods. The first two columns regards the marginal coverage. The theoretical guarantees are valid in finite sample. The last column counts the number of times that the algorithm A is run on data set containing training points, for obtaining a prediction set for a new test point. The parameter Rigiid represents the number different possible values.
Method
Theoretical guarantee
Typical empirical coverage
Model training cost
Split
2 1 - a 2 1 a a
2 1 a
Full
2 1
- a > 1 a if μ overfits
igrid n
Jackknife+
2 2a
1 a 2 1 a
Cross
1 - 2a 22/ 2/vni
K
Mod-cross
2 1 - 2a
> 1 -
K
e/u/eu-mod-cross
2 1 - 2a
E [1 20, - ai)
K
6. Discussion
other hand, if conformal prediction is used merely as "weak guidance" for downstream decisions, meaning the user is willing to tolerate violations of the 1 - a target, then we recommend running the proposed cross-conformal variants at level a (where the worst-case coverage is -2a, but actual coverage lies between 1 2a and a). Finally, if the situation is intermediate, where conformal prediction is neither applied extremely rigorously nor used as loose guid- ance, and the goal is to achieve 1 - a coverage for "typical" datasets and algorithms, while accepting both overcoverage and undercoverage for unusual distributions or algorithms, then (modified) cross-conformal prediction may be the most appropriate choice.
2a. The same
knife+ introduced by Barber al. (2021) or multi-split conformal prediction (with threshold set to a half) by Solari & Djordjilović (2022).
Specifically, similar to cross- voos-validation, the proposed ap- proaches require training the models only K times, unlike times for the jackknife+ or even potentially an infinite number of times for full conformal prediction (see Table 2). The empirical coverage of the proposed methods usually oscillates between levels 1 - 2a and - while for stan- dard cross-conformal prediction the empirical coverage is usually around the nominal - a level. As reported in the experimental results, the size of the sets is smaller than that obtained by split conformal prediction and cross-conformal prediction. Since the results depend on randomized or asymmetric combinations of p-values, the size is gener- ally, though not consistently, more variable compared to cross-conformal prediction. In particular, while randomiza- tion and asymmetric combination improve efficiency of the prediction sets, they add an extra-layer of randomness to the procedure. The results presented in Sections 4.1, 4.2 and 4.3 can also be extended to the case where the number of observations in the folds different. Cross-conformal prediction can be improved using the same techniques, as shown in Section 4.4.
In general, the sets presented in Section 4 show good prop- erties in terms of size and coverage, both in simulations and in applications. The methods can be especially useful in settings where full conformal prediction or jackknife+ are computationally prohibitive.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are some potential societal consequences of our work, some of these have been care- fully considered and are explicitly outlined and emphasized within the text of the paper.
References
Angelopoulos, A. N. and Bates, S. Conformal prediction: gentle introduction. Foundations and Trends in Machine Learning, (6(4):494599. 2023.
Angelopoulos, A. N., Barber, R. F., and Bates, Theoreti- cal foundations of conformal prediction. arXiv preprint arXiv:241 1. 1 2024.
The question of which variant of cross-conformal prediction to use in practice is a subtle one. If it is crucial to obtain a 1 a guarantee against worst-case distributions and unsta- ble algorithms (for example, when downstream decisions critically depend on the provided theoretical guarantees), then it makes sense to run our methods at level a/ a/2. On the
Barber, R. F., Candès, E. J., Ramdas, A., and Tibshirani, J. Predictive inference with the jackknife+. The Annals of Statistics, 49(1) 507, 2021.
Barber, R. F,, Candès, E. J., Ramdas, A., and Tibshirani,

---

Improving the Statistical Efficiency of Cross-Cofformal Prediction
J. J. Conformal prediction beyond exchangeability. The Annals of Statistics, (1 845, 2023.
Kuchibhotla, A. K. Exchangeability, conformal prediction. and rank tests, arXiv preprint arXiv:2005.0660 2020.
Boström, H., Linusson, H., Löfström, T., and Johansson, U. Accelerating difficulty estimation for conformal re- gression forests. Annals of Mathematics and Artificial Intelligence, 81:125-144, 2017.
Lei, J., G'Sell, M., Rinaldo, A., Tibshirani, R. J., and Wasserman, L. Distribution-Ffi predictive inference for regression. Journal of the American Statistical Associa- tion, 1136523):1094-111
2018.
Carlsson, L., Eklund, M., and Norinder, U. Aggregated con- formal prediction. Artificial Intelligence Applications and Innovations: AIAI 2014 Workshops: CoPA, MHDW, IIV,, and MT4BD, Rhodes, Greece, September 19-21, 2014. Proceedings 10, pp. 231-240. Springer, 2014.
Liang, R., Zhu, W., and Barber, R. F. Conformal prediction after efficiency-oriented model selection. arXiv preprint S1l::2408.070666, 2024.
Linusson, H., Norinder, U., Boström, H., Johansson, U., and Löfström, T. On the calibration of aggregated conformal predictors. In Proceedings of the Sixth Workshop Conformal and Probabilistic Prediction and Applications, volume 60 of Proceedings of Machine Learning Research, pp. 173. PMLR, 13-16 Jun 2017.
Chen, W., Chun, K.-.,, and Barber, R. Discretized con- formal prediction for efficient distribution- inference. Stat, 7(1 e11):177, 2018.
Cherubin, G. Majority vote ensembles of conformal predic- tors. Machine Learning, 108(3):475-48, 2019.
Linusson, H., Johansson, U., and Boström, H. Efficient conformal predictor ensembles. Neurocomputing, 397: 266 166-278,12 2020.
Dean, A. and Verducci, J. Linear transformations that pre- serve majorization, schur concavity, and exchangeability. Linear algebra and its applications, 127:121-138, 1990.
Morgenstern, D. Berechnung des maximalen sig- nifikanzniveaus des testes "Lehne Ho ab, wenn & unter n gegebenen tests zur ablehnung führen"". Metrika, 27: 285- 285-286, 1980.
Fernandes, K., Vinagre, P., Cortez, P., and Sernadela, On- line News Popularity. UCI Machine Learning Repository, 2015.
Nash, W., Sellers, T., Talbot, S., Cawthorn, A., and Ford, W. Abalone. UCI Machine Learning Repository, 1994.
Fisher, R. Combining independent tests of significance. American Statistician, 2-30, 1948.
Papadopoulos, H., Proedrou, K., Vovk, V., and Gammerman, A. Inductive confidence machines for regression, Ma- chine learning: ECML 2002: 13th European conference machine learning Helsinki. Finland, August 19-23. 2002 proceedings 13, pp. 345 356..56.00 Springer, 2002.
Fontana, M., Zeni, G., and Vantini, S. Conformal prediction:
unified review of theory and new challenges. Bernoulli, 29(1):1-23, 2023.
Gasparin, M. and Ramdas, A. Merging uncertainty sets via majority vote. arXiv preprint arXiv:2401.09377 2024.
Prinster, D., Liu, A., and Saria, S. Jaws: Auditing predictive uncertainty under covariate shift. Advances in Neural Information Processing Systems, 35:35907-35920, 2022.
Gasparin, M., Wang, R., and Ramdas, A. Combining exchangeable p-values. Proceedings of the National Academy of Sciences. 122(11):2240884122 2025.
Ramdas, A. and Manole, T. Randomized and Exchangeable Improvements of Markov's, 's Chebyshev's 's and Chernoff's inequalities. Statistical Science, forthcoming. 2025.
Gupta, C., Kuchibhotla, A. K., and Ramdas, A. Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496 2022.
Redmond, M. Communities and Crime. UCI Machine
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. Surprises in high-dimensional ridgeless least squares in- terpolation. Annals of statisticx, 50(2):949, 2022.
Learning Repository, 2002.
Romano, Y., Patterson, E., and Candes, E. Conformalized quantile regression. In Advances in Neural Information Processing Systems, volume 32, 2019.
Hore, R. and Barber, R. Conformal prediction with local weights: randomization enables robust guarantees. Jour- nal of the Royal Statistical Society Series Statistical Methodology, 11 2024. ISSN 1369-7412.
Rüger, B. Das maximale signifikanzniveau des tests: Lehne Ho ab, wenn k unter gegebenen tests zur ablehnung füihren". Metrika, 25:171-178, 1978.
Kim, B., Xu, C., and Barber, R. Predictive inference is free with the jackknife+ Backniif+-atter-beeee bootstap Advances in Neural Information Processing Systems, 33:4138 4149, 2020.
Rüschendorf, L. Random variables with maximum sums. Advances Applied Probability, 14(3):623-66 -322, 1982.
10

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Saunders, C., Gammerman, A., and Vovk, V. Transduction with confidence and credibility. Sixteenth International Joint Conference Artificial Intelligence (IJCAI), pp. 722-726, 1999.
Yang, Y. and Kuchibhotla, A. K. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, pp. 1-13, 2024.
Shafer, G. and Vovk, V. A Tutorial on Conformal Prediction. Journal of Machine Learning Research, 9(3), 2008.
Solari, A. and Djordjilovié, V. Multi-split conformal predic- tion. Statistics Probability Letters, 184:109395, 2022. ISSN 0167-7152.
Steinberger, and Leeb, H. Conditional predictive infer- ence for stable algorithms. The Annals of Statistics, (1):290 3, 2023.
Stutz, D., Roy, A. G., Matejovicova, T., Strachan, P., Cemgil, A. T., and Doucet, Conformal prediction under am- biguous ground truth. Transactions on Machine Learning Research, 2023. ISSN 2835-8856.
Tibshirani, R. J., Foygel Barber, R., Candes, E., and Ram- das, Conformal prediction under covariate shift. In Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019.
Toccaceli, P. and Gammerman, A. Combination of con- formal predictors for classification. In Proceedings of the Sixth Workshop Conformal and Probabilistic Pre- diction and Applications, volume 60 of Proceedings of Machine Learning Research, pp. 39-61. PMLR, 13-16 Jun 2017
Tsanas, A. and Little, M. Parkinsons Telemonitoring. UCI Machine Learning Repository, 2009.
Vovk, V. Cross-conformal predictors. Annals of Mathemat- ics and Artificial Intelligence, 74:9-28, 2015.
Vovk, V. and Wang, R. Combining p-values via averaging. Biometrika, 107(4):791-805 2020.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning a Random World. Springer, 2005.
Vovk, V., Nouretdinov, I., Manokhin, V., and Gammerman, A. Cross-conformal predictive distributions. In Pro- ceedings of the Seventh Workshop on Conformal and Probabilistic Prediction and Applications, volume 91 of Proceedings of Machine Learning Research, pp. 37-51.
PMLR, 11-13 Jun 2018.
Vovk, V., Gammerman, A., and Shafer, G. Algorithmic Learning in a Random World. Springer Nature, edition, 2022a.
Vovk, V., Wang, B., and Wang. R. Admissible ways of merging p-values under arbitrary dependence. The Annals of Statistics, 50(1):351-3755 2022b.

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
A. Split Conformal Prediction
We briefly describe the split (or inductive) conformal prediction method introduced in Papadopoulos et al. (2002); Lei et al. (2018). We assume that we are in the same setup described in Section 2 and the goal to obtain prediction set for the response value Y given the training data and covariates in X In this case, data are divided into two disjoint subsets Durain and Deal- The algorithm is trained using the data points in Drraiu while the scores S; == ((X; Y.); Dirain) ; i Deal, are obtained from the observations in the calibration set. The split conformal prediction set is simply defined as
{ { E y/ : ::::s((A5)) ((Xn+1, Perain) S o):
Öuplity
n,a (X (Xn+1)= =
(17)
where q == quantile (SI,..,,Sppa Spp li (1 - a) 1/12cal))) ()). The set in (17) can be re-written as Cmplit (Xn+1) {y E: P(y) > a),
where
P(y)= 1+ EiED 11 {s ((X u); Dtrain) S 8 ((X;, Yi); Dtrain))
|Peall +
that is p-value when calculated in Y similar the one defined in (5). This implies that, if the data are iid, the marginal coverage of the set Cxplit (Xn+1) is at least 1 - In addition, if the residuals have no ties (they have continuous joint distribution) then
P PY Caplic (Xn+1)) S 1 - a +
1
[Deal +1
The proof of the result can be found in Lei et al. (2018), and the result states that the marginal coverage is essentially 1 when the number of observations is sufficiently large.
One of the attractive properties of split conformal prediction is that the computational cost of the procedure is low compared to that of full (or transductive) conformal prediction. In fact, the model only needs to be trained once, and the predictions are then calibrated using the data points in Deal-
B. Marginal Coverage of Cross- Conformal Prediction and Connection with CV+
As stated in Remark 3.1, it is possible to establish an alternative bound for the marginal coverage of cross-conformal prediction, distinct from the one shown in (4). In particular, Barber et al. (2021) proves that
1 K/n
P (Yu+2 Chrose (Xn+1) 2 2o 2(1 a) K K+
(18)
The proof technique is completely different from the technique presented in Section 3 based on p-values and relies on counting arguments applied to tourmament matrices (Barber et al., 2021: Angelopoulos et al., 2024). Combining the results in (4) and (18), we obtain
P (Yn+z E Ecrose (X 2 2a 2(1 - a) min ( 1/1 1- 1-K/n) [n/K+1 K +11 }
2a
(19)
The two bounds are compared in Figure 4 and it is possible to see that the two bounds have opposite behaviors. As depicted in Figure 4, even for small or moderate n, the bound in (4) is the one that applies to commonly employed values of K.
In addition, in a regression setting, cross cross-conformal prediction (Vovk, 2015) is closely related to K-fold CV+ introduced in Barber et al. (2021). In particular, both methods can be used to obtain prediction sets with finite sample coverage guarantees. Cross-conformal prediction is covered in Section 3; here, we introduce CV+ and explain its connection to cross-conformal prediction. In this case as well, the data points are divided into K disjoint folds /1,..., Ix of size m = n/ K, and j-r4 refers to the regression function trained using data in [nx] IR. is [K]. The K-fold CV+ prediction set is defined
n,K. (Xn+1)= = [- quantile ((- (a-tecs)
(X (x--lec,(xn+11
- ((V+)) ))(
iEIm] (1- a)(1
(20)
quantile (li- (Nn+1) + SCV+) sEIn ;1 a)(1 + 1/m1)]
We define quantile(::7) = inf(a:n Ex 1(2, Sa) 2 7). for any E R..
12

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
n=100
n=1000
1.0
1.0
0.9
0.9
Coverage
Coverage
0.8
0.8
(1-1/K)(n/K++1
0.7
(1-KIn)(K++)
0.6
0.5
0.5
25
50
75
100
0
25
50
75
100
Figure 4. Comparison of the bounds in (4) and (18) for different values of K with 0.1. Dashed lines represent the levels 1-20-2/ and 2a.
where SCV+ - - (X:)l. E [n], are the residual scores (or absolute residuals). An attractive property of the set (20) is that it is interpretable, since is always an interval (rather than, possibly, a union of intervals). In particular, when K, it corresponds the jackknife+ interval by Barber et al. (2021).
At first glance, the sets Crross (X.tk..( (X and C (Xn+1) proves that, when the score function in (3) is the residual score, then
(. can appear distinct; however, Barber et al. (2021, Appendix B.2)
n.K.o (X S C (Xa+1).
As corollary, it follows that the marginal coverage guarantee in (19) also holds for the CV+ method. This implies that the marginal coverage guarantee for the jackknife+, the case K = n, is at least - 2a. The empirical coverage often exceeds the stated 1 2n 2/ /n, typically aligning closer to the level - a, and sometimes approaching one. In fact, the value 2o can be considered as the worst-case scenario for the method. Under some assumptions about the stability the prediction algorithm, modified version of the jackknife+ is shown have marginal coverage close to 1 a. similar problem studied in Steinberger Leeb (2023), where the authors prove a conditional coverage probability statement for K K-fold crossvvalidation (a set similar to the in (20)) valid under some assumptions the algorithm and the distribution of the data. We refer to Angelopoulos et al. (2024, Ch. 6) for detailed discussion of the properties of cross-conformal prediction and jackknife+.
C. Cross- Coss--onfforml Prediction with Varying Fold Sizes
In this Section we treat the case where the number observation each fold can differ. We consider the same setup as the beginning of Section 3, and we allow different sizes among the subsets. Let my denote the number of observations in subset 4,, & [K]. By definition, the mi + ..... mæ equals the number of observations In this case, the definition of conformal p-values in (5) change slightly, allowing for dependence my in the denominator:
1+ Eien 11 (s ((X,+1 y): v): Dnjua) & S(V)
(v
(21)
my +
where SCV is defined in (2). However, P(PP(( S a) S a, still holds for any a E (0, 1). In addition, we define the weights
my +
Wk
(22)
n +
13

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
where we note that the weights are positive, sum to one and it holds that wi = 1/KK if m² m..
It is now possible to prove that the marginal coverage of cross-conformal prediction with varying fold sizes remains the same.
Lemma C.1. Suppose that my = | E [K], then the set Ecrouss
",,K,0 (Xn+1) in (3), is such that
Ccross n,K,Ka K.K.a (Xn+))) 2 1- 2a - 2(1 - 0:) - 1/K
P(Yn+1 E
n/K K +1
Proof. According to the definition of the cross-conformal prediction set in (3), we can see that y R,K,a (Xn+1) 1) if and only if
1+ Ei (((x))))((()))))))))))
())
S S
K wp >
K-1
(23)
+ 1
NL K
where wk and (v) are defined in (22) and (21), respectively. To complete the proof, we apply the fact that the weighted average of p-values provides a quantity that a p-value up to a factor of 2 (Vovk Wang, 2020).
At this point, one may wonder whether the validity of the sets defined in Sections 3.2, 4.1, 4.2 and 4.3 can also be extended to the case where the fold sizes vary. Since twice the (simple) average of p-values is itself a p-value under arbitrary dependence of the starting p-values, it follows that the coverage guarantee of sets K,K,a (Xn+1) and Cu-mod-cross (Xn+1) K,K,a
is preserved even if Pi (v)...., Px (y) are obtained using different m...
Caa (X is valid when the underlying p-values are exchangeable, and this is related to the number of data points in each fold, as stated in Remark 4.3. However, p- p-values can be made exchangeable through a random permutation of the indices. For example, assume n 101 and K = 5; in this case, the subset with 21 observations does not always have to be the same, but should be randomly selected among the 5 folds. This implies that the coverage guarantees for the sets Co-mod-cross
The coverage guarantee for sets Ce-mod-cross (X++1) and a, n,K,a
K,K.a (Xn+1) and Čeu-mod-eross (X.+1))))))))))) can still hold. a,K.a
More attention should be paid to Section 4.4. In fact, as seen on the right side of (23), belongs to the set only if the weighted average of the conformal p-values exceeds a certain threshold. However, the weighted average is an asymmetric function, and results on the combination of exchangeable p-values do not hold in this case. Only the result using randomization remains valid.
D. Additional Results Related to Section 5.1
We compare the results obtained in Section 5.1 with split conformal, full conformal prediction, and jackknife+. In addition, eu-mod-cross conformal prediction is added for comparison. Full and split conformal prediction are fitted using the package R conformallnference. The simulation scenario considered is the same as that described in Section 5. and all methods are trained at level a = 0.1. The theoretical and empirical guarantees and the computational cost of the methods are reported in Table 2 (Section 6). The different methods will be compared in terms coverage and interval size.
Also in Figure 5, we can see some spikes in the width of the sets at different levels of p. Since split conformal prediction uses n/2 data points to train the model, the peak is observed p = 50; while for the jackknife+ this peak is observed p 100. However, the peak for the jackknife+ is smaller than that observed for split conformal prediction and the eu nu-mod--os cross method. The smaller sets are usually obtained using e eu-mod-croo croos conformal prediction (or jackknife+)) It is important to note that the jackknife+ has the same coverage guarantee as eu-mod-ca cross conformal prediction; however, the empirical coverage for the jackknife+ is around the level 1 - a while for our method it lies between levels 2a and - a. As reported in Table 2, the computational cost of the jackknife+ is higher than that of cross-conformal prediction methods: it requires n calls to the prediction algorithm (versus the required by cross-conformal methods). However, the method is non-randomized, since can be seen as an extension of cross-conformal prediction the extreme case K
As observed in Barber et al. (2021), when p > n. full conformal prediction results in intervals of infinite length because for each possible value of the response, all residuals are equal to zero. In practice, the interval is truncated to finite range, which has a minimal effect on the marginal coverage (Chen et al., 2018). Split conformal prediction and jackknife+ have similar coverage, but the intervals obtained from jackknife+ are usually smaller (except when the algorithm proves to be unstable).
14

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Averaged prediction set size
(200med in)
Empirical coverage
125
20
10
100
15
09
Coverage
CU mod cross
Size
Site
10
ful
Jackentcc
0
P
Figure 5. Simulation results, showing the size and the coverage of the predictive intervals for jackknife+, split conformal prediction and full conformal prediction. The eu -oo--rosssss method is added for comparison and the a-level is set to 0.1. The smaller sets are usually observed by eu-mod-cron cross conformal prediction. Split conformal prediction and jackknife+ have empirical coverage 1
E. Additional Experiments
Communities and Crime dataset. We apply the proposed methods the Communities and Crime dataset (Redmond, 2002). The dataset contains information capita violent rate. After removing the columns containing missing values and categorical variables, the number of regressors is 99. Two regression algorithms are used, specifically lasso regression with penalty parameter set to 0.01 and random forest with 50 trees grown for each forest.
1994 communities in the United States and the goal is to predict the
The a-level set to 0.1 and the conformal prediction methods are applied on 1000 data points randomly sampled without replacement. The remaining part used as test set compute the metries. The procedure is repeated 100 times to remove the randomness of the split and we report the averages over these 100 trials. The methods used are cross-conformal prediction and its variants (with K 10), and split conformal prediction is added for comparison.
The results are reported in Figure 6, where it is possible to see that the smaller sets are obtained using the eu-mod-cross method. The modified variants using exchangeability and randomization exhibit higher variability in interval width, likely due to the use of randomization and the asymmetry of the combination rules. All proposed methods have an empirical coverage of at least 2a. We remark that cross-conformal prediction guarantees coverage of least 1 2o,, but is usually conservative. The coverage of the new methods is closer to the level 2a and the new variants outperform cross-conformal prediction in terms of set size.
Boston Housing dataset. We apply conformal prediction methods on a dataset of moderate dimensions, with p 13 and n = 506. The aim is to predict the cost of a house in Boston given some information on the neighborhood. The algorithm used is standard linear regression. We apply conformal prediction methods using 200 training points, the remaining part is used as test set. The number of different subsets for cross-conformal prediction set to K 5 and the miscoverage rate 0.1. The procedure is repeated 100 times, and we report the averages over the 100 replications.
From Table 3, produced by split conformal prediction, which exhibits high variability in set size. The methods e-mod-oa -eroseosss and u-mod-cross have an empirical coverage slightly lower than 1 - a, with an average size generally smaller than that obtained using cross-conformal prediction. Full conformal prediction exhibits low variability terms of size, with the sets typically being smaller than those produced by split conformal prediction and cross crofo-conformal prediction. However, as already seen, these advantages are counterbalanced by a high computational cost.
that smaller sets obtained using eu-mod-cross conformal prediction, while larger
15

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Lasso
Random Forest
E Empirical Coverage
1.0
0.6
0.9
Coverage
Size
Size
0.8
Lasso
0.7
RF
mad-cross
e-mad--cross
u- -cross
eu-med--cam
cross
spllt
mad-cross
e-mod e-mod-cross
u-mod -cross
eu-mad-cross
crass
splft
mad-crass
e-mod -oods
u-mad u-mad--cooss
-cross
Qu-mod-cress
cross
split.
Figure 6. Results for the "Communities and Crime" dataset. Empirical size and empirical coverage of different conformal prediction algorithms are reported. The a-level is set to 0.1. The smaller sets are obtained using cu-mod-crose whose empirical coverage is around 0.85. Cross-conformall prediction conservative, but tends to produce stable sets.
Table Results for the "Boston Housing" dataset using OLS regression algorithm. The results refer set size, except for the last row, which refers to the marginal coverage. The a-level is set to 0.1. The smaller sets are obtained using eu eu-mod-cre cross conformal prediction. The variability especially high when using split conformal prediction.
mod-cross e-mod-cross
u-mod-cross
eu-mod-cross
cross
split
full
Mean Sd
17.303
14.920
14.143
13.370
15.753
16.357
14.516
1,440
1.998
1.152
1.899
1.307
2.751
1.244
Median
17.188
14.692
14.113
13.128
15.679
16.041
14.656
Min
13.883
10.068
11,551
8.822
12.766
11.730
11.998
Max
20.935
20.537
17.150
18.339
19.101
27.469
17.756
Coverage 0.927
0.888
0.878
0.855
0.908
0.897
0.888
UPDRS dataset. We tested our methods on a dataset containing information on patients with early-stage Parkinson's disease (Tsanas & Little, 2009). The goal is predict the total UPDRS (Unified Parkinson's 's Disease Rating Scale) using range of biomedical voice measurements. In particular, after some preprocessing operations, the data set includes points and p 13 covariates. The two regression algorithms used are lasso regression (with penalty parameter equal to 0.01) and random forest (with 25 trees grown for each forest). The a-level is set to 0.1, the number of folds is K = 10 and the conformal prediction methods are applied on 3000 data points randomly sampled without replacement. The remaining part is used as a test set to compute the metrics. The procedure repeated 100 times to remove the randomness of the split. The results reported are the averages over these 100 trials. We compare our proposals with cross-conformal prediction. In addition, split conformal prediction with miscoverage rate set a and 2a added for comparison.
5875
The results are reported in Table 4 and Table 5. In Table 4, using split conformal with miscoverage rate set to 2a. Overall, our approaches typically yield smaller sets compared to those obtained using standard cross-conformal prediction and split conformal prediction. However, we can observe a higher variability derived from the use randomization (or sequential processing of the p-aauues). Interestingly, when the random forest is used as a regression algorithm (Table 5), the smaller sets are obtained using the exchangeable and randomized cross-conformal prediction method. In particular, on average, the method also outperforms the split conformal prediction
that for lasso regression the smaller sets obtained
16

---

Improving the Statistical Efficiency of Cross-onfformal Prediction
trained level 2o. In both cases, the marginal coverage of the proposed methods fluctuates between levels 2a and 1 On the other hand, from Table 5 it is possible to see that cross conformal is conservative with coverage higher than the nominal
Table 4. Results for the UPDRS dataset using lasso as regression algorithm. The results refer to set size, except for the last row, which refers the marginal coverage. The a-level to 0.1. On average smaller sets are obtained using split conformal with miscoverage rate 20. The marginal coverage of the proposed methods lies between 1 2a and 1 a.
mod-cross
e-mod-cross
u-mod-cross eu-mod-cross
cross
split
split (2xx)
Mean Sd 29,946
29.965
28.956
26.427
26.252
29.686
29.901
23.773
0.404
1.019
1.744
1.942
0.383
0.878
0.402
Median
29.175
26.202
26.092
29.725
29.703
23.734
Min
11.450
10.019
8.477
9.248
11.340
28.539
22.913
Max 32,808
30.826
31.267
30.716
32.698
32.318
25.223
Coverage 0.904
0.892
0.854
0.850
0.901
0.901
0.800
Table 5. Results for the UPDRS dataset using random forest as regression algorithm. The results refer to set size, except for the last row, which refers to marginal coverage. The a-level set to 0.1. average smaller sets are obtained using the exchangeable and randomized version of cross-conformal prediction. The marginal coverage of the proposed methods lies between
22x and
mod-cross
e-mod-cross
u-mod-cross
eu-mod-cross
cross
split
split (2xx)
Mean Sd
17.180
15.186
14.737
13.718
17.015
19.210
14.550
0.918
1.058
1.481
1,370
0.908
0.825
0.638
Median
17.175
15.303
14.643
13.762
16.954
19.232
14.541
Min
8.697
7.376
6.716
5.725
8.697
16.842
13.079
Max
23.890
17.945
22.129
17.725
23.560
20.954
16.551
Coverage
0.931
0.883
0.887
0.846
0.929
0.900
0.802
Abalone dataset. The proposed methods are applied to the abalone dataset (Nash et al., 1994). The goal is to predict the age of abalones (the number of rings) using where 4000 observations are used training points, while the remaining part is used as a test set. In this experiment, we directly modify the cross-conformal prediction described in Section 4.4 (indeed, remove the word mod from the labels in Tables 6, 7 and 8). The procedure is repeated 100 times to remove the randomness of the split and the results reported are the average over the 100 trials. The a-level is set to 0.1 and we use different number of folds, in particular, K = (5, 10, 20}. The regression algorithm used is a random forest with 25 trees grown for each forest.
physical mcasurements. The dataset contains n 4177 observations
The results are reported in Tables 6, 7 and 8. The coverage level for the proposed method oscillates between levels 1 - 2a and - a. The smaller sets are obtained on average by split conformal prediction with miscoverage rate equal to 2a. The suggested methods improve quite significantly the performance the variability is generally higher. There is slight decrease in the size of sets, and slight increase in variability, of the and eu su-mod-- mod-cross cross methods as K increases. The results for the split conformal conformal prediction essentially the same for all tables as a different number of folds is applicable just for cross conformal prediction and its variants.
cooss-ooforrmal prediction in terms of set size, although
Table 6. Results for the "Abalone dataset" using random forest regression algorithm. The results refer set size, except for the last row, which refers to the marginal coverage. The number of folds is K = 5 and the a-level is set to 0.1. The marginal coverage of the proposed
methods lies between 1 2a and 1
cross
e-cross
u-cross
eu-cross
split
split (2a)
Mean Sd
6,864
6.372
5.708
5,477
6.730
4.617
0.074
0.255
0.040
0.316
0.155
0.103
Median
6,858
6.332
5.713
5.390
6.703
4.583
Min
6.798
6.049
5.659
5.195
6.512
4.516
Max
6,986
6.762
5.755
6.015
6.912
4.777
Coverage
0.911
0.890
0.873
0.854
0.903
0.803
17

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Table Results for the "Abalone dataset" using random forest regression algorithm. The results refer size, except for the last
row, which refers to the marginal coverage. The number of folds is K 10 and the a-level is set to 0.1. The marginal coverage of the
proposed methods lies between 2a and a.
cross
e-cross
u-cross
eu-cross
split
split (2a)
Mean Sd
6.869
6.323
5.695
5,444
6.816
4.741
0.060
0.225
0.069
0.258
0.171
0.110
Median
6.865
6,360
5.692
5,450
6.815
4.750
Min
6.725
5,559
5.545
4.667
6.351
4,419
Max
7.030
6,800
5.878
6.061
7.235
5.060
Coverage
0.910
0.886
0.863
0.843
0.899
0.798
Table 8, Results for the "Abalone datasct" using random forest as regression algorithm. The results refer to set size, except for the last and a-level is to 0.1. marginal coverage of the
row, which refers the marginal coverage. The number of folds proposed methods lies between 1 2a and
a.
cross
e-cross
u-cross
eu-cross
split
split (2ox)
Mean Sd
6.855
6,210
5.649
5.379
6.817
4.717
0.062
0.340
0.063
0.381
0.190
0.089
Median
6.850
6.283
5.642
5,403
6.837
4.728
Min
6.648
4.992
5.520
4.321
6.396
4.503
Max
7.032
6.760
5.787
6.315
7.358
4.971
Coverage
0.909
0.879
0.862
0.839
0.899
0.795
Electricity consumption dataset. We additionally analyze real dataset on electricity consumption, where accurate uncertainty quantification is crucial as the supplier's revenue depends on customer energy use. The dataset contains 35 41 observations and 20 covariates; 30 000 observations are used for training, while the remaining ones are used for testing. The splitting is repeated 100 times, and the algorithm used is random forest (with ntree 100). In this case, methods such as full conformal prediction or jackknife+ can be computationally expensive due to the relatively large number of observations, making sample-spliting-
methods preferable.
The results are presented in Table 9. The column "uneven split" represents split conformal prediction, where the training set comprises (K - 1)/ K fraction of the data points. This corresponds to split conformal prediction with the same fraction of training data points used by a single round cross conformal prediction. The last two columns represent cases where the p-values are combined using the Bonferroni rule at level a (i.e., K min(p)) or at level 2a (i.e., K /2 min(p)) rather than the simple average. This implies that the corresponding prediction sets have coverage at least equal to and 2a, respectively.
The smaller sets are obtained by the eu-mod-croo method, and in general there is improvement in the set size if we use cross conformal prediction instead of split conformal prediction. Bonferroni method produces very large prediction sets and this is expected since the Bonferroni rule is not powerful when p-values (or sets) are highly dependent. Indeed, the Bonferroni correction tightest when the p-values are nearly independent, while the conformal p-values across folds are highly dependent. On the other hand, the rule "twice the mean" used in cross conformal prediction is more powerful when p-values are dependent; see Section 6.1 Vovk Wang (2020) for a discussion. This aligns with Theorem 4 in Lei et al. (2018), which states that the use of multisplit conformal prediction conjunction with the Bonferroni rule produces wide sets (specifically, under some assumptions, "uneven" split conformal prediction is smaller than that of split conformal prediction but slightly larger than that of cross conformal prediction. Moreover, its variability (Sd) is higher.
wider than "single split" conformal prediction). The average size of
18

---

Improving the Statistical Efficiency of Cross-Conformal Prediction
Table Results for the "Flectricity consumption dataset" using random forest as regression algorithm. The results refer set size, except for the last row, which refers to the marginal coverage. The number of folds is K 10 and the a-level is set to 0.1. The marginal coverage of proposed methods lies between 2a and 1 a. The Bonferroni method gives large prediction sets.
mod-
e-mod-
u-mod-
eu-mod-
uneven
split
Bonf
cross
cross
cross
cross
cross
split
split
(2x)
Bonf
(2a)
Mean Sd
50.85
47.10
33.78
32.27
50.71
59.59
52.25
26.52
196.68
149.63
0.49
1.66
0.31
1.54
0.49
1.64
2.97
0.54
6.51
2.92
Median
50.83
47.38
33.80
32.47
50.69
59.64
52.12
26.47
197.46
149.71
Min
49.73
41.97
32.99
27.74
49.60
56.54
44.45
25.25
174.87
141.06
Max
52.38
49.67
34.41
36.20
52.25
64.95
59.84
27.96
210.94
157.85
Coverage
0.91
0.89
0.86
0.85
0.90
0.90
0.90
0.80
0.98
0.97
F. Proofs of the Results
2 + [0, _|K be the transformation that takes as input the n + iid Proof of Proposition 4.1. Let G (X' =)
(and thus exchangeable) data points Z1.... Zu+1 and returns as output the p-values Pi (Yx+1)........ Pk (Yn+1). other words, the i-th element of G is computed by training the algorithm A using the dataset Plo],, and then computing the scores and the corresponding p-value defined in (5) using data points in (n+-(+1))- It is important note that the score function 8 satisfies the condition in (I), and so the scores do not depend on the order of the data points in [n Let 01 [n]] + [K] be the function that assigns the training data points to the K different folds and d2 : [n] + [m] be the function that assigns the positions of the training data points within the assigned folds. In words, each point E [m] is
assigned a unique pair {ai (1)) that identifies its fold and its position inside the fold. For example, if a (1) = 2 and
02(1)= = 3 then the first data point in the original dataset the third data point the second fold. Let gi [K] - [K] be
permutation of the indices, then for all ge+1
x G Ens 2n+1) -(m,(().....,... (n:
where π2 : In 1] + [n + 1] is such that
(m)(0)()) - 1] mmmmo 00)), i n 11 i == n +
T2(1)= = 1+1,
In words, 72 permutes the training data points into their respective permuted folds (i.e., i (a (an (0)). while the test point remains in the (n 1)-th position. It holds that G(-) preserves exchangeability and this concludes the proof.
Proof of Theorem 4.4. By definition
min (E(K]
Pa(
K Σ Px(x).
so less points will be included in the set. From Proposition 4.1 we have that the conformal p-values are exchangeable. The coverage property in (11) is direct consequence of the result stated in Gasparin et al. (2025), which states that mineg Ei= Ps (Yn+1) ) is valid p-value up a factor of 2 if p-values Pi PY Px (Yn+1) are exchangeable.
Proof of Theorem 4.6. By definition
K Σ Pa( k=1
1 K <
1
Pa(v).
2 U-U
K
since 1/(2- -)) U) < almost surely. The result implies that less points will be included in the set. The coverage property in (13) a consequence of Gasparin et al. (2025), which states that
2 1 K
Σ Pa(Y.+1)
2 - U K
k=
19

---

Improving the Statistical Efficiency of Cross-onfformal Prediction
is valid p-value. In particular, the result holds under arbitrary dependence of the starting p-values P1(Y++1); . (Yn2)+1):
Proof of Theorem 4.7. By definition
1
1 Σ Pa(v)
min
Pi(y), min EE[K]
min [E(R]
Pa(v).
2 2-
The result implies that less points will be included in the set and Öry (Xn+1) C a,
K,K
Cn-mod-cross
(Xn+1). The fact
that (te-md--crost (Xn+1) S Crnod cross (Xn+1) (Xn+1)) is outlined in Theorem 4.4. n,
K,K,o
From Proposition 4.1 we have that the conformal p-values are exchangeable. The coverage property in (15) is a consequence of the fact that
min
min P(((++))
Σ [E|K]
Pa(Yos))
2 --U
a p-value up to a factor of two if p-values P1(Yn+1),.... PK (Yn+)) are exchangcable (Gasparin et al., 2025, Appendix B).
Proof of Theorem 4.9. Comparing Equation (6) with the set defined in Equation (8) we have that Cmood Crmod-cross
(Xn+1) coin-
cides with Éerces (Xn+1). The same result is obtained, for example, in Vovk al. (2022a, Chapter 4.4). The coverage statement and the properties regarding the size of the sets are corollaries of Theorems 4.4, 4.6 and 4.7, applied with threshold a'.
20


Reviews:
[{"review_id": "6ztOlaMI9J", "reviewer": "Reviewer_qkMw", "summary": "The authors propose new variants of cross-conformal prediction that leverages recent results on combining p-values through exchangeability and randomization. They theoretically demonstrate that their methods can reduce the size of the prediction set while maintaining a marginal coverage of at least $1 - 2\\alpha$. The paper also highlights the computational advantages of these new methods, as they require training the model only a limited number of times (K times) rather than for every possible response value.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback on our paper. Please find below a detailed response to your concerns.\n\n### Experimental Designs Or Analyses:\nThank you for the suggestions. Below, we present an example where the experimental setting is identical to the last experiment in Appendix E, but with $K$ set to 5, 10, and 20. In addition, the number of trials is 100. The second table ($K=10$) is similar to the table reported in the paper with 20 trials (this number is used in many conformal prediction works; see, for example, Barber et al. (2021) or Romano et al. (2019)). There is a slight decrease in the empirical size of sets, and a slight increase in variability, of the e and eu-mod-cross methods as $K$ increases. Clearly, nothing changes for the split conformal methods. We will add the example and add more trials for other experiments.\n\n| K=5 | cross | e-cross | u-cross | eu-cross | split | split($2\\alpha$) |\n|--|--|--|--|--|--|--|\n| Mean | 6.887 | 6.382 | 5.711 | 5.508 | 6.764 | 4.735 |\n| Sd | 0.072 | 0.162 | 0.058 | 0.182 | 0.167 | 0.100 |\n| Median | 6.881 | 6.389 | 5.711 | 5.518 | 6.748 | 4.719 |\n| Min | 6.656 | 5.964 | 5.576 | 5.074 | 6.331 | 4.516 |\n| Max | 7.064 | 6.762 | 5.837 | 6.015 | 7.268 | 4.967 |\n| Coverage | 0.910 | 0.885 | 0.867 | 0.845 | 0.897 | 0.800 |\n\n| K=10 | cross | e-cross | u-cross | eu-cross | split | split(2$\\alpha$) |\n|--|--|--|--|--|--|--|\n| Mean | 6.869 | 6.323 | 5.695 | 5.444 | 6.816 | 4.741 |\n| Sd | 0.060 | 0.225 | 0.069 | 0.258 | 0.171 | 0.110 |\n| Median | 6.865 | 6.360 | 5.692 | 5.450 | 6.815 | 4.750 |\n| Min | 6.725 | 5.559 | 5.545 | 4.667 | 6.351 | 4.419 |\n| Max | 7.030 | 6.800 | 5.878 | 6.061 | 7.235 | 5.060 |\n| Coverage | 0.910 | 0.886 | 0.863 | 0.843 | 0.899 | 0.798 |\n\n| K=20 | cross | e-cross | u-cross | eu-cross  | split | split($2\\alpha$) |\n|--|--|--|--|--|--|--|\n| Mean | 6.855 | 6.210 | 5.649 | 5.379 | 6.817 | 4.717 |\n| Sd | 0.062 | 0.340 | 0.063 | 0.381 | 0.190 | 0.089 |\n| Median | 6.850 | 6.283 | 5.642 | 5.403 | 6.837 | 4.728 |\n| Min | 6.648 | 4.992 | 5.520 | 4.321 | 6.396 | 4.503 |\n| Max | 7.032 | 6.760 | 5.787 | 6.315 | 7.358 | 4.971 |\n| Coverage | 0.909 | 0.879 | 0.862 | 0.839 | 0.899 | 0.795 |\n\nWe additionally analyze the case where the number of observations in each fold differs. Since in cross-conformal prediction the $K$ folds serve the same role (being used for both training and calibration), having folds with significantly different sizes would be unwise. This principle applies not only to cross-conformal prediction but also to other methods that randomly partition the data into $K$ folds, such as Hulc (Kuchibhotla et al., 2024) and MoM (Lugosi & Mendelson, 2019). As explained at the beginning of Section 3, this means that the folds can differ by at most $K-1$ observations (with $K$ typically set to 5 or 10).\nFor completeness, we present the results of a simulation study based on the Boston dataset. The setting is the same as described in Appendix E, except that $n=204$ and one fold at random contains 44 observations instead of 40 (a 10% increase). The number of trials is 100. One could, in principle, have four folds with 41 observations and one with 40, but we consider a more 'extreme' setting. The results are presented in the Table, and the conclusions remain qualitatively similar to those reported in Appendix E.\n| | mod-cross | e-mod-cross | u-mod-cross | eu-mod-cross | cross |\n|--|--|--|--|--|--|\n| Mean   | 17.299 | 15.206 | 14.083 | 13.565 | 15.883 |\n| Sd    | 1.542 | 2.218 | 1.211 | 2.159 | 1.414 |\n| Median  | 17.245 | 15.229 | 14.068 | 13.605 | 15.819 |\n| Min   | 14.029 | 9.518 | 11.699 | 8.895 | 13.000 |\n| Max   | 21.196 | 20.869 | 16.885 | 20.199 | 19.243 |\n| Coverage | 0.926 | 0.892 | 0.877 | 0.859 | 0.909 |\n\n### Weaknesses:\nWe agree that randomization can introduce variability in the prediction sets; however, employing randomized and asymmetric combination rules is the only way to enhance the efficiency of cross-conformal prediction sets while preserving the same (worst-case) coverage guarantee. Furthermore, as noted in Remark 4.8, randomization plays a role at various stages of the data pipeline in both cross and split conformal prediction. As discussed in the paper, in some applications of large-scale deployment involving thousands of daily predictions, improved statistical efficiency may be preferred. \n\nIn light of the responses provided, we hope we have addressed your concerns and that you may consider raising the score.\n\nKuchibhotla, A. K., Balakrishnan, S., & Wasserman, L. (2024). The HulC: confidence regions from convex hulls. Journal of the Royal Statistical Society Series B: Statistical Methodology, 86(3), 586-622.\n\nLugosi, G., & Mendelson, S. (2019). Mean estimation and regression under heavy-tailed distributions: A survey. Foundations of Computational Mathematics, 19(5), 1145-1190.", "claims_and_evidence": "The theoretical guarantees are well supported by proofs in the appendices, leveraging the coverage properties of p-value combination results. Simulations and real-world experiments validate the smaller prediction set sizes compared to baselines, with empirical coverage aligning with theoretical bounds.", "methods_and_evaluation_criteria": "The use of exchangeable p-values and randomization is novel and logically derived in this context. The regression tasks on benchmark datasets are appropriate.", "theoretical_claims": "The theoretical claims are well supported by the proof in appendices.", "experimental_designs_or_analyses": "The experimental design is appropriate but could be strengthened by increasing the number of trials (e.g., from 20 to 100) to improve reliability and including the experiments with varying fold sizes.", "relation_to_broader_scientific_literature": "The work in this paper builds on cross-conformal prediction and recent p-value combination methods, improving the statistical efficiency, and further advancing the development of conformal prediction.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n1.\tThe research innovatively utilizes combination of p-values through exchangeability and randomization to cross-conformal prediction.\n2.\tMaintains theoretical guarantees with smaller prediction sets and computational efficiency (K folds).\nWeaknesses:\n1.\tRandomization introduces variability in prediction sets, which may limit deterministic applications and lead to reproducibility concerns.", "other_comments_or_suggestions": "No further suggestions.", "questions_for_authors": "NA", "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": {"ethical_review_concerns": "NA"}}, {"review_id": "vBwn2ZJywd", "reviewer": "Reviewer_uMcf", "summary": "The paper proposes new variants of cross-conformal prediction to obtain smaller prediction sets while guaranteeing the same worst-case miscoverage rate. They use recent results on the combination of dependent and exchangeable p-values to obtain their results. Empirical evaluation on simulated data and the news popularity dataset show that their proposed improvements lead to smaller sets than cross-conformal prediction and modified cross-conformal prediction. Similar improvements are observed in the additional experiments.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive feedback on our paper. We truly appreciate your comments. \n\nThank you for noticing the typo, we corrected it.", "claims_and_evidence": "Claims made in the paper are supported by theory (Theorem 4.4 - 4.9) and empirical evidence. The results show that the proposed improvements result in smaller prediction sets while maintaining the coverage guarantees.", "methods_and_evaluation_criteria": "The empirical evaluation is extensive and the experiments are performed on multiple datasets. The benchmark datasets and the reported size and coverage metrics make sense for the problem.", "theoretical_claims": "I went over the proofs for Theorem 4.6-4.9 in Section F.", "experimental_designs_or_analyses": "I checked the soundness of all experiments, including the simulation study, real data application, and additional results reported in the appendix. The experimental details and choices have been carefully explained, and there is effort to experiment with different algorithms and parameters.", "relation_to_broader_scientific_literature": "Building on the literature of cross-conformal prediction and combination of dependent p-values, this paper contributes in producing smaller sets than cross-conformal prediction (and modified version) and split conformal prediction; while the empirical coverage lies between $1 - 2\\alpha$ and $1 - \\alpha$. The guarantees presented and supporting empirical evidence show improvement over prior work with similar model training cost.", "essential_references_not_discussed": "I feel the paper is fairly complete in its discussion of important references for understanding the context.", "other_strengths_and_weaknesses": "I appreciate the clear writing and how the paper lays out past work to contextualize their work and contributions better. The remarks in the paper further add to the clarity.", "other_comments_or_suggestions": "minor typo: p2 l68: obtained ‘by’ applying", "questions_for_authors": "No specific questions.", "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": "6Xh76AaJEk", "reviewer": "Reviewer_opLB", "summary": "The authors move from the interesting, yet relatively limited literature on methods that work on improving the dramatic data inefficiency of split conformal prediction.\nTheir proposal exploits novel results about p-value combination to introduce a variant of the well known cross-conformal prediction methods that achieves better theoretical coverage properties.\nAfter a thorough description, and proofs about its theoretical properties, the author put their modified cross-conformal prediction method to the test, in both a simulation and a real world example.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback. Below is our response to your comments\n# Experimental Designs\nWe now additionally analyze a real dataset on electricity consumption, where accurate uncertainty quantification is crucial as the supplier’s revenue depends on customer energy use. The dataset contains 35,411 observations and 20 covariates; 30,000 observations are used for training, while the remaining ones are used for testing. The splitting is repeated 20 times, and the algorithm used is a random forest. In this case, methods such as Full CP and Jackknife+ can be computationally expensive, making sample-splitting-based methods preferable. From the table, it can be seen that Cross CP is more efficient than Split CP, producing more informative sets while ensuring valid coverage. See the first point in *Questions* below for a further discussion.\n\nThe column *Uneven split* represents Split CP, where the training set comprises a $(K-1)/K$ fraction of the data points (ie, Split CP with the same fraction of training data points used by a single round of Cross CP). The last two columns represent cases where p-values are merged using the Bonferroni rule at level $\\alpha$ (ie,$K\\min(p)$) or at level $2\\alpha$ (ie,$K/2\\min(p)$). These results are discussed in the 2nd point of the *Questions* section\n||mod-cross|e-mod-cross|u-mod-cross|eu-mod-cross|cross|split|uneven split|split(2$\\alpha$)|Bonf|Bonf(2$\\alpha$)|\n|-|-|-|-|-|-|-|-|-|-|-|\n|Mean|50.53|47.20|33.64|32.26|50.40|59.59|53.43|26.59|223.86|153.81|\n|Sd|0.52|1.70|0.32|1.27|0.51|1.39|2.74|0.45|10.99|5.82|\n|Min|49.50|42.74|33.00|29.08|49.36|57.09|48.12|25.64|202.48|141.66|\n|Max|51.47|49.23|34.43|33.72|51.34|62.26|58.62|27.71|244.33|165.03|\n|Cov|0.90|0.89|0.86|0.84|0.90|0.90|0.90|0.80|0.98|0.96|\n# References\n- Thank you for pointing to this. We will add the paper by Saunders et al\n- We will discuss the two references appropriately in the text\n# Questions\n**Conclusions**\n\nWe believe that the methods has practical utility. For instance, when dealing with a large number of observations (and potentially a high-dimensional feature space), some methods, such as full CP and jackknife+, become impractical. One possible approach is to trade off some statistical efficiency for reduced computational cost by using methods based on sample-splitting. However, split CP can be inefficient because it only uses a subset of the data for model training. Cross CP generally improves the efficiency of split CP but can overcover. Our work improves statistical efficiency of Cross CP (at the same computational efficiency) while maintaining its coverage guarantee.\n\nThe question of which variant of cross CP is to be preferred in practice is subtle. \n- If one really needs to have a rigorous $1-\\alpha$ guarantee against the worst case distributions and unstable algorithms (for example, if there are downstream decisions that crucially depend on the provided theoretical guarantee), then it makes sense to run our new methods at level $\\alpha/2$\n- If one is only using conformal prediction as \"weak guidance\" for downstream decisions, and the user is somehow ok with violations of the target $1-\\alpha$, then we recommend running our variants of cross-conformal at level $\\alpha$ (where its worst case guarantee is $1-2\\alpha$ but it achieves coverage in between $1-2\\alpha$ and $1-\\alpha$)\n- If the situation is in between, where conformal prediction is neither being used extremely rigorously, nor as loose guidance, but one wants $1-\\alpha$ coverage for \"typical\" datasets and algorithms, but is ok with both overcoverage and undercoverage for odd distributions/algorithms, then perhaps the original (modified) cross-conformal is best\n- If one does not tolerate over- or under-coverage of any sort, and really wants essentially exact $1-\\alpha$ coverage, then only split conformal delivers the goods\n\nWe acknowledge that the conclusions can be improved and will incorporate the above takeaway messages there\n\n**Discussion Lei et al**\n\nThe results in Lei et al are based on the Bonferroni rule, that is not powerful when p-values (or sets) are highly dependent. Indeed, the Bonferroni correction is tightest when the p-values are nearly independent, while the conformal p-values across folds are highly dependent. On the other hand, the rule \"twice the mean\" used in cross CP is more powerful if p-values are dependent; see Sec.6.1 in Vovk & Wang (2020). For completeness; the above table also reported the use of the Bonferroni rule as merging function. The last 2 columns guarantee coverage of at least $1-\\alpha$ and $1-2\\alpha$, respectively. However, the methods have coverage near 1. This aligns with Thm.4 in Lei et al, which states that multisplit+Bonferroni produce wide sets (specifically, sets are wider than single split CP). For comparison, we have added split CP with an uneven split. The set size is smaller than that of Split CP but larger than that of Cross CP and variants. Moreover, its Sd is higher. We will add this discussion", "claims_and_evidence": "All claims are well supported by well crafted proofs, I am a bit more skeptical about the applicative results (but more on this later)", "methods_and_evaluation_criteria": "Both the simulation and the real world example are satisfactory. It would be worth maybe to propose a slightly extended real world test, in order to grasp better the practical advancements introduced by the method.", "theoretical_claims": "I have carefully checked all the proofs in the paper, and everything seems in order.", "experimental_designs_or_analyses": "As mentioned previously, I believe that the experimental study on real world cases is a bit too limited, as it does not really give much insights with respect to the situations where the method proposed by the authors give significant practical advantages", "relation_to_broader_scientific_literature": "The background on Conformal Prediction is not correctly stated. CP was not introduced in Vovk et al. 2005, (which instead represents an early formalisation of the first research on the subject), but in Saunders et al 1999 (https://www.ijcai.org/Proceedings/99-2/Papers/010.pdf).", "essential_references_not_discussed": "I would mention the second edition of Algorithmic Learning in a Random World (Vovk et al. 2023).\nLei et al. 2018 moreover specifies a very interesting results about merging multiple splits in Conformal Prediction, which triggers some questions (see below)", "other_strengths_and_weaknesses": "nothing of relevance", "other_comments_or_suggestions": "nothing of relevance.", "questions_for_authors": "I find the conclusions quite underwhelming. I appreciate the interesting work the authors have proposed, but fail to understand the practical implications of it. Is the method useful? In what situations? In what use cases? Please give more insights.\n\nI find this result contrasting quite strikingly with a result offered in Lei et al. 2018 (section 2.3). I wonder if you have something to comment on this.", "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": "zDUqvX7mvp", "reviewer": "Reviewer_BC25", "summary": "This paper proposes several new variants of (modified) cross-conformal prediction--called  e/u/eu-modified cross conformal prediction--that theoretically and empirically attain more efficient (i.e., smaller and thus more informative) prediction sets/intervals than the original (modified) cross-conformal prediction method, all while maintaining the same worst-case coverage guarantee ($\\geq 1-2\\alpha$, where $\\alpha \\in (0, 1)$ is the target miscoverage rate). These new methods and their guarantees are derived using new results on the combination of exchangeable p-values in Gasparin et al. 2024.\n\n## update after rebuttal\n\nI maintain my positive score--I appreciate the authors' clarifications, highlighting experimental results related to coverage variability, and discussion related to my question about recommendations on conditions for using which CP methods (which could be good to mention in the paper's discussion/conclusion). Although much of the theoretical analysis is mainly citing Gasparin et al. 2024, the contribution is solid, and with the paper's clear writing, it should be of interest to the community.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive and constructive comments on our paper. Please find below a detailed response to your questions.\n\n### Experimental Designs:\n- To improve clarity, we will add the target coverage level $1-\\alpha=0.9$ in the captions.\n- As index of variability, in Table 1, we report the maximum and the minimum of the empirical coverage observed over the 20 replications. A part of the table (which refers to LM) is reported below. The variability (see Range) is not so different for all the methods.\n\n|| mod-cross | e-mod-cross | u-mod-cross | eu-mod-cross | cross | split | split(2$\\alpha$) |\n|--|--|--|--|--|--|--|--|\n| Mean | 0.903 | 0.899 | 0.851 | 0.858 | 0.902 | 0.902 | 0.800 |\n| Min | 0.896 | 0.885 | 0.834 | 0.840 | 0.895 | 0.890 | 0.779 |\n| Max | 0.917 | 0.915 | 0.874 | 0.881 | 0.916 | 0.920 | 0.831 |\n| Range | 0.021 | 0.030 | 0.040 | 0.041 | 0.021 | 0.030| 0.052 ||\n\n- Some of the simulation studies report also the results of split conformal prediction with target coverage $1-2\\alpha$. This implies that the proposed variants (trained at level $\\alpha$) and split conformal prediction with target level $1-2\\alpha$ guarantee the same teorethical coverage (and this is equivalent of using $\\alpha/2$ to obtain coverage $1-\\alpha$). In Table 5, for example, the eu-mod-cross method is better in terms of size than split conformal prediction trained at level $2\\alpha$. (Standard) cross-conformal prediction at level $2\\alpha$ could be added; however, we expect smaller sets if compared to those of split conformal but with the same empirical coverage (as observed for the $\\alpha$ level). We discuss more on this in the first point of *Other suggestion*. \n\n### Weaknesses:\nSee the first point in *Other Suggestions*.\n\n### References:\nThank you very much for pointing out some relevant references. We will add them to the paper.\n\n### Other Suggestions:\n- Thank you for you comment. The question of which variant of cross-conformal prediction is to be preferred in practice is subtle: \n    - If one really needs to have a rigorous $1-\\alpha$ guarantee against the worst case distributions and unstable algorithms (for example, if there are downstream decisions that crucially depend on the provided theoretical guarantee), then it makes sense to run our new methods at level $\\alpha/2$. \n    - If one is only using conformal prediction as \"weak guidance\" for downstream decisions, and the user is somehow ok with violations of the target $1-\\alpha$, then we recommend running our variants of cross-conformal at level $\\alpha$ (where its worst case guarantee is $1-2\\alpha$ but it achieves coverage in between $1-2\\alpha$ and $1-\\alpha$). \n    - If the situation is in between, where conformal prediction is neither being used extremely rigorously, nor as loose guidance, but one wants $1-\\alpha$ coverage for \"typical\" datasets and algorithms, but is ok with both overcoverage and undercoverage for odd distributions/algorithms, then perhaps the original (modified) cross-conformal is best. \n    - If one does not tolerate over- or under-coverage of any sort, and really wants essentially exact $1-\\alpha$ coverage, then only split conformal delivers the goods. \n\n- We agree with this suggestion and we will revise the text accordingly to clarify the distinction.\n\n- Thank you for the suggestion, we will consider this change.\n\n- We will add the assumption of exchangeability within the theorem statements, as suggested. Example:\n\"*... . If data are exchangeable,*\n$$\nP\\left(Y_{n+1}\\in\\hat C_{n,K,\\alpha}^{\\mathrm{e-mod-cross}}(X_{n+1})\\right)\\ge1-2\\alpha.\n$$\n\n- Theorems 4.4 and 4.7 require that the p-values $P_1, \\dots, P_K$ be exchangeable (and the exchangeability of the p-values is shown in Theorem 4.2). However, the assumption of exchangeability is not necessary for proving Theorem 4.6. It is sufficient that $P_1, \\dots, P_K$ are valid p-values (i.e., $P(P_k \\leq \\alpha) \\leq \\alpha$), and this assumption is satisfied in the case of rank-based p-values. In fact, the rules $2 \\times \\text{mean}(\\mathbf{P})$ (used by Vovk et al. (2018) to prove the coverage guarantee for cross conformal prediction) and $2/(2-U) \\times \\text{mean}(\\mathbf{P})$ are valid under arbitrary dependence, which is a broader condition than exchangeability. We will clarify this in the text.", "claims_and_evidence": "Yes. Proofs are provided for the main theorems and sufficiently convincing experiments are provided on both synthetic data with an unstable algorithm and real data.", "methods_and_evaluation_criteria": "Yes. Sufficiently convincing experiments are provided on synthetic data with an unstable algorithm (ie, instability around d=80 is an “adversarial” case where is important to show coverage holds empirically) and on real datasets, supporting the provided coverage guarantees and claims about more efficient prediction sets.", "theoretical_claims": "Yes. I have made an effort to check the proofs and they appear to be sound--key steps largely cite results in Gasparin et al. 2024. The theorems provide coverage guarantees for the proposed methods (Theorems 4.4, 4.6, & 4.7) and demonstrate that the proposed methods are not more conservative (ie, prediction sets no larger) than the original cross-conformal method (Theorem 4.9).", "experimental_designs_or_analyses": "Mostly yes, I have reviewed the overall experimental setting described and they seem reasonable and reliable. Eg, the synthetic-data experiments are reasonably implemented with the same setting as Barber et al. 2021, where the algorithm is unstable around d=80 which makes for an important “adversarial” test case where it is good to verify coverage claims (and coverage appears appropriate). The real data experiments include standard tabular UCI datasets that are often used for evaluation in the conformal literature.\n\nSome suggestions: \n- It would be good to make it clearer in the figure captions or figures themselves what alpha is (ie, what target coverage is)\n- (Optional) It could be interesting/valuable to add an evaluation of coverage *variance*, ie how the coverage varies over different random draws of training/cal data.\n- (Optional) It could be interesting/valuable to add supplemental experiments comparing the proposed e/u/eu-mod-cross method run with target coverage *$\\alpha/2$* versus cross/split conformal run at target coverage $\\alpha$. That is, especially since the empirical coverage of the proposed methods may dip below the target level (ie in $[1-2\\alpha, 1-\\alpha]$), practitioners may wish to run eg the eu-mod-cros method targeting $1-\\alpha/2$ to ensure $\\geq1-\\alpha$ worst-case miscoverage. So, further discussion and evaluation of this would be useful.", "relation_to_broader_scientific_literature": "*Most relevant prior literature:* Cross-conformal prediction was originally introduced by Vovk (2015) with worst-case coverage guarantees of the form $1-2\\alpha - B$ (for some $B=2(1-\\alpha)(K-1)/(n+K)$ that becomes negligible for smaller numbers of folds, $K$); a simple modification was introduced in Vovk et al. (2018), which cites earlier work by Vovk and Wang (2012), to achieve a guarantee at $\\geq 1-2\\alpha$. Barber et al. (2021) also considers this “modified cross-conformal” method from Vovk et al. (2018) (to introduce a related cross-validation+ method). Gasparin et al. (2024) has results on combining exchangeable p-values that are used in this paper.\n\n*Contribution in context:* The proposed method improves the statistical efficiency of prior cross-conformal methods in that it empirically attains sharper (smaller and more informative) prediction sets, and theoretically the sets are no larger than original cross-conformal. The main proof steps are largely citing Gasparin et al. (2024).", "essential_references_not_discussed": "Essential references are discussed. A few further related works that could be relevant or interesting for the authors to look at or mention are given in the “Other Comments or Suggestions” section.", "other_strengths_and_weaknesses": "*Strengths:* The paper is very clearly written, and all claims are sufficiently supported with proofs and/or empirical evidence. The paper’s contribution is framed appropriately and can be useful for future progress on thinking about improving the efficiency of conformal prediction sets. \n\n*Weaknesses:* One limitation of the proposed methods is that--whereas the original (modified) cross-conformal methods typically have empirical coverage at or above the target level ($\\geq 1-\\alpha$)--the proposed methods seem to have typical empirical coverage that may be below the target level and closer to the worst-case guarantee, ie, $\\in [1-2\\alpha, 1-\\alpha]$ (eg, see Table 2). It would probably improve the paper to further discuss and/or evaluate this, and potentially to provide recommendations for how the proposed method should be used in practice: ie, should practitioners run the method targeting a more conservative level (eg, targeting $1-2\\alpha$) to achieve $1-\\alpha$ in the worst-case, or run targeting $1-\\alpha$, while acknowledging that empirically it appears more likely that the coverage will fall in $[1-2\\alpha, 1-\\alpha]$?", "other_comments_or_suggestions": "**Other refs that may be relevant/of interest to authors:**\n\n*Other ref using result of Vovk and Wang (2020) for combining conformal sets:*\n- Stutz, D., Roy, A. G., Matejovicova, T., Strachan, P., Cemgil, A. T., and Doucet, A. Conformal prediction under ambiguous ground truth. arXiv preprint arXiv:2307.09302, 2023\n- Couple refs on selecting conformal sets for efficiency:\n- Yang, Y. and Kuchibhotla, A. K. Selection and aggregation of conformal prediction sets. Journal of the American Statistical Association, pp. 1–13, 2021.\n- Liang, R., Zhu, W., & Barber, R. F. (2024). Conformal prediction after efficiency-oriented model selection. arXiv preprint arXiv:2408.07066.\n\n*Refs on related cross-validation style conformal methods (jackknife+ and CV+) under distribution shift (ie, extending the proposed methods to account for distribution shift could be an interesting future direction for the authors):*\n-  Prinster, D., Liu, A., & Saria, S. (2022). Jaws: Auditing predictive uncertainty under covariate shift. Advances in Neural Information Processing Systems, 35, 35907-35920.\n- Prinster, D., Saria, S., & Liu, A. (2023, July). Jaws-x: addressing efficiency bottlenecks of conformal prediction under standard and feedback covariate shift. In International Conference on Machine Learning (pp. 28167-28190). PMLR.\n\n\n**Other Suggestions:**\n- Related to “Weakness” mentioned before, it could be useful to add discussion about when the authors recommend practitioners to use one method or another. Eg, when/why would be recommended to use proposed methods at target $1-\\alpha$ (thus achieving $1-2\\alpha$ guarantee) versus at target $1-\\alpha/2$ (thus achieving $1-\\alpha$ guarantee).\n- It may be helpful to use language such as “target/nominal” coverage or miscoverage when referring to the user’s inputted $1-\\alpha$ or $\\alpha$, to more clearly distinguish from worst-case guarantee level.\n- Authors may want to consider slight modification to names of their methods: Eg, it’s understandable from reading the paper why they name one of their methods “exchangeable modified cross-conformal prediction (e-mod-cross),” ie because it’s attained using results on merging exchangeable p-values, but it may cause confusion, as sometimes standard CP methods are called “exchangeable CP” methods to refer to assumption of exchangeable data. Example slight modification could be “exchangeable p-value modified cross conformal (ep-mod-cross)”\n- It might be advisable to state exchangeability/IID as an assumption within the actual theorem statements themselves\n- End of proof of Theorem 4.6: When you state “holds under arbitrary dependence,” do you mean arbitrary dependence that still maintains exchangeability? If so, would be good to make this explicit to ensure avoiding confusion (understand may be implicit)", "questions_for_authors": "No major questions, see “Suggestions” for minor questions/comments. Congrats on a nice paper!", "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:

Meta-review: The paper presents novel methods for cross-conformal prediction that leverage exchangeable p-values and randomization to produce smaller and more efficient prediction sets while maintaining strong theoretical guarantees for worst-case coverage rates. The reviewers agree that the paper makes a significant theoretical and practical contribution, with rigorous proofs and empirical validation on both synthetic and real-world datasets. The methods also demonstrate computational efficiency, requiring fewer model runs compared to prior approaches.

While some reviewers initially suggested improvements, such as providing practical guidance on applying the methods and expanding real-world experiments, these concerns have been thoroughly addressed in the rebuttal. The authors have clarified the choice between targeting 1 − α and 1 − 2α, provided additional context for practical applications, and addressed questions about experimental design. These responses resolve the reviewers' primary concerns and strengthen the paper's overall impact.

Given the strong contributions, clear writing, and effective rebuttal, I recommend accepting the paper. The proposed methods represent a meaningful advancement in the field of conformal prediction and are well-supported by both theory and experiments.
Decision: Accept (poster)