When a time-ordered dataset is shuffled before being split into training and test sets, each test point arrives with its temporal neighbors already in the training set. These are observations from minutes, hours, or days earlier and later, often nearly identical to it. A model that memorizes training data can then "predict" the test point by recalling its neighbors. This proposal argues that the resulting optimism is a form of algorithmic stability, which is not arbitrary noise. Algorithmic stability is the property that a model's prediction changes little when a few training points are removed. We propose to measure one specific version of it: how much a model's loss on a test point rises when the training points within a temporal window around that point are deleted. We call this quantity neighborhood stability. Our central prediction is that this one number, together with a separately measured drift term, accounts for most of the inflation that random splits produce. It should also explain a striking symptom: learning curves under random splits decay at fast, interpolation-like rates that disappear under chronological evaluation.
The practical stakes are concrete. Random splitting inflated flight-delay AUC by an average of 0.057 on the Aeolus dataset (Aeolus). Recommender rankings across 230 configurations reached only Kendall's τ = 0.5284 agreement between leave-one-last and global temporal splits on Dunnhumby (Exploring Data Splitting Strategies). Market-forecasting models that looked accurate under shuffling fell to near chance under rolling windows (Pyo et al.). These papers document the gap but do not say which models will be inflated, by how much, or why the inflation grows with data. We want a per-model, mechanistic prediction of the gap and a principled way to split it into its parts.
Core Claim
Let $R_{\text{rand}}$ be the test risk measured under a random split, $R_{\text{chron}}$ the risk on a strictly later time block, and $R_{\text{gap}}(b)$ the risk under a random split that additionally deletes, or "purges," all training points within $b$ time steps of each test point. We claim the inflation decomposes as
$$ R_{\text{chron}} - R_{\text{rand}} \;=\; \underbrace{\big(R_{\text{gap}}(b) - R_{\text{rand}}\big)}_{\Delta_b:\ \text{neighbor recall}} \;+\; \underbrace{\big(R_{\text{chron}} - R_{\text{gap}}(b)\big)}_{D:\ \text{drift / future-distribution access}}. $$
The first term, $\Delta_b$, equals the expected increase in loss at a held-out point $z$ when its $b$ temporal neighbors $N_b(z)$ are removed from the training set $S$. It is therefore $\mathbb{E}[\ell(A(S\setminus N_b(z)), z) - \ell(A(S), z)]$, where $A(S)$ is the model trained on $S$ and $\ell$ is the loss. This is a leave-neighborhood-out stability quantity, and it can be estimated directly by retraining.
The second term, $D$, is what remains once local dependence has been removed. It comes from the shuffled training set containing samples from the future distribution, which is the drift effect stressed by Simonetto et al..
The decomposition itself is an identity. The substantive claims are three.
First, $\Delta_b$ can be predicted from cheap stability measurements and saturates once $b$ exceeds the dependence length of the series.
Second, $\Delta_b$ is large for models that interpolate and small for strongly regularized ones. This ordering follows the classical intuition that uniformly stable algorithms (Hardt et al.) have no individual point with excessive leverage.
Third, $R_{\text{rand}}$ exhibits spuriously fast learning-curve exponents. As $n$ grows, the temporal spacing between a test point and its nearest training neighbor shrinks. For an interpolating model, the error at a point between two nearby memorized points falls quickly with spacing. We therefore expect random-split error curves for interpolating models to look like $O(1/n)$ or steeper, while purged and chronological curves stay near $O(1/\sqrt{n})$ or plateau. This is a heuristic expectation that the experiments will test; we do not assume it.
This reverses the usual reading of fast rates. Work on the rate gap shows that interpolating models genuinely achieve test risk far below $O(1/\sqrt{n})$, reaching $O(1/n^2)$ in noiseless random-feature models (Exact Gap). Empirical-variance and relative-deviation bounds explain such fast rates when training loss vanishes (Relative Deviation Margin Bounds, Evaluated CMI Bounds). All of that work assumes independent test points. Our claim is that on dependent data, part of an observed fast rate can be counterfeit. Neighborhood stability is the quantity that separates the genuine part from the counterfeit part.
Relation to Prior Work
The closest theory consists of stability bounds for dependent data. Mohri & Rostamizadeh extend stability to stationary mixing processes using an independent-block construction and obtain $O(1/\sqrt{m})$ bounds for kernel ridge and support vector regression. Fu et al. sharpen this to near-optimal $O(1/\sqrt{n})$ bounds by deleting buffer zones of $b$ points to create an effective sample size.
Both papers supply method for us: the buffer construction is exactly our purge. Both also constrain us. They assume stationarity, so their bounds cover $R_{\text{gap}}$ and say nothing about $D$. They also bound the true generalization gap; they do not explain why a random-split estimate would undershoot it.
We do not attempt to prove fast-rate stability bounds for mixing processes, which is the obvious extension of their work. We use their buffer device to diagnose evaluation optimism, and we show that the rate that appears under shuffling is itself a symptom of leakage.
The empirical leakage literature motivates this proposal. That literature includes Aeolus, Meng et al., Simonetto et al., and the buffer gaps used in ENSO forecasting (Temporal Convolutional Networks for ENSO). These papers measure aggregate inflation but have no per-model predictor and no separation of local recall from drift.
WOODS shows that invariance methods rarely beat empirical risk minimization on time-domain shifts. That result tells us to treat drift ($D$) as something to measure, not something to remove with an off-the-shelf method.
FreKoo regularizes parameter trajectories across time domains. It is a strong chronological model, and we use it as a reference point, not as a competitor to our diagnostic.
Research Program
The first component is a small formal result for two analyzable learners: kernel ridge regression and k-nearest-neighbor or random-feature interpolation, both on a stationary mixing process with a smooth target. For these learners we will show that $\Delta_b$ is bounded above by a neighborhood analogue of uniform stability plus a mixing coefficient at lag $b$, and that $\Delta_b$ vanishes for $b$ beyond the dependence length. We will also derive how $R_{\text{rand}}$ scales with $n$ when the ridge penalty goes to zero, compared with when it is held fixed. Leave-neighborhood-out residuals have closed forms for kernel ridge, so the theory and the measurements can be checked against each other exactly. We will add the drift term under a bounded-drift assumption, but we will not claim a general theory of non-stationarity.
The second component is an estimator. Retraining with deletions for every test point is expensive. We will therefore estimate $\Delta_b$ on a random subsample of 200 to 500 test points, retraining once per point for models where closed forms do not exist, such as gradient boosting and small neural networks. We sweep $b$ to locate the saturation point $b^\star$, the smallest gap beyond which $\Delta_b$ stops growing. The deliverable is a curve of $\Delta_b$ against $b$ for each model. This curve says how large a purge gap is enough, and it predicts each model's inflation before any chronological test is run.
The third component is an audit of the learning-curve exponents of every model under random, purged, and chronological splits. We fit a slope on log-log axes over at least five training-set sizes.
Baselines
The naive reference point is the random-split estimate $R_{\text{rand}}$ itself, which is what leaky benchmarks report. A predictor of inflation that does no better than "every model is inflated by the dataset-average amount" adds nothing. On Aeolus, that constant predictor is the reported average AUC inflation of 0.057 (Aeolus). Our measured $\Delta_b + D$ must predict per-model inflation with clearly lower error than this constant, and it must achieve a substantially positive rank correlation with the observed per-model gaps.
The ground-truth reference is strict chronological evaluation. We use the published 6:2:2 split on Aeolus and global temporal splits on Dunnhumby, following Meng et al.. For the delayed setting we use rolling windows with a label-plus-deployment delay, following Simonetto et al.. Every split uses the same models, the same feature pipelines with normalization fitted on training data only, and the same hyperparameter budget, tuned on a validation block that respects each split's own rules.
The strongest competing estimator is purged random cross-validation with a fixed gap. This applies the buffer idea of Fu et al. and of the ENSO work as an evaluation protocol. We found no reported result on Lacuna for purged cross-validation on these benchmarks. We will run it with the gap set by common heuristics, either one seasonal period or the autocorrelation decay length, using the same compute as our method. Our method beats it if two things hold: the saturation point $b^\star$ from the $\Delta_b$ curve gives a purged estimate closer to chronological risk at equal or smaller data loss, and the residual $D$ explains the remaining gap where purging alone falls short.
For context on chronological performance, on Elec2 the best reported error is FreKoo's 9.2%, against a previous best of 11.8% (FreKoo).
Two ablations isolate the key ingredient. The first replaces temporal-neighborhood deletion with deletion of an equal number of randomly chosen training points. This is ordinary on-average stability in the sense of Evgeniou et al.. If random deletion predicts inflation equally well, then temporal structure is not doing the work, and the claim fails. The second ablation drops the $D$ term. This shows how much of the inflation on drifting datasets such as Lending Club Loan Data, Elec2, and Aeolus comes from future-distribution access rather than neighbor recall.
Why not just…?
Why not just always split chronologically? For new work, one should. Our proposal does not replace chronological evaluation; it uses it as ground truth. The value lies elsewhere. Our method tells you which existing random-split results are inflated, and by how much, using only neighborhood-deletion runs on the original data. It also explains why the inflation varies by model, which is what makes rankings flip at τ = 0.5284 (Meng et al.). A chronological split also confounds generalization with drift (Simonetto et al.). The decomposition separates the two, which a single chronological number cannot do.
Why not just use purged cross-validation with a buffer gap? This is the real threat. If a heuristic gap already recovers chronological risk on every benchmark, then the stability analysis reduces to a gap-selection rule. The experiment settles this directly. We expect purging to close the gap on stationary-looking series such as AusElec. We expect it to leave a large residual on drifting ones such as Aeolus and Lending Club, where the shuffled training set still contains future regimes. If that residual is negligible everywhere, we will report that the useful contribution is the $\Delta_b$-based choice of $b^\star$, and nothing more.
Why not just use the effective-sample-size correction of mixing-process stability bounds? The bounds of Fu et al. and Mohri & Rostamizadeh control the true gap for stationary data at the slow rate. They are worst-case over models and do not predict that an interpolating network will be inflated more than a ridge model. We test this by checking whether a bound-derived correction, which is identical for all models with the same stability constant, ranks per-model inflation as well as measured $\Delta_b$ does.
Why not just report the empirical gap, as Aeolus does? An aggregate gap cannot be computed for a single model before a chronological holdout exists, and it says nothing about rates. Our learning-curve audit makes a falsifiable claim that the aggregate gap cannot: the random-split exponent should be steeper than the purged exponent, and the difference should scale with $\Delta_b$.
Proposed Experiments
The datasets are Aeolus, using the tabular and flight-chain modalities; Elec2; WOODS AusElec and PedCount; Lending Club Loan Data with a simulated 38-day delay; and Dunnhumby for ranking stability. The models span the stability range. They are kernel ridge regression at several penalties, including near-interpolation; random-feature regression; gradient-boosted trees; an MLP trained with SGD for a short budget and for a long budget, to vary stability along the lines suggested by Hardt et al.; and FTTransformer or an LSTM on Aeolus.
Three checks are decisive. First, across all model-dataset pairs, the measured $\Delta_{b^\star}$ plus $D$ should correlate strongly with the observed random-versus-chronological gap, and it should beat the random-deletion ablation. Second, interpolating models should show steeper random-split learning-curve slopes than purged slopes, and regularized models should show little difference. If slopes are equal across splits for all models, the "manufactured fast rate" claim is false. Third, ranking models by $R_{\text{gap}}(b^\star)$ adjusted by $D$ should agree with chronological rankings, with a Kendall τ well above the 0.5284 agreement that leave-one-last splits achieve on Dunnhumby. Each check can fail independently, and we will report each one separately.
References
- Aeolus: A Multi-structural Flight Delay Dataset
- Exploring Data Splitting Strategies for the Evaluation of Recommendation Models
- Predictability of machine learning techniques to forecast the trends of market index prices: Hypothesis testing for the Korean stock markets
- On the Impact of Industrial Delays when Mitigating Distribution Drifts: An Empirical Study on Real-World Financial Systems
- Train faster, generalize better: Stability of stochastic gradient descent
- Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
- Relative Deviation Margin Bounds
- Evaluated CMI Bounds for Meta Learning: Tightness and Expressiveness
- Stability Bounds for Non-i.i.d. Processes
- Sharper Bounds for Uniformly Stable Algorithms with Stationary Mixing Process
- Temporal Convolutional Networks for the Advance Prediction of ENSO
- WOODS: Benchmarks for Out-of-Distribution Generalization in Time Series
- Learning Robust Spectral Dynamics for Temporal Domain Generalization
- Leave One Out Error, Stability, and Generalization of Voting Combinations of Classifiers