Gradient Compression and Quantised Collectives

Lin and colleagues measured how much of the gradient traffic in distributed SGD actually matters and found that 99.9% of the exchange is redundant. Transmitting only the largest-magnitude coordinates, with momentum correction, local gradient clipping, momentum factor masking and warm-up to preserve accuracy, achieved compression ratios of 270x to 600x: ResNet-50's gradient fell from 97 MB to 0.35 MB, and DeepSpeech's from 488 MB to 0.74 MB (Lin et al., ICLR 2018, arXiv:1712.01887).

Numbers like that suggest gradient compression should be universal. It is not, and the reason is a structural property of the collective rather than a defect of the compressors.

Why sparsification fights the all-reduce

Ring all-reduce is efficient because it is decomposable: the reduce-scatter and all-gather phases each move a fixed slice per step, and the sum of two dense vectors is a dense vector of the same shape.

Top-\(k\) sparsification breaks this. Worker A's top-\(k\) coordinates and worker B's are different sets, so their sum has up to \(2k\) non-zeros, and after \(M\) workers the union can approach \(Mk\). The compressed representation is not closed under addition, so a sparsified exchange degenerates into an all-gather of index-value pairs, whose cost grows linearly with worker count. Compression that looks like 500x on paper delivers far less at 256 workers.

The methods that survived at scale are the ones whose compressed form is linear, so that compressed vectors can be summed directly.

Low-rank. PowerSGD approximates the gradient matrix by a rank-\(r\) factorisation computed with a single power-iteration step. Rank-\(r\) factors add, so the exchange remains a genuine all-reduce over small dense matrices. It was the only method in its evaluation to deliver consistent wall-clock speedups against SGD with an optimised communication backend (Vogels et al., NeurIPS 2019, arXiv:1905.13727).

Quantisation. QSGD quantises each coordinate stochastically to a small number of levels, preserving unbiasedness and therefore convergence guarantees, and reported training ResNet-152 on ImageNet 1.8x faster to full accuracy on 16 GPUs (Alistarh et al., 2016, arXiv:1610.02132). Because the quantisation is unbiased, the average of quantised gradients is still an unbiased estimate of the average gradient.

One bit. signSGD transmits only the sign of each coordinate and aggregates by majority vote, giving 1-bit communication in both directions with a convergence rate matching SGD under conditions determined by the relative \(\ell_1/\ell_2\) geometry of gradients, noise and curvature (Bernstein et al., 2018, arXiv:1802.04434). The sign operator is biased, which is why the theory needs those conditions and why error feedback is required in practice.

Error feedback is the component that makes it work

Every biased compressor needs the same correction. Keep a local residual buffer \(e_m\); compress \(g_m + e_m\) rather than \(g_m\); set \(e_m\) to whatever the compressor discarded. The dropped signal is not lost, only delayed, so a coordinate that is individually small accumulates until it is large enough to be transmitted.

Without error feedback, aggressive compression converges to a different, worse solution rather than converging more slowly. This is the single most common reason a compression scheme that looks fine on a small benchmark fails on a real training run.

When it breaks

Compression competes with overlap, and overlap usually wins. A well-implemented training loop already overlaps gradient all-reduce with the backward pass, so much of the communication is hidden behind computation that has to happen anyway. Compressing a collective that was already free adds encode and decode cost to the critical path for no gain. Gradient compression pays off when bandwidth is genuinely scarce, which in practice means inter-datacentre links, federated settings, or clusters without a high-speed fabric.

The compression is per-tensor, and small tensors dominate the launch cost. Bucketing many small tensors into one buffer is what makes all-reduce efficient; per-tensor compression fragments the buckets and can raise total time even when it lowers total bytes.

Interaction with mixed precision is subtle. Gradients are already bf16 or fp8 in a modern run, so the headroom compression schemes assumed in the fp32 era is partly spent. Compressing an fp8 gradient is a different problem from compressing an fp32 one, and results from the earlier literature do not transfer unexamined.

The infrequent-synchronisation alternative is often stronger. Communicating a compressed gradient every step and communicating a full parameter delta every 500 steps both reduce bytes, and the second changes the fabric requirement by a larger factor without touching the gradient at all. See low-communication distributed training; in the low-bandwidth regime the two are usually combined, with quantisation applied to the outer-loop exchange.