Exact Variance Identity Picks the Best Cross-Validation Design

Two researchers have derived an exact, finite-sample expression for the variance of a cross-validated performance estimate, and it delivers a practical verdict: at a matched training-set size, plain K-fold is variance-optimal at first order, while Monte Carlo split-sampling and the bootstrap are not. For anyone who reports a cross-validated score with an error bar, that turns a habitual default into a defensible choice.

The preprint, "A Theory of Cross-Validation Variance," comes from Nathaniel S. O'Connell of the Department of Biostatistics and Data Science at Wake Forest University School of Medicine and Jaime L. Speiser, the listed corresponding author. According to the arXiv record (2611.14463v1, dated 10 November 2026), it runs 27 pages of main text plus 57 pages of supplementary material across six sections, carries one figure, and is released under a CC BY 4.0 licence.

What did the paper prove?

The central result is an identity for the variance of the cross-validated estimate that the authors say holds exactly, at every sample size, for any resampling design that trains on the same fraction of the data in every split. Instead of analysing each scheme in isolation, they model cross-validation as a randomized design in which both the sample and the splits vary, and the splits decide how much weight each observation carries in validation and in training. Written that way, the variance becomes a function of those weights, with constants supplied by the model, the metric and the population. According to the authors, the identity covers metrics averaged over observations, such as squared error and the Brier score, and, given the labels, metrics averaged over case–control pairs such as the AUC. Earlier variance representations by Burman (1989), Nadeau and Bengio (2003), Bengio and Grandvalet (2004) and Austern and Zhou (2020) fall out as special cases.

Why does each observation count twice?

Because every data point plays two parts. It is scored when it sits in the held-out fold, and it helps fit the models that score the other points when it sits in the training set, which makes held-out evaluations correlated through the training data they share. The random splits set the weight in each part. From this, the paper separates the variance into two pieces: sampling variance, which comes from which observations ended up in the dataset and depends only on the training size, and split noise, which comes from the random assignment of observations to folds and appears when the weights change from one draw of the splits to the next. At a fixed training fraction, the authors argue, every design carries the same sampling variance and differs only in split noise, so a design whose weights do not vary is variance optimal.

Is K-fold really the lowest-variance choice?

At first order, according to the paper, yes. K-fold weights observations equally by construction, so it is balanced and therefore variance optimal at first order, a property Monte Carlo and bootstrap cross-validation lack. Two further results follow: the first-order variance of K-fold does not depend on the number of folds, and, under additional conditions on the model, leave-one-out has the smallest variance of any K-fold scheme. With a fixed fitting budget, the authors say the preference is for a single run with as many folds as possible, with leave-one-out as the limiting case. The comparison is drawn at matched training size, which is the same footing under which Arlot and Lerasle (2016) found K-fold preferable to Monte Carlo splitting for least-squares density estimation and credited the balanced use of observations.

What changes for AUC and other pairwise metrics?

Pairwise metrics break the tidy story, and the paper says so. Ordinary K-fold only evaluates case–control pairs that land in the same held-out fold, which adds split noise that grows with the number of folds. The remedy the authors point to is paired K-fold (Yousef, 2019), which evaluates every case–control pair, removes that noise and approaches leave-pair-out, the pairwise analogue of leave-one-out. This matters because widely used fixed-model formulas, such as DeLong's for the AUC (DeLong et al., 1988), quantify only the uncertainty coming from the evaluation observations and say nothing about the models being refit. The supplementary material extends the treatment to variants including the .632 and .632+ estimators, and includes a one-nearest-neighbour regression example where one of the paper's regularity conditions fails.

Can you put a confidence interval on a cross-validated score?

The paper proves that the cross-validated estimate is asymptotically normal with the identity's full variance, including higher-order terms, and that with a positive limiting variance a consistent estimate of it yields valid Wald intervals and tests. It also works through which terms several existing variance estimators actually capture. One caveat the authors keep in view: Bengio and Grandvalet (2004) showed that no distribution-free unbiased estimator of K-fold variance exists, and this paper does not claim to overturn that. What it offers instead is an exact account of what the variance is made of, plus the asymptotic justification for interval estimates built on it. An empirical verification section accompanies the theory.

How to work through it in Grafy

The paper is a good candidate for Grafy Reader, which can read, search and question PDFs and papers with AI: load the arXiv PDF and ask targeted questions, such as where the dual-role weights enter the proof of the variance identity, or what condition leave-one-out needs to be the minimum-variance K-fold scheme. For the intuition, Grafy Chat can put the same question to several models side by side, which is useful on a topic where the Hoeffding decomposition and the split-noise argument are easy to state badly. To check the claims yourself, Grafy Code can write and run the simulations the paper's empirical section describes, comparing the split noise of K-fold, Monte Carlo and paired K-fold at a fixed training size.

Frequently asked questions

Is K-fold cross-validation the variance-optimal design in this paper?

At first order, yes. Because K-fold weights every observation equally by construction, those weights do not shift between draws of the splits, so it carries no split noise at that order, while Monte Carlo and bootstrap designs do. The authors add two qualifications: the first-order variance does not depend on the number of folds, and under extra conditions on the model, leave-one-out has the smallest variance of any K-fold scheme.

Does the number of folds change the paper's variance identity?

No. The identity is written in terms of the weights each observation receives in validation and in training, and it holds exactly at every sample size for any scheme that trains on the same fraction of the data in each split. What does move with the fold count is split noise for pairwise metrics: ordinary K-fold evaluates only the case–control pairs that share a fold, and the paper says that noise grows as the number of folds rises.

Does the paper provide an unbiased estimator of cross-validation variance?

No, and it does not attempt to. Bengio and Grandvalet (2004) established that no distribution-free unbiased estimator of K-fold variance exists, a result the authors cite rather than challenge. What the paper contributes is an exact expression for the variance itself, a proof that the cross-validated estimate is asymptotically normal with that full variance, and an analysis of which terms existing variance estimators capture.

---

Source: Grafy Research Lab — A Theory of Cross-Validation Variance