Shuffling for the Sparse Kernel: Co-Selecting Minibatch Composition and Dataflow

When a model is trained on sparse data, such as bag-of-words documents or graph neighborhoods, the random order in which examples are visited decides two things at once. It decides how fast the optimizer converges. It also decides what sparse matrix the hardware actually multiplies at each step. Random reshuffling, the practice of visiting every example once per pass in a fresh random order, is what practitioners use and what theory rewards. The trouble is that it assembles each minibatch from unrelated examples. The rows of that minibatch then touch many scattered columns, and memory traffic goes up. Accelerators that can switch dataflow, meaning the loop order used to multiply sparse matrices (inner product, outer product, or row-wise), pick the best loop order for whatever matrix arrives. Nobody asks whether the sampler should shape what arrives.

This note proposes treating minibatch composition as a controllable knob. Each pass, examples are grouped into minibatches that mix a tunable number of locality clusters, and batches are visited in uniformly random order. With the clusters fixed, the procedure is exact random reshuffling over a random set of batches, so the standard guarantees carry over at the level of batches. Shaping the batches does have a price: it enlarges the gradient noise across batches that shuffling theory tracks, and it shrinks the memory traffic that dataflow selectors care about. A small controller picks the mixing level and the dataflow together, once per pass, to minimize predicted time to a target accuracy. Because the sampler builds the batches, their structural features can be predicted from cluster statistics before the batch exists. That removes the profiling cost that limits runtime selectors.

Core Claim

Consider training with minibatches on sparse inputs. Our claim is that an epoch sampler that is locality-aware but still fully randomized over batches, paired with dataflow selection conditioned on that sampler's mixing level, reaches a given loss faster in wall-clock time than two alternatives. The first is plain reshuffling combined with the best per-batch dataflow selector. The second is locality-preserving orderings that give up per-epoch randomness. The claim rests on a tradeoff that can be measured.

Take $L$-smooth, $\mu$-strongly convex losses with condition number $\kappa = L/\mu$, split into $m$ batches per pass. Random Reshuffling: Simple Analysis with Vast Improvements shows that reshuffling needs $O(\kappa + \sqrt{\kappa m}\,\sigma_*/(\mu\sqrt{\epsilon}))$ steps to reach accuracy $\epsilon$. In that bound, $\sigma_*$ is the spread of the component gradients at the optimum; here the components are batch gradients. Let $k$ be the number of clusters mixed into each batch, and let $c(k,d)$ be the cost per step under dataflow $d$. Predicted time to accuracy is then

$$ \mathcal{T}(k,d) \;\approx\; c(k,d)\left(\kappa + \frac{\sqrt{\kappa m}\,\sigma_*(k)}{\mu\sqrt{\epsilon}}\right), $$

where $\sigma_*(k)$ is the batch-gradient spread at mixing level $k$. It is largest for $k=1$, where each batch comes from a single cluster, and approaches the spread of fully random batches as $k$ grows. The cost $c(k,d)$ tends to fall as $k$ shrinks, because fewer distinct weight or feature blocks are touched.

The proposal is worth doing if three things hold. First, $\mathcal{T}$ has an interior minimum well below its value at large $k$. Second, the minimizing dataflow $d$ changes with $k$. Third, both $\sigma_*(k)$ and $c(k,d)$ can be estimated cheaply enough to steer the choice online.

Relation to Prior Work

Three kinds of prior work motivate the proposal. Dataflow selectors establish that the best loop order depends on matrix structure. Misam trains a small decision tree on features such as blocks_accessed, a count of memory blocks a multiply touches, which it identifies as the dominant feature. It routes sparse-sparse products to inner-product, outer-product, or row-wise engines. Flexagon builds hardware that switches among the three dataflows, with the choice made offline per layer. Both treat matrices as given. We instead make the input matrices a product of the sampler and condition the selector on the sampler's parameter.

Optimizing Sparse Matrix Multiplications for Graph Neural Networks shows that matrix density drifts over training epochs and switches storage formats with a runtime classifier. It never examines how examples are ordered or batched. For graph workloads we adopt its format space (CSR, COO, BSR) as the GPU counterpart of the accelerator dataflow space.

The shuffling literature supplies the guarantees we reuse, and it also constrains the design. A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond measures how far each pass's partial gradient sums stray from the full gradient, a quantity it calls order error. It shows that dependent orderings such as gradient balancing, which pair examples with opposing gradients, can shrink this error. It ignores where those examples live in memory. We use order error as a diagnostic, and we treat gradient balancing as a competitor whose memory cost we will measure.

The benefits of full data shuffle, now with optimal I/O cost is the closest systems work. It achieves reshuffling with input/output cost linear in the number of blocks read, using two rounds of in-memory shuffling and matrix transposition. It proves that pairwise independence, a much weaker condition than a fully uniform permutation, keeps the accelerated rate for strongly convex losses. That work solves the cost of reading data in shuffled order. It deliberately produces batches whose content is as random as a full shuffle, which is the worst case for the sparse compute kernel. Our proposal targets the cost of computing on the batch rather than the cost of fetching it, so the two could be combined.

How Good is SGD with Random Shuffling? and Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization act as constraints. They warn that deterministic or once-only orderings can inherit adversarial structure or persistent variance. This is why we keep a fresh random batch order and a fresh random batch assembly every pass, rather than freezing a locality-friendly order.

Research Program

The sampler first partitions examples, once and offline, into $C$ clusters by feature support. For sparse linear models we group documents that share vocabulary columns, using a cheap bucketing on the column indices each document touches. For graphs we group nodes by neighborhood overlap. Each pass, every cluster is independently shuffled and split into shards. Each batch is then filled by drawing shards from $k$ randomly chosen clusters. Finally the batches are visited in uniformly random order. With the clusters fixed, this is exact batch-level reshuffling over a random partition. The strongly convex analysis of Mishchenko et al. applies directly with batch-level $\sigma_*(k)$, and the $k=1$ and $k=C$ endpoints recover cluster-pure and fully random batching.

