Distribution-informed Efficient Conformal Prediction for Full Ranking

Wenbo Liao, Huipeng Huang, Chen Jia, Huajun Xi, Hao Zeng, Hongxin Wei · 2026

Read Distribution-informed Efficient Conformal Prediction for Full Ranking by Wenbo Liao, Huipeng Huang, Chen Jia, Huajun Xi, Hao Zeng, Hongxin Wei (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23128.txt.

Introduction

Wenbo Liao and five co-authors quantify uncertainty for full rankings of items. Ranking models order products, papers, or candidates, and safe use needs honest error bounds. Conformal prediction can build sets for the true ranks of test items, using relative ranks from calibration data.

Full ranking is harder than top-few prediction, since every position matters. Their distribution-informed method aims for efficiency, keeping prediction sets small while valid. Trustworthy rankings help search, hiring, and recommendation systems explain their confidence. Relative ranks from calibration items anchor the construction, giving absolute rank sets for test items with stated coverage.

Catalog record

CREATORWenbo Liao, Huipeng Huang, Chen Jia, Huajun Xi, Hao Zeng, Hongxin Wei
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-23128

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distribution-informed Efficient Conformal Prediction for Full Ranking Wenbo Liao, Huipeng Huang, Chen Jia, Huajun Xi, Hao Zeng, Hongxin Wei Abstract Quantifying uncertainty is critical for the safe deployment of ranking models in real-world applications. Recent work offers a rigorous solution using conformal prediction in a full ranking scenario, which aims to construct prediction sets for the absolute ranks of test items based on the relative ranks of calibration items. However, relying on upper bounds of non-conformity scores renders the method overly conservative, resulting in substantially large prediction sets. To address this, we propose Distribution-informed Conformal Ranking ( DCR ), which produces efficient prediction sets by deriving the exact distribution of non-conformity scores. In particular, we find that the absolute ranks of calibration items follow Negative Hypergeometric distributions, conditional on their relative ranks. DCR thus uses the rank distribution to derive non-conformity score distribution and determine conformal thresholds. We provide theoretical guarantees that DCR achieves improved efficiency over the baseline while ensuring valid coverage under mild assumptions. Extensive experiments demonstrate the superiority of DCR, reducing average prediction set size by up to 36 % 36\% , while maintaining valid coverage. 1 Introduction Ranking models are widely deployed in real-world applications, including search engines ( 33 ) , recommendation systems ( 15 ; 12 ) , and information retrieval ( 5 ; 20 ) . However, most ranking models only output deterministic orderings without conveying the uncertainty associated with their predicted ranks, which hinders their safe and trustworthy deployment. The challenge highlights the importance of uncertainty quantification for ranking models, which enables deployed systems to recognize when their predicted ranks are unreliable. To this end, Transductive Conformal Prediction for Ranking (TCPR) ( 9 ) proposes to construct prediction sets for the ranks of test items in a full ranking scenario. Formally, given n+m items, we observe the relative ranks of n calibration items and seek to construct prediction sets for the absolute ranks of m test items with a pre-trained ranking model. Classical conformal prediction (CP) methods cannot be directly applied here because the non-conformity scores of calibration items cannot be computed without knowing their absolute ranks, which in turn depend on the unknown ranks of test items. TCPR addresses this by constructing high-probability upper bounds for non-conformity scores. However, this upper-bound approach is conservative, yielding excessively large prediction sets that do not faithfully articulate the uncertainty of the ranking model. This limitation motivates us to design a method for the full ranking scenario that bypasses conservative upper bounds and produces significantly efficient prediction sets. In this work, we introduce Distribution-informed Conformal Ranking ( DCR ), a novel method that constructs efficient prediction sets for absolute ranks of test items with valid coverage. In particular, we establish that the absolute ranks of calibration items follow Negative Hypergeometric distributions, conditional on their relative ranks. This allows us to derive the exact distribution of unobservable non-conformity scores of calibration items in closed form, without resorting to conservative upper bounds. The precise thresholds derived from the score distribution are then incorporated into the CP framework to produce efficient prediction sets for test items. We provide rigorous theoretical guarantees that DCR achieves valid coverage under the exchangeability assumption. We further prove that DCR is guaranteed to produce smaller prediction sets than TCPR at the same miscoverage rate. Besides, to further address scalability in large-scale ranking problems, we also propose a stochastic variant of DCR, termed Monte-Carlo Distribution-informed Conformal Ranking (MDCR), which significantly reduces computational complexity compared to DCR while preserving marginal coverage guarantees. Our method imposes no parametric assumptions about the data distribution and is applicable to any black-box ranking model, making it a practical tool for quantifying ranking uncertainty. To verify the effectiveness of our method, we conduct extensive evaluations on various models and datasets. The results demonstrate that DCR produces significantly more efficient prediction sets with valid coverage. For example, on ESOL ( 7 ) with LambdaMart ( 20 ) at a target coverage rate 90\% , DCR produces a relative length of 57.64%, while maintaining coverage above 90\% . In comparison, TCPR produces a relative length of 72.50%. Besides, we conduct additional analyzes on how effectively DCR can exploit the rank distribution. Through additional analyzes, we show that as the calibration set size increases or the test set size decreases, DCR achieves realized coverage increasingly close to the target level by more effectively exploiting the rank distribution. Additionally, we find that the VA score is more adaptive than the RA score. We summarize our contributions as follows: • We propose DCR, a novel method that constructs efficient prediction sets for absolute ranks of test items with valid coverage. The core idea behind DCR is to derive the non-conformity score distribution based on the absolute rank distribution. • We theoretically prove that DCR achieves valid coverage under the exchangeability assumption and is guaranteed to be more efficient than the baseline in expectation at the same miscoverage rate. • We perform additional analyzes that lead to improved understandings of our method. In particular, we find that as the calibration set size increases, DCR achieves realized coverage increasingly close to the target level by more effectively exploiting the rank distribution. 2 Background Full ranking setup. We study the problem of quantifying ranking uncertainty in a full ranking scenario ( 20 ; 26 ; 6 ) . Let \mathcal{X} denote the input space and \mathbb{R} denote the score space, which helps us properly define each item’s rank. We have a collection of n+m items, each associated with a pair (X_{i},Y_{i})\in\mathcal{X}\times\mathbb{R} . These items are partitioned into a calibration set of size n , \{(X_{i},Y_{i})\}_{i\in[n]} and a test set of size m , \{(X_{n+j},Y_{n+j})\}_{j\in[m]} , where [n]:=\{1,\ldots,n\} . To formalize ranking relationships, for any Y\in\mathbb{R} and any finite subset \mathcal{D}\subset\mathbb{R} , we define the rank of Y in \mathcal{D} as \mathrm{R}(Y,\mathcal{D}):=\sum_{z\in\mathcal{D}}\mathbf{1}\{Y\geq z\}. Using this definition, we define the position of item i within the calibration set by R_{i}^{c}=\mathrm{R}\!\left(Y_{i},\Lbag Y_{j}\Rbag_{j\in[n]}\right), within the test set by R_{i}^{t}=\mathrm{R}\!\left(Y_{i},\Lbag Y_{n+j}\Rbag_{j\in[m]}\right), and within the entire dataset by R_{i}^{c+t}=R_{i}^{c}+R_{i}^{t}. In this work, we assume that the calibration scores \{Y_{i}\}_{i\in[n]} are known but test scores \{Y_{n+j}\}_{j\in[m]} are unobserved. Thus, the relative ranks of calibration items \{R_{i}^{c}\}_{i\in[n]} are known, but the absolute rank of any item is unknown. To establish statistical guarantees, we make the following assumptions as in prior work ( 9 ) . Assumption 2.1 . The vector (X_{i},Y_{i})_{i\in[n+m]} is exchangeable and (Y_{i})_{i\in[n+m]} has no ties almost surely. Remark 2.2 (Handling Ties) . To strictly satisfy the no-tie condition in Assumption 2.1 , we apply a standard random tie-breaking procedure in our experiments. Specifically, we add microscopic noise \xi\sim\mathcal{U}(0,\epsilon) to the scores, which ensures a unique ranking order almost surely without affecting the substantive performance metrics. We assume access to a pre-trained ranking model A:\mathcal{X}\times\mathcal{X}^{n+m}\to\mathbb{K}, which predicts the rank of a point inside a multiset. Its inputs are the target item X_{i} and the items \Lbag X_{j}\Rbag_{j\in[n+m]} among which it seeks to sort. We use \Lbag\cdot\Rbag to denote a multiset (or bag), which is an unordered set with potentially repeated elements. For clarity, when there is no confusion, we will omit the dependence in the multiset: A(X_{i}):=A(X_{i},\Lbag X_{j}\Rbag_{j\in[n+m]}) . A(X_{i}) could either be a

Read the complete text