CRPS-Optimal Binning for Univariate Conformal Regression

Paolo Toccaceli

cs.LGMar 23, 2026

CRPS-Optimal Binning for Univariate Conformal Regression

Authors: Paolo Toccaceli

Organizations: Centre for Reliable Machine Learning, Royal Holloway, University of London, Egham, Surrey TW20 0EX, UK

Abstract

We propose a method for non-parametric conditional distribution estimation based on partitioning covariate-sorted observations into contiguous bins and using the within-bin empirical CDF as the predictive distribution. Bin boundaries are chosen to minimise the total leave-one-out Continuous Ranked Probability Score (LOO-CRPS), which admits a closed-form cost function with $O(n^2 \log n)$ precomputation and $O(n^2)$ storage; the globally optimal $K$ -partition is recovered by a dynamic programme in $O(n^2 K)$ time. Minimisation of within-sample LOO-CRPS turns out to be inappropriate for selecting $K$ as it results in in-sample optimism. We instead select $K$ by $K$ -fold cross-validation of test CRPS, which yields a U-shaped criterion with a well-defined minimum. Having selected $K^*$ and fitted the full-data partition, we form two complementary predictive objects: the Venn prediction band and a conformal prediction set based on CRPS as the nonconformity score, which carries a finite-sample marginal coverage guarantee at any prescribed level $\varepsilon$ . The conformal prediction is transductive and data-efficient, as all observations are used for both partitioning and p-value calculation, with no need to reserve a hold-out set. On real benchmarks against split-conformal competitors (Gaussian split conformal, CQR, CQR-QRF, and conformalized isotonic distributional regression), the method produces substantially narrower prediction intervals while maintaining near-nominal coverage.

Figures & tables

Panel of Figure 1 — Figure 1: Geometric interpretation of $\mathrm{CRPS}(\hat{F}_{m},y)$ as the integral of the squared vertical gap between the predictive CDF $\hat{F}_{m}$ (blue step function, $m=4$ atoms) and the step $\mathbf{1}[t\geq y]$ (grey) at the observed outcome $y$ . Blue shading marks intervals where $\hat{F}_{m}(t)>\mathbf{1}[t\geq y]$ (too little forecast mass above $t$ ); orange marks intervals where $\hat{F}_{m}(t)<\mathbf{1}[t\geq y]$ (too little mass below $t$ ). CRPS $=\int(\hat{F}_{m}(t)-\mathbf{1}[t\geq y])^{2}\,\mathrm{d}t$ is large when the forecast is mis-centred or over-dispersed relative to $y$ .

Figure 2: The synthetic dataset with the optimal

6

-bin partition (

K^{*}=6

). Shaded regions correspond to the six bins; dotted vertical lines mark the bin boundaries (midpoints between adjacent training observations).

Figure 3: Within-sample LOO-CRPS (left) and cross-validated test CRPS (right) as functions of

K

on the running example. The within-sample criterion is nearly monotone decreasing, confirming its susceptibility to optimism bias ( Hastie et al., 2009 ) . The test CRPS has a clear U-shape with minimum at

K^{*}=6

. Note that the left and right

y

-axis scales differ: the left shows a total (sum over all observations), the right an average (per held-out test point).

Figure 4: Conformal p-value

p(y_{h})

as a function of the candidate response

y_{h}

at three test points

x^{*}\in\{0.3,1.5,2.7\}

for

\varepsilon=0.10

. The shaded region is the prediction set

\Gamma^{0.10}

; vertical red lines mark the true

90\%

interval under

\mathcal{N}(3x^{*},(1+x^{*})^{2})

. The p-value curve is unimodal (each monotone piece is convex, since the underlying nonconformity score

\alpha(y_{h})

is convex), yielding a single connected prediction set in each case.

Figure 5: Conformal

90\%

prediction intervals (shaded blue) and true

90\%

intervals (dashed red) across the covariate range, with bin boundaries marked by dotted vertical lines. The interval width adapts to the within-bin spread, tracking the increasing conditional variance of the heteroscedastic data-generating process.

Figure 6: Bimodal mixture DGP (

n=600

\varepsilon=0.10

K^{*}=6

). Shaded rectangles show the conformal prediction set for each bin; grey dots are training observations. Left: CRPS score — one wide interval per bin, spanning both mode tracks. Right:

k

-NN score (

k^{*}=7

, CV-selected) — narrow intervals tracking each mode; the low-density inter-modal gap is excluded.

Figure 7: Old Faithful. Left: scatter of eruption duration vs. waiting time with the optimal 4-bin partition. Boundaries at

63.0

67.5

, and

71.5

minutes resolve the transition between the short-eruption and long-eruption regimes. Right: within-bin empirical CDFs; the outer bins are unimodal, confirming the partition captures the regime structure.

