Placing Gradient-Coding Redundancy Where Stragglers Are Predicted

In synchronous distributed training, every worker computes a gradient on its share of the data, and the step cannot finish until the slowest worker, the "straggler", reports. Gradient coding (giving each worker extra, overlapping data so the full gradient can be rebuilt from any $n-s$ of $n$ workers) removes that wait. The cost is that every worker must do roughly $s+1$ times the work, every round, even though in real clouds most workers are fast most of the time. Recent hybrid schemes cut this waste. They send most work as plain, uncoded tasks and code only a small remainder, and they exploit the fact that stragglers come in bursts over time. Those schemes, however, need the master to be allowed to finish a job several rounds late. That only works when rounds are independent, for example when several separate models are trained at once. Ordinary single-model SGD has no such slack, because step $t+1$ needs the update from step $t$.

We propose to use the burstiness in a different way: to predict rather than to postpone. At each step, a lightweight forecaster estimates from recent completion times which workers are likely to be slow next. Data owned by likely-fast workers is assigned uncoded. A small binary repetition code, which decodes by plain summation and so has no floating-point conditioning problem, covers only the workers the forecaster flags plus a bounded margin for surprises. The claim is that this recovers most of the load savings of delayed hybrid coding at zero delay. The work is also designed to close an empirical gap in this literature. It uses a trace-replay harness built from real cloud straggler measurements, so that every competing scheme faces the identical sequence of slowdowns.

Core Claim

For single-model synchronous SGD on clusters whose stragglers persist across consecutive steps, forecast-placed hybrid coding should do two things. First, it should reach the same time-to-accuracy as standard gradient coding at a small fraction of its per-worker compute load. Second, it should beat both uncoded training and forecast-driven load rebalancing without coding. Whether it wins should be governed by one measurable quantity: how predictable each worker's next-step slowness is from its recent history. If real traces show weak persistence, the method should reduce to ordinary gradient coding. We treat that outcome as a legitimate negative result, not something to argue around.

Relation to Prior Work

Two papers motivate the approach by showing that mixing uncoded and coded tasks pays off under bursty stragglers. Coded Sequential Matrix Multiplication For Straggler Mitigation interleaves uncoded mini-tasks with polynomial-coded tasks across a stream of jobs. It reports a 41% cut in average processing time over polynomial codes under Fritchman bursty stragglers, but only on 4 workers and with a delay parameter $T>0$. Sequential Gradient Coding For Straggler Mitigation multiplexes uncoded re-attempts with coded tasks across rounds (M-SGC) on 256 AWS Lambda workers. It explicitly notes that the scheme collapses to standard gradient coding when $T=0$. Both schemes absorb burstiness by waiting. We keep their uncoded/coded split but absorb burstiness by forecasting, which is the only option when steps are sequentially dependent.

Other papers supply the coding machinery or constrain its design. Gradient Coding provides the base construction and the $(s+1)$-fold load we aim to avoid. Generalized Fractional Repetition Codes for Binary Coded Computations gives binary repetition codes that work for any $n$ and $s$, which we need because the size of the flagged group changes every step. That paper has no experiments, so ours would be its first deployment. Two papers argue against real-valued polynomial decoding for a code whose group size changes dynamically. Communication-Computation Efficient Gradient Coding reports numerical instability beyond $n=20$. Numerically stable coded matrix computations via circulant and rotation matrix embeddings bounds the conditioning problem but still has a condition number that grows with $s$.

Leveraging partial stragglers within gradient coding salvages partial work through an interactive least-squares protocol and reports roughly $2\times$ speedup over gradient coding, but only in simulation. We include it as a competitor in our harness rather than as a component. Its extra broadcast round is exactly the kind of cost that only a physical measurement reveals.

Research Program

The system has three parts. The first is the forecaster. For each worker $i$ it estimates $p_i(t)$, the probability that the worker's step-$t$ finishing time exceeds a threshold. We start with the simplest defensible model, a per-worker two-state Markov chain fit online (the discrete analogue of the Fritchman model used in the sequential-coding paper). We add a shared cluster-level burst term only if traces show correlated slowdowns across workers.

The second part is the assignment. Workers with $p_i$ below a cutoff each receive one chunk, uncoded. The flagged workers, plus $m$ margin workers drawn from the fast set, form a group that holds the flagged workers' chunks under a fractional repetition code. The group tolerates $\hat s + \delta$ stragglers, where $\hat s=\sum_{\text{flagged}} p_i$ is the expected number of slow workers in the group and $\delta$ is a safety margin. The average per-worker load is then roughly $1 + (\hat s+\delta)\,g/n$, where $g$ is the group size, instead of gradient coding's $s+1$.

The third part is the decode policy. Group results are summed. If an unflagged uncoded worker straggles unexpectedly, the master either waits (the exact mode) or drops that chunk after a timeout (the bounded-approximate mode). Every run logs the fraction of steps that used an exact gradient.

