Backward Conformal Prediction Under Covariate Shift: New Method Improves Estimation Accuracy

Backward Conformal Prediction (BCP) is a method that fixes the prediction set size and instead estimates the miscoverage rate. However, traditional BCP assumes that calibration data and test data are exchangeable, which often does not hold in real-world applications. A recent study extends BCP to the covariate shift setting, maintains its theoretical guarantees through importance weighting, and proposes a new method for density ratio estimation based on sorted score vectors.

Why Does BCP Fail Under Covariate Shift?

BCP's core advantage is that it does not fix the coverage rate, but instead fixes the prediction set size and then estimates the miscoverage rate of that set. This property makes it highly attractive in scenarios requiring strict control over prediction set size. The problem, however, is that standard BCP assumes the calibration set and test set come from the same distribution—i.e., the data is exchangeable.

When covariate shift is present—meaning the input distribution P(X) changes while the conditional distribution P(Y|X) remains unchanged—this exchangeability is broken. Directly applying BCP leads to biased miscoverage rate estimates. The study points out that the solution is to introduce importance weighting, reweighting calibration samples by the density ratio w(x)=P_test(x)/P_cal(x). When the density ratio is known, BCP's miscoverage rate guarantees can be preserved.

Covariate Shift and Exchangeability: Covariate shift is a common form of distribution shift where the marginal distribution of input features changes, but the conditional distribution of labels given inputs remains unchanged. For example, in medical diagnosis, patient feature distributions may differ across hospitals, but the same disease manifests consistently under the same features. Exchangeability means that the order of samples does not affect their joint distribution—i.e., samples in the calibration set and test set are statistically symmetric. The core theoretical guarantee of conformal prediction relies on exchangeability, as it ensures that nonconformity scores are uniformly distributed under permutation. When covariate shift occurs, the calibration set and test set no longer come from the same distribution, exchangeability is broken, and the prediction sets constructed from calibration set quantiles exhibit systematic bias in coverage on the test set. Therefore, mechanisms such as importance weighting must be used to correct distributional differences and restore theoretical guarantees.

Key Finding: A Better Domain Classifier Does Not Necessarily Lead to Better Estimation

This study reveals a counterintuitive phenomenon: BCP's tight miscoverage rate report depends only on the relative weights assigned to the omitted calibration samples. This means that a "better" domain classifier—one that more accurately distinguishes calibration from test distributions—can sometimes produce worse miscoverage rate estimates.

This finding challenges intuition—we typically assume that more precise density ratio estimation is always beneficial. But under the BCP framework, what truly matters is the weight distribution of those calibration samples not covered by the prediction set. If the domain classifier focuses excessively on certain regions, it may distort the relative weights of these critical samples, leading to inaccurate miscoverage rate reports.

Density Ratio Estimation and Domain Classifiers: The density ratio w(x)=P_test(x)/P_cal(x) is central to importance weighting. In practice, the density ratio is usually unknown and must be estimated through a domain classifier: train a classifier to distinguish calibration samples from test samples, then use its output probabilities to derive the density ratio. The quality of a domain classifier is typically measured by its discriminative ability (e.g., AUC), with the intuition that stronger is better. However, in backward conformal prediction, the miscoverage rate report depends only on the relative weights of those calibration samples not covered by the prediction set. If the domain classifier overfits or focuses too much on certain regions when estimating the density ratio, it may distort the weight distribution of these critical samples, leading to biased miscoverage rate estimates. Therefore, the overall discriminative ability of the domain classifier and the final estimation accuracy are not monotonically related—sometimes a "weaker" but more stable classifier can actually provide more reliable weights.

Innovative Method: Estimating Density Ratios on Sorted Score Vectors

Based on the observation that BCP depends only on nonconformity scores, researchers propose an elegant method: instead of estimating the density ratio in the high-dimensional input space, estimate it on the sorted score vector.

The core insight of this method is that BCP's miscoverage rate computation only involves calibration sample scores and whether they are covered, without requiring complete input information. Therefore, operating directly in score space avoids the difficulties of high-dimensional density ratio estimation. Researchers prove that under interpretable conditions, this method asymptotically recovers the same miscoverage rate report as input-space estimation, and characterizes the bias when conditions are not satisfied.

Nonconformity Scores and Sorted Score Vectors: Nonconformity scores are metrics in conformal prediction that measure the discrepancy between model predictions and true labels—for example, absolute error is commonly used in regression tasks, and 1 minus the predicted probability of the true class is used in classification tasks. Backward conformal prediction fixes the prediction set size and estimates the miscoverage rate by examining the proportion of calibration samples whose scores exceed a certain threshold. The sorted score vector is obtained by arranging all calibration samples' nonconformity scores in ascending order. Researchers propose estimating the density ratio on this sorted score vector rather than in the original high-dimensional input space. This is because BCP's miscoverage rate computation depends only on calibration sample scores and whether they are covered, without requiring complete input features. By transferring the density ratio estimation problem from input space to one-dimensional score space, it not only avoids the curse of dimensionality in high-dimensional estimation but also simplifies computation and improves stability. Theoretical analysis shows that under certain interpretable conditions, this score-space weighting asymptotically recovers the same miscoverage rate report as input-space weighting, and clarifies the magnitude of bias when conditions are not met.

Experimental Results: Score Weighting Outperforms Embedding Weighting

The research team validated the proposed method through simulation experiments and benchmark distribution shift datasets. The results show that:

• Score-based weighting schemes consistently produce more accurate miscoverage rate estimates than embedding-based weighting;
• The proposed method overall improves BCP's miscoverage rate estimation performance under covariate shift.

This means that in practical applications, when facing distribution shift, prioritizing density ratio estimation in score space may be more robust. For researchers and engineers working in uncertainty quantification, risk control, or requiring reliable prediction sets, this finding provides direct practical guidance.

Implications for Conformal Prediction Practice

The contribution of this work operates on two levels. Theoretically, it extends BCP's guarantees to the covariate shift setting and explains the non-monotonic relationship between domain classifier quality and miscoverage rate estimation accuracy. Practically, it provides a simple yet effective strategy—weighting in score space rather than input space.

For teams needing to deploy conformal prediction systems, this means that when distribution shift is present, there is no need to pursue the most powerful domain classifier; instead, focus on the weighting scheme in score space. At the same time, this research reminds us that extending conformal prediction requires careful consideration of how weighting mechanisms affect the final report, rather than simply applying standard procedures.