Practical Advantages of Online Conformal Prediction for Data Streams

Introduction

The deployment of machine learning models in safety-critical and resource-constrained environments, energy markets, finance, sensor networks, has made uncertainty quantification a first-class requirement. A point prediction, however accurate on average, is of limited use without a well-calibrated measure of confidence. Conformal Prediction (CP) [15] instead gives finite-sample, distribution-free marginal coverage under the sole assumption of exchangeability, wrapping any pre-trained score function into a prediction set $C_{\alpha}(X)$ satisfying $\mathbb{P}(Y \in C_{\alpha}(X)) \ge1-\alpha$ for any user-chosen $\alpha$. Full Conformal Prediction (FCP) achieves the tightest such set, but at a prohibitive cost: for every test point and every candidate label $y \in\mathcal{Y}$, the model must be re-scored or re-trained on the augmented sample. Split CP [11] avoids this by fixing the model and calibrating on a held-out set, trading statistical efficiency (only part of the data drives the quantile) for a single forward pass. Neither FCP nor Split CP is designed for non-stationary streams, where the joint distribution of $(X,Y)$ drifts over time, a setting that is the rule rather than the exception in the applications above.

Several lines of work address non-stationarity within CP: Adaptive Conformal Inference (ACI) [8] updates the coverage level online via a proportional controller on the pinball loss, recovering long-run coverage under drift; an aggregated variant improves robustness further. Weighted CP [4, 13] down-weights distant observations via importance ratios, giving a principled oracle for non-exchangeable streams. Online quantile-tracking methods with regret guarantees [3] bound a scalar tracker directly.

None of these jointly resolves two distinct requirements: (i) valid coverage and tight width under drift, and (ii) per-step cost independent of the stream length $t$. ACI-style methods satisfy (ii) trivially (a scalar update) but not (i): they leave the predictor untouched, so once the base model goes stale the quantile update alone must absorb an error it did not cause. Weighted CP satisfies (i) but not (ii): its exact set is recomputed from the full re-weighted history at every step, which is exactly the bottleneck that made FCP impractical to begin with. Regret-bounded quantile trackers satisfy (ii) but treat the underlying model as given, and, to our knowledge, no prior work benchmarks the resulting pipeline against the exact full/weighted-CP set it implicitly approximates, in either regression or classification.

In the present work, we empirically investigate whether, under distribution shift, an online variant of conformal prediction can match full conformal prediction (full CP) at a fraction of its cost. The studied method, QT+WLS, pairs a forgetting-factor model update (Recursive Least Squares, RLS) with an online-gradient quantile tracker, so that its memory and per-step cost are $O(p^2)$, where $p$ is the dimension of the feature space, and independent of $t$, the iteration of the online setting, unlike weighted or exponentially weighted variants that still carry a growing residual array. We compare four online conformal regression methods against a full CP oracle using the entire observed history (an exact weighted homotopy solver, not a windowed approximation) on three synthetic regimes and the real world ELEC2 dataset.

Background

In this section, we introduce the conformal settings considered in the paper: (i) full conformal prediction, (ii) weighted conformal prediction, and (iii) online conformal prediction, before providing further details on the exact algorithms studied in § 3.

Let $\mathcal{X} \subseteq\mathbb{R}^{p}$ be the input space and $\mathcal{Y}$ the output space ($\mathcal{Y} \subseteq\mathbb{R}$ for regression, a finite label set for classification). We observe a stream $(X_1,Y_1),(X_2,Y_2),\ldots$ indexed by $t=1,2,\ldots$. For a training horizon $T_{\mathrm{tr}}$ and calibration horizon $T_{\mathrm{cal}}$, let $T_0=T_{\mathrm{tr}}+T_{\mathrm{cal}}$ denote the start of the online phase.

Full Conformal Prediction

We briefly remind the full conformal setting, its associated complexity and its coverage guarantees.

and $C^{\mathrm{full}}_{\alpha}(x_{n+1}) = \{y \in\mathcal{Y} : s^{y}_{n+1} \le\hat{q}^{y}_{\alpha}\}$.