The controller runs once per pass. It estimates $\sigma_*(k)$ for a few candidate values of $k$ by evaluating batch-gradient spread at the current iterate on a subsample. It predicts $c(k,d)$ from cluster-level statistics: expected union of column blocks, row-length variance, and density. These are exactly the Misam feature inputs, but here they are computed analytically from the mixing rule rather than profiled per batch. The controller then chooses the $(k,d)$ pair that minimizes $\mathcal{T}$.

We will analyze two things. The first is how much $\sigma_*(k)$ exceeds its fully random value, as a function of cluster heterogeneity. The second is whether a per-pass choice of $k$ preserves the rate when $k$ changes between passes. We expect a bound in terms of the maximum $\sigma_*(k)$ used during training, which follows from applying the per-pass contraction argument pass by pass.

For compute, we use two back ends. One is a cycle-level model of the three dataflows following Flexagon's organization. The other is real GPU kernels choosing among CSR, COO, and BSR, as in Qiu et al.

Baselines

The naive reference is plain per-pass random reshuffling with one fixed dataflow, or on GPU the default CSR format. It is run for the same number of passes with a step size tuned on the same grid as all other methods. This anchors every speedup.

The strongest existing competitor is random reshuffling followed by a per-batch dataflow selector in the style of Misam, which measures each batch's features and routes it to the best engine. On static SuiteSparse matrices, Misam reports 94% selection accuracy and average speedups of 2.7× over inner product, 2.1× over outer product, and 2.64× over row-wise. Those numbers come from static matrices, not training; no reported result found on Lacuna for per-batch selection inside a training loop. We give this baseline an oracle variant that always picks the fastest dataflow per batch at zero profiling cost. We then count a win only if our method beats the oracle in time to accuracy, not merely the realistic selector.

On GPU graph workloads, the matching competitor is the format selector of Qiu et al. It reports 89.1% prediction accuracy, 89% of oracle performance, and a 1.17× average speedup over PyTorch. We re-run it on our batches with its 19-feature classifier retrained on our data.

The I/O-optimal shuffle of Afshani et al. is included to show that fixing input/output does not fix compute. It is run on identical data layouts.

The ablations isolate the two ingredients. Mixing-level tuning with a fixed dataflow measures how much comes from shaping batches alone. Joint selection with measured features instead of predicted ones measures how much the prediction shortcut saves. A cluster-pure $k=1$ sampler with random batch order measures the variance penalty in isolation. All methods share data, hardware or simulator configuration, step-size grid, and total wall-clock or cycle budget.

Why not just…?

Why not just shuffle once after sorting data for locality? A fixed locality-friendly order gives the best memory behavior. However, Safran and Shamir, and Liu and Zhou, show that frozen orderings can keep adversarial or persistent-variance structure. A sorted order is the extreme case of such structure. We include shuffle-once on a clustered layout as a baseline. If it matches our method in time to accuracy on the real-sim, w8a, and RCV1 datasets, the per-pass randomization is unnecessary and we will say so.

Why not just use block-level shuffling, which keeps contiguous chunks together and shuffles among them? This is the real threat, since it is our sampler with ad hoc clusters and no controller. Afshani et al. report that the block-buffer method CorgiPile leaves millions of adjacent pairs clustered, compared with 79,598 for two-round IO Shuffle against 79,600 for an ideal Fisher–Yates shuffle. That suggests uncontrolled block shuffling sits at an unknown point on the variance axis. We run block shuffling at several block sizes as a sweep. If some block size matches our controller everywhere, the contribution reduces to the analysis of $\sigma_*(k)$ plus dataflow conditioning, and the ablation will show whether conditioning adds anything.

Why not just keep random reshuffling and let a good dataflow selector absorb the irregularity? Selectors choose the best loop order for a fully random batch but cannot reduce its blocks_accessed, which Misam identifies as the dominant cost driver. The oracle-selector baseline tests this directly. If the oracle on random batches matches our method, shaping batches buys nothing.

Why not just sample with replacement and prefetch? It forfeits the faster rate of shuffling established by Ahn et al. and Rajput et al., and it produces batches that are just as random. We include it only as a reference curve.

Proposed Experiments

The primary testbed is ℓ2-regularized logistic regression on real-sim, w8a, and RCV1, the strongly convex setting used by Mishchenko et al., where the theory is tight. The metric is wall-clock time, or simulated cycles, to reach relative suboptimality $10^{-4}$, alongside blocks_accessed per pass, measured $\sigma_*(k)$, and order error following Li et al.

The secondary testbed is graph neural network node classification on Cora, CoraFull, and PubmedFull with minibatched neighborhood aggregation. Its metric is time to a fixed validation accuracy. This setting is non-convex, where no guarantee is claimed, so it tests whether the tradeoff survives outside the theory. We also include gradient balancing from Li et al. with its memory traffic counted, to measure whether its lower order error survives the scattered accesses it causes.

The decisive checks are three.

The first check sweeps $k$ from 1 to $C$ and plots measured $\mathcal{T}$. If time to accuracy is monotone in $k$ with its minimum at full mixing, the idea fails.

The second check asks whether the oracle-best dataflow changes across $k$ on at least some datasets. If it never does, joint selection collapses to choosing $k$ alone, and we will report the simpler method.

The third check asks whether the controller's predicted $\mathcal{T}$ ranks $(k,d)$ pairs in the same order as measurement, with rank correlation reported. It also asks whether the predicted-feature selector costs less than the few-percent overhead Qiu et al. report while matching the measured-feature selector's choices.