Disk Layout Sets the Shuffling Noise: Gradient-Balanced Block Orders for Out-of-Core Training

When a training set is too large for memory, data loaders stop shuffling individual examples. They read contiguous blocks from disk, because random small reads are slow. To recover some randomness, they visit the blocks in random order and shuffle examples inside an in-memory buffer. Systems built this way report large speedups while matching the accuracy of true random sampling. Optimization theory for "random reshuffling", meaning a fresh permutation of the data every epoch, says the speed of convergence is governed by one quantity: how far the running sum of per-example gradients strays from zero partway through an epoch. Block-structured loaders change exactly this quantity, and nobody has measured or bounded by how much. We argue the damage is set by the disk layout and is largely untouched by the buffer. If examples stored near each other have similar gradients, as with plate-ordered single-cell files or class-sorted image folders, then random block order inflates this running-sum noise by roughly the "design effect" familiar from cluster sampling in surveys, $1+(b-1)\rho$. Here $b$ is the block size and $\rho$ is the fraction of gradient variance explained by block membership. Enlarging the shuffle buffer leaves the inflation unchanged.

The second half of the proposal removes the inflation without giving up sequential reads. During each epoch we keep a tiny random-projection sketch of every block's mean gradient. Before the next epoch we order the blocks so that their sketched gradients cancel in running sum: a greedy sign-balancing step applied to blocks rather than examples. The I/O pattern is identical to existing block loaders, yet the epoch-level noise can fall below that of a random block order. In short, we want a theory that predicts when quasi-random loaders hurt from two measurable numbers, $b$ and $\rho$, and a near-free loader change that fixes the bad cases.

Core Claim

Write $g_i=\nabla f_i(x^*)$ for the gradient of example $i$ at the optimum. Shuffling analyses, including the "shuffling variance" of Random Reshuffling: Simple Analysis with Vast Improvements, bound the error of an epoch by prefix sums of these gradients along the permutation $\pi$:

$$ \Delta(\pi)=\max_{j\le n}\Big\|\sum_{t=1}^{j} g_{\pi(t)}\Big\|^2 . $$

That analysis is the source of random reshuffling's advantage over plain stochastic gradient descent, and of the gaps between permutation schemes. How Good is SGD with Random Shuffling? separates reshuffling every epoch, $\Omega(1/(nk)^2+1/(nk^3))$, from shuffling once, $\Omega(1/(nk^2))$, and from a fixed order, $\Omega(1/k^2)$.

Consider a loader that draws whole blocks of size $b$ in random order and shuffles inside a buffer holding several blocks. At every buffer boundary, its prefix sum equals a sum of whole-block gradient totals. Shuffling inside the buffer cannot change that sum. Treating block totals as the units of a random reshuffle over $m=n/b$ blocks gives

$$ \mathbb{E}\,\Delta_{\text{block}} \approx \big(1+(b-1)\rho\big)\,\mathbb{E}\,\Delta_{\text{RR}} , $$

where $\rho$ is the intraclass correlation of the $g_i$ within blocks. This form is the standard variance inflation for cluster sampling, which applies because the block totals are sampled without replacement exactly like single examples.

The claim yields three testable predictions. First, the inflation grows linearly in $b\rho$. Second, it does not shrink as the buffer grows. Third, a block order chosen so that the sketched block totals cancel brings $\Delta$ back to the reshuffling level or below, at zero extra I/O.

Relation to Prior Work

Three systems motivate this work by showing that block-structured access is necessary and empirically safe in the cases they tried. None of them analyzes the quantity that shuffling theory says matters.

scDataset samples random disk blocks and reshuffles a fetched buffer. It proves a "sandwich bound" on minibatch diversity when block size is at most half the fetch factor. Our claim concerns a different object. Minibatch diversity governs per-step noise, whereas epoch-level prefix sums govern the reshuffling gain. Our prediction that buffer size does not cure layout inflation is therefore not covered by, and could conflict with, their recommendation.

Brand / Redox redirects requests to whichever file in an already-loaded chunk is available. Its safety argument is that more than $10^{88}$ permutations remain reachable on ImageNet. A permutation count says nothing about $\Delta$: astronomically many permutations can all share large block-correlated prefix sums.

Mini-batch Gradient Descent with Buffer and Large Linear Classification When Data Cannot Fit in Memory make several passes over each loaded block. The first proves, for linear regression and PL losses, that such reuse biases the model toward the buffer. The second cycles blocks deterministically. Both concern reuse, which is orthogonal to our question, so we fix one pass per block per epoch.

Shuffling theory supplies the method. Beyond the two papers above, Understanding Gradient Bias in Random Reshuffling ties within-epoch cancellation to data structure. Tighter Lower Bounds for Shuffling SGD shows that well-chosen permutations can reach $\Omega(\kappa^3/(n^2K^2))$, matching gradient-balancing reordering (GraB). This is better than any random permutation, and it is our reason to expect that balancing helps.

What has not been done is to apply balancing at block granularity under a disk constraint, using stale, sketched block gradients. Sketch and Validate for Big Data Clustering supports the sketching choice: random projections can preserve the geometry needed while the full data stays on disk.

Research Program

The theory strand extends the shuffling-variance analysis of Random Reshuffling: Simple Analysis with Vast Improvements to a two-level permutation. The outer level is a block order, either random or balanced. The inner level is a within-buffer shuffle. The goal is a bound, for smooth strongly convex and PL objectives, in which the shuffling variance becomes the design-effect-weighted term.

