Improving Backward Conformal Prediction via Non-Conformity Score Transformation

Conformal Prediction (CP) provides a statistical framework for uncertainty quantification that constructs prediction sets with coverage guarantees. While CP yields uncontrolled prediction set sizes, Backward Conformal Prediction (BCP) inverts this paradigm by enforcing a predefined upper bound on set size and estimating the resulting coverage guarantee. However, the looseness induced by Markov's inequality within the BCP framework causes a significant gap between the estimated coverage bound and the empirical coverage. In this work, we introduce ST-BCP, a novel method that introduces a data-dependent transformation of nonconformity scores to narrow the coverage gap. In particular, we develop a computable transformation and prove that it outperforms the baseline identity transformation. Extensive experiments demonstrate the effectiveness of our method, reducing the average coverage gap from 4.20\% to 1.12\% on common benchmarks.

Machine learning systems are increasingly used in high-stakes settings such as medical diagnosis and autonomous driving, where understanding uncertainty is critical. Conformal prediction is a statistical framework that helps address this issue by producing prediction sets that are designed to contain the correct answer with guaranteed reliability. However, these prediction sets are often too large to be practically useful. Backward Conformal Prediction (BCP) addresses this problem by enforcing limits on prediction set size while estimating the resulting reliability. A key challenge of BCP is that its reliability estimates are often overly conservative, making AI systems appear less trustworthy than they actually are. This can lead to unnecessary human intervention even when predictions are sufficiently reliable. We propose ST-BCP, a method that improves BCP through a data-dependent transformation of scores. Our approach reshapes the score distribution to better match the mathematical tools underlying the reliability guarantee, while preserving the theoretical validity of conformal prediction. Experiments on multiple image classification benchmarks demonstrate that ST-BCP produces tighter and more stable reliability estimates.