Reassigning data each step costs data movement. To avoid it, we pre-place each chunk on a small fixed set of candidate workers and let the forecaster choose among these placements only. This constraint is itself something we will study.

The empirical contribution is the harness. We will record per-worker, per-step completion times on AWS Lambda (matching the 256-worker setup of the M-SGC paper) and on a multi-GPU EC2 cluster. We then replay the identical traces under every scheme, and also run the schemes live, so that simulation-to-deployment gaps are measured rather than assumed.

Baselines

The naive reference is uncoded synchronous SGD that waits for all workers. The complementary naive reference drops every straggler each step, using a timeout set on held-out traces. Both run on identical traces with identical hyperparameters. Beating them means lower time-to-target-accuracy.

The strongest exact competitor is standard gradient coding from Gradient Coding. We implement it with a fractional repetition code at the $s$ that minimizes mean step time on held-out traces, so that it gets the same tuning budget as our cutoff and margin. The reference points in the file are the following. Gradient coding reports needing 10% replication to handle 20% slowdowns. Communication-Computation Efficient Gradient Coding reports a 32% running-time cut versus uncoded training on Amazon Employee Access with 10 to 20 EC2 workers.

The strongest hybrid method is M-SGC, which reports being 11.6% faster than gradient coding and 21.5% faster than uncoded training on four concurrent ResNet-18 models on CIFAR-100, with per-worker load 0.008 versus 0.062 for gradient coding. That result relies on $T>0$ and several models. For single-model, $T=0$ training we found no reported result on Lacuna for any hybrid coded-uncoded scheme. We therefore run M-SGC in two settings: forced to $T=0$ on single-model training, and in its native multi-model setting as an upper reference. Beating gradient coding means matching its time-to-accuracy at at most half its per-worker load, or improving time-to-accuracy at equal load.

The partial-straggler least-squares protocol is run live with its broadcast round included. We also include an asynchronous baseline from the Pseudo-Asynchronous-LocalSGD implementation, tuned with the same budget.

The key ablation replaces the coded group with forecast-driven rebalancing. In this variant, flagged workers' chunks are simply handed, uncoded, to predicted-fast workers. This isolates what the code contributes beyond the forecast. A second ablation replaces the forecaster with a random choice of the same group size, which isolates what the forecast contributes.

Why not just…?

Why not just rebalance load away from predicted stragglers, with no coding at all? This is the most serious threat. If the forecaster were perfect, rebalancing would be optimal and coding would add nothing. The code exists to cover the forecaster's misses, the stragglers it failed to flag. The rebalancing ablation settles the question. We will plot the gap between the two methods against measured forecast precision and recall on the traces. If rebalancing matches our method at the precision real clouds actually show, we will report that forecast-driven rebalancing is the right answer and that coding is unnecessary for single-model SGD.

Why not just drop stragglers each step? On dense image data, dropped gradients may barely hurt convergence, so this baseline could win on CIFAR-100, and we will report it if so. Gradient Coding shows that dropping loses rare features on the Amazon Employee Access data and degrades AUC. For that reason we include that dataset specifically, and we compare methods on time-to-target-accuracy rather than on step time.

Why not just use asynchronous or local SGD? These methods remove the barrier entirely, but at the price of stale or divergent updates. We tune the Local SGD baseline with an equal budget and compare end-to-end wall-clock time to accuracy. No number from the file speaks to this comparison, so the experiment decides it.

Why not just use backup tasks? Speeding Up Distributed Machine Learning Using Codes reports that coded matrix multiplication cut average runtime by 40% and 95th-percentile latency by 60% relative to replication. We therefore expect backup tasks to lose, but we still run them on the same traces so the comparison is on shared ground.

Proposed Experiments

The first check comes before any training and decides whether the idea is viable. From the Lambda and EC2 traces, we measure each worker's step-to-step slowdown persistence and the forecaster's precision and recall. If $p_i(t)$ is barely better than the base rate, we stop and report that single-step forecasting cannot replace delay. As a negative control, i.i.d. shifted-exponential synthetic traces should show no advantage over gradient coding. An advantage there would signal a bug or an unfair comparison.

Training runs use three workloads: single-model ResNet-18 on CIFAR-100, a CNN on MNIST, and logistic regression on Amazon Employee Access. Each runs at 16, 64 and 256 workers, both replayed and live. We report mean and 95th-percentile step time, time-to-target-accuracy, average per-worker compute load, master decode and scheduling time (as a fraction of the step, comparable to the 2–9% master overhead reported by CoCoI), data-movement volume from reassignment, and the fraction of steps with an exact gradient.

The method succeeds if, on real traces at 256 workers, it matches gradient coding's time-to-accuracy at at most half the load, beats rebalancing-only whenever forecast recall is below one, and keeps master overhead under 10% of step time. Releasing the traces and the replay harness lets later schemes, including the rotation-embedding and binary codes that have so far been evaluated only on synthetic matrices or by proof, be tested against the same real slowdowns.