Delta-Compressed Step-Parallel Training

Gradient descent is a chain: each update needs the parameters produced by the one before it. Step-parallel optimizers break the chain by guessing a whole window of future parameter vectors at once, computing the gradients at all of them on separate GPUs, and refining the guesses until they stop changing. When they settle, the result matches ordinary sequential training. PASO: Step Parallel Stochastic Optimization does this and reports "up to 21×" fewer sequential steps. Its wall-clock speedup on GPT-2 and Llama-3.2-1B is only "4.5×", and the authors attribute the gap to communication. The reason is structural. Every refinement pass ships a full gradient for every position in the window, so step parallelism multiplies the gradient traffic that already dominates distributed training.

This note proposes a fix that uses the structure of the refinement process. Between two refinement passes, the parameter guess at each window position moves only slightly. The gradient computed there therefore changes only slightly too, and the change shrinks as the passes converge. Workers should send that sweep-to-sweep gradient change, not the gradient. The precision of each message should follow how far the solver is from converging: very coarse bits early, finer bits near the end, with leftover error carried forward and flushed before a step is accepted. Errors made in early passes are overwritten by later passes, which is not true of compression in ordinary data-parallel training. Step-parallel solvers should therefore tolerate much more aggressive compression than standard training, while still matching the serial trajectory to within a stated tolerance.

Core Claim

Write the window's fixed-point update as $w_j^{(k+1)} = w_0 - \eta \sum_{i<j} g_i(w_i^{(k)})$. Here $w_j^{(k)}$ is the guess for the parameters after step $j$ at refinement pass $k$, $g_i$ is the minibatch gradient for step $i$ (PASO fixes the minibatch per step index, so it is deterministic), and $\eta$ is the learning rate. Each worker sends a compressed version of $\Delta_i^{(k)} = g_i(w_i^{(k)}) - g_i(w_i^{(k-1)})$. If the gradient is $L$-smooth, $\|\Delta_i^{(k)}\| \le L\,\|w_i^{(k)} - w_i^{(k-1)}\|$, so the messages shrink at the same rate the solver converges. We choose the quantization level per pass so that the compression error $e_i^{(k)}$ satisfies

$$\|e_i^{(k)}\| \le \rho \, \|w_i^{(k)} - w_i^{(k-1)}\|,$$

where $\rho$ is a fixed fraction below one. The design rests on a standard result for inexact fixed-point iteration: if the contraction is perturbed by errors that decay geometrically, it still converges to the same fixed point. The claim to test is that this residual-tied schedule, combined with error feedback that is flushed before acceptance, has three properties. It keeps the number of passes close to PASO's. It cuts the bytes per accepted step well below even uncompressed data-parallel training. It turns most of PASO's 21× step reduction into wall-clock speedup on bandwidth-limited clusters.

Research Program

The proposal takes two existing techniques, delta encoding of successive states and error feedback, and moves them into a new place: the inner loop of a step-parallel solver. Delta encoding comes from the sequential data-parallel line. SDP4Bit (Hao Feng et al.) quantizes successive weight differences to 4 bits. Error feedback comes from DeMo: Decoupled Momentum Optimization, which subtracts uncommunicated residue from the momentum it keeps locally and reports an "85x" transfer reduction. Both methods compress across training steps, where an error is permanent unless later steps compensate for it. In our setting the errors are temporary, because the solver revisits the same steps.

The constraints come from three directions. Layer-Parallel Training for Transformers shows that inexact parallel-in-time solvers introduce gradient bias that hurts convergence near minima, and it needs adaptive tolerances to recover. That is a warning that fixed lossy compression could break equivalence with serial training, and it is why our precision tracks the residual. Saurabh Agarwal et al. show that compression kernels compete with the backward pass for GPU compute. We therefore restrict ourselves to cheap elementwise quantization with per-chunk scales and measure the kernel time explicitly. BitDP: Ultra-low-bit Communication for Data Parallelism in LLM Training notes that low-bit formats lose the hardware-optimized all-reduce and must fall back to all-gather. In step-parallel training this cost largely disappears. The update needs a prefix sum over window positions, which is naturally an all-gather of per-position deltas followed by a local scan, so the low-bit messages fit the communication pattern the algorithm already requires.

We will build three components. The first is a decentralized NCCL implementation of PASO's sliding window, with the prefix sum done as a collective; this replaces PASO's CPU-mediated master. The second is the residual-tied quantizer with per-position error-feedback buffers. The third is an acceptance rule. A window position is committed only once its accumulated buffer has been sent at full precision and the fixed-point residual falls below PASO's tolerance. On the analysis side, we will derive the pass count under the bound above as a function of $\rho$, and measure empirically how the observed delta norms compare to the parameter movement across passes.

