Ring All-Reduce and the Cost of Averaging Gradients Across Devices

In data-parallel training each device computes the gradient for its own slice of the batch, and before the optimiser runs, the gradients must be averaged across all devices so that every replica applies the same update. The operation is an all-reduce: every participant ends with the same reduced result. Its naive implementation sends all gradients to one device, which then sends the average back, and that costs twice the gradient size through a single link that becomes the bottleneck.

The ring algorithm replaces that star pattern with a circulation in which every link carries the same traffic, and the traffic per device is independent of the number of devices. The independence is the important property: adding devices does not add communication per device, so the ratio of communication to computation stays fixed as the cluster grows.

The reduce-scatter plus all-gather decomposition

An all-reduce over $P$ devices can be decomposed into two collectives. Reduce-scatter takes a buffer of $S$ bytes split into $P$ chunks and leaves each device holding the fully reduced version of one chunk, of size $S/P$. All-gather then takes those $P$ chunks and distributes the complete buffer to every device.

Each of the two phases moves $S \cdot (P-1)/P$ bytes into and out of each device, so the total traffic per device is $2S(P-1)/P$, which approaches $2S$ as $P$ grows. The ring is the algorithm that achieves this bound.

How the ring steps work

Arrange the devices in a logical circle. Each device has a buffer divided into $P$ chunks, one per device index. In step $k$ of the reduce-scatter phase, device $i$ sends chunk $(i - k) \bmod P$ to device $i+1$ and receives chunk $(i - k - 1) \bmod P$ from device $i-1$, adding the received values into its local copy. After $P-1$ steps, device $i$ holds the complete sum of chunk $i$ across all devices.

In step $k$ of the all-gather phase, device $i$ sends chunk $(i - k + 1) \bmod P$ to its successor and receives chunk $(i - k) \bmod P$ from its predecessor, overwriting rather than accumulating. After another $P-1$ steps every device holds every reduced chunk.

The chunk that a device owns is never the one it starts with in the second phase, which is why the phase boundary requires the accumulated chunk to be in the right position. Implementations usually express this as a rotation of the buffer indices rather than a physical move.

def ring_allreduce(chunks, rank, send, recv):
    """chunks: list of P tensors holding this rank's partial sums. send/recv
    must be non-blocking: a blocking ring send deadlocks, since every rank
    posts a send to its successor before posting the matching receive."""
    p = len(chunks)
    for k in range(p - 1):                       # reduce-scatter
        send_idx = (rank - k) % p
        recv_idx = (rank - k - 1) % p
        send(chunks[send_idx], (rank + 1) % p)
        chunks[recv_idx] += recv((rank - 1) % p)
    for k in range(p - 1):                       # all-gather
        send_idx = (rank - k + 1) % p
        recv_idx = (rank - k) % p
        send(chunks[send_idx], (rank + 1) % p)
        chunks[recv_idx] = recv((rank - 1) % p)
    return chunks

Each step moves $S/P$ bytes, and there are $2(P-1)$ steps, so the per-device traffic is $2S(P-1)/P$ as claimed. The number of steps grows with $P$, but the size of each step shrinks proportionally, so the bandwidth term stays flat. What does grow is the number of latency-bearing operations: $2(P-1)$ messages per device per all-reduce, each with a fixed startup cost that does not shrink with the payload.

The latency term and why it dominates at scale

A collective’s time is modelled as $\alpha + \beta m$ for a message of $m$ bytes, where $\alpha$ is latency per step and $\beta$ is the inverse bandwidth. For the ring, total time is approximately

$$T = 2(P-1)\alpha + \frac{2S(P-1)}{P}\beta$$

At small $P$ the second term dominates, because the gradient is large and each message is a substantial transfer. At large $P$ the first term grows linearly while the second saturates at $2S\beta$. For gradients of hundreds of megabytes over an interconnect with microsecond-scale latency, the crossover arrives when $P$ reaches the tens: past that point, adding devices costs more in message count than it saves in per-device bandwidth.

The latency term is also why small all-reduces are inefficient. A 1 MB gradient on 64 devices is 126 messages of 16 KB each, and each message’s fixed cost is comparable to the transfer time. The hardware’s per-message cost is on the order of a microsecond, so 126 messages per all-reduce, performed once per step, is a visible fraction of a step that should take tens of milliseconds.

Bucketing as a latency remedy

The standard fix is to reduce the number of messages by combining gradients. Instead of one all-reduce per parameter tensor, group tensors into buckets of a target size and issue one collective per bucket. With buckets of 25 MB, a 1 GB gradient becomes 40 collectives instead of the hundreds a per-tensor scheme would produce.

Bucket size is a trade against overlap. A bucket cannot start until every tensor in it has its gradient computed, so a large bucket delays the start of communication for its early members. The scheduling that matters is the ordering of backward: gradients become available in reverse layer order, so buckets formed from adjacent layers fill in a predictable sequence. Starting the all-reduce for a bucket as soon as it fills lets communication overlap with the backward computation of earlier layers.

The overlap is the dominant effect in practice. If the backward pass takes longer than the all-reduce, and the communication is issued incrementally, the communication cost disappears from the critical path almost entirely. The condition is that the last bucket’s reduction finishes before the optimiser step would otherwise begin, which requires the first buckets to be issued early enough. Frameworks expose this as a bucket size parameter plus an option to overlap, and the failure mode of a poorly chosen size is a step that is communication-bound at the end even though the average bandwidth utilisation looked fine.

Choosing the reduction order and dtype

Floating-point addition is not associative, so the order in which partial sums are combined changes the result in the last bits. Ring all-reduce in its basic form sums in a fixed order determined by the ring positions, which is deterministic for a fixed device count and topology but changes when $P$ changes. Runs at different scales are therefore not bit-identical even with identical seeds, which matters for reproducibility claims.

The more consequential choice is the reduction dtype. Reducing in bf16 or fp16 halves the traffic but accumulates rounding across $P$ additions, and the error grows with $P$. Reducing in fp32 doubles the traffic and keeps the error bounded. A common compromise is to reduce in the input dtype and accept the drift, or to keep the gradient in fp32 for the reduction and cast afterwards.

There is a third option that is better on both axes when the interconnect supports it: in-network reduction, where the switch performs the addition as packets pass through, so the traffic is a single pass rather than $2(P-1)/P$ passes. This requires hardware support and a collective library that can use it; the ring algorithm remains the fallback.

Why this bounds the data-parallel degree

The communication per step is proportional to the gradient size, which is proportional to the parameter count. The computation per step is $6ND$ FLOPs. The ratio of compute time to communication time therefore scales as $D$, the tokens per step, over the parameter count times the bandwidth. Doubling the number of devices doubles the tokens per step for a fixed per-device batch, which improves the ratio; but doubling the devices also increases the latency term.

The practical limit on data parallelism is the point where the all-reduce no longer fits under the backward pass. Beyond that, adding replicas costs more than it returns, and the model must be split by another means. Splitting the parameters themselves across devices reduces the per-device gradient, which reduces the all-reduce volume proportionally; this is the mechanism behind optimiser state sharding, which turns the all-reduce into a reduce-scatter followed by an all-gather of parameters. Pipeline and tensor partitioning address the same limit from the model side, and combining them is the composition problem described in parallelism plan design.