Transductive Conformal Inference for Full Ranking

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.

1) Problem formulation and motivation

1-1 "constructing prediction sets for the ranks would be practically useful":

We 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.

A 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.

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.":

We 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.

Here are two applications considered in the paper where we want to rank the $n+m$ items:

• 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.
• 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.

In 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.

1-3 "I cannot think of a realistic setting where we observe only the relative orders of $Y$":

There 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).

The 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).

Finally, 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.

2) "the resulting formula seems to be based on concentration-type bounds"

In 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.

-- "it does not feel to me that the method is indeed a kind of conformal inference."

We 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.

The 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.

Overall, 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.

3) Typos

We thank the reviewer for identifying some typos in the paper. We have made the necessary corrections.

We hope we have addressed your concerns and are happy to discuss further if needed.

[1] Learning to Rank for Multi-Step Ahead Time-Series Forecasting, Duan and Kashina, (2021).

[2] A Survey and Empirical Comparison of Object Ranking Methods, Kamishima et al., (2010).

[3] IMDB-WIKI-SbS: An Evaluation Dataset for Crowdsourced Pairwise Comparisons, Pavlichenko and Ustalov, (2021).

[4] Person Perception Biases Exposed: Revisiting the First Impressions Dataset, Junior et al. (2020).

[5] Transductive conformal inference with adaptive scores, Gazin et al. (2024).

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.

a) Weaknesses: A possible misunderstanding of the proxy scores

We 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:

"The proxy scores are computed over artificial intervals—again not informed by the true data realization".

We 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.

b) Weaknesses: Exchangeability of $(X, R)$ and tight bounds for $R_{-}$ and $R_{+}$.

We would like to address the comment that:

"these assumptions are rarely satisfied or testable in real applications."

It 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. Note 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.

1.1) Uniform order statistics and calibration ranks

First, 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.

1.2) How often do the real calibration ranks fall outside the envelope on actual datasets?

Theoretically, 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. We 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.

2.1) Validity of the set only under marginal rank-based assumption

We 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.

2.2) How can practitioners trust these sets in the presence of covariate shift or model miscalibration?

This 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]. Regarding model miscalibration, we are not sure we understand what you mean by that. Could you elaborate on it?

3) Why is this preferable to a data-driven bootstrap or nonconformity-based estimation?

To 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.

Regarding the two points of the question:

• 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.

• 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.

We hope our answers have clarified our approach and addressed the reviewer’s concerns.

[1] Conditional validity of inductive conformal predictors, Vovk, V. (2012).

[2] Conformal prediction under covariate shift. Tibshirani, R. J., Foygel Barber, R., Candes, E., Ramdas, A. (2019).

[3] Conformal prediction beyond exchangeability. Barber, R. F., Candes, E. J., Ramdas, A., Tibshirani, R. J. (2023).

[4] Efficient conformal prediction under data heterogeneity. Plassier, V. et. al. (2024).

[5] Asymptotics for conformal inference. Gazin, U. (2024).

We sincerely thank the reviewer for their thoughtful and positive review. We answer her/his interesting questions below.

1) Role of ranking structure

This 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.

One 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.

2) Top k prediction set

Thank 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.

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).

a) Weakness: Size too wide

We 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).

Concerning 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).

1) Motivation and Practical Utility

1.1) Why applying CP methods to ranks?

CP 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.

1.2) Exchangeability of subjects’ covariates and outcomes

As 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.

1.3) Length of the predicted intervals alongside the FCP

We 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$:

You can observe that the length decreases as long as the target confidence level $\alpha$ is increasing.

Overall, 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).

2) Evidences on the tightness of the bounds

Thank 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.

3) Missing literature

Thank you for pointing out thoses interesting references. We will add the following paragraph to the paper:

A 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.

We hope we have addressed your concerns and are happy to discuss further if not.

[1] Lagrangian Inference for Ranking Problems, Liu, Y., Fang, X., and Lu, J. (2023)

[2] Uncertainty Quantification in the Bradley–Terry–Luce Model, Gao, G., Shen, Y., and Zhang, A. (2023)

[3] Ranking Inference from Top Choices in Multiway Comparisons, Fan, J., Lou, Z., Wang, W., and Yu, M. (2025)

[4] Asymptotics for conformal inference, Gazin (2024).