Baselines

The naive reference point is standard synchronous data parallelism with AdamW on the same GPUs, the same per-step minibatch sequence, and the same bandwidth. It defines the target validation loss and serves as the serial trajectory that equivalence is measured against.

The strongest existing method for cutting sequential steps is PASO itself. It reports a "4.5× speedup" in wall-clock time and "up to 21×" fewer gradient-descent steps on WikiText-2 with GPT-2 (124M) and Llama-3.2-1B (PASO). No reported WikiText-2 perplexity for PASO was found on Lacuna, so we will rerun it to obtain one. We will run two versions. The first is PASO's released algorithm. The second, more important, is our own uncompressed NCCL reimplementation, which isolates how much of the gap is plain engineering. Both get the same window sizes, tolerance search, and GPU-hour budget as our method. Beating PASO means reaching the data-parallel target loss sooner in wall-clock time than the uncompressed NCCL version at matched bandwidth, without raising the final validation loss beyond the noise across seeds.

The strongest communication-reduction baselines are BitDP and DeMo, applied to ordinary sequential data parallelism. BitDP reports a "5.15x speedup" over FP32 on InfiniBand and "7.47x" on 1/10GbE for GPT-13B, and GPT-350M perplexity of "22.74 vs. 22.17" at 2 bits. Those numbers come from a different scale, so we rerun both methods at our model sizes. Beating them means a faster time to target loss. This comparison matters because compression alone cannot reduce the number of sequential steps.

The key ablation is a fixed-precision variant. It quantizes PASO's gradient deltas at a constant 1 or 2 bits with ordinary error feedback but no residual-tied schedule and no flush before acceptance. A second ablation sends compressed full gradients rather than deltas. These two isolate whether the gain comes from compressing differences between passes and from tying precision to convergence.

Why not just…?

Why not just reimplement PASO with fast collectives? This is the most serious threat. If the 4.5× versus 21× gap is mostly caused by PASO's CPU-mediated master, an uncompressed NCCL version may close it on InfiniBand. We treat this as an experiment to run, not an argument to make. We will profile communication as a share of window time for uncompressed NCCL PASO at InfiniBand-class bandwidth and at emulated 10GbE. If the share is small at high bandwidth, we will say so and narrow the claim to bandwidth-limited and cross-node settings. Those settings are where Hanzhen Zhao et al. report communication taking up to 92% of time. Even in the best case, step parallelism sends gradients for every window position on every pass, so its traffic exceeds data parallelism by roughly the window size times the pass count. That multiplication is what the proposal targets.

Why not just compress standard data-parallel gradients with BitDP or DeMo? These methods reduce the time per step, but the number of sequential steps stays the same. Compression also carries the compute-contention cost described by Agarwal et al.. Our comparison runs both at the same bandwidth. If compressed data parallelism matches our time to target loss, then step parallelism is not worth its extra compute, and that would be a useful negative result.

Why not just use DiLoCo-style infrequent synchronization? Scaling Laws for DiLoCo cuts bandwidth by "10x to 100x" with $H=30$ local steps. However, it changes the optimization trajectory and still runs each replica's steps in sequence. Our method keeps equivalence to serial training and shortens the sequential chain, so the two methods address different bottlenecks. Running delta-compressed step parallelism inside DiLoCo replicas is a natural follow-up, but we do not attempt it here because replica drift (Louis Fournier et al.) would confound the measurements.

Proposed Experiments

The main setting reproduces PASO's: GPT-2 124M and Llama-3.2-1B on WikiText-2. A second setting uses a 300M OLMo-style model on Dolma v1.5, matching DeMo, so bytes per step can be compared against DeMo's reported "7.5 MB vs. 637 MB per step". Each method runs at InfiniBand-class bandwidth and at emulated 10GbE and 1GbE, the regimes in which BitDP reported its speedups. The metrics are wall-clock time to the data-parallel target validation loss, bytes communicated per accepted step, passes per window, compression kernel time as a share of compute, and distance between the accepted parameters and the serial trajectory at matched steps.

Three checks decide the outcome. First, the residual-tied method should keep passes per window within a small margin of uncompressed PASO, while the fixed 1-bit ablation should either inflate the pass count or drift from the serial trajectory. If fixed precision performs just as well, the central claim fails and the contribution reduces to engineering. Second, measured delta norms should shrink across passes as fast as parameter movement does; if they do not, the compressibility premise is wrong. Third, at 10GbE the method should beat both uncompressed NCCL PASO and BitDP-style compressed data parallelism in time to target loss. At InfiniBand we will report honestly whether any advantage remains.