Figure 8: Old Faithful: 90% prediction intervals from five methods. Our CRPS-based conformal intervals adapt to the local conditional spread within each bin, producing narrower intervals than all competitors in both regimes. In the transition region around

67

–

70

minutes, the proposed method’s interval is deliberately wide: the single bin spanning both eruption modes must cover the full bimodal spread, an honest consequence of the partition geometry.

Method	Coverage (%)	Mean width (min)
Our method ( $n/2$ )	$88.5\pm 0.3$	$1.270\pm 0.010$
Gaussian split conformal	$91.2\pm 0.0$	$1.683\pm 0.006$
CQR (cubic)	$91.2\pm 0.0$	$1.490\pm 0.006$
CQR-QRF	$91.4\pm 0.0$	$1.333\pm 0.006$
CQR-IDR	$91.4\pm 0.0$	$1.294\pm 0.007$
Our method (full $n$ )	$90.6\pm 0.1$	$1.217\pm 0.002$

Table 1: Old Faithful (

n=272

): empirical coverage and mean width of prediction intervals at nominal level

1-\varepsilon=0.90

, averaged over

R=200

random 50/50 splits (

\pm

one standard error). Top block : all methods use the same training half (

n/2

); Our method (

n/2

) is directly comparable to the competitors. Below the line : Our method (full

n

) uses all

n

observations, a design advantage inherent to full-data conformal methods.

Figure 9: Motorcycle accident. Left: cross-validated test CRPS as a function of

K

with the selected

K^{*}=6

. Right: scatter with the 6-bin partition; boundaries are concentrated in the high-variance impact phase.

Figure 10: Motorcycle accident: 90% prediction intervals. Gaussian split conformal is constrained to constant width; our method, CQR-QRF, and CQR-IDR adapt to the non-stationary variance structure. A small number of data points in the high-variance impact phase (

20

–

30

ms) fall outside the proposed method’s intervals, consistent with the approximate within-bin exchangeability in this small and strongly heteroscedastic dataset.

Method	Coverage (%)	Mean width (g)
Our method ( $n/2$ )	$86.9\pm 0.5$	$100.6\pm 1.3$
Gaussian split conformal	$92.5\pm 0.0$	$172.4\pm 1.0$
CQR (cubic)	$92.5\pm 0.0$	$134.1\pm 1.5$
CQR-QRF	$93.1\pm 0.1$	$87.9\pm 0.7$
CQR-IDR	$92.7\pm 0.0$	$127.6\pm 0.6$
Our method (full $n$ )	$90.3\pm 0.2$	$77.3\pm 0.2$

Table 2: Motorcycle accident (

n=133

): empirical coverage and mean width of prediction intervals at nominal level

1-\varepsilon=0.90

, averaged over

R=200

random 50/50 splits (

\pm

one standard error). Top block : all methods use the same training half (

n/2

); Our method (

n/2

) is directly comparable to the competitors. Below the line : Our method (full

n

) uses all

n

observations, a design advantage inherent to full-data conformal methods.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 11: Venn prediction band (shaded) and training ECDF

\hat{F}_{m}

(step function) for each of the six bins, alongside the true conditional CDF at the bin midpoint (dashed red). The band width

1/(m+1)

ranges from

0.004

0.012

, invisible at these bin sizes.

$x^{*}$	Bin	$\Gamma^{0.1}$	Width	True $90\%$ width
$0.3$	2	$[-1.30,\;3.98]$	$5.28$	$4.28$
$1.5$	4	$[-0.15,\;8.74]$	$8.89$	$8.22$
$2.7$	6	$[\phantom{-}1.20,\;13.48]$	$12.27$	$12.17$

Appendix

Table 3: Conformal

90\%

prediction intervals at three representative

x

-values. Widths grow monotonically with

x

, closely tracking the oracle under the true distribution.

Figure 12: Distribution of conformal p-values

p(y^{*})

on the

2{,}000

-point test set. Under a valid conformal predictor the p-values are uniform, or super-uniform (density

\leq 1

everywhere); slight conservatism reflects the approximate exchangeability within bins. P-values are discrete, taking values in

\{1/(m+1),\ldots,1\}

for the

m

training points in each bin; the histogram is smoothed by the varying bin sizes across test points.

Figure 13: Conditional coverage per bin on the

2{,}000

-point test set at three levels

\varepsilon\in\{0.05,0.10,0.20\}

. Dashed lines mark the nominal level. Bin 1 (

m=86

, leftmost) under-covers due to within-bin shift of the true conditional distribution; the remaining bins are close to their nominal targets.

Figure 14: PIT histograms per bin. The PIT for test point

(x^{*},y^{*})

assigned to bin

b

\hat{F}_{b}(y^{*})=m_{b}^{-1}\sum_{i=1}^{m_{b}}\mathbf{1}[y_{b,i}\leq y^{*}]

