When +1% is Not Enough: A Paired Bootstrap Protocol for Evaluating Small Improvements

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-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.