For the balanced order, the analysis must handle two sources of error. One is staleness: sketches are computed at the previous epoch's iterates, which we bound by smoothness times the epoch's parameter drift. The other is the distortion introduced by projecting to $k$ dimensions. We will also check whether the general-convex last-iterate machinery of On the Last-Iterate Convergence of Shuffling Gradient Methods carries over, but we do not promise it.

The systems strand builds the block-balanced loader as a drop-in for scDataset-style block sampling. During epoch $e$, the loader accumulates for each block a $k$-dimensional projection (with $k\approx256$) of its mean gradient. For deep networks it uses per-example last-layer gradients, which are cheap to form from the output error and the penultimate features. Between epochs it runs greedy sign balancing over block sketches. A small random perturbation keeps the order from repeating across epochs. Memory cost is $m\times k$ floats, and reads stay block-sequential. A separate estimator measures $\rho$ from the same sketches, so a practitioner can check the design effect before choosing $b$.

Baselines

The naive reference point is sequential streaming of the native layout. It is the fastest possible reader and corresponds to a fixed-order pass. scDataset reports that it reaches "near-chance accuracy" on Tahoe-100M drug and mechanism-of-action classification. True per-example random sampling is the accuracy ceiling. We run it at its full I/O cost where feasible and by simulation in memory on the smaller linear datasets.

The strongest practical competitor is scDataset's block sampling with buffered fetching at its recommended setting, block size at most half the fetch factor. On Tahoe-100M it reports a "204x Speedup" over AnnLoader and "perfectly matched the predictive performance of true random sampling". We run it with the same block size, the same read throughput, the same model, and an equal hyperparameter-tuning budget for learning rate and schedule. Its large-buffer variant is the direct test of our second prediction.

On ImageNet, Redox-style chunk redirection is the comparison. Brand reports "up to a 4.57x speedup in end-to-end training time compared to PyTorch" at the "same Top-1 and Top-5 accuracy". We reimplement its redirection policy on our chunks rather than assume its numbers transfer.

Offline shuffle-once followed by random block order is the baseline most likely to tie us. Its wall clock includes the external shuffle.

Two ablations isolate the key ingredient. In the first, balancing runs on sketches randomly reassigned among blocks. This keeps the ordering machinery but removes the gradient information. In the second, balancing uses fresh rather than stale sketches, which quantifies staleness loss. Beating a baseline means a smaller suboptimality, or higher held-out accuracy at matched wall clock, in high-$\rho$ layouts. It also means no loss where $\rho\approx0$.

Why not just…?

Why not just enlarge the shuffle buffer? This is scDataset's lever, and it plainly improves minibatch diversity. Our analysis says the prefix sum at buffer boundaries is still a sum of whole-block totals, so the epoch-level inflation should not depend on buffer size. The convex experiments vary the fetch factor at fixed $b\rho$ to test this directly. If $\Delta$ and suboptimality fall with buffer size, our core claim is wrong and we will report that.

Why not just use smaller blocks? Smaller $b$ shrinks the design effect, but it moves reads back toward the random small-read regime. Brand documents that this regime underuses NVMe drives, and I/O exceeds 90% of epoch time for light models. We will trace the throughput–accuracy frontier over $b$. Balancing succeeds only if it reaches small-$b$ accuracy at large-$b$ throughput.

Why not just shuffle the data on disk once? This is the real threat. It drives $\rho$ to about zero, after which random block order behaves almost like reshuffling. The lower bounds of How Good is SGD with Random Shuffling? separate shuffle-once from reshuffling only by a factor that may be invisible in few-epoch deep training. Our counter-arguments are cost and lost locality. A terabyte external shuffle must be repeated when the dataset grows. Clustered layouts also compress better and serve other queries, a point that matters given the zlib-compressed blocks of Large Linear Classification When Data Cannot Fit in Memory. We will measure compressed size and preprocessing time for clustered versus shuffled layouts. If offline shuffling matches balanced ordering on total wall clock and storage, the contribution narrows to the diagnostic: the $\rho$ estimate tells practitioners whether the shuffle is worth paying for.

Proposed Experiments

The first experiment is a decisive convex test of the design effect. We train $\ell_2$-regularized logistic regression on real-sim, RCV1, epsilon and webspam. Webspam runs under a 1 GB memory cap as in Large Linear Classification When Data Cannot Fit in Memory, which reports only that standard LIBLINEAR "essentially stalled due to disk swapping"; no reported accuracy number was found on Lacuna for this setting. We control $\rho$ by writing the data in random, label-sorted and feature-clustered layouts. We compute $x^*$ to high precision and measure realized $\Delta$ under each loader across a grid of block and buffer sizes. Then we plot suboptimality against epochs at small constant step sizes, where the shuffling term dominates. The design effect must predict the measured inflation across layouts and must stay flat in buffer size. Otherwise the theory fails. No reported numerical result was found on Lacuna for shuffling methods on real-sim, w8a or RCV1.

The second experiment uses Tahoe-100M in its native plate-ordered layout. We compare all baselines on drug and mechanism-of-action accuracy, training-loss spikes, read throughput, and wall clock including preprocessing. We also report the estimated $\rho$ per layout, to test whether the regime where scDataset already matches random sampling is a low-$\rho$ regime.

The third experiment uses ImageNet-1k in class-sorted folder order with Redox-style chunks. It measures Top-1 accuracy at matched wall clock and checks whether balancing survives the per-step noise of deep training. The reference here is the 60-versus-110-hour BMGD result in Mini-batch Gradient Descent with Buffer, which we treat as a reuse-based comparison rather than a like-for-like one.

A negative deep-learning result, with the convex predictions confirmed, would still be informative. It would show that per-step noise, not epoch-level cancellation, limits out-of-core training at realistic step sizes. That would tell future loader design to optimize minibatch diversity and stop there.