. Under perfect calibration the histogram is uniform (dashed line at density 1). Boundary bins (1 and 6) show departures due to within-bin heterogeneity.

Explore similar work

Mar 2, 2026

Co-optimization for Adaptive Conformal Prediction

Conformal prediction (CP) provides finite-sample, distribution-free marginal coverage, but standard conformal regression intervals can be inefficient under heteroscedasticity and skewness. In particular, popular constructions such as conformalized quantile regression (CQR) often inherit a fixed notion of center and enforce equal-tailed errors, which can displace the interval away from high-density regions and produce unnecessarily wide sets. We propose Co-optimization for Adaptive Conformal Prediction (CoCP), a framework that learns prediction intervals by jointly optimizing a center

m(x)

and a radius

h(x)

.CoCP alternates between (i) learning

h(x)

via quantile regression on the folded absolute residual around the current center, and (ii) refining

m(x)

with a differentiable soft-coverage objective whose gradients concentrate near the current boundaries, effectively correcting mis-centering without estimating the full conditional density. Finite-sample marginal validity is guaranteed by split-conformal calibration with a normalized nonconformity score. Theory characterizes the population fixed point of the soft objective and shows that, under standard regularity conditions, CoCP asymptotically approaches the length-minimizing conditional interval at the target coverage level as the estimation error and smoothing vanish. Experiments on synthetic and real benchmarks demonstrate that CoCP yields consistently shorter intervals and achieves state-of-the-art conditional-coverage diagnostics.

Xiaoyi Su, Zhixin Zhou, Rui Luo

Department of Systems Engineering, City University of Hong Kong, Hong Kong SAR, China · Alpha Benito Research, Los Angeles, USA

Conformal Prediction Regression Prediction Intervals

Ask PDF

Mar 6, 2026

CREDO: Epistemic-Aware Conformalized Credal Envelopes for Regression

Conformal prediction delivers prediction intervals with distribution-free coverage, but its intervals can look overconfident in regions where the model is extrapolating, because standard conformal scores do not explicitly represent epistemic uncertainty. Credal methods, by contrast, make epistemic effects visible by working with sets of plausible predictive distributions, but they are typically model-based and lack calibration guarantees. We introduce CREDO, a simple "credal-then-conformalize" recipe that combines both strengths. CREDO first builds an interpretable credal envelope that widens when local evidence is weak, then applies split conformal calibration on top of this envelope to guarantee marginal coverage without further assumptions. This separation of roles yields prediction intervals that are interpretable: their width can be decomposed into aleatoric noise, epistemic inflation, and a distribution-free calibration slack. We provide a fast implementation based on trimming extreme posterior predictive endpoints, prove validity, and show on benchmark regressions that CREDO maintains target coverage while improving sparsity adaptivity at competitive efficiency.

Luben M. C. Cabezas, Sabina J. Sloman, Bruno M. Resende +3

Department of Statistics, Federal University of S˜ao Carlos, S˜ao Carlos, Brazil · Institute of Mathematics and Computer Science , University of S˜ao Paulo, S˜ao Carlos, Brazil · Universit´e Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, France +1

Regression Prediction Intervals Conformal Prediction Epistemic Uncertainty

Ask PDF

Aug 6, 2026

Beyond Marginal Validity: Finite-Sample Guarantees for Localized Conformal Prediction

Conformal prediction endows arbitrary black-box predictors with finite-sample, distribution-free marginal coverage, yet marginal validity can hide severe covariate-specific miscalibration, while exact distribution-free conditional coverage is finite-sample unattainable. Randomly localized conformal prediction (RLCP) mitigates this gap by calibrating near the test point while preserving marginal coverage. Existing theory, however, lacks finite-sample guarantees for the realized localized set that jointly control conditional validity and oracle efficiency. We provide such guarantees. For any fixed score, under Hölder regularity of the conditional score CDF and standard density and kernel assumptions, we prove high-probability bounds, uniform over a realized localization neighbourhood, for the conditional-coverage gap and the length error relative to the oracle. The bounds decompose into an

O(h^β)

localization bias and a calibration term decreasing with calibration size, clarifying the bandwidth bias-variance tradeoff and when RLCP tracks the oracle. We also analyze data-split learned scores: when the score targets a pivotal score, as in conformalized quantile regression, uniform local guarantees decompose into fixed-score calibration and uniform score-estimation errors, showing that improved learning sharpens localized guarantees.

Anton Conrad, Rustam Isaev, Denis Belomestny +2

Laboratoire de Recherche d’EPITA, 14–16 rue Voltaire, 94276 Le Kremlin-Bicêtre CEDEX, France · Faculty of Computer Science, HSE University, 11 Pokrovsky Boulevard, Moscow 109028, Russia · Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, 1 Leninskie Gory, Building 52, Moscow 119991, Russia +2

Conformal Prediction Statistical Learning Theory

Ask PDF