Beyond Marginal Coverage: Efficient Localized Conformal Prediction via Residual Rank Calibration

Conformal prediction provides finite-sample marginal coverage guarantees under exchangeability, but marginal validity alone does not ensure that prediction intervals adapt to local structure in the conditional distribution. Existing adaptive methods such as conformalized quantile regression (CQR) and conformal histogram regression (CHR) improve conditional coverage by incorporating estimated quantiles or conditional densities into the conformity score, but doing so requires direct estimation of the conditional distribution of response $Y$ given covariates $X$, which can be statistically and computationally demanding. We propose RLR-CHR, a residual-based local rank conformal histogram regression method that sidesteps full conditional distribution estimation by decoupling location and scale effects via a learned noise proxy and constructing histogram-based conformity scores on the standardized residuals. Local calibration is then performed through rank comparisons rather than weighted conformal quantiles, yielding a procedure that is both localized and computationally efficient. We establish finite-sample marginal coverage for RLR-CHR under exchangeability and asymptotic conditional coverage under local stability of the residual score distribution. We further prove that RLR-CHR is asymptotically equivalent to its weighted-localization counterpart RBC-CHR under suitable regularity conditions, providing a precise theoretical justification for the reduction in per-query computational cost without sacrificing asymptotic accuracy. Experiments on synthetic and real datasets demonstrate that RLR-CHR consistently improves worst-slab coverage and produces more compact prediction intervals than existing conformal approaches.