Distribution-informed Efficient Conformal Prediction for Full Ranking

Ranking models guide decisions in search, recommendation, screening, and information retrieval, yet a deterministic ordering does not express uncertainty about an item’s position. Standard conformal prediction is difficult in full-ranking problems because calibration items may be observed only through their relative order, leaving their absolute ranks in the calibration–test pool latent. TCPR handles this uncertainty with high-probability rank envelopes and worst-case scores, a construction that can be conservative. We propose Distribution-informed Conformal Ranking (DCR), which maps the reference distribution induced by uniform rank interleaving into a mixture of potential calibration scores. MDCR approximates the same target through independent Beta–Binomial draws, avoiding dense reference-mixture construction. Our theory quantifies finite-sample coverage error and establishes asymptotic marginal validity under explicit local conditions; it does not infer exact validity from exchangeability alone. Across a controlled Gaussian setting and learned rankers on ESOL and fixed-anchor Yummly similarity, DCR and MDCR substantially reduce conservatism relative to the evaluated TCPR envelope. The experiments also expose predictor-dependent coverage–size trade-offs, including settings where a mean-rank point estimate is competitive, and identify when direct sampling reduces computation