Theorem 1 (Marginal coverage of full CP (Vovk et al. [15]). If $(X_{1}, Y_{1}), \ldots, (X_{n}, Y_{n}), (x_{n+1}, Y_{n+1})$ are exchangeable, then for any $\alpha\in(0, 1)$,

Online CP

Conformal prediction was originally introduced in an online setting, where examples arrive one at a time and the set for $Y_t$ is built from the first $t - 1$ observations [14, 15]. Online conformal prediction (OCP) keeps this sequential protocol but drops the exchangeability assumption, so as to handle streams whose distribution drifts. At each $t \ge T_0$, the learner observes $X_t$, outputs a set $\hat{C}_t(X_t)$ before $Y_t$ is revealed, then observes $Y_t$ and updates its internal state. This state has two components: the base model, which produces the prediction $\hat{Y}_t$ and hence the score $R_t$, and the conformal threshold $\hat{q}_t$, which turns past scores into a prediction set.

The existing literature on OCP under distribution shift essentially focuses on the threshold. Adaptive Conformal Inference (ACI) (Gibbs and Candes [8]; Gibbs and Candès [9]) adjusts the working miscoverage level from the observed coverage errors and guarantees long-run coverage under arbitrary shifts, and several works refine the choice of its step size, through aggregation (Zaffran [16]), strongly adaptive online learning (Bhatnagar et al. [5]), or decaying step sizes with regret bounds (Angelopoulos et al. [3]). A complementary view interprets the threshold update as a feedback controller (Angelopoulos et al. [1]). In most of these works, the base model is treated as given. The rules used to update the model and the threshold, and how they compare to the full-CP oracle, are the object of the next section.

Online Conformal Methods

All methods follow the same three-phase protocol: (i) training on the first $T_{\mathrm{tr}}$ observations; (ii) calibration on the next $T_{\mathrm{cal}}$, collecting honest out-of-sample scores (predictions made before the model updates); (iii) online prediction from $T_0$ onward, where methods differ in how the model and quantile adapt. Table 1 summarizes every method compared in this paper for regression with their associated complexity.

Method	Time per step	Memory
Full CP (oracle)	$O(p^{3} + t \log t)$	$O(tp)$
CP+LS	$O(p^{2} + t)$	$O(p^{2} + t)$
nexCP+LS, nexCP+WLS	$O(p^{2} + t \log t)$	$O(p^{2} + t)$
QT+WLS	$O(p^{2})$	$O(p^{2})$

Quantile Updates

Let $R_i = |Y_i - \hat{Y}_i|$, and $R_t = \{R_i\}_{i<t}$.

Uniform weights. $\hat{q}_{t,\mathrm{uni}} = \operatorname{quantile}_{1-\alpha}(R_t)$: appropriate under stationarity, slow to adapt after a shift since all past residuals carry equal weight.

Exponential weights. $w_{i,t}=\rho^{t-i}$, $\rho\in(0,1)$, giving the weighted empirical quantile

([4]). The effective sample size $N_{\mathrm{eff}}\simeq1/(1-\rho)$ for large $t$ represents the number of influential past examples, i.e., how quickly old observations are forgotten. This still requires storing and re-sorting a growing residual array, $O(t\log t)$ per step.

OGD quantile tracking. Inspired by ACI ([8]) and the quantile-tracking view of the conformal P-controller ((Angelopoulos and Bates, 2023)), we maintain a single scalar threshold $\theta_t$ via online subgradient descent on the pinball loss:

with step size $\eta>0$: constant memory and computation per step, regardless of $t$, and no residual array at all. Its validity follows from the online ACI guarantee ([8]) rather than from convergence to an FCP limit.

Model definitions and updates

Time varying linear model At each time $t$, the learner observes a covariate vector $x_t\in\mathbb{R}^p$ and predicts a scalar response $y_t\in\mathbb{R}$ (Table 2). The integer $p$ is the order of the model, i.e. its number of coefficients; when an intercept is used, it is one of the $p$ columns of $x_t$ (a constant column). All methods share the same prediction function, which is linear in the covariates:

Table 2: Covariates, response and model order $p$ of each stream. “1” denotes the constant column of the intercept, which counts in $p$. Temperatures are in °C, humidities in %, pressures in mm Hg (Energy) or hPa (PRSA), and wind speeds in m/s; the Bike weather covariates are normalized to [0, 1].

Stream	Covariates $x_t$	Response $y_t$	$p$
Synthetic	four independent $\mathcal{N}(0,1)$ variables	$x_t^\mathsf{T}\beta_t+\varepsilon_t$	4
ELEC2	electricity price and demand in New South Wales and in Victoria	electricity transfer	4
Energy	energy use of lights, kitchen temperature and humidity, outdoor temperature, humidity, pressure and wind speed, 1	energy use of appliances (Wh)	8
Bike	temperature, humidity, wind speed, working-day indicator, 1	number of rented bikes	5
PRSA	dew point, temperature, pressure, cumulated wind speed, 1	PM2.5 concentration	5

where $\widehat{\beta}_t$ is estimated from the observations $i<t$ only, so that $\widehat{y}_t$ is formed before $y_t$ is revealed. The data are modeled as

with a possibly time-varying coefficient vector $\beta_t$. For the synthetic streams, ((6)) holds exactly with $\varepsilon_t\sim\mathcal{N}(0,1)$ and a known $\beta_t$.

Least-squares model (CP+LS, nexCP+LS). The static model uses all past observations with equal weight:

It is initialized on the first $T_{\mathrm{tr}}$ observations (which requires $A_{T_{\mathrm{tr}}+1}$ to be invertible) and keeps absorbing every new observation.

Forgetting model (nexCP+WLS, QT+WLS). The adaptive model discounts old observations exponentially with the forgetting factor $\rho_{\mathrm{LS}}\in(0,1)$:

Its effective memory is $N_{\mathrm{eff}}=1/(1-\rho_{\mathrm{LS}})\approx111$ observations.

Scores and prediction sets. Whichever model is used, $\hat{y}_t$ in (5) yields the score $R_t=\lvert y_t-\hat{y}_t\rvert$ and the interval

where $\hat{q}_t$ is the uniform, exponentially weighted or OGD quantile of § 3.1. The methods thus differ only through $\hat{\beta}_t$ and $\hat{q}_t$.

Oracle model. For a candidate value $y$ of the response, the full-CP oracle refits the weighted model on the augmented sample $\{(x_i,y_i)\}_{i\leq t}\cup\{(x_t,y)\}$, with the same weights $\tilde{w}_i=\rho_{\mathrm{LS}}^{t+1-i}$:

so that the oracle and nexCP+WLS fit the same weighted problem.

OLS updates via Sherman–Morrison. For the two methods using a static (unweighted) least-squares regressor, we avoid re-inverting a $p\times p$ matrix at every step via the Sherman–Morrison rank-one update, at $O(p^2)$ per step with no loss of exactness.

RLS updates. For the two methods that must also let the base model forget outdated observations, we use Recursive Least Squares with forgetting factor $\rho_{\mathrm{LS}}$, also $O(p^2)$ per step; observations older than roughly $N_{\mathrm{eff}}=1/(1-\rho_{\mathrm{LS}})$ steps are effectively forgotten.

The main empirical distinction (§ 4.1) is between methods that adapt only the quantile (CP+LS, nexCP+LS) and those that also adapt the model via forgetting (nexCP+WLS, QT+WLS): model adaptation turns out to be necessary, not optional, under drift.

Experiments and Results

Results and Interpretation

Table 3 reports the average coverage and width of each method, and Figure 1 shows their rolling counterparts. Additional results can be found in Appendices Section C on Figure 2.

Stream	Method	Coverage	Width
i.i.d.	Full CP (oracle)	.912 ± .021	3.41 ± .05
i.i.d.	CP+LS	.897 ± .006	3.28 ± .07
i.i.d.	nexCP+LS	.896 ± .002	3.30 ± .05
i.i.d.	nexCP+WLS	.897 ± .003	3.31 ± .05
i.i.d.	QT+WLS	.894 ± .010	3.27 ± .10
Changepoints	Full CP (oracle)	.911 ± .028	4.15 ± .06
Changepoints	CP+LS	.844 ± .007	6.26 ± .13
Changepoints	nexCP+LS	.891 ± .003	7.13 ± .14
Changepoints	nexCP+WLS	.903 ± .004	4.20 ± .08
Changepoints	QT+WLS	.876 ± .009	3.78 ± .11
Drift	Full CP (oracle)	.912 ± .024	3.45 ± .05
Drift	CP+LS	.836 ± .008	3.73 ± .06
Drift	nexCP+LS	.886 ± .003	4.30 ± .09
Drift	nexCP+WLS	.898 ± .002	3.36 ± .05
Drift	QT+WLS	.892 ± .010	3.30 ± .09
ELEC2	Full CP (oracle)	.897	0.521
ELEC2	CP+LS	.870	0.594
ELEC2	nexCP+LS	.891	0.606
ELEC2	nexCP+WLS	.893	0.509
ELEC2	QT+WLS	.899	0.515
Energy	Full CP (oracle)	.915	280.5
Energy	CP+LS	.920	355.8
Energy	nexCP+LS	.906	308.7
Energy	nexCP+WLS	.911	286.4
Energy	QT+WLS	.929	364.1
Bike	Full CP (oracle)	.867	3192
Bike	CP+LS	.740	3640
Bike	nexCP+LS	.836	4078
Bike	nexCP+WLS	.862	3190
Bike	QT+WLS	.773	2512
PRSA	Full CP (oracle)	.915	148.1
PRSA	CP+LS	.883	191.4
PRSA	nexCP+LS	.899	195.9
PRSA	nexCP+WLS	.900	148.2
PRSA	QT+WLS	.894	148.1

Synthetic data On the i.i.d. dataset, all online methods reach the nominal coverage (0.894 to 0.897) with widths within 2% of one another, so forgetting has no visible cost when the distribution is stable. The oracle slightly over-covers (0.912) with intervals 3 to 4% wider, consistent with the conservativeness of a finite-sample quantile computed on an effective sample of about 100 points. Under drift, the methods differ according to whether the base model forgets. With a static model, CP+LS under-covers (0.844 after the changepoints, 0.836 under

gradual drift), and nexCP+LS recovers 0.891 and 0.886 only by inflating its intervals by 72% and 25% with respect to the oracle (7.13 against 4.15, 4.30 against 3.45): the quantile must absorb an error that it did not cause. nexCP+WLS, whose model forgets, matches the oracle in both settings (coverages 0.903 and 0.898, widths 4.20 and 3.36). QT+WLS is as accurate under gradual drift (0.892, 3.30) but under-covers by about 2.5 points after abrupt breaks (0.876), as a tracker moving by increments of size $\eta$ needs several steps to recover.

Real world datastreams The four real streams confirm this ranking under drifts of unknown nature and intensity. On ELEC2 and PRSA, nexCP+WLS is almost indistinguishable from the oracle (0.893/0.509 against 0.897/0.521, and 0.900/148.2 against 0.915/148.1), and so is QT+WLS (0.899/0.515 and 0.894/148.1), whereas the static-model methods pay for the drift: nexCP+LS needs intervals 16% and 32% wider than the oracle’s, and CP+LS under-covers (0.870 and 0.883) despite intervals 14% and 29% wider. On Energy, whose target is heavy-tailed, every method over-covers; nexCP+WLS again follows the oracle, while CP+LS, nexCP+LS and QT+WLS need intervals 27%, 10% and 30% wider. Bike is the hardest stream, with only 731 daily points and a strong trend in demand: even the oracle under-covers (0.867), nexCP+WLS matches it (0.862, width 3 190 against 3 192), CP+LS falls to 0.740, and QT+WLS to 0.773 with intervals 21% narrower, as fewer than 600 online steps leave the tracker too little time to follow the drift.

Overall, what separates the methods is whether the base model forgets, not how the quantile is computed.

About the computational cost

The complexity of each method is summarized in Table 1 and we provide, in Table 4, the average computational time of each method per step.

Method	i.i.d.	Changep.	Drift	ELEC2	Energy	Bike	PRSA
Full CP	43.17	43.30	42.59	148.67	146.96	4.71	142.86
CP+LS	0.058	0.058	0.057	0.062	0.067	0.079	0.053
nexCP+LS	0.045	0.047	0.045	0.065	0.074	0.038	0.061
nexCP+WLS	0.047	0.052	0.052	0.069	0.088	0.032	0.057
QT+WLS	0.009	0.010	0.011	0.010	0.012	0.012	0.008

Storing residuals makes CP+LS and nexCP+LS 3 to 8 times slower than QT+WLS, yet with a static model this extra cost buys wider intervals, not better coverage. nexCP+WLS reaches the oracle’s accuracy on every stream at three orders of magnitude less, and QT+WLS, with constant time and memory, matches it on smooth drifts, at the price of a slower reaction to abrupt changes.

Conclusion

In this paper, we evaluated whether online conformal methods that adapt both the base model and the conformal quantile via forgetting factors can match the coverage and width of a true, unbounded history full CP oracle under distribution shift, rather than merely another online approximation. Across three synthetic regression regimes and four real-world benchmarks, which span different drift mechanisms, the methods that adapt the model (nexCP+WLS and QT+WLS) track the oracle’s coverage and interval width closely, while the methods that adapt only the quantile and leave the model static (CP+LS and nexCP+LS) fall short under drift. Furthermore, the experiments illustrate that QT+WLS has memory and per-step cost of $O(p^{2})$, independent of $t$, which makes it the only method suited to settings where storing the full history is not feasible.

Scope of the Model-Update Comparison

Concerning § 3.2, two gaps are worth stating explicitly rather than leaving implicit. First, QT+WLS has no exact full-CP counterpart: because it never revisits past residuals, there is no finite-history object it is a recursive approximation of: its validity follows from the ACI guarantee, not from matching a full-CP limit, so we report it for reference in § 4.1 but exclude it from the oracle-matching claim itself.

Experimental Protocol

We consider seven regression streams: three synthetic settings and four real-world datasets. In the three synthetic settings, $X_t \sim\mathcal{N}(0,I_4)$ and $Y_t = X_t^{\mathsf{T}}\beta_t + \varepsilon_t$ with $\varepsilon_t \sim\mathcal{N}(0,1)$, for $t = 1,\ldots,N = 2000$ and without intercept. The covariates and the noise are shared by the three settings, which differ only through the coefficients $\beta_t$. In the i.i.d. setting (setting 1), $\beta_t = (2,1,0,0)^{\mathsf{T}}$ is constant, which provides a stationary control. In the changepoint setting (setting 2), $\beta_t$ successively equals $(2,1,0,0)^{\mathsf{T}}$, $(0,-2,-1,0)^{\mathsf{T}}$ and $(0,0,2,1)^{\mathsf{T}}$ on $[1,500)$, $[500,1500)$ and $[1500,2000]$. In the gradual drift setting (setting 3), $\beta_t$ moves linearly from $\beta_{\mathrm{start}} = (2,1,0,0)^{\mathsf{T}}$ to $\beta_{\mathrm{end}} = (0,0,2,1)^{\mathsf{T}}$, that is $\beta_t = \beta_{\mathrm{start}} + \frac{t-1}{N-1}(\beta_{\mathrm{end}}-\beta_{\mathrm{start}})$, so that the last two settings connect the same two extreme models through an abrupt and a slow transition, respectively.

The three synthetic streams are complemented by four real streams, whose drift mechanism, unlike that of the synthetic ones, is unknown. ELEC2 ([10]) contains half-hourly records of the New South Wales electricity market. Following Zaffran [16], we discard the first 17 760 observations, during which the response is constant, and keep only the half-hours between 9:00 and 12:00, which leaves $N = 3\,444$ points. Energy ([6]) records the consumption of household appliances every 10 minutes, together with indoor and outdoor temperature and humidity measurements and two random variables, from 11 January 2016. Bike ([7]) gives the daily number of rented bicycles of the Capital Bikeshare system in 2011–2012 ($N = 731$), with calendar and weather covariates. PRSA ([12]) reports the hourly PM2.5 concentration in Beijing with meteorological covariates, starting in January 2010; the hours with a missing response are removed. For Energy, Bike and PRSA, the targets are, respectively, the appliances consumption, the daily count of rentals and the PM2.5 concentration. We remove the row identifiers and the covariates that are duplicated, constant or null on the training window, which would make the initial least-squares problem singular, as well as the casual and registered counts for Bike, whose sum is the response. To keep the exact oracle tractable, Energy and PRSA are truncated to their first $N = 3\,444$ observations, the length of ELEC2, which leaves $p = 26$, 10 and 11 covariates for Energy, Bike and PRSA, again $p = 4$ for ELEC2. Finally, as the step size $\eta$ of QT+WLS is expressed in the unit of the response, it is set to $\eta= 0.01\hat{\sigma}_Y$ on these three streams, where $\hat{\sigma}_Y$ is the standard deviation of the response on the training window; this is equivalent to standardizing the response and leaves the other methods unchanged.

The oracle is the exact weighted full-CP set of § 2.1, computed by the homotopy solver with the same exponential weights as nexCP+WLS, so that both solve the same weighted problem and differ only in whether the solution is recomputed from scratch or updated recursively. Because its cost grows with the history size, it is evaluated every 20 steps; its coverage, width and run time are averaged over these evaluation times, which does not bias the averages but increases their variance. We report the average empirical coverage, the average width $\frac{1}{T-T_0}\sum_{t=T_0}^{T}2\hat{q}_t$, and the mean wall-clock time per iteration computing:

For the online methods this time covers the prediction, the quantile computation and the model update. The curves of Figure 1 are smoothed by a rolling average of 50 steps (synthetic) or 300 steps (ELEC2).

Additional Experimental Results

We present, on Figure 2 the detailed results on the three remaining real data: Bike, PRSA and Energy, presenting the evolution of both coverage and interval width along time.