Leaf-Local, Time-Decayed Out-of-Bag Calibration for Streaming Random Forests

Random forests are a common workhorse for forecasting energy load, solar output and air quality. In these streams, prediction intervals (ranges meant to contain the true value, say, 90% of the time) must stay honest as the data drifts. The existing tools split into two camps. One camp uses "out-of-bag" residuals: each tree is trained on a random resample of the data and never sees about 37% of the points, so the errors on those unseen points act as free validation data. The other camp uses online feedback rules that widen or shrink intervals after each observed miss. The first camp assumes the data never drifts. The second applies a single global correction that treats every region of input space the same.

We propose to have the forest decide which past errors matter for the current prediction. For a new input, we take recent out-of-bag residuals and weight each one by how often it shared a leaf with the new input. We count only trees that never trained on that residual's point, and we discount older residuals exponentially. An adaptive feedback rule then sits on top of this local estimate and keeps long-run coverage at the target. The tree structure itself changes only slowly, while the calibration changes at every step. This split of timescales is how we reconcile the stability that makes out-of-bag errors trustworthy with the speed needed to track drift.

Core Claim

Interval width under drift should depend on both "when" and "where." The forest's own partition, read only through trees for which a calibration point was out-of-bag, gives a cheap and principled way to say "where." Concretely, let $t$ be the current time and $x$ the new input. Let $r_i$ be the out-of-bag residual of an earlier point $i$, and $B_i$ the set of trees that did not train on $x_i$. Let $\lambda \in (0,1)$ be a decay rate. We define the weight

$$w_i(x) = \lambda^{\,t-i}\,\frac{1}{|B_i|}\sum_{b \in B_i} \mathbf{1}\{\text{leaf}_b(x) = \text{leaf}_b(x_i)\}.$$

The interval is the forest prediction plus or minus the weighted $(1-\alpha_t)$ quantile of the residuals $r_i$ under weights $w_i(x)$, with a point mass at infinity for the test point. The level $\alpha_t$ is updated by the adaptive conformal inference rule $\alpha_{t+1} = \alpha_t + \gamma(\alpha - \text{err}_t)$ from Adaptive Conformal Inference Under Distribution Shift. Here $\alpha$ is the target miss rate, $\gamma$ the step size, and $\text{err}_t$ indicates a miss.

That rule guarantees long-run coverage for any sequence of interval constructions, so the guarantee is inherited rather than claimed anew. What is new is the construction underneath it. A tree in $B_i$ never trained on $x_i$, and the test point is also unseen, so the leaf-sharing weight does not peek at either point's label. That is the property localized weighted conformal methods need. The testable claim is that this construction gives narrower intervals and markedly better coverage within feature regions and within volatile periods, at the same marginal coverage.

Where This Sits

The closest work is EnbPI, from Conformal Prediction for Time Series and its precursor Conformal prediction interval for dynamic time-series. EnbPI already combines bootstrap ensembles, leave-one-out residuals and a sliding residual window. It pools residuals from all feature regions into one global quantile, and the authors themselves report under-coverage during localized volatility such as solar noon. Our proposal keeps EnbPI's out-of-bag and online ingredients and changes exactly one thing: residuals are pooled by forest co-membership and recency rather than uniformly. EnbPI therefore serves as both motivation and the main baseline.

Three static out-of-bag methods supply our machinery. Regression conformal prediction with random forests showed out-of-bag residuals can replace a calibration set, and localized intervals with a k-nearest-neighbour error normalizer (RFok). That normalizer costs a search over the training set for every test point, whereas leaf lookups come free with prediction. Nested conformal prediction and quantile out-of-bag ensemble methods (QOOB) shows out-of-bag quantile forests give the sharpest static intervals, especially at $n \le 100$, but it assumes exchangeable data. Stability of Random Forests and Coverage of Random-Forest Prediction Intervals proves out-of-bag intervals cover at $1-\alpha-O(\sqrt{\nu_{n,B}})$ because forests are stable, where $\nu_{n,B}$ measures how much the forest changes when one point is removed.

That stability result is a constraint on design. If we rebuilt trees on every arrival to chase drift, we would erode exactly the property that makes out-of-bag residuals mirror test errors. Hence the slow tree schedule.

Split Localized Conformal Prediction motivates localization by showing global thresholds over-cover easy regions and under-cover hard ones. Its kernel smoothing is quadratic in calibration size and needs a held-out split. Forest-kernel ideas such as Random forest kernel for high-dimension low sample size classification suggest leaf co-membership is a meaningful similarity, but none use it for streaming calibration.

Online Conformal Prediction via Online Optimization models temporal autocorrelation in a one-dimensional score series and points out ACI's bang-bang behaviour. It is complementary: its tracker could replace ACI as our top layer. It is also a competitor if temporal modelling alone captures most of the gain.

Research Program

We will build a streaming forest that maintains $B$ trees. Every $k$ steps, the oldest tree is replaced by one trained on a fresh bootstrap of a recent window. For each stored point $i$ we record which current trees left it out. When a tree is replaced, we update its out-of-bag predictions and leaf indices for points in the window, at a cost linear in window size per refresh rather than per step.

At each arrival, the system does four things in order. It predicts, computes the leaf-weighted, time-decayed quantile, issues the interval, and then, once the label arrives, updates $\alpha_t$ and appends the new residual. The new point is out-of-bag for all existing trees, so its residual is honest immediately.

The analysis has two parts. The first is an empirical decomposition of how much of the gain comes from locality, how much from recency, and how much from the feedback layer. The second is a modest theoretical statement. Under a frozen forest and exchangeable data, our weights satisfy the conditions of weighted conformal prediction, giving near-nominal local coverage. Under drift, coverage comes from the ACI layer. We will also measure empirically how quickly local coverage degrades as the refresh period $k$ shrinks, which directly probes the stability-versus-agility tension.

Baselines

The do-nothing reference is split conformal prediction over a frozen random forest. A held-out calibration slice from the training period sets one fixed width. It is run on the same training data, minus that slice, with the same forest hyperparameters. It shows how badly static intervals fail. For context, CUQDS: Conformal Uncertainty Quantification Under Distribution Shift for Trajectory Prediction reports static conformal coverage of 0.402 against 0.746 for its dynamic controller under shift, on a different model class.

The strongest existing out-of-bag streaming method is EnbPI with a random forest base learner and its sliding residual window, plus a variant with ACI layered on top. For width, the best number in the file is from Ensemble Conformalized Quantile Regression for Probabilistic Time Series Forecasting. On Solar it reports a normalized average width (PINAW) of 0.631 for EnbPI and 0.354 for EnCQR with an LSTM backbone, both near 90% coverage. EnCQR is therefore the strongest reported width result on that benchmark. We will rerun it on our splits rather than copy the number.

For temporal tracking, we include linear quantile tracking over the forest's global out-of-bag score. The file gives only a relative result for it: a 10% set-size reduction over the best baselines on ERCOT, with no absolute width reported.

A localized competitor is RFok's k-nearest-neighbour normalization applied to a sliding window. A quantile regression forest refit on a rolling window with ACI on top is a further competitor (see below). All methods share identical forests where applicable, the same window length, the same refit schedule, and a matched tuning budget over decay rate, window and step size, chosen on an early prefix of each stream.

Two ablations isolate the key ingredient. One sets all leaf weights to one, which recovers time-decayed EnbPI with ACI. The other uses in-bag rather than out-of-bag leaf sharing.

Beating the field means matching nominal marginal coverage within one percentage point while reducing worst-group coverage error, measured over hour-of-day bins and forest-leaf clusters. We also require mean width at or below EnbPI, and competitive with rerun EnCQR on Solar.

Why not just…?

Why not just put ACI on top of EnbPI? This is the ablation with uniform weights. ACI fixes long-run marginal coverage but adjusts a single global level. Split Localized Conformal Prediction shows global thresholds trade over-coverage in easy regions for under-coverage in hard ones. If uniform weights match ours on per-hour and per-region coverage, locality buys nothing and we will say so.

Why not just use a quantile regression forest refit on a rolling window, with ACI? This is the most serious threat, because such a forest already produces input-dependent intervals. The difference is that its quantiles come from in-bag responses sitting in the same leaves the tree was fit to, which tends to make them overconfident. Our quantiles come from out-of-bag residuals. If the rolling quantile forest with ACI matches our width and local coverage, the contribution collapses to "use QOOB online." That would still be a useful finding, and we would report it as such. The in-bag versus out-of-bag ablation is designed to settle this directly.

Why not just model temporal autocorrelation with linear quantile tracking? Online Conformal Prediction via Online Optimization shows strong gains from temporal modelling. Its tracker, however, sees only a scalar score series and cannot tell which region of input space is drifting. We test it both as a competitor and as a replacement for our ACI layer. If it wins on streams whose drift is purely temporal (Elec2), but loses where drift is regional (Solar, where hour of day carries the change), that delineates when locality matters.

Proposed Experiments

We will use streams the cited work established. These are the solar radiation series for Atlanta and the California cities, Hackberry wind, and Beijing air quality and appliances energy from the EnbPI papers. We add ERCOT and Elec2 from the online-optimization and drift literature. Static sanity checks use the UCI sets from the stability paper (Concrete, Airfoil, Naval).

Metrics are coverage probability (PICP) and PINAW overall, and coverage within hour-of-day bins and within clusters of forest leaves. We also report rolling-window coverage around detected shift points, interval churn measured as the step-to-step change in width, and per-step latency against RFok.

The decisive checks are three. On Solar, coverage at the noon transition should rise toward 90% where EnbPI dips, without widening intervals overall. The in-bag ablation should be measurably worse in local coverage. Shrinking the refresh period $k$ should first improve tracking and then degrade local coverage, which would make the stability tension visible and give a concrete rule for choosing $k$.