When +1% Is Not Enough: A Paired Bootstrap Protocol for Evaluating Small Improvements
Du Wenzhang · 2025
Read When +1% Is Not Enough: A Paired Bootstrap Protocol for Evaluating Small Improvements by Du Wenzhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-19794.txt.
Introduction
Wenzhang Du warns that small machine learning gains are often noise dressed as progress. Papers routinely claim one or two point improvements from a single run, yet scores swing with random seeds, data order, and minor code details. Under real budgets only a few runs are affordable, so the test must be strict.
The proposed protocol pairs runs across seeds, builds bias-corrected bootstrap confidence intervals, and adds a sign-flip permutation test on per-seed differences. On CIFAR and AG News scenarios, single runs and unpaired tests often bless phantom gains. The paired protocol, even with three seeds, never does, acting as a guardrail against over-claiming.
Catalog record
| CREATOR | Du Wenzhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-19794
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When +1% Is Not Enough: A Paired Bootstrap Protocol for Evaluating Small Improvements Du Wenzhang Abstract Recent machine learning papers often report one–two percentage point improvements from a single run. These gains are measured on standard benchmarks and are highly sensitive to random seeds, data ordering, and implementation details, yet are rarely accompanied by uncertainty estimates or significance tests. It is therefore unclear when a reported “+1–2%” reflects a real algorithmic advance versus noise. We revisit this problem under realistic compute budgets, where only a few runs are affordable. We propose a simple, PC-friendly protocol based on paired multi-seed runs, bias-corrected and accelerated (BCa) bootstrap confidence intervals, and a sign-flip permutation test on per-seed deltas. The protocol is intentionally conservative and is meant as a guardrail against over-claiming. We instantiate it on CIFAR-10, CIFAR-10N, and AG News using synthetic “no-improvement”, small-gain, and medium-gain scenarios. Single runs and unpaired t t -tests often suggest significant gains for 0.6–2.0 point improvements, especially on text. With only three seeds, our paired protocol never declares significance in these settings. We argue that such conservative evaluation is a safer default for small gains under tight budgets. 1 Introduction Single numbers still dominate empirical reporting in machine learning. A typical paper trains a baseline and a new variant once, reports a difference of one or two percentage points on a benchmark, and concludes that the new method “significantly outperforms” the baseline. Yet a growing body of work has shown that performance can vary substantially across random seeds, data orderings, and even hardware and library versions [ 1 , 2 , 3 , 8 , 9 ] . Small improvements are particularly fragile: a different seed or slightly different environment may erase or reverse the observed gain. Despite this, multi-seed reporting and principled uncertainty quantification remain the exception rather than the rule. When authors do repeat experiments, they often apply unpaired t -tests that assume independence and approximate normality, conditions that may not hold for small samples and skewed metric distributions [ 5 , 6 , 7 ] . Moreover, many practitioners can afford at most a handful of seeds (e.g., three), making classical asymptotic arguments even less convincing. In this paper we do not propose yet another training trick. Instead, we turn the knife toward evaluation itself and ask: Given a small number of runs and a small apparent improvement, how can we avoid over-claiming success? Our answer is a simple protocol that any lab can run on a single consumer GPU. For each of k random seeds, we train both the baseline and the new variant under identical conditions (same data split, same seed, same number of epochs), record the per-seed metric difference, and then analyse these deltas with a BCa bootstrap interval and a sign-flip permutation test. A method is allowed to claim a “significant improvement” only if the BCa interval lies entirely above zero and the permutation p -value is below a chosen threshold (we use 0.05). Otherwise, the default recommendation is not to claim significance. We study how this protocol behaves in realistic small-gain settings by constructing controlled scenarios on three benchmarks—CIFAR-10, CIFAR-10N, and AG News—with no, small, and medium modifications. We compare three evaluation schemes: (i) single-run deltas; (ii) unpaired Welch t -tests on independent runs; and (iii) our paired BCa+permutation procedure. Empirically we find that single-run comparisons and unpaired tests frequently report apparently significant gains, especially on noisy labels and text [ 14 , 15 ] , while our protocol systematically refuses to endorse 0.5 – 2 percentage-point gains when only three seeds are available. Our contributions are: 1. A simple, paired evaluation protocol for small improvements that combines per-seed deltas, BCa bootstrap confidence intervals, and sign-flip permutation tests into a conservative decision rule. 2. A controlled case study across three benchmarks and synthetic S0/S1/S2 scenarios, showing how standard practice overstates evidence for small gains, while our protocol behaves as a guardrail against over-claiming. 3. Practical guidance for authors and reviewers on interpreting small improvements under tight compute budgets. 2 Related Work 2.1 Reproducibility and variance in ML experiments Multiple studies have documented substantial run-to-run variance in deep learning experiments, arising from random initialisation, mini-batch sampling, data ordering, and implementation quirks [ 1 , 2 , 3 , 8 , 14 ] . Such variance can reorder model rankings and invalidate conclusions drawn from single runs, especially on modest-size benchmarks. Reproducibility initiatives and checklists for major conferences encourage authors to report seeds, hyperparameters, and environment details, and to release code when possible [ 4 , 9 ] . These efforts improve transparency but do not by themselves answer the question of how many runs are enough, or how to aggregate a small number of runs into a statistically grounded conclusion. Our work is complementary: we focus not on open-sourcing or environment management, but on the statistical layer on top of a handful of runs. 2.2 Statistical comparison of learning algorithms Classical work on comparing classifiers advocates a variety of tests, including cross-validated t -tests, the 5 \times 2CV test, Wilcoxon signed-rank tests, and permutation methods [ 5 , 6 , 12 ] . These approaches typically assume reasonably large sample sizes (either many datasets or many folds) and i.i.d. conditions. In modern deep learning, we often have the opposite: a single dataset, few seeds, and complicated dependence structures. Bootstrap methods have been proposed as more robust alternatives for non-Gaussian, skewed metrics. The BCa bootstrap adjusts for bias and skewness in the resampled distribution and enjoys good asymptotic properties [ 10 , 11 ] . Permutation tests provide finite-sample control of type-I error under symmetry assumptions [ 12 ] . Our protocol builds on these tools but adapts them to the per-seed delta setting, where we explicitly exploit pairing and accept that the number of deltas is tiny ( k\approx 3 ). 2.3 Multi-seed reporting and paired evaluation In NLP and vision, several recent papers have argued for reporting score distributions over random seeds and for stronger statistical testing [ 8 , 7 , 9 ] . They show that rankings between models can flip when new seeds are added, and that standard practice often underestimates variance. These works typically use unpaired tests or cross-dataset comparisons. We extend this line by (i) formalising a paired delta + bootstrap + permutation pipeline, and (ii) empirically characterising its behaviour as a conservative filter in realistic small-gain scenarios. 3 Paired Bootstrap Evaluation Protocol 3.1 Problem setting We consider two models: a baseline M_{0} and a variant M_{1} . Given a dataset D and a performance metric \theta(\cdot) (e.g., test accuracy), each training run produces a random outcome due to stochastic optimisation and data sampling. Let X and Y denote the metric for M_{1} and M_{0} respectively in one run. The quantity of interest is the expected improvement \Delta_{\mathrm{true}}=\mathbb{E}[X-Y]. We aim to answer: Is \Delta_{\mathrm{true}} clearly positive, zero, or negative? Given only a small number of runs k , how cautious should we be in claiming \Delta_{\mathrm{true}}>0 ? 3.2 Paired multi-seed design We adopt a paired design. For each seed s_{i} , i=1,\dots,k : 1. Fix all randomness (initialisation, data shuffling, augmentation) via seed s_{i} . 2. Train M_{0} and evaluate \theta_{0,i} on a fixed