Transductive Conformal Inference for Full Ranking
Authors: Jean-Baptiste Fermanian
Pierre Humbert
Gilles Blanchard
Venue: NeurIPS 2025 poster ()
Keywords: Conformal Prediction
Ranking Algorithm
False Coverage Proportion
Primary area: general_machine_learning
TL;DR: Conformal sets are constructed for the relative ranks of numerous items ordered by a black box algorithm.

Abstract: We introduce a method based on Conformal Prediction (CP) to quantify the uncertainty of full ranking algorithms. We focus on a specific scenario where $n+m$ items are to be ranked by some ``black box'' algorithm. It is assumed that the relative (ground truth) ranking of $n$ of them is known.  The objective is then to quantify the error made by the algorithm on the ranks of the $m$ new items among the total $(n+m)$. In such a setting, the true ranks of the $n$ original items in the total $(n+m)$ depend on the (unknown) true ranks of the $m$ new ones. Consequently, we have no direct access to a calibration set to apply a classical CP method. To address this challenge, we propose to construct distribution-free bounds of the unknown conformity scores using recent results on the distribution of conformal p-values. Using these scores upper bounds, we provide valid prediction sets for the rank of any item. We also control the false coverage proportion, a crucial quantity when dealing with multiple prediction sets. Finally, we empirically show on both synthetic and real data the efficiency of our CP method for state-of-the-art ranking algorithms such as RankNet or LambdaMart.

Transductive Conformal Inference for Full Ranking
Jean-Baptiste Fermanian
Pierre Humbert
IMAG, IROKO, Univ. Montpellier, Inria, CNRS, Montpellier, France jean-baptiste Seeaatiistte.frmmmmiaanniiia fermanian@inria.ft
LPSM, Sorbonne Université,
Paris, France
humbert@lpem paris
Gilles Blanchard
Université Paris Saclay, Institut Mathématique d' O'Orsyy,
Orsay, France
gilles. blancharddumivverstteeeeepa sarissssala-ssss-s-aaaaaaaa
Abstract
We introduce a method based on Conformal Prediction (CP) to quantify the uncer- tainty of full ranking algorithms. We focus on specific scenario where n + m items are to be ranked by some "black box" algorithm. It is assumed that the relative (ground truth) ranking of n of them is known. The objective then quantify the error made by the algorithm on the ranks of the m new items among the total (n + m). such a setting, the true ranks of the original items in the total (n + m) depend on the (unknown) true ranks of the m new ones. Consequently, we have no direct access to calibration set to apply a classical CP method. To address this challenge, we propose to construct distribution-free bounds of the unknown conformity scores using recent results on the distribution of conformal p-values. Using these scores upper bounds, we provide valid prediction sets for the rank of any item. We also control the false coverage proportion, a crucial quantity when dealing with multiple prediction sets. Finally, we empirically show both synthetic and real data the efficiency of our CP method for state-of-the-ae ranking algorithms such RankNet LarbdaMart.
Introduction
Ranking is a fundamental problem in machine learning where the objective is to sort some items, such documents or products, by their relevance query or user profile. It has a wide range of applications, ranging from document retrieval (Cao et al.) 2006). collaborative filtering [Liu and Yang 2008). sentiment analysis [Liu et al. [2017]. and product rating. These applications are grouped under the term preference learning [Fürkkranz et al. 2008). While there exist a lot of ranking algorithms in the literature (see e.g. [iu al. [009] for a review), the quantification of the uncertainty in their rank predictions using conformal prediction is relatively new [Angelopoulos et al.
2023a Xu et al.)
2024]. Indeed, so far, the design of ranking algorithms has mainly focused on the training phase and their evaluations regarding the uncertainty of their predicted ranking, is not often studied. With the increasing popularity of ranking methods (especially the learning-to-rant literature Liu et al., 2009), this evaluation is however mandatory step to deploy them for real-world applications.
Our main objective is quantify the uncertainty of ranking algorithms by constructing distribution free prediction set for the ranks of each items. Formally, given n m items with an underlying unknown total order, we want to construct prediction sets that contain the true rank of each item with high probability. We consider particular scenario where the first n items have known relative rankings, but their positions within the whole + m items are unknown. Furthermore, the remaining m items have no known ranking information.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

This scenario occurs for many problems. In matchmaking problem for instance [Herbrich et al. 2006 Alman and McKay 2017 Minka al. 2018], the m new items are new players entering the game that we want to rank among the previous players to organize matches between players with similar skills. In product rating, the m new items can be new products such as movies that we want to rank among those already known by a particular user for which we have his feedback. In these cases, we can assume that we have access to the exact relative rank of the n first items. We also consider the case where we want to combine an expensive ranking algorithm with cheaper but less reliable one (based, for example, on a smaller architecture). In this situation, we want to estimate the reliability of the cheaper algorithm compared to the costly one considered randomly select n items, rank them using the more efficient algorithm, and then use these rankings to quantify the uncertainty of the less efficient algorithm when it ranks the remaining items.
proxy truth. We can therefore
Formally, for each item [a + m]. we want to construct marginally valid set which contains, with high probability, its unknown rank R inside the n + m items:
IP R2 E C.) > al
where a E 10 is a desired miscoverage level. In addition, as we construct prediction sets for multiple points, we also want to control the false coverage proportion, which is the average number of mispredictions. More precisely, we want to construct m prediction sets (C. (C:) satisfying for some small [ > 0:
1 77
m
IR $
C.)
Ea
> 3.
There exist several methods to construct marginally valid sets in regression or classification settings. based on the so-called Conformal Prediction (CP) framework [Papadopoulos et al. [002 Vovk et al. 2005] Romano et al. 2019]. but these do not directly apply in this specific setting of ranking. Indeed, the problem of ranking can be seen as a regression problem where the outcome, the rank, depends on all the points observed, or as a classification problem with a moving number of classes. An important difference with a classical CP framework is that a calibration set is not directly accessible, knowing the relative rank of the n first items is not sufficient to know their ranks within the whole sample.
Contributions. This work constructs marginally valid prediction sets, satisfying Eq. [1 for the ranks of n + m items. We assume already having ranking algorithm (considered as a "black box") and knowing the exact relative ranks of n items. These n items will be used to quantify the uncertainty of the algorithm A. Our main contribution is to propose a general method for this calibration phase. The difficulty is that we cannot directly quantify the algorithm's 's error on the calibration set, as the true ranks are only known through the relative ranks. We then provide computable bounds of these ranks, supported by theoretical arguments, to construct valid prediction sets for which we also control the false coverage proportion. These findings provide a practical solution to the challenges of constructing valid prediction sets in ranking problems, where traditional CP methods face limitations due to the interdependence of ranks.
2 Background
2.1 Split conformal prediction
Conformal Prediction (CP) is framework introduced by Vovk et al. (2005] to construct distribution- free prediction sets quantifying the uncertainty in the predictions of an algorithm. Formally, given a calibration set {(x,, Yt) he] of points in X' x y' and an algorithm A, CP method constructs for new point X,+1 E X' a set & containing the unobserved outcome Yn-1 E y with high probability:
P(Y+11 E c(xx++1) > 1
In classification, y is the set of classes and A a classifier and in regression, y = R and A is regressor. The idea behind CP methods is to first build non-conformity scores Vú = s (X,, Y.) on the calibration set, where X x y - R, is a score function which is intended to quantify the error of the algorithm at a given point. Many score functions have been considered to catch different type of information, see e.g. Angelopoulos et al. 2023bb for review. In regression, common choice is to

---

use the absolute residual s(z, y) = ly A(z) where the algorithm A can either be trained on an independent sample (split conformal prediction, Papadopoulos et al. 2002) retrained on a subset of points (full conformal prediction Vovk et al. 2005). In this paper, we will focus on the case where an already trained algorithm provided, which corresponds the case of split CP. Then, for this score function and some integer k, the prediction set is
Cx = {u E s(x, & V(N).
(4)
where V(N) is the k-th smallest score of Ví . Vn, co. This set is marginally valid under mild assumptions presented in the following theorem.
Theorem 2.1 (Vovk et al. for any a (0, and k
2005 Lei et al. 2018). If the scores Vi,... V are exchangeable, then (n + I) the set (4) returned by the split CP method satisfies:
PP (Yn+e (x((xn+)) > a
We refer to Vovk et al. [2005] Angelopoulos et al. [203bb and Fontana et al. (2023) for in-depth presentations CP. See also Manokhin [2024) for a curated list of CP papers.
2.2 False coverage proportion
Some recent results have considered the transductive setting Vovk 2013 where conformal prediction sets are constructed for m 2 2 test points {(xn+i, Yn+s) J==1- )
this case, while maintaining the coverage guarantee (3) usual goal is to control the False Coverage Proportion (FCP) defined as:
FCP
1 m
Σ
m MfVYre & (((xnt))
where C(Xn++)) are some prediction sets. They can be constructed in Eq. 4 for instance. In words, the FCP is the proportion of observations in the test set that fall outside the constructed prediction sets.
the prediction sets are of the form 4 under the assumptions of Theorem 2. we have E FCP) < a.
Furthermore, the exact distribution of the FCP is known (Marques F. 2024 Huang al. 2024 Going further, Gazzn et al.) 2024) studied the full joint distribution of the insertion ranks of test scores into calibration scores, leading under the same assumptions
uniform control of the FCP. The asymptotic behaviour of the FCP in the form of a functional CLT has also been studied recently by Gazin [0024). With all these theoretical results, it is possible control in probability the FCP by adjusting the coverage of the prediction sets.
2.3 Related work in ranking
Given set of items the goal of ranking is to infer particular ordering over these items. There exist a multitude of settings and approaches to solve the ranking problem.
In the learning-to-ran tornk literature, and more specifically, in the pairwise approach, the ranking task formalized as classification of pairs of items into two classes: tuple is correctly ranked or incorrectly ranked. Herbrich et al. [1999] proposed an algorithm based on Support Vector Machine (SVM) called RankSVM to solve this elassification problem. Alternative techniques can be used such as boosting with RankBoost [Freund et al., 20033 Neural Network with RankNet [Burges et al. 2005], random forest with LambdaRank [Burges et al. 2006) and LambdaMart [Wu et al. [2010] (see Burges 2010 Qin et al. 202 overview). Other methods based on the pointwise or listwise
approaches are also widely study [Cao et al., 2007 Liu et al. 2009
2011].
Another line of research solve the ranking problem through binary comparisons of items. The different settings considered allow these binary comparisons be measured either completely at random WWauthier et al. 2013). actively [Ailon] 2012, Heckel et al. 2019). several times [Negahban et al. 2012 Feige et al. 1994). They can also assume that the possible comparisons between the items are known but up some noise [Braverman and Mossel 2007 2009 A significant body of literature also focuses on the problem uncertainty quantification in ranking problems under
the Heelley-Terry-Lune model (Bradley and Terry 1952
Luce et al. 1959). For instance, Liu et al.
3

---

consider the BTL model and infer its general ranking properties. Gao et al. [2023 and Fan a.. 2025] study the maximum likelihood estimator and the spectral estimator to estimate the parameters of the BTL model, enabling them to construct confidence intervals for individual ranks.
2023
However, the quantification of uncertainty of these ranking algorithms has been little studied in CP framework. Recently, |ngelopoullss et al. [2023a] have developed CP method for quantifying the uncertainty of learning-to-rait to-rank algorithms specially tailored for recommendation systems. Xu et al. [2024) also proposed to use CP, but for the ranked retrieval task. While related to the present work, they do not consider the same setting.
3 Conformal prediction for ranking algorithms
We now describe our setting, as well as our methodology to provide valid prediction sets.
Notation: For point y in R and finite subset 'D C IR, the rank of y in DD is R(y, D) E:ED l > 2} For an index < i & [D], if D has no ties, we denote the point of D of rank i by R (i, == E:ED (R(2,, D) = i). A multiset (or bag) will be denoted ?-} and is an unordered set with potentially repeated elements.
3.1 Setting
Let us consider n + m items, each associated with a pair (X,, Y2) E X R. We suppose that these items are divided into two sets: a calibration set of size n, {(x,, ri) and test set of size m, {(Xn+i; Yn++) )e+ se] For any item X; is, for instance, a vector of features, while Y, allows to properly define its true rank within each subset or the entire set through the following variables:
RC = (Y: R² (V RØ+* = R(Y.:(73//4/+mm) RR + R
We assume throughout the paper that:
Assumption 3.1. The vector (Y]) is exchangeable and has no ties. In particular, this implies that there is a total order between the n + m items.
The values (Yt); can be interpreted as an unobservable underlying truth. our setting, we insist that only the features (X;) and the true ranks of the calibration points [R]) are observed. For example, they can model the intrinsic skill of some players only observable by comparing them with each other. Assumption 1 is needed to model correctly assumption is essential to be able to construct conformal prediction sets for the ranks.
problem of full ranking. The following
Assumption 3.2. The vector (X,, 1255 )e[[nm]] is exchangeable.
To estimate the true ranks R ..... n+mm we assume that we have access to an algorithm A X' x 2 + K which is intended to predict the rank of point inside set of points. Its inputs are the target item and the multiset of items among which it seeks to sort it. For clarity, when there is no confusion, we will sometimes omit the dependence in the multiset of items: A(x) == A(x, Zæz This algorithm can predict for each point either rank or a value from which rank can be deduced. For these two situations, we propose two conformity score functions which quantify the error made by A in its ranking:
(RA) setting: K N. the rank is directly predicted by the algorithm A: Rett =
A (Xx, (X,,2X (85)e))+))))) this situation, we can consider the classical residual scores, i.e, for
x, (xg)y in X' and N:
RA (z, r, (z,,,) = 1r
This is simply the absolute difference between and the predicted rank of x inside (1z)5- (VA) setting: K IR, the predicted rank deduced from values constructed by the algorithm A:
Ret = RRA((X, (2x, )
(((x,,

---

Here, because A(x) is a real value, we consider more refined score function than RRA, for x, (z))g in X and N VA (a, = (r.iAA((() - A(x)
This score quantifies the distance between the value attributed by the algorithm the point x and the value it should have had to be at rank r. We restrict ourselves to these two scores for our experiments, but methodology and theoretical results more generally valid for any score function s(x, T, (z)
Remark 3.3. The fact that the algorithm depends on the multiset rather than an (n + m))mmm)ttu -uuple is important, as it implies that the algorithm treats the points exchangeably. With Assumption 3.2 the vector (e(X)))eEn+mll is thus exchangeable.
Remark 3.4. By considering the predicted ranks scores, Moreover, as in (RA), R (r, (r,,)))))))))) r, VA reduces to the residual function gRA,
that (RA) is sub-case of (VA).
3.2 Methodology and main results
We now introduce our main theoretical results construct prediction sets for the ranks R9 ..... Ratm- Recall that our objective is to build for j E [n + m]] a marginally valid set č for Rott, i.e satisfying Eq. (T) for a given (0, 1). As we construct multiple prediction sets, we also provide control of the FCP (5).
To construct these sets, natural strategy is to calculate the quantile of order of the scores s(X,, R&5 (A(X)))se
computed on the calibration set as this is done in the split CP method
(see Section 2.1b. However, these scores depend on the quantities { (R2+*) Jie[m]] which are unknown. Consequently, they are not computable and we must find another strategy. The following result shows
that, if we can bound the ranks of the calibration (R!**) jefin] with high probability, then it is possible
to construct marginally valid sets for the test ranks { fe
Theorem 3.5. Let a E (0,1), 5 < and RT R E R (i E [m]] be random variables depending on (X,, Ri)et( and satisfying
P(vi E [n] R E [R] R(1)) > 1 1- 8.
(6)
Let us define the proxy scores for [n]:
; max (XX
EE [R
and the associated conformal prediction set:
(X: & Swm) S(s) being the k-th smallest proxy score in . Sn. If Assumption 3.1 is satisfied, then for k: = a + 8) + 1)] and any [m]:
(x(x)
(8)
PP (Rett E (X > a
For the score functions ,RA and & VA the proxy scores of Eq. ? and the associated conformal sets have explicit expressions which make them easy to compute. Example 3.6 (s = RA). The maximum is necessarily attained at the edges of the interval [R RR+
RA (I, = max( A(x, A(z, - A(z,(
rE rE(R- RR+)
The associated conformal set is (x) =
+ S(m)
Example 3.7 (s s VA). Similarly as the previous example, the maximum is attained at the edges of [R R+]
VA VA (z. (x,r, rE(R .RI
( (r,22A((0)))))
max re(R RR)
max
5

---

The corresponding conformal set is then the interval
CVA
S(a), (() (A(())(()))))))(( + Suo,
We see that contrary to the conformal intervals CRA which have the same length for any point the length of the conformal interval @VA can vary depending the amount of points around A(x).
The following result gives control in high probability of the false coverage rate the test sample.
Proposition 3.8. Let E (0.1) and consider the prediction sets Cg defined in Eq. (8) Assume Assumption 3.2 holds, let = [(1 an + 1)1, then with probability at least 1
n $ (Xnts)) & a Anm
(9)
m
where Anm
log C
Tn.m
Tn.m
nm
and C 2 works.
Tn.m
n + m
When the sample sizes increase, then An.m - and the average error on the test sample is at most a. In practice, using a' = An. to control the FCP at level is too conservative. We instead use the numerical procedure explained by Gaazn et al. [2024, Remark 2.6] to find a sharper but implicit value for A.,m. They use the exact distribution of the FCP to adjust the level of each set accordingly, in order to control (see Appendix for details).
3.3 Alternative targets
In the previous section, we focused on the construction of prediction sets for the ranks of test points within the entire data set. In this section, we discuss how to derive from this initial construction. predictions sets for alternative targets. More details are provided in Appendix B
Calibration points. To obtain predictions sets for the calibration points, can directly the high probability bounds 66) on which our method built. Indeed, by construction the sets [R, R
contain R2 and have a null FCP with probability at least 1 - 5 for E [Tx]]-
Rank among the test points. A user might also be interested in the ranking of the test points among themselves, rather than within the entire data set. Such sets can constructed directly from the previous sets (8). by substracting the number of calibration points of smaller rank to each interval boundary (see Corollary B.I).
Top-K items. It is also possible to target the top-K items by selecting all items whose associated prediction set includes least one rank smaller than or equal This strategy can be sufficient we target a "top" proportion of the items (see Corollary B.2).
Rank of the calibration points
To make our method complete, it remains to find R. and R satisfying Eq. (6) Let us recall that R R + R Hence, we know that R e [R, RC + m] and we can use Theorem 3.5 with R = RR and R = R m. However, using these bounds for instance with the residual conformity function ,RA, will increase the length of the conformal set (x)) by m. In this section, we show that is possible to find theoretical bounds and practical bounds satisfying Eq. (6) that do not excessively increase the length of the final conformal sets.
4.1 Theoretical bound
As the calibration and test values (Y:)se [m]] are exchangeable (Assumption 3.1 that calibration point with low rank in the calibration set will have low rank in the test set. The following proposition justifies this intuition.
we can expect
Proposition 4.1. Under Assumption for 8 (0, 1):
P R E [R. Rt n [n mI, [n]]] >

---

where RT= R (m 1)
R a
log(Cy/ran m6/
Tn,m
and C 4v2 works.
Tm.m
n2 + m
The proof can be found in the supplementary and relies on Gazin et al. [2024] Theorem 2.4]. While the naive method provides an interval of length m for the rank RT our approach achieves interval of length (m// /T,,)) The length has been thus reduced by factor vTn.m = min (Vn, vm).
This explicit theoretical bound provides qualitative insight into the behavior and evolution of the ranks with (m. n2) However, the constant not tight (see Figure 1 To obtain finer envelopes, we propose the following numerical method calibrate them, with theoretical guarantee (Proposition 4.2).
4.2 Numerical bounds
Linear Quantile
500
The explicit bounds given by Proposition 4.1 often too conservative in practice. In this section, we construct sharp numerical bounds RT, R for the ranks RG+ such that the event
Theory
400
300
(A ViEjs & R9- is between RT and R
holds with high probability. Let us denote for E [n]], (e()) the rank the whole sample of the item of rank in the calibration. In partic- ular, (R) RT Our idea is to use that the random vector R = (R ...... R(,)) fol- lows universal distribution independent of the distribution the data to simulate them and to estimate envelope.
100
0 10 20
30
40
50
Rf
Figure 1: The two envelopes for n 50, 500, = 0.1 and K = 10 The blue and red lines are respectively the linear and quantile envelopes, and each black curve an ordered realization of Ro+t
The green line is the envelope from Prop. 4.1
This distribution can be drawn using Algo- r thanks to the exchangeability of the data
Algorithm 1 Simulation of Rest
(Assumption 3.1] see[aazin et al., 2204 for more details). An envelope can then be estimated by a Monte- approach using the empirical cu- mulative distribution function. We consider two
1: Draw n + m uniform random variable U, on
[0. 1].
2: for 1.....,, do
3: Rott RU
forms envelope in this work, the linear and the quantile detailed below, which are parame- terized by real factors e and 7. To estimate these
4: end for
5: Output: Sort Re-t
envelopes, draw K realizations of vectors following the same distribution (Rat() by repeating K times Algorithm]] | and estimate the (multidimensional) cumulative function of this sample. Then, optimize the parameter or y for minimizing the width of the envelope (which depends directly on this parameter) while containing a proportion 5 of the K trajectories.
Linear envelope: We consider envelope of the form of Proposition 4.1
R +
R
=
(m + 1)
where is minimized under the condition that a proportion (1 - 8) of the generated vectors are the envelope. We then take the minimum with n + and the maximum with to keep the bounds in [n + mm.
Quantile envelope: For an item of rank r = R we propose to choose the bound R (respectively RT) as the empirical quantile of order - 7 (resp. 7) of the simulated ranks nett, i.e. the ranks in the whole sample of the points of rank in the calibration. As want uniform control of these bounds, we need to adjust y Hence, the parameter y is maximized under the condition that a proportion of the generated vectors are in the envelope. Algorithm 2 in Appendix C givee the full process to construct this envelope.
As it can be observed in Figure the quantile envelope is smaller for the low and high rank points while the linear envelope smaller for the points of medium rank, Furthermore, they both outperform the theoretical envelope.

---

RankNet (m 500)
RankNet (m 500)
0:15
0.6
Relative length
0.10
0.4
0.3
22
0.00
0.2
100
500
2500
100
500
2500
(RA)
TCPR Lenv
TCPR Lenv
Figure 2: Synthetic data: FCP and relative lengths obtained for RankNet with the (RA) and (VA) score, for the quantile (Qenv) and linear (Lenv) envelopes when m = 500 and n E {100, 500, 2500). White circles represent the means.
Monte-Carlo guarantees: The estimation of the envelopes brings another source of error in our procedure. In the following proposition, we show that this error can be easily controlled and the parameter K can be chosen large enough make it negligible.
Proposition 4.2. Let K,n,m m N and (R(K) ]E[K]] K-sample of ordered ranks drawn from Algorithm with parameters and m. If (Rt )aE[n] is an estimated envelope, possibly depending on (I(())) & such that, almost surely K E 1 Di: (k) $ [ [ & &8, then:
log nK
PP Pivi: R
R Rtg
3 1 4v
(10)
The proof is given in Appendix A.5 Notice that this result is not specific to the linear or the quantile envelope we consider but rather the Monte-Carlo procedure itself. It indeed based control of the multi-dimensional empirical cumulative distribution function from Naaman 202T
5 Experiments
In this section, we empirically evaluate the performance of our CP method referred to as Transductive CP for Ranking (TCPR) on different datasets and algorithms. We construct prediction sets using the score function s RA or s VA and with the linear or the quantile envelopes described in Section 4.2 We compare ourselves to the Oracle method, which is the conformal method using conformitt scores
calculated with the unobserved true ranks (R++)) 1
This comparison allows for an evaluation of ]i[["]]
the effect of the envelope.
The code of our method is available at www.-ee-ooooooooaaaaaaeeeeeeeeee for-ranking
Ranking algorithms: We use the experiments the following algorithms: RankNet [Burges et al.,
2005). LaRTdaMART [Wu et al.) 2010) and RankSVM (Herbrich et al.) 1999]. These methods learn score function of the features from pairwise comparisons. In Appendix, we also use
Balanced Rank Estimation (BRE) (Wauthier et al. 2013 which ranks items using limited number of comparisons.
Parameters:
The parameters a, 1 1 8 and ô, equal to respectively, the probability of miscoverage, the probability control the FCP at level a, and the probability of the quantile envelope, are set to, respectively, 0.1, 0.75 and 0.02, in all our experiments.
Metrics:
We use the following metrics evaluate method. 1) The FCP of the new ranks (Eq (5)). 2) The relative length of the prediction sets defined as the average size of the sets divided by n + m.
3) The oracle ratio defined the ratio between the size of the set from TCPR and from the oracle.
Some metrics are not presented in this section and can be found Appendix [ with additional information on the data sets and the algorithms, such their hyperparameters and architecture.

---

RankNet
RankNet
1000
TCPR (RA)
1000
TCPR (VA)
Oracle (RA)
Oracle (VA)
800
800
600
600
200
200
0
200
400
600
800
1000
200
400
600
800
1000
R345
Rg1)
Figure 3: Data from Section
True ranks R in function of their predicted rank R by RankNet and their prediction sets with scores RRA and VA for n m 500.
5.1
5.1
Synthetic data
Data generation: We use the same generation process as Pedregosa et al. [2012] with slight modifications match our setting. In detail, draw + m pair of points (X,, Y,) where X; is Gaussian vector (0,, La) of dimension d = 5. Y, = (1 + exp(-w" X.)) + with w ~ NO La) and 6; (0, 0.07). The rank R& of an observation is defined as the rank of the corresponding Y,. The sizes of the calibration and test pair (n, m), we compute the FCP and the relative length on B = 1000 generated data sets.
are chosen among n, E { {100, 500, 2500} and for each
Results: Figure Saaureeeaa displays the FCP and the relative length for RankNet with the score function s gRA or s VA and the two proposed envelopes when m 500. Results for other values n and m and for LambdaMART, RankSVM and BRE in Appendix D
We first remark that the FCPs are correctly controlled by our method as they remain below a at least 100 (1 3y% 75% of the time, as indicated by the upper boundary of the boxes. It is important to note, however, that due the necessity using proxy scores, our method tends be conservative for small values of n. For example, when = 100, we see that the FCPs obtained with TCPR are close to whereas those obtained with oracle method are in average near 0.07. Nevertheless, this conservatism diminishes the calibration size increases with FCPs close to 0.1 when n = 2500. In terms relative length, the prediction sets constructed using the quantile envelope are, average, consistently smaller than those obtained with the linear envelope for FCPs closer to 0.1. The quantile envelope is therefore preferable. Finally, notice that, at least for RankNet, using RA s VA gives sets with similar sizes.
Adaptivity of score s VA. To further highlight the adaptability of score VA relatively to s R.A. we consider another data set of size m 500. Each pair (X,, Y;) is defined by Y; X, + E; where X; ~ Betatete .04, .04) and ~ .N00. Here, because the random variables (X,); follow a Beta distribution with parameters lower than 1, the probability of observing a value near
is much larger than the probability of observing value near 0.5. As there is more observations close to these values, RankNet ranks with more difficultly the observations near 0 or 1 than the others. However, as the prediction sets constructed with , ,RA have all the same size, they do not reflect this difficulty (see an example in Figure left panel). On the contrary, the sets returned with VA are narrower when ranking is easier (close to 500 0.5 (n + m)) and wider for small and large ranks (Figure right panel).
5.2 Real data: Yummly-10k
Dataset:
We evaluate our approach on the Yummly Food-10k data which consists in 12624 images of dishes embedded in R001 These embeddings have been constructed to reflect similarities taste among the dishes (see Wilber al. 2015 for complete description).
Ranking task: As in Canal et al. [2019, to define full order of these items, we select an (unknown) preference point x* and detine this ordering using the distance this point. The (Yi); are thus these distances. We use RankNet, LambdaMART, and RankSVM to rank the dishes and our method
CCopaaioo website:

---

Rank error
FCP (RA)
RL. (RA)
OR (RA)
(CP(VA)
(VA)
OR (VA)
RankNet
675.9
0.069 1: 0.005
0.306 1 0.003
1.095 1 0.003
0.069 1. 0.005
0.312 1: 0.003
1.104 1. 0.005
LART
714.8
0.072 + 0.004
0.324 4 0.003
1087 + 0.005
0.071 + 0.005
0.323 + 0.003
1.089 0.004
R
751.3
0.076 0.003
0.400 0.004
1.044 0.003
0.071 0.004
0.408 + 0.004
1.079 0.005
Table I: Results on the Yummly-108 data set. RL for Relative Length and OR for Oracle Ratio.
LambdaMART(S. 50)
LambdaMART(20.. 300)
16000
16000
(RA)
(VA)
12000
12000
8000
8000
4000
4000
(RA)
(VA)
1
4000
8000
12000
16000
4000
8000
12000
16000
R,11
Figure 4: Ranks predicted by LambdaMART((eaves,, trees) in function of the ranks predicted by a larger model of 400 trees of 20 leaves.
TCPR with the quantile envelope to construct the prediction sets. We divide the data into training, calibration and test sets of respective size f45 = 2624, = 2000 and m 8000. We repeat this splitting 10 times to compute the metrics.
Results: Table reports the values of the different metrics. Firstly, all methods are well-calibrated with FCP consistently remaining below the chosen threshold 0.1. Secondly, the size of the intervals decreases as performance improves, as reflected by the rank error and the relative length metrics. The impact the envelope is reflected in the ratio with the oracle. This impact negligible the ratio remains close to 1. We can however notice that it increases as model performance improves. Indeed, the more effective the algorithm, the more the error introduced by the envelope becomes noticeable and impacts the size of the prediction set. Additional results are given in Appendix E.
5.3 Real data: Anime recommendation LTR data set
Dataset and ranking task: This dataset is composed of features of 16681 movies, characteristics of 15163 users and 10" ratings associated with a tuple (user, movie) with values ranging from 0 to 10. Given the characteristics of new user, the objective is to produce ordered list of all the movies ranked by the user's level of interest. We aim to quantify the uncertainty of a smaller model relative to the performance of a larger one, which serves as reference and defines the ground-truth full ordering of the items, i.e., R2 More details are provided in Appendix E.2
As shown in Figure 4 the size of the prediction sets for both (RA) and (VA) decreases as the model quality improves. In particular, LambdaMART (leaves=20, trees=300) yields results that closer to those of the larger model (LambdaMART with 20 leaves and 400 trees) than the smaller ranker (I (LambdaMART with 5 leaves and 50 trees). This approach has the advantage of allowing for easy comparison between the two methods without requiring the large model to be movies which can be expensive. We can also point out again the better adaptivity of the score VA The metries and comparisons with other architectural configurations are presented in Appendix E.2
Results:
all
6 Conclusion
We have developed a conformal prediction method that quantifies the error of an algorithm ranking m new items among n previously ranked items. Our approach is based on constructing an envelope around these ranks to quantify the algorithm's error. Both theoretical and empirical evidence demonstrate that this envelope does not significantly impact the size of the intervals, especially when is large relative to m. One limitation of our work is that we only focus on full ranking. It would therefore be interesting to extend our method to partial ranking framework. Another important line of research would be cover top-k algorithms. Finally, the dependence of our method on the choice of the envelope we select should be investigated. We expect that choice more adapted the problem considered could improve the size of the prediction sets.
10

---

Acknowledgements
The authors acknowledge Ulysse Gazin and Etienne Roquain for helpful comments. G.B. gratefully acknowledges funding from the grants ANR-21-CE23-0035 (ASCAI), ANR-19-CHIA-0021 (BISCOTTE) and ANR-23-CE40-001844 (BACKUP) of the French National Research Agency ANR. P.H. gratefully acknowledges the Emergence project MARS of Sorbonne Université.
References
Yunbo Cao, Jun Xu, Tie- Yan Liu, Hang Li, Yalou Huang, and Hsiao- Hon, Adapting ranking svm to document retrieval. In Proceedings of the 29th anmual international ACM SIGIR conference on Research and development in information retrieval, pages 186-193, 2006.
Nathan N Liu and Qiang Yang. Eigenrank: a ranking-oriented approach to collaborative filtering, In Proceedings of the s1 annual international ACM SIGIR conference on Research and development in information retrieval, pages 83 83-90, 2008.
Yang Liu, Wun Bi, and Zhi-Ping Fan. Ranking products through online reviews: A method based on sentiment analysis technique and intuitionistic fuzzy set theory. Information Fusion, 36: 149-161, 2017.
Johannes Fürnkranz, Eyke Hüllermeier, Eneldo Loza Mencía, and Klaus Brinker. Multilabel classifi- cation via calibrated label ranking. Machine learning, 73:133-153, 2008.
Tie-Yan Liu al. Learning rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3(3):225-33 13, 2009.
Anastasios N Angelopoulos, Karl Krauth, Stephen Bates, Yixin Wang, and Michael Jordan. Recom- mendation systems with distribution reliability guarantees. In Conformal and Probabilistic Prediction with Applications, pages 175-193. PMLR, 2023a.
Yunpeng Xu, Wenge Guo, and Zhi Wei. Conformal ranked retrieval. arXiv preprint arXiv:2404.17769, 2024.
Ralf Herbrich, Tom Minka, and Thore Graepel. Trueskill a bayesian skill rating system. Advances in neural information processing systems, 19, 2006.
Josh Alman and Dylan McKay. Theoretical foundations of team matchmaking. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 1073-1081, 2017.
Tom Minka, Ryan Cleven, and Yordan Zaykov. Trueskill 2: An improved bayesian skill rating system. Technical Report, 2018
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Machine Learning: ECML 2002: 13th European Conference Machine Learning Helsinki, Finland, August 19-23, 2002 Proceedings 13, pages 345-356. Springer, 2002.
Vladimir Vovk, Alexander Gammerman, and Glenn Shafer. Algorithmic learning in random world.
Springer Science & Business Media, 2005.
Yaniv Romano, Evan Patterson, and Emmanuel Candes. Conformalized quantile regression. Advances in neural information processing systems, 32, 2019.
Anastasios N Angelopoulos, Stephen Bates, et al. Conformal prediction: A gentle introduction. Foundations and Trends in Machine Learning, 16(4):494-50 591, 2023b.
Jing Lei, Max Gelll, Alessandro Rinaldo, Ryan Tibshirani, and Larry Wasserman. Distribution-free predictive inference for regression. Journal of the American Statistical Association, 113(523): 1094-1111, 2018.
Matteo Fontana, Gianluea Zeni, and Simone Vantini. Conformal prediction: a unified review of theory and new challenges. Bernoulli, 29(1):1-23, 2023.

---

Valery Manokhin. Awesome conformal prediction.
https:// www.ggttttooommeoeeeeooo www.coommllaaaaaa valeman///
awesome- conformal - predictionnnnnnn 2024. Github repository.
Vladimir Vovk. Transductive conformal predictors. In Artificial Intelligence Applications and Innovations: 9th IFIP WG 12.5 International Conference, AIAI 2013, Paphos, Cyprus, September 30-October 2, 2013, Proceedings 9, pages 348-360 Springer, 2013.
Paulo C. Marques F. Universal distribution of the empirical coverage in split conformal prediction. arXiv preprint, 2024.
Kexin Huang, Ying Jin, Emmanuel Candes, and Jure Leskovec. Uncertainty quantification over graph with conformalized graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Ulysse Gazin, Gilles Blanchard, and Etienne Roquain. Transductive conformal inference with adaptive scores. In International Conference Artificial Intelligence and Stufistics, pages 1504- 1512. PMLR, 2024.
Ulysse Gazin,
Asymptotics for conformal inference. arXiv preprint 2rXivv2409.12019, 2024.
R. Herbrich, T. Graepel, and K. Obermayer. Support vector learning for ordinal regression. In 1999 Ninth International Conference on Artificial Neural Networks ICANN 99. (Conf. Publ. No. 470), volume 1, pages 97-102, 1999. doi: 10. 1049/cp: 19991091.
Yoav Freund, Raj Iyer, Robert E Schapire, and Yoram Singer. An efficient boosting algorithm for combining preferences. Journal of machine learning research, 4(Nov):933 (9M9999933-969 2003.
Chris Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Greg Hullender. Learning to rank using gradient descent. In Proceedings of the 22nd international conference on Machine learning, pages 89 96, 2005.
Christopher Burges, Robert Ragno, and Quoc Le. Learning to rank with nonsmooth cost functions. Advances in neural information processing systems, 19, 2006.
Qiang Wu, Christopher JC Burges, Krysta M Svore, and Jianfeng Gao. Adapting boosting for information retrieval measures. Information Retrieval, 13:254 270, 2010.
Christopher JC Burges. From ranknet to lambdarank to lambdamart: An overview. Learning, 11 (2,1581):81, 2010.
Zhen Qin, Le Yan, Honglei Zhuang, Yi Tay, Rama Kumar Pasumarthi, Xuanhui Wang, Michael Bendersky, and Mare Najork. Are neural rankers still outperformed by gradient boosted decision trees? In International conference on learning representations, 2021.
Zhe Cao. Tao Qin, Tin-Yan Liu, Ming-Feng Tsai, and Hang Li. Learning to rank: from pairwise approach to listwise approach. In Proceedings of the 24th international conference on Machine learning, pages 129-136, 2007.
Hang Li. A short introduction to learning to rank. IEICE TRANSACTIONS on Information and Systems, 00(1))((11))))) 18111)):8844881 186--862,21111181111111111112118 2011.
Fabian Wauthier, Michael Jordan, and Nebojsa Jojic. Efficient ranking from pairwise comparisons.
In International Conference on Machine Learning, pages 109-117. PMLR, 2013.
Nir Ailon. An active learning algorithm for ranking from pairwise preferences with almost optimal query complexity. Journal of Machine Learning Research, 13(1), 2012.
Reinhard Heckel, Nihar B. Shah, Kannan Ramchandran, and Martin J. Wainwright. Active ranking from pairwise comparisons and when parametric assumptions do not help. The Annals of Statistics, 47(6):3099-3124 2019.
Sahand Negahban, Sewoong Oh, and Devavrat Shah. Iterative ranking from pair-wise comparisons. Advances in neural information processing systems, 25, 2012.
12

---

Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on Computing, 23(5):1001-1018, 1994.
Mark Braverman and Elchanan Mossel. Noisy sorting without resampling. ACM-SIAM Symposium on Discrete Algorithms, 2007.
Mark Braverman and Elchanan Mossel. Sorting from noisy information. CoRR, abs/0910.1191, 2009.
Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4))324-345, 1952.
Duncan Luce al. Individual choice behavior, volume Wiley New York, 1959.
Yue Liu, Ethan Fang, and Junwei Lu. Lagrangian inference for ranking problems. Operations research, 71(1):202-223, 2023.
Chao Gao, Yandi Shen, and Anderson Y Zhang. Uncertainty quantification in the bradley-tery- model. Information and Inference: Journal of the IMA, 12(2):1073-1140 2023.
Jianqing Fan, Zhipeng Lou, Weichen Wang, and Mengxin Yu. Ranking inferences based on the top choice of multiway comparisons. Journal of the American Statistical Association, 120(549): 237-250, 2025.
Michael Naaman. On the tight constant in the multivariate dvoretzky wieffr-ieffffoooeeee inequality. Statistics & Probability Letters, 173:109088 2021.
Fabian Pedregosa, Elodie Cauvet, Gaël Varoquaux, Christophe Pallier, Bertrand Thirion, and Alexan- dre Gramfort. Learning to rank from medical imaging data. In Machine Learning in Medical Imaging: Third International Workshop, MLMI 2012, Held in Conjunction with MICCAI 2012, Nice, France, October 1, 2012, Revised Selected Papers 3, pages 234-241. Springer, 2012.
Michael Wilber, Iljung S Kwak, David Kriegman, and Serge Belongie. Learning concept embeddings with combined human-machine expertise. In Proceedings of the IEEE International Conference on Computer Vision, pages 989-989, 2015.
Gregory Canal, Andy Massimino, Mark Davenport, and Christopher Rozell. Active embedding search via noisy paired comparisons. In International Conference on Machine Learning, pages 902-911. PMLR, 2019.
Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz. Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, pages 642-669, 1956.
A Paszke. Pytorch: An imperative style, high pegeomerformacce deep learning library. arXiv preprint 191iv: 2019.
13

---

Appendix
A Proofs
A.1 Proof of Theorem 3.5
Let us denote Es (Vi E [n] nett E [ On the event Es, for all i E [n]] we have:
ST == sX,, Rot,, (X+)Re(ntm)) < max s(X,, r, (Xx) == S.. re(R, RR
Hence, the quantiles of the "true" scores Strue upper bounded by the quantiles of the proxy scores [St i... for & E [n]:
Strue S(k)
(1I)
Then, for E [m]]:
(Rsts & ((Xn+i)
& Roti & ((Xn+)) n Es) P(E)))
< P(ssXnnts Retts (X, (X))sE(n-m)) > S(k) n Es) + F(E))
< IP (P(s(Xntrr Ro (Xz)je(n=m) Strue
+ < a + a
To pass from the second to the third line, we have used 11 which is satisfied on the event Eg. The last inequality is obtained using that if the score function s(x, F; (xz))) is invariant by permutation of its last argument and the vectors (X;, (E,,R+)))eeeee exchangeable. Therefore,
(++*))een+m) ><[[n+m] exchangeable, then the scores {Strue Jie[m] use Theorem 1 with & = (n 1)(1 + 6)].
A.2 Restatement of Gazin et al. 2024, Theorem 2.4]
We restate here Theorem 2.4 of Gazin et al. 2024 which controls the empirical cumulative distribu- tion function of conformal p-values.
Theorem A.1. Let n, 2 2, Vi,..., Va+m be exchangeable real random variables having no fies
almost surely. Let us. for 1 < n, define the conformal p-values:
1
P
1
1[V,
Vn+s}
(12)
and (t(t) == n- Ei= Hp < tt be their empirical cumulative distribution function. Then, for 3 1);
log(1/8) + log(1 + 2
IP sup [E(D,1]
(t(t) -m)()) >
28
(13)
2Tn.m
where Tn,m
and Tm (1) 1(m + 1)t]/mm+11)
Proof. The concentration inequality is obtained from Gazin al. 2024 Theorem 2.4]. The lower deviation was enounced in its proof (Fquation (38)). We apply the theorem with r = and upper bound mm /vn m by /n.m/
V (1) = LA [og[(13) + log(1 2 2F..m
log(1/3) + log(1 + 2 Fn,m
vn+mm
2Tn.m
2Tn.m
log (2 2
2Tn.m
The first term is the deviation obtained by Gazin et al. (2024). The first upper bound the one appearing in equation 13) The second upper bound is used to get Proposition 3.8
D
14

---

A.3 Proof of Proposition 3.8
On the event {Vi E [nd] R E [R R$]} we have:
Stru == s (X,, R,t, (Xx)ReIntm)) < max s (X,,r, (Xx))e(n+m)) = S
re(R; .Rā]
Hence, as earlier the quantiles of the "true" scores Strus are upper bounded by the quantiles of the proxy scores (Si)se[n) i.e., for all l E [n]]
(8) < S(k)
(14)
Then, on this event:
m
m 1
E1{ R & Cg (X = Σ
(S > S(z) &
Σ
Strue nt
Strue (R)
(15)
the true scores have no ties, we can directly apply Thcorem A.I to obtain a control of the FCP. The following technical details allow control it in the case where the score function is discrete, for instance when 8 = ,RA. Let us introduce
min Eitjsn Stow SS
Strue
Stru
and an independent family of random variables % for E [n + m] (also independent of (Strue) ]e][n-m]] following a uniform distribution on (-I/2,1/2). Define S; := STrue + for i E [n + m]. Observe that T depends on the true scores, but is invariant by permutation these scores, Hence, the "perturbed" scores S; are exchangeable and have (almost surely) no ties Moreover for i [m]]
Strue nts
STruN > k
Pntt
(k)
{ strue + 7nti Strue + t33 > k
Sati > 3/} >/ kk - { { > 5(m)
j=1
The main argument of these inequalities is that by construction of the random variables y. for all i,
the event ( (Stzue > Strue] } is included in {5. 5;
Then upper bound the FCP using 15
Rett $ (X
{B3nte Satt > 55x)
(16)
We want to apply Theorem A.I to the exchangeable random variables 3, which have no ties. Let us express the FCP in term of conformal p-values. We introduce for i E [m]]]
1
Σ 1=l
( 33)
1
and for é e 10
(m) 1 m
1 1
m
PI' is not defined if all scores equal. However, in this the FCP is null and then upper bounded
15

---

Then for i E [m], the following events are equal:
{ (Snti {())
Sn+t 53} k
Σ Σ1 1 Sunc 3 $3} 3 k
nti 2 S) { > 1 1 { - k/m
where we have used that the scores S have ties. Injecting these equalities into 16
get:
pett $ Cu(Xnti)) < F' (F/( +1)
Then, with probability 1 (3 + 0), using
13 (inverting and m), we get:
Σ I Ret' & Cx (Xnts))) < In [k/(n+1)) An,m n + + Aam & a + Anm
A
log( C CTT.m//3))
where Anmm
Tn,m
A.4 Proof of Proposition
Let us apply Theorem A.1 to Vi for 1 < i n + m. Then the p-value pr-s are affine transformations of the ranks of the calibration point in the test sample:
1
R.)
P
where we recall that R RYY.. (Y )etmi) Let us then rewrite the empirical cumulative
distribution function Fg in function of RR, for t E (0, 1):
Px(t) 1 Σ 1 < (m + 1}.
Let us now remark that for some u E 4 it equivalent for a calibration sample point j to have its rank in the test set smaller than than to have more points than its rank in the calibration with rank smaller than w:
Vj E [m]
R R
Σ
R nFn ((u 1)/(m + 1)) > Rý.
We point out that the first equivalence is satisfied as the order the items in the calibration set is conserved when considering their insertion ranks in the test set: for all 1 & i,j & n. Rt < Rý Rº & Ry. Thus, for j E [n|] if R2 < u, the Rł calibration items E [n]] satisfying RÇ < Ry also satisfy R & u. showing the direct implication (=) the last display. Conversely, if is the number of calibration items i E [n]] satisfying RC & u, they are necessarily exactly the items corresponding to the i smallest calibration ranks. Otherwise, there would be calibration item j [n] with RG = V/' > k and Rt & u, implying (by the previous token) that Σm_ ( & u > k k, contradiction. Thus any calibration item with RG- l satisfies R3 &
Thus, with probability 26, thanks to 13 for all t E 1):
log(1/6) + log (1 + /2TT
(1) (. (1) X, where X
2Tam
Assume this event is satisfied. Then particular, for u = (m + ()55/n/ 2): nf ((u + 1)/(m + 1)) = nF,, (Rg/nn X 1/(m + +1)
> nIm ( 1/(m + 1)) nn
= n () + +1//mm + 1) - nd
> n (Rgg/n nu >> n7.
16

---

Thus, R3 & (m 1) + X) for <.j < n. Let us now lower bound these ranks, Similarly, we
have the equivalence for and < E n:
R2 R R
< m) - + < Rg.
With a (m + [1y// A), we have n ((u + 1)/(m + 1)) < R2 and then Rÿ > (m
1) ()/8//nn X) for j which concludes the proof.
A.5 Proof of Proposition 4.2
The proof is based on the concentration bound of Naaman 2021 recalled below which is a recent multi-dimensionss version of the Dvoretzky- SeeitikkyKKeefe---ee wollfor- (DKW) inequality (Dvoretzky et al.
1956].
Theorem A.2 Naaman
2021
Let X(1,, ((I))..((K)
x(K) i.i.d. random vectors R". Then for t 0,
F(0) Fi((0) > < n(( + 2K12
P sup DER"
(17)
=(0)=[(x(') where P x < 0s. vil and Fx is the empirical edf defined by:
(0)
Σ x < Oz vi
K
Proof of Proposition 4.2. For 0 E R", let us denote
F(0) IP
Vi [m]
1805 <0.]
and FR. the empirical edf:
K
(+) = K
Σ
1f ( ( < 0,, vi e E [m]]
R=
Let us now remark that:
P P(vi E [m] R E Rgg Ri
]] = PP E [m] R E [RT RR|]
= = - F(R
The ordered ranking vector nest follows indeed the same distribution than the drawn vectors 17,"
Then:
F(Rt) F(R (F(Rt) - FR((At)
(R+) (x
F(0) - (x(()) + (1-5),
sup
BERa
as by assumption on the envelope, (R+) Fx (R-) > 5 almost surely. Then after taking the expectation, we get:
> 5 - 2E sup F(0) Ficco]]
P
Vi
E
[n]]
R
E
R Rg.
Rt
It remains upper bound that expectation. Let denote Z supa F(0) (x) let >
E = ZZZzz Z1zzi <t+pp < t + n(K + l)e 2Kt² 22Ke²
We have used that Z is bounded by 1 and Theorem A.2
We conclude by choosing nk
17

---

B
Alternative targets
We detail this section the guarantees we get on the alternative target sets evoked Section 3.3
Rank among the test points. A user might be interested in the ranking of the test points among themselves, rather than within the entire dataset. Such set can be constructed directly from the previous sets, as presented in following Corollary
B.1
Corollary B.I. For E [m]] let
Unti min Cu (Xn+s), and
Uats = max (Xnte))
(18)
N nti = {(j E R. < ontill and N - 1i [n]] Rj & butssll
(19)
100+s-----: Then Ch (X [ants N in buti - N il is marginally valid, P P( C2 (XKnti) and has a controlled FCP, with probability 1 $ 8:
3 1 -
1
1
R & (((tto)) & Anm
(20)
m
with amm defined in Proposition 3.8
we assume that the event Eg {vj E [n]] : tetht E 117, RR11) holds. Then if a E Cx(n+))) C [on+i, butal it implies that Ry E (nn+i R Uhttsbati 1h Thus, we can upper and lower bound Re by just noticing that R Kj [m], Rg & R It follows:
Proof. As in the proof of Theorem 2.1
No. < Ki E [n| 1i5h < antitl < R8+ < Ki e [n]] 125ht & Untiil N Nott
as 17ght E [87. R27). J. It gives the marginal coverage as, then:
an- R buti + C [An+s - N bntt N N+41l
The control of the FCP is obtained in the same manner using Proposition 3.8
Top-K items. It is also possible to target the top-K items by selecting all items whose prediction set includes at least one rank smaller than or equal to K. Corollary ex2hibits that this set contains in average K am of the top K items. This can be sufficient if we target a "top" proportion of the items. This strategy is used in Section E. to identify top-1 candidates in the Yummy Food dataset.
Corollary B.2. For K [m]] let ČtopN {Xn+i: 36 & K, (x((i)))). Then
@uppr n clops
E
> K am,
(21)
where CLopK { {x Bett < k] is the set of the true top items.
Proof. Let us just link the expectation size to the coverage:
ICCropiy y n ctopx
i [m]] R & K, and VE E [K],e l & (x(xxti))
i [m]] n < K, and nett En (X
é [m]] R & Eu (X }
1 Rott & Eu (x(xxt))).
By taking the expectation, we get that E I(Cropyoo n c ctopk K - am.
< am and then E
C @ropk n nc clopk
18

---

Details on the procedure
C.1 Quantile envelope
Algorithm 2 explicitly details the construction of the quantile envelope, estimated by Monte Carlo with sample of size K.
Algorithm 2 Quantile envelope procedure
1: Input: n. m, K, and 5 E (0, 1), (R))
2: for k 1, 1..... K do
3: R(a) Output of Algorithm
4: end for
5: 7 maxy
such that: Σx 1 Ji: !k
$ O (1( )[)
< K8
6: for = -..... do
7: Rj 2g (12)
(1((())))) )ee[k))
8: R2 -i Q-- (12) (1)
)(E(K))))))
9: end for
Output: RRg R for i [n].
In this algorithm, for a E IRK and E (0, 1), (x) denotes the empirical quantile of order u of the sample
C.2 FCP control
In this section, we give details on the procedure to control the FCP at level ā E (0, 1). First, let us remark that FCP m m- - [p; & (), where the pt given in Eq. (12). In other words, the FCP is the proportion of conformal p-values that are lower than f. Furthermore, we have that (Gazin al. 2024
[FCP < a)
m Σ 1l < <tE
Ei
Σ 1p < & [m al
f {p((maa+4) > >
where P(a) denotes the a-th smallest value among (pi,-..:PMy Pm)) We that controlling the FCP at level ā is equivalent to control that the ordered p-value P([m-aJ+1) is strictly larger than t. Hence, for 3 > 0, if we denote by ta the quantile of level / of the distribution of P[[m-o]+1) then P(FCP ā) (P(P(Lm-a++1) ta)
B.
It remains find tg. As proven by Gazin et al. 2024 Proposition 2.1], if the scores Vi,..., Vn+m are exchangeable random variables having no tie almost surely, the vector of conformal p-values (pI.....PP. Pm)) follows known universal distribution. Hence, it is possible to simulate samples following the same distribution as ([]m++++ by first simulating the vector (pI...., Pm) and then by tacking the (im- a 1) smallest value. Then, we compute the empirical quantile of order to find tg. The full procedure is given in Algorithm 3
D Additional results on synthetic data
We present in this section additional experiments the synthetic data of Section 5. and another synthetic data set especially constructed to highlight the adaptivity of the score
D.1 Additional results for synthetic data of Section 5.1
We complete the results of Section 5.] when instead of using RankNet use:
19

---

Algorithm 3 Control of the FCP
1: Input: a; B, n, and K
2: P f- vector of size K
3: for k 1...... K do
4: Draw + uniform random variable U, on [0,
5: for = 1,..... do
6:
Pi m+1 [+ 11U5tn 2 Ui3)
7: end for
8:
Ps + +m ( (fI..... pm))
9: end for
10: ig + (P)
11: Output: lg
RankNet
RankNet
1000
TCPR (RA)
1000
TCPR (VA)
Oracle (RA)
Oracle (VA)
800
800
R
R
200
0
0
200
400
600
800
1000
0
200
400
600
800
1000
RC*
RC4]
Figure 5: Synthetic data: True ranks R in function of their predicted rank Rett by RankNet and their prediction sets with scores R.A. and for m 500.
LambdaMART with 100 trees of 5 leaves trained on n4r = 300 data points. Performances, in term of FCP and relative length, for different values of {100, 500, 2500} and m E 500,,500, 2500} are presented in Figure 9
RankSVM trained with nrr
300. Performances for different values of {100, 500, 2500} and m E {100, 500, 2500) are presented in Figure I0
BRE applied with 1% of all the possible comparisons. Performances for different values n {100, 500, 2500} and m E {100, 500, 2500} are presented Figure I1 Note that BRE is of different nature than the three other algorithms it does not learn a score from their features but ranks items using a small number pairwise comparisons. The ranking eπrors due to this limited number of comparisons.
We also provide performances when using RankNet for {100, 500, 2500) and m {100, 2500) Figure Note that in all the synthetic experiments, we use RankNet with ReLU Neural Network (NN) of 5 hidden layers of size 10. This NN is trained using Pytorch (Paszke) 2019]. Figure 5 displays an example of the prediction sets we construct with TCPR and with the oracle method. All the numerical results are postponed to Section E.3 for clarity of presentation.
Results: As already observed in the main paper, our method, TCPR, always control the false coverage proportion at level = 0.1. Furthermore, at any given size m, as the size of the calibration set increases, our methods return better sets with FCP closer 0.1 and increasingly smaller sizes. In general, we need more calibration points than the number of test points to be able to construct prediction sets that are not too large, which quite intuitive. For n large relatively to m, we reach the performance of the oracle. For LambdaMART and RankS the score function .AA gives in general better prediction sets than those constructed with VA, However, this difference less notable for BRE. Nevertheless, it should be noted that sets with RA less adaptive than the
20

---

RankNet
RankNet
10000
10000
8000
8000
6000
6000
R511
4000
4000
2000
2000
TCPR (RA)
TCPR (VA)
Oracle (RA)
Oracle (VA)
0
2000
4000
6000
8000
10000
2000
4000
6000
8000
10000
R[1
R:1;
Figure 6: Yummly-10k: True ranks R in function of their predicted rank R by RankNet and their prediction sets with scores RA and VA.
ones with VA as explain Section 5.1 Overall, the difference of performance between the score functions depends on the distribution of the data and the algorithm.
E
Additional results on real data
In this section, we present additional information and results on the two real data sets considered in the main paper.
E.1 Yummly-10k
Hyper-parameters: For all the experiments this data set, RankNet with ReL.U NN of hidden layers of size 10. This NN is trained using PyTorch [Paszke 2019].
Additional results: Figure 6 illustrates example of the prediction sets returned by method and by the oracle. As already seen from Table T the differences between TCPR and the oracle are relatively small. This be explained by the large size of the data set which makes the impact of the envelopes negligible. Notice that from these predictions sets, we can infer who the potential candidates of rank would be. Figure shows these candidates when the prediction sets constructed using TCPR or the oracle method with 8 VA, The candidates are all the images containing
the rank in their prediction set, i.e. we display ddshhes X E Ō(X)). As the prediction set of
the image of true rank 1 contains 1 with high probability, this set will contain this image with high probability. The image highlighted red is the randomly chosen reference x which is, by definition, the true rank 1 dish (see Section 5.2). Firstly, we observe that the reference x is included among these top-1 candidates and that the other dishes are closely related it. Secondly, as expected, number of candidates is greater for TCPR (14 candidates) than for Oracle (10 candidates) but not by much. Thirdly, remark that, due to the use of s VA, the prediction sets are narrower for the lower ranks, the number of candidates remains relatively low. For this specific task. the score VA is particularly more adapted than RAA
E.2 Anime recommendation LTR data set
Data set: In details, this data set consists in the three following lists
1. A list of 16681 movies with the following associated features: name, genres, is tv, year, is adult, above above_five stvr_star, users, above five_star, potu_rating,, above_ live_five_tttteeeeeeeeeeeeeeesse coro_sttr_ratttee ratio.
above_five_stt
2. A list of 15163 users with the following associated characteristics: review_count count, user feature avg_score, user_feature score_stddev, user_feature above_five lite_fvv_tttarcountt user user_feature, above five wtw.rfenuurrabboeeeeeeeaaaaaaaar
21

---

(a) TCPR
(b) Oracle
Figure 7: Candidates for the rank dish when using TCPR the oracle methods with s VA The reference x² (which is the true rank 1 dish) is highlighted in red.
LambdaMART
Lambda MART
LambdaMART
0.30
0.725
[9A] [VA]
0.700
1.20
[VA
Palto with Gradte
0 0.06
0.650
3.35
0.625
0.04
1.10
(RAI
0.575
(VA)
0.550
2600
2200
2000
Figure 8: Results on the anime recommendation LTR data set. Each point corresponds to model (embbdaMART((ree.leaaaa
trees (50, 100, 200) and leaves (5, 10, 15, 20). The FCP, relative length, and ratio with the oracle are displayed for each score in function of the average rank error of each model.
3. A list of ratings for 106 tuples (movie, user), with values ranging from 0 to 10.
Ranking task and calibration: We LambdaMART from the LightGBM implementation for this LTR problem. The model assigns a score to each (user, movie) tuple and has been trained on subset of 15000 users. The reference model has 400 trees and 20 leaves, the smaller ones have trees = {50, 100, 200, 300} and leaves = {5, 10, 15, 20). For a particular user, we then suppose only having access to the scores predicted by the large model for 2000 anime, and evaluate the others scores with the smaller models.
m 16661-
Results: Figure displaas the different metrics with respect to the rank error of all the LambdaMART models. The uncertainty across different instances is well captured by our procedure, as illustrated in the second row of the plots: the size of the prediction intervals increases with the ranking algorithm's errors. For all methods, the FCP is well controlled and remains below the threshold of 0.1. Once pronounced for high-performing algorithms: the
again, we observe that the envelope effect ratio with the oracle decreases as the ranking eтror increases. Nevertheless, the ratios remain close to 1 for all methods, suggesting that the overall effect of the envelope is minor.
22

---

E.3
Additional numerical results
This section contains additional experiments for the synthetic dataset (different tuples (n, m)).
LambdaMART (m 100)
LambdaMART (m 100)
0.15
0.7
Relative length
0.10
FCP
0.5
0.3
0.00
100
500
2500
100
LambdaMART (m 500)
LambdaMART (m 500)
0.15
0.10
0.5
Relative
0.05
0.00
0.2
100
500
2500
100
500
2500
LambdaMART (m 2500)
LambdaMART (m 2500)
Relative lenoth
0.10
0.05
0.4
100
500
2500
100
500
2500
Qenv (RA)
(RA)
(VA)
Qenv (VA)
Figure 9: Synthetic data: FCP and relative lengths obtained for LambdaMART with the (RA) and (VA) score, for the quantile (Qenv) and linear (Lenv) envelopes when {100, 500, 2500} and n {100, 500, 2500]. White circles represent the means.
23

---

RankSVM (m = 100)
RankSVM (m 100)
0.15
1.0
Relative length
0.8
0.10
FCP
0.6
0.4
0.00
100
2500
100
2500
RankSVM (m = 500)
RankSVM (m = 500)
0.15
Relative length
0.10
FCP
0.4
0.00
100
500
2500
100
500
2500
RankSVM (m= 2500)
RankSVM (m = 2500)
0.15
Relative length
0.8
0.10
0.6
0.00
100
500
2500
100
500
2500
Qenv (RA)
SSN
(VA)
Qenv (VA)
Figure 10: Synthetic data: FCP and relative lengths obtained for RankSVM with the (RA) and (VA) score, for the quantile (Qenv) and linear (Lenv) envelopes when {100, 500, 2500} and n {100, 500, 25003. White circles represent the means.
24

---

BRE (m 100)
BRE (m = 100)
0.15
1.0
Relative length
0.10
FCP
0.6
0.4
0.00
100
2500
100
2500
BRE (m = 500)
BRE (m = 500)
0.15
Relative length
0.8
0.10
0.
0.05
100
500
2500
100
500
2500
BRE (m = 2500)
BRE (m =2500)
0.15
Relative length
0.10
0.6
0.05
0.00
0.2
100
500
2500
100
500
2500
Qenv (RA)
NSN
(VA)
Qenv (VA)
Figure 11: Synthetic data: FCP and relative lengths obtained for BRE with the (RA) and (VA) score, for the quantile (Qenv) and linear (Lenv) envelopes when {100, 500, 2500} and n {100, 500, 2500). White circles represent the means.
25

---

RankNet (m 100)
RankNet (m 100)
0.6
Relatvve lengtn
0.5
0.10
0.05
0.2
100
500
2500
100
500
2500
RankNet (m 2500)
RankNet (m 2500)
Relative length
0.6
0.10
0.5
0.05
0.3
200
100
500
2500
100
500
2500
Oracle (RA)
TCPR Qenv (RA)
TCPR Lenv (RA)
Oracie (VA)
TCPR Qenv (VA)
TCPR Lenv (VA)
Figure 12: Synthetic data: FCP and relative lengths obtained for RankNet with the (RA) and
(VA) score, for the quantile (Qenv) and linear (Lenv) envelopes when m 25000 and n E
{100, 500, 2500). White circles represent the means.
26

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justifiicton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract and the introduction explain our approach et the setting of full ranking we consider.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
27

---

Justification: In all the experiments, we evaluate the ratio with the oracle length and discuss multiple times the potentially disruptive impact of the envelope when assessing the performance of high-performing algorithm.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Proofs are given in Appendix The assumptions are stated in the main paper and recall at each result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
28

---

The Python code is provided in the supplementary material, and the datasets are either simulated or open data. Overall the method simple and could be reimplemented from scratch by interested reader.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The Python code is provided in the supplementary material, and the datasets are either simulated or open data. Overall the method simple and could be reimplemented from scratch by interested reader.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https //nips. http://wwww///eieeeee//etttttaaa
for more details.
29

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
These informations are in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide boxplots and the standard deviations of all the metries.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2iggma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [No]
30

---

Justification:
Our experiments do not require a lot of computational resources and run standard machine.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ete:://neuipspe httpp/ewww..ppuuaeeeeeeeeeeeeeee cc/pbbllc/Bhhhiicdudddell1111
Answer: [Yes]
Justification:
We are fully in accordance with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction..
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: is discussed in the introduction.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
31

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [No]
Justification:
This is not applicable to our method.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the datasets we used precisely. For the code, apart from standard Python code (numpy, pytorch, matplotlib, etc.) we rely mostly on our own code. It will be release under MIT License.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
A notebook is provided with our code in the supplementary material.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
32

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not have experiments with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
We do not have experiments with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
We do not use LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non ntn-standard components.
Please refer to LLM policy for what should or should not be described.
33


Reviews:
[{"review_id": "BR03nuoNNW", "reviewer": "Reviewer_4soE", "summary": "This paper introduces a method for constructing conformal prediction intervals for ranks under two settings: the RA setting and the VA setting. It employs a proxy conformal score function to compute nonconformity scores and demonstrates that the method achieves an upper-bounded false coverage rate (FCR) at level α. Various numerical experiments further support the effectiveness of the approach.", "questions": "Motivation and Practical Utility:\nIt would be helpful if the authors could more clearly articulate the motivation for applying conformal prediction methods to ranks. For instance, if the subjects’ covariates and outcomes are exchangeable—and therefore their ranks as well—wouldn't the resulting prediction intervals for ranks be quite wide? A discussion on this potential limitation would add clarity. In addition, it would be informative to evaluate the length of the predicted intervals alongside the false coverage rate (FCR), as long intervals may reduce practical utility despite valid coverage.\n\nInterval Width and Tightness of Bounds:\nThe proposed method constructs prediction intervals for ranks using both test and calibration data by estimating upper and lower bounds. However, since the true ranks of new (test) observations are inherently uncertain, there is a concern that the resulting intervals may be overly conservative. Could the authors provide further empirical or theoretical insights into whether these bounds tend to be tight or overly loose in practice?\n\nRelated Work on Ranking Inference:\nThere is a growing body of literature on ranking inference that also focuses on constructing confidence intervals for ranks. The authors may consider acknowledging or comparing their work with some recent contributions in this area, such as:\n\nLagrangian Inference for Ranking Problems, Liu, Y., Fang, X., and Lu, J. (2023)\n\nUncertainty Quantification in the Bradley–Terry–Luce Model, Gao, G., Shen, Y., and Zhang, A. (2023)\n\nRanking Inference from Top Choices in Multiway Comparisons, Fan, J., Lou, Z., Wang, W., and Yu, M. (2025)\n\nIncluding a discussion of these works would help better position the current contribution within the existing literature.", "limitations": "See the questions", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength: This paper is the first to propose a conformal prediction method for ranks, which is a novel and valuable contribution to the literature.\n\nWeakness: One concern is that the resulting prediction intervals may be too wide in practice, potentially limiting their utility—for example, as illustrated in Figure 3.", "was_revised": true, "final_justification": "I have read the other reviews and the authors' rebuttal. I am comfortable keeping my original score, but I am also open to raising it to a 4. My only remaining concern is the practical applicability of the method, as the prediction intervals may be quite wide.", "rebuttal": "We sincerely thank the reviewer for her/his constructive feedback and insightful questions. Below, we address each point in detail. We also appreciate the suggestions regarding the additional references, we will discussed them in the final version (see answer $3)$ below).\n\n**a) Weakness: Size too wide**\n\nWe agree that the prediction sets returned by our method can sometimes be large. However, it is important to note that this is also true for the prediction sets returned by the oracle method (i.e. the best possible method). Therefore, we can conclude that the large size of our sets is mostly due to the inherent complexity of the problem and not because of our methodology. Moreover, as demonstrated empirically in the paper, i) when the ranking task is easier, for example for central ranks of Figure 5, our sets are then really small when we use the score (VA), ii) the size of our prediction sets tends to converge to those of the oracle (e.g. see metrics of Table 1, or visual comparisons of Figures 4, 5 or 6). \n\nConcerning your remark on Figure 3, although we agree that the sets appear wide, we also see that this width is necessary to ensure that 90% of the blue dots fall within our prediction sets. Furthermore, in Figures 4, 5 and 6, we visually compare our sets to those of the oracle and see that the difference is small, further supporting our previous findings. Notice that this conclusion was also present in the synthetic experiments where boxplots related to the metric \"relative length\" for our method and the oracle are very close (at least when $n$ is large).\n\n**1) Motivation and Practical Utility**\n\n**1.1) Why applying CP methods to ranks?**\n\nCP for ranking algorithms provides valid prediction sets for the ranks of new items. Being able to provide prediction sets for rank is an important topic in the ranking literature as this is particularly useful in decision-making where understanding the confidence of predictions is crucial (see e.g. the papers you mention). One key advantage of CP over other existing techniques is its distribution-free property. This means that, if we have an algorithm that ranks items based on their characteristics, we can determine, without making any assumptions about the underlying distribution other than exchangeability, whether the algorithm is confident in its ranking or not. This is a very important property in practice as, in general, it is hard to verify any assumptions on the data. Notice that, as discussed below in answer 3), this property is not satisfied in the papers mentioned in your review, as they rely on the Bradley-Terry-Luce (BTL) model.\n\n**1.2) Exchangeability of subjects’ covariates and outcomes**\n\nAs in standard CP, to prove that our prediction sets are valid, we rely on the assumption that non-conformity scores are exchangeable. More specifically, as you mentioned, we assume that the data are exchangeable, which implies that their ranks are also exchangeable. However, this assumption does not necessarily lead to excessively large sets. Indeed, through the non-conformity scores, we incorporate the information provided by the variable $X$. Your concern about the size of the sets would be valid if the scores were constructed using only the variables $R$ and without using $X$. In standard CP, this would be equivalent to constructing scores using only $Y$ and not from the absolute residuals $\\lvert Y−f(X) \\rvert$. In our article, we follow a similar idea to that of absolute residuals but adapted to the ranking problem and thus incorporate the information of the $X$. Our sets are of the form (predicted rank depending on the features $X$) $\\pm$ (uncertainty computed by CP). If the rank predicted from the features is high, then the prediction set will include correspondingly high ranks.\n\n**1.3) Length of the predicted intervals alongside the FCP**\n\nWe are not entirely certain about what you mean by \"plotting the length alongside the FCP\" but if you are suggesting varying $\\alpha$ and comparing the size of the sets with the FCP, we will add a figure to address this. Above is a table with the average relative length of the predicted sets and the FCP obtained on the Anime data set for some values of $\\alpha$:\n\n| Level $\\alpha$  | 0.1  | 0.2  | 0.3  | 0.4  |\n| --------------- | ---- | ---- | ---- | ---- |\n| FCP             | 0.05 | 0.16 | 0.25 | 0.34 |\n| Relative Length | 0.72 | 0.60 | 0.51 | 0.44 |\n\nYou can observe that the length decreases as long as the target confidence level $\\alpha$ is increasing.\n\nOverall, we fully agree with your remark that it is important to look at the size of the sets which is why we give them in all our experiments (e.g. Figures 3, 5, and 6) and to validate the proxy scores, we have compared ourselves to an oracle CP method, which has access to the ground truch and does not use proxy scores. We would also like to point out that we have also looked how the size of the predicted sets evolves as a function of the performance of the ranking algorithm in Figure 8. This is different from what you suggest but we think that these experiments also show that our method captures effectively the uncertainty of the ranking algorithm (also see Figure 4, score VA as discussed in Answer a). \n\n**2) Evidences on the tightness of the bounds**\n\nThank you for this interesting question. Recall that we provide theoretical support in Proposition 4.1, where we prove that our bounds converge to zero at an order of $O(m/\\sqrt{\\tau_{n, m}})$. This deviation is tight, as it relies on the concentration properties of the conformal p-value, whose asymptotic behavior has been thoroughly analyzed in [4]; see Theorem 3.1 of this work. Furthermore, as mentioned above in Answer (a), our experiments empirically demonstrate that the sets returned by our methods are very similar to those of the oracle method; at least when $n$ is large enough (see, for example, the right panel of Figure 2). This indicates that the non-conformity proxy scores, that we construct using our bounds (Eq. 7), are very similar to those obtained without bounds (i.e., the oracle scores). Therefore, this suggests that our bounds are tight enough to not perturb the conformal procedure. As suggested by the reviewer, we conducted a quick additional experiment comparing the quantiles of the proxy scores and the oracle scores obtained in the Anime data set (Section 5.3). The results in the following table show that their values are indeed similar, confirming our claim.\n\n| Quantile    | 0    | 0.2  | 0.4  | 0.6  | 0.8  | 1    |\n| ----------------- | ---- | ---- | ---- | ---- | ---- | ---- |\n| Proxy scores (VA) | 0.05 | 0.21 | 0.36 | 0.54 | 0.80 | 2.16 |\n| Oracle scores     | 0.00 | 0.19 | 0.38 | 0.61 | 0.89 | 1.79 |\n\n\n**3) Missing literature**\n\nThank you for pointing out thoses interesting references. We will add the following paragraph to the paper:\n\nA significant body of literature already focuses on the problem of uncertainty quantification in ranking problems. In [1] for instance, the authors consider the Bradley-Terry-Luce (BTL) model and infer its general ranking properties. They show that, under this model, it is possible to control the False Discovery Rate (FDR) and thereby infer the top-K ranked items. In [2], the authors study the maximum likelihood estimator (MLE) and the spectral estimator to estimate the parameters of the BTL model, enabling them to construct confidence intervals for individual ranks. Similarly, [3] refines the analysis of [2] and shows that under a uniform sampling scheme, it is possible to efficiently estimate the preference scores of each item allowing them to construct simultaneous confidence intervals for the ranks of the items. Note that all these papers rely on the BTL model. This is a major difference  with our contribution as we do uncertainty quantification for any ranking algorithms and without relying on any specific underlying model.\n\nWe hope we have addressed your concerns and are happy to discuss further if not.\n\n[1] Lagrangian Inference for Ranking Problems, Liu, Y., Fang, X., and Lu, J. (2023)\n\n[2] Uncertainty Quantification in the Bradley–Terry–Luce Model, Gao, G., Shen, Y., and Zhang, A. (2023)\n\n[3] Ranking Inference from Top Choices in Multiway Comparisons, Fan, J., Lou, Z., Wang, W., and Yu, M. (2025)\n\n[4] Asymptotics for conformal inference, Gazin (2024)."}, {"review_id": "0wWjyQZUwY", "reviewer": "Reviewer_eSy5", "summary": "This paper addresses the challenge of quantifying the uncertainty for full ranking tasks using conformal prediction (CP) methods, specifically in scenarios where only the relative ranks of a portion of the data are known and new items need to be ranked amongst them. The authors introduce a transductive conformal prediction approach that does not assume access to full calibration rankings, instead constructing non-trivial bounds for the unknown ranks based on recent results for the distribution of conformal p-values. The work establishes theoretical guarantees (including False Coverage Proportion control), proposes both explicit and Monte Carlo envelope construction methods for bounding unknown ranks, and empirically evaluates the methods on synthetic and real datasets using several learning-to-rank algorithms.", "questions": "The envelope is simulated from uniform order statistics assuming exchangeability. How often do the real calibration ranks fall outside your proposed envelope on actual datasets? Have you empirically validated this high-probability inclusion assumption?\n\nClassical CP yields sets valid conditional on observed features. Your sets are valid only under marginal rank-based assumptions. How can practitioners trust these sets in the presence of covariate shift or model miscalibration?\n\nYou compute max conformity scores over artificial rank intervals not tied to observed data or residuals. Why is this preferable to a data-driven bootstrap or nonconformity-based estimation?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**:\n\nThe paper addresses a timely and practically important problem: quantifying the uncertainty of ranking outputs when full calibration data is unavailable, a situation common in real-world applications.\n\nThe main methodological contribution is clearly described: adapting split/transductive conformal prediction to ranking problems with partial calibration, using recent theoretical results to construct valid prediction sets. This is a nontrivial extension of CP.\n\nThe authors derive marginal validity and false coverage proportion (FCP) bounds under a carefully constructed framework. The methodology is built on top of CP theory, including bounds for joint distributions of p-values.\n\nThe experiments are thorough, spanning synthetic data and real-world ranking tasks. \n\n**Weaknesses**:\n\nThe methodology relies critically on exchangeability of the pair $(X_i, R_i^{c+t})$, and more importantly, on the assumption that tight high-probability bounds $[R_i^−, R_i^+]$ can be obtained for the calibration items’ true ranks. These assumptions are rarely satisfied or testable in real applications, particularly when the ranking algorithm is trained on data or is adaptive.\n\nConstructing rank envelopes via Monte Carlo simulations of order statistics is not grounded in observed data. The resulting bounds on calibration ranks are not conditional on observed $X_i$ or model predictions, and are not adaptively learned from the actual calibration set. As a result, the prediction sets are not meaningful for the observed data realization, and any formal guarantee is only marginal over hypothetical permutations, not conditionally valid in practice.\n\nIn classic CP, conformity scores are grounded in residuals between predictions and ground truth. Here, the proxy scores are computed over artificial intervals—again not informed by the true data realization. Consequently, the prediction sets are not robust to model misspecification or data shift.", "was_revised": true, "final_justification": "Thank you for the detailed and thoughtful rebuttal. Your clarifications regarding the data-driven nature of the proxy scores, and the justification for the envelope construction based on the universal distribution of conditional ranks, helped address several of my earlier concerns. In particular, I now better understand how the method uses observed features and model outputs in constructing the conformity scores, and how the simulation-based envelope still retains distribution-free validity under the exchangeability assumption.\n\nI still have some reservations, particularly regarding the method’s sensitivity to practical violations of exchangeability (e.g., when the model is trained or tuned on overlapping data), and the limited adaptivity of the envelope to model-specific or instance-level uncertainty. These concerns may affect the method's reliability in real-world deployments. That said, I appreciate the authors’ candid acknowledgment of these limitations and the clear positioning of their contribution within the standard CP framework.\n\nGiven these clarifications, I am raising my score.", "rebuttal": "We deeply thank the reviewer for her/his feedback and questions. It appears that there may have been a misunderstanding regarding the use of our data in the proposed method. We would like to draw the reviewer's attention to the fact that the data are indeed used to calibrate the ranking algorithm’s error, as explained in our point a) below.\n\n\n**a) Weaknesses: A possible misunderstanding of the proxy scores**\n\nWe want to begin with a comment on a particular point regarding our paper that seems to have led to an important misunderstanding. Indeed, it seems that the reviewer thinks that we do not use the data to compute the proxy scores as she/he said in the review that: \n\n*\"The proxy scores are computed over artificial intervals—again not informed by the true data realization\"*. \n\nWe would like to clarify here that this is not the case. The scores are not computed from artificial data but using the ground-truth pairs $(X, R^c)$ from the calibration set. Indeed, $\\hat{R}^{c+t}$ is constructed via the ranking algorithm and therefore uses the features $X$ while the computation of the scores uses $\\hat{R}^{c+t}$ and $R^c$. The part on the envelope is only necessary to bound the unobserved variable $R^t$ (the rank of the item among the test set). As $R^{c+t} = R^c+ R^t$, we then get a bound on the whole rank and then, are able to evaluate the error of the ranking algorithm on the calibration data, as done in standard conformal prediction methods. The variable $R^t$ is linked to the concept of conformal p-values, which have a known distribution. This allows us to approximate its distribution via Monte Carlo method for computational efficiency. However, importantly, since everything is distribution-free, we can theoretically control this approximation to still provide finite sample guarantees (see Proposition 4.2). We believe this is an important distinction to make.\n\n**b) Weaknesses: Exchangeability of $(X, R)$ and tight bounds for $R_{-}$ and $R_{+}$.**\n\nWe would like to address the comment that:\n\n*\"these assumptions are rarely satisfied or testable in real applications.\"*\n\nIt is true that in Theorem 3.5, we assume the availability of high probability bounds for $R^{c+t}$ (Eq. 6)  in order to have a general statement. While we present this as an assumption, in Section 4, we demonstrate how to construct such bounds, both theoretically and empirically. In fact, as shown in Proposition 4.1, the ability to construct such bounds is a consequence of the exchangeability of the pairs $(X, R)$ and (Eq. 6) is therefore satisfied as soon as the data are exchangeable. We have chosen this presentation to allow the user to incorporate alternative bounds that they may find more appropriate, for example, by using external information. \nNote also that we may have misunderstood your point on the difficulty of having exchangeability. As you mention, for adaptive algorithms this property is indeed not necessary verify. However, this is inherently satisfied for most ranking algorithms (for example the ones in the experiments) when the data are i.i.d., and the calibration data are not used for the training. Therefore, this assumption seems to us to be reasonable and is quite standard in conformal prediction framework.\n\n**1.1) Uniform order statistics and calibration ranks**\n\nFirst, recall that we use the envelope to approximate the unobserved true rank of the calibration $R^{c+t}$ because only the ranks $R^c$ are observed. We are able to compute the envelope using uniform order statistics (Algorithm 2) because the distribution of $R^{c+t}$ knowing $R^c$ is universal (see discussion l.233). In other words, the distribution of $R^{c+t}$ knowing $R^c$ does not depend on the distribution of the initial data. We then rely on this distribution-free property in our method.\n\n**1.2) How often do the real calibration ranks fall outside the envelope on actual datasets?**\n\nTheoretically, under the exchangeability assumption, we know that the envelope will contain with high probability all the ranks of the calibration points (Proposition 4.1). We will add numerical results illustrating this property in the final version of the paper.\nWe would like to point out that we have compared our method to an oracle that uses the true ranks of the calibration data to compute the scores. Since our method approaches the oracle very closely as $n$ increases (Figure 2, Table 1), this also empirically demonstrates that the envelopes we use are reasonable.\n\n\n\n**2.1) Validity of the set only under marginal rank-based assumption**\n\nWe refer the reviewer to the beginning of our rebuttal (Answer a)) regarding this point and recall that our prediction sets depend on $X$ as we use the groundtruth pairs $(X, R^c)$ to compute the scores. Furthermore, as shown in the experiments (boxplots and Figures 4, 5, and 6) our prediction sets are close to the one returned by the oracle that does not require the envelope. This suggests that our bound is tight. We also would like to recall that having distribution-free coverage guarantees, conditionally on the features, is impossible for non-trivial sets [1]. Our coverage guarantees are then in high probability over the randomness of the calibration and the test sets, as standard CP methods.\n\n**2.2)  How can practitioners trust these sets in the presence of covariate shift or model miscalibration?**\n\nThis is an interesting remark. We agree that our method is not robust to a covariate shift. This is a common problem for CP methods, and different solutions exist [2, 3, 4]. We have considered this question outside the scope of this work, but this is obviously a very interesting line of research for future work. One possibility could be to use weighted quantiles instead of standard ones, as in the framework of weighted CP. Another strategy could be to rely on recent asymptotic results on weighted conformal p-values, for instance [5].\nRegarding model miscalibration, we are not sure we understand what you mean by that. Could you elaborate on it?\n\n**3)  Why is this preferable to a data-driven bootstrap or nonconformity-based estimation?**\n\nTo begin, we would like to reaffirm here that we do indeed use the observed data $(X, R^c)$ to compute our prediction sets. Indeed, through the non-conformity scores, we incorporate the information provided by the variable $X$ and $R^c$ (see also Answer a) above). Hence, our method is indeed a data-driven method.\n\nRegarding the two points of the question:\n\n- The main advantages of our CP method over a bootstrap strategy are that we provide strict finite sample marginal guarantees, meaning our sets are guaranteed to contain the true rank $(1-\\alpha) \\cdot 100\\%$ of the time, regardless of the number of calibration points and the distribution of the data. This is not the case for confidence intervals constructed with bootstrap technique, which generally rely on asymptotic theory.\n\n- For nonconformity-based estimation, we are not sure whether we have well understood the remark. If you mean that we could simply compute the scores as in standard CP, this strategy is simply not feasible in our ranking problem: In standard CP, computing the nonconformity scores requires the ground truth of the calibration points, here their rank $R^{c+t}$ among the $n+m$ points. In our ranking setting, this information is not fully available as we only observe the relative rank $R^c$ of the calibration. As $R^{c+t} = R^c+ R^t$, we use the notion of envelope to approximate the ground truth.\n\nWe hope our answers have clarified our approach and addressed the reviewer’s concerns.\n\n[1] Conditional validity of inductive conformal predictors, Vovk, V. (2012).\n\n[2] Conformal prediction under covariate shift. Tibshirani, R. J., Foygel Barber, R., Candes, E., Ramdas, A. (2019). \n\n[3] Conformal prediction beyond exchangeability. Barber, R. F., Candes, E. J., Ramdas, A., Tibshirani, R. J. (2023).\n\n[4] Efficient conformal prediction under data heterogeneity. Plassier, V. et. al. (2024).\n\n[5] Asymptotics for conformal inference. Gazin, U. (2024)."}, {"review_id": "yXlVvpOjv4", "reviewer": "Reviewer_C52t", "summary": "This paper studies the problem of uncertainty quantification of full ranking algorithms relying on black box predictions. In particular, they develop conformal prediction sets for the correct ranking of each element that satisfies 1) marginal coverage for each element and 2) controls the joint false coverage ratio of the sets. In their method, as they only have partial calibration data (meaning only have access to the true ranking of the some of the elements in calibration time), they propose a conformal calibration method relying on lower and upper bounds on the unseen ground truth elements. Furthermore, they propose several ways to come up with these bounds. They also numerically evaluate the performance of their method.", "questions": "- What is the role of ranking structure here? what i mean by that is, in normal CP, oftentimes there is not much relation between different labels. However, here, it might not make sense if you find yourself in as situation that you are uncertain whether the ranking of en element is 1 or 10, but certain that its not 2 to 9. In other words, it looks like to me that there might be some structure specific to the ranking problem that one might be able to exploit to further improve the algorithm.\n\n- An adjacent problem to what you are considering, which might also be interesting for a range of real-world applications would be: lets imagine the same setting which you are working on. But this time, instead of asking for one prediction set for the ranking of each element, one might be interested in what is the element with rank 1? and subsequently a prediction set that quantify the uncertainty of the rank 1. That is to say, a prediction set that includes the rank 1 with high probability. Any comment whether you method gets extended to these scenarios?", "limitations": "yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "- This is a novel application of CP to ranking problems. In particular, due to the partial nature of calibration data in this setting, it raises some statistical challenges, which the authors take care of carefully, that might be of independent interest beyond the application of ranking.\n- I like the presentation of the paper. The problem formulations are well motivated and well explained.\n- The theoretical guarantees and arguments are sound to me.", "was_revised": true, "final_justification": "I have read the other reviews and I am happy to keep my score of acceptance, as I think this is a novel application of CP, with some interesting theoretical challenges that the authors have overcome. That being said, I also believe further clarifications and empirical evaluations (e.g. to the works that reviewer 4soE mentioned) are needed to understand the depth of the practical value of this paper.", "rebuttal": "We sincerely thank the reviewer for their thoughtful and positive review. We answer her/his interesting questions below.\n\n**1) Role of ranking structure**\n\nThis is an interesting point. In our method, we implicitly use the ranking structure through the choice of the score functions. The two score functions we consider can be interpreted as residual scores and provide a set of the form of an interval (see lines 188 and 191 for the definitions of the related sets). This implies that we will not select ranks far away from each other in the prediction set without selecting the ranks between them. The situation you mention is then *hopefully* not possible.\n\nOne possibility to further leverage the structure of the ranking problem, which we have considered but not explored in depth, is to transform the resulting sets into sets of possible permutations. Since we provide possible ranks for each item, it is possible that some values may be incompatible, as the ranks are dependent on each other. Therefore, we can remove these incompatible values as a post-processing step, thereby reducing the number of possible rankings. However, we have considered that this method might lose readability and thus did not include it in the paper.\n\n**2) Top k prediction set**\n\nThank you once again for this interesting question. We have mentioned this extension in the conclusion of the paper. To obtain a set containing the top-k items with high probability, one possibility is to select all items whose prediction set includes at least one rank smaller than or equal to $k$. We applied this strategy to identify the top-1 item in the Yummy Food dataset, as detailed in Section D.1. Using Proposition 3.8, this set contains at least approximately the top $k-\\alpha m$ of the items. This can be sufficient if we target a \"top\" proportion of the items. To have specific guarantee for the top-1 item, we have different directions to explore in order to adress this question. One idea could be to use techniques from the framework of selective CP, where the selection is defined as the \"top-1.\" Another one could be to view this problem as a distribution-shift problem. This is because the distribution of a point, given that its rank is $1$, is not the same as that of the other points. Thus, we could potentially rely on weighted conformal prediction techniques."}, {"review_id": "j3DZW7xC9r", "reviewer": "Reviewer_MSYV", "summary": "This work provides a methodology for constructing prediction sets for the ranks among unobserved outcome variables.", "questions": "1.  I would recommend that the authors further elaborate on the problem formulation and motivation. At this point, the target problem feels somewhat artificial. Specifically:\n\n1-1. I'm not entirely sure whether constructing prediction sets for the ranks would be practically useful. Inference on the ranks can certainly be a meaningful problem, but I'm not convinced that it necessarily needs to take the form of prediction sets. In the experiments, there is an example with $m = 2500$. What can a practitioner realistically learn from the 2500 prediction sets for the ranks, and in what situations would one prefer this form of inference?\n\nIf it is inference on the outcome $Y_{n+j}$'s, prediction set sounds natural, but if we are interested in the relative order between the outcomes, I feel that a more useful target would be to select the individuals with the largest values among them (with some guarantee), or to test if the ranks are correct, etc.\n\n1-2. Also, the target of inference is set as the \"rank among all the $n + m$ points\" rather than the \"rank among the $m$ test points,\" which seems less useful to me. I believe the test set is typically the \"set of targets of interest\" in inference problems, but in this work, the target essentially includes the calibration data as well---whose within-calibration set ordering is known---so it is not very clear why this is set as the target of inference.\n\n1-3. I cannot think of a realistic setting where we observe only the relative orders of $Y$, but not the actual values, in the calibration set. In the examples mentioned in the paper---“new players entering the game that we want to rank among the previous players to organize matches between players with similar skills” or “movies that we want to rank among those already known by a particular user for which we have his feedback”---it does not seem that the data would actually take the form of (feature, relative rank). Rather, it would more naturally be in the form of (feature, outcome)---e.g, (feature, skill evaluation score) or (feature, feedback score).\n\n2. The proposed methodology is said to be a conformal-type method that requires only exchangeability, but the resulting formula seems to be based on concentration-type bounds. Is this an approximation of some explicit finite-sample formula (as in conformal prediction) introduced to address potential computational challenges, or is there no such underlying finite-sample expression? (I know \"finite-sample formula\" is not an accurate expression, but hopefully the meaning is clear.)\n\nIn the experiments, it is also stated that the proposed method performs well for large $n$, such as 2500, but is not very informative when $n = 100$, so it does not feel to me that the method is indeed a kind of conformal inference.\n\n3. Minor comments\n- line 139 $(Y_i)_i$, line 154 $(X_j)_j$ : seem like typos?\n\n- In line 302, it says that Figure 2 shows the results under $m = 2500$, but the caption of Figure 2 states $m = 500$.\n\n- There are some issues with the referencing of theorems, propositions, and assumptions.", "limitations": "-", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "The paper provides rigorous theoretical arguments.\n\nHowever, the writing requires significant improvement—in terms of sentence structure, notation, and overall organization.\nThe motivation is unclear, and the problem formulation appears somewhat artificial, seemingly designed to fit an existing approach. This makes the proposed methodology appear not very useful in practice, despite its theoretical appeal.", "was_revised": true, "final_justification": "My major concerns were not resolved---the problem setting seems quite artificial and do not seem much useful to me.", "rebuttal": "We thank the reviewer for their constructive questions regarding the conformal nature of our method. Below, we clarify why our approach can indeed be considered conformal. We also provide additional references and explanations to support the practical relevance of both the setting and the type of data we consider, points that the reviewer has questioned, and on which we respectfully disagree.\n\n**1) Problem formulation and motivation**\n\n**1-1 \"constructing prediction sets for the ranks would be practically useful\":** \n\nWe do not defend that constructing all the intervals is always useful. One can simply use our method to obtain a prediction set for the rank of a single item of interest, for which our method provides the first conformal methodology, to the best of our knowledge. By adjusting the level, we have demonstrated that the method also provides control over the False Coverage Proportion (FCP) if the user wishes to apply it to all items, but this is an additional benefit.\n\nA major advantage of controlling the FCP is that the numerous prediction sets can be combined. For example, one can derive a set containing the top-$k$ items with high probability by including all items whose prediction set contains at least one rank smaller than or equal to $k$ (see Section D.1 and Figure 7). Using the control of the FCP of Proposition 3.8, this set contains, with high probability, at least approximately $k-\\alpha m$ items among the top-$k$ ($\\alpha m$ being the worst number of miscovered points). We will provide a more detailed explanation of this application.\n\n**1-2 \"the target of inference is set as the \"rank among all the points\" rather than the \"rank among the test points,\" which seems less useful to me.\":**\n\nWe do not entirely agree with your remark. While it is true that, in some situations, only the rank of the $m$ new items is of interest, it is not always the case. We thus consider the ranking problem among $n+m$ items in the paper as it arises in certain applications (see below) and, moreover, is more general than ranking solely the $m$ new items.\n\nHere are two applications considered in the paper where we want to rank the $n+m$ items:\n- The arrival of new items to be ranked among already known items. This arrival may follow a temporal dynamic with successive entries; see, for example, [1]. We simulated this type of scenario in Section 5.2 using the Yummy Food dataset.\n- The combination of a powerful but costly ranking algorithm with a less performant but more efficient one. The powerful algorithm may correspond to a heavy architecture requiring significant computational or energy cost, or alternatively, to manual comparisons performed by humans. We considered this type of setting in Section 5.3 with the Anime recommendation dataset.\n\nIn addition, note that we can already derive sets for the rank among the $m$ test points from our prediction sets on the $n+m$ points. We only need to shrink all the sets by the number of calibration points of smaller rank. Let $C_{k}(X_{n+j}) = [a_{n+j},b_{n+j}]$, $N_{n+j}^{-} = |\\lbrace i: 1\\leq i \\leq n, R_{i}^{+} < a_{n+j} \\rbrace| $ and $N_{n+j}^{+} = | \\lbrace i: 1\\leq i \\leq n, R_i^+ \\leq b_{n+j}  \\rbrace |$, then $[a_{n+j} -N_{n+j}^-,  b_{n+j} -N_{n+j}^+]$ are prediction sets for the rank among the $m$ test points. They satisfy a marginal coverage, and the FCP satisfies (9), using that we have a uniform control of the rank of the calibration points (Eq. 6). We will add this discussion in the final version of the paper.\n\n**1-3 \"I cannot think of a realistic setting where we observe only the relative orders of $Y$\":**\n\nThere are many contexts in which only pairwise comparisons between items are observed, as the target notion $Y$ is difficult, or even impossible, to measure. Common examples include taste, skill, emotion, and more. In fact, the literature of *object ranking* focuses on constructing a global ranking from such comparisons (see, for example, [2] for a survey).\n\nThe Yummy Food dataset, for instance, is constructed from triplet-wise comparisons of dishes precisely because a direct value $Y$ of the notion of taste is not measurable. As other examples, we can mention the dataset IMDB-WIKI-SbS [3], which is a dataset constructed from pairwise comparisons of pictures of people to determine which people are older and capture the subjective human opinion. In psychology, [4] aims to measure how people are perceived by others to highlight potential biases in the population. This dataset is constructed from pairwise comparisons of people to determine which one seems the most friendly (a subjective value difficult to measure directly).\n\nFinally, often, these comparisons are used to compute a score, such as the Elo rating, which is derived from sequences of pairwise matches. Nevertheless, the original observations remain comparisons between items, and in this last example, players.\n\n**2) \"the resulting formula seems to be based on concentration-type bounds\"**\n\nIn our paper, we use a concentration result derived from [5] (recalled in Theorem A.1). This result is distribution-free and assumes only exchangeability. In fact, we agree that the deviation bound $\\lambda_{n,m}$ present in the bound of Proposition 3.8 could be replaced by the exact quantile of the distribution-free statistics $\\|\\| F_{n} - I_{m}\\|\\|_{\\infty}$ (see Eq. 13). However, since we are not aware of an exact expression for such a quantile, we use a concentration bound for our theoretical results. In practice, we use either an estimation of this quantity (the linear envelope), or the quantile envelope, which adaptively controls the distance between $F_n$ and $I_m$. Both methods perform better than the theoretical one, as illustrated in Figure 1, and have theoretical coverage guarantees (Proposition 4.2). Finally, while we effectively use a finite sample for estimating these in practice, we do not provide a \"conformal analysis\" as it is not straightforward to link the quantile envelope to a score function.\n\n**-- \"it does not feel to me that the method is indeed a kind of conformal inference.\"**\n\nWe respectfully disagree with the reviewer's comment. While it is true that in CP, the number of calibration points does not significantly influence coverage, it does greatly affect the informativeness of the prediction sets, i.e. their length. Indeed, the length of a CP set often depends heavily on the number of calibration samples. As a pathological but illustrative example, when the number of calibration points is smaller than $\\simeq\\alpha^{-1}$, the resulting prediction set becomes overly conservative as it must contain all possible values.\n\nThe influence of the number of calibration points on the lengths of the sets is observable in our experiments (in the different boxplots): the size of the sets decreases as the number of calibration points $n$ increases. With more calibration data, our method can better capture the error of the ranking algorithm, leading to tighter and thus more informative prediction sets.\n\nOverall, we want to reaffirm here that our method remains a conformal one in the rigorous sense: it guarantees a coverage, a False Coverage Proportion (FCP) in our experiments, that exceeds the target level $1-\\alpha$, regardless of the values of $n$ (or $m$) and the distribution of the data i.e. our method is distribution-free.\n\n**3) Typos** \n\nWe thank the reviewer for identifying some typos in the paper. We have made the necessary corrections.\n\n\nWe hope we have addressed your concerns and are happy to discuss further if needed.\n\n[1] Learning to Rank for Multi-Step Ahead Time-Series Forecasting, Duan and Kashina, (2021).\n\n[2] A Survey and Empirical Comparison of Object\nRanking Methods, Kamishima et al., (2010). \n\n[3] IMDB-WIKI-SbS: An Evaluation Dataset for Crowdsourced Pairwise Comparisons, Pavlichenko and Ustalov, (2021).\n\n[4] Person Perception Biases Exposed: Revisiting the First Impressions Dataset, Junior et al. (2020).\n\n[5] Transductive conformal inference with adaptive scores, Gazin et al. (2024)."}]

Author rebuttal:

Meta-review: This paper considers the problem of applying conformal prediction (CP) to provide uncertainty quantification of full ranking algorithms based on black-box prediction. The proposed CP method produces sets for the correct ranking for each element to achieve two coverage guarantees: marginal coverage and controlled false coverage proportion (important but less studied in the CP literature). Since the calibration data contains true ranking for only a subset of elements, the paper proposes methods to compute lower and upper bounds for the unknown groud-truth and how to use them form conformal calibration. Overall, this is a novel problem space for CP which is important in real-world applications and the paper is mostly well-executed. 

Most reviewers' liked the paper but also asked a number of questions which were mostly addressed as part of the author response and discussion. The writing of the paper could be improved in terms of real-world motivation that matches with the problem formulation and experiments as per the Reviewer MSYV. The paper can also include some discussion on how to use the uncertainty sets in practice. These are minor concerns and I think can be addressed in the final paper (as per the authors' responses).

By considering all the factors, I'm leaning towards accepting the paper -- This is a novel problem space and will likely inspire the CP community to build on it. I strongly encourage the authors' to address the above two recommendations and incorporate all the discussion elements in the final paper to improve the clarity of the paper.
Decision: Accept (poster)