Derive the cost of a ring all-reduce. Why is it bandwidth-optimal, and where does it stop scaling?

TL;DR: A ring all-reduce over n ranks splits the buffer into n slices and runs two phases, reduce-scatter and all-gather, each with n−1 steps in which every rank sends and receives one slice. Each phase moves (n−1)/n of the buffer per rank, so the total is 2(n−1)/n × S per rank, which tends to 2S and does not grow with n. That is optimal in bytes, since every rank must receive at least (n−1)/n × S of other ranks' data to compute the sum and another (n−1)/n × S to hold the result. Its weakness is latency: 2(n−1) sequential steps, each paying the link's round trip, which is why NCCL switches to tree algorithms for small buffers at large n.

How to approach it

Set up the problem precisely: n ranks, each with a buffer of S bytes, and every rank must end with the elementwise sum. Then describe the ring's two phases with a small n so the interviewer can see each step. Count the bytes per rank per phase and add them. Give the lower bound so the word "optimal" has a proof behind it. Then write the full cost model with a latency term and show the crossover. Finish with what NCCL actually does.

A strong answer

A typical situation: a candidate is asked why gradient synchronization costs "about twice the model" and not "n times the model", and the answer is the ring.

Set up: n ranks in a logical ring, each holding a buffer of S bytes, which is cut into n equal slices of S/n. Rank i starts by sending slice i to rank i+1.

Phase 1, reduce-scatter, n−1 steps. In each step every rank sends one slice to its right neighbor and receives one slice from its left neighbor, adding the received slice into its own copy. After n−1 steps, each rank holds the fully reduced sum for exactly one slice: rank i owns the complete sum of slice i−1 (indices modulo n). Every rank sent n−1 slices, so it moved (n−1) × S/n bytes.

Phase 2, all-gather, n−1 steps. Each rank sends the completed slice it owns to its right neighbor, which stores it and forwards it in the next step. After n−1 steps every rank has every completed slice. Again each rank sent n−1 slices, (n−1) × S/n bytes.

inputs:  n ranks, buffer S bytes, per-rank link bandwidth B, per-step latency α

bytes sent per rank:
  reduce-scatter = (n−1) × S/n
  all-gather     = (n−1) × S/n
  total          = 2 (n−1)/n × S

time (bandwidth term only) = 2 (n−1)/n × S ÷ B

example: S = 16 GB (an 8B model's bf16 gradient), n = 64, B = 50 GB/s
  bytes per rank = 2 × 63/64 × 16 GB = 31.5 GB
  time           = 31.5 ÷ 50 = 0.63 s
same S at n = 8 over NVLink, B = 900 GB/s:
  bytes per rank = 2 × 7/8 × 16 GB = 28 GB
  time           = 28 ÷ 900 = 31 ms

sanity: doubling n from 64 to 128 changes 2(n−1)/n from 1.969 to 1.984, under 1%;
        the per-rank bytes are flat in n, which is what "scales" means here.

Why no algorithm does better on bytes. Each rank must end with the sum, which depends on all n inputs, so it must receive information from n−1 other ranks about every element. The minimum is (n−1)/n × S received in the reduction phase (it already holds its own 1/n contribution to each slice, but even in the most favorable arrangement it must take in the other ranks' contributions for the slice it reduces, and the reduced results for the slices it does not) plus (n−1)/n × S received in the distribution phase for the slices reduced elsewhere. Under the model where every rank has one link in and one link out and bandwidth is the constraint, 2(n−1)/n × S is the floor and the ring meets it. Ring vs Tree All-Reduce has the comparison with the alternatives.

Where it stops scaling. The bandwidth term is flat in n, but the ring takes 2(n−1) sequential steps and every step pays a fixed latency α: the time to launch the transfer, traverse the switch, and synchronize with the neighbor. The full cost is:

T_ring = 2 (n−1) × α + 2 (n−1)/n × S ÷ B

with α ≈ 10 µs across an InfiniBand fabric:
  n = 64,   S = 16 GB:  latency 1.3 ms, bandwidth 630 ms  → bandwidth dominates
  n = 1,024, S = 16 GB: latency 20 ms,  bandwidth 640 ms  → still fine
  n = 1,024, S = 1 MB:  latency 20 ms,  bandwidth 0.04 ms → latency dominates by 500×

sanity: small buffers at large n are the failure case, and they are common:
        DDP buckets of 25 MB, per-layer FSDP gathers, and any collective
        launched for a scalar such as a gradient norm.

A tree all-reduce (a reduce up a binary tree and a broadcast down) takes about 2 log₂(n) steps instead of 2(n−1), so at n = 1,024 it pays 20 latencies instead of 2,046, at the cost of a bandwidth term that is worse by a constant. NCCL and Collective Algorithms describes how NCCL picks: it models both costs per collective size and topology and chooses ring for large buffers and tree for small ones, and NCCL_ALGO=Ring or Tree overrides it for measurement. On NVSwitch systems there is a third option, NVLS, where the switch itself performs the reduction and the per-GPU traffic drops toward S.

Decision: the ring is the right mental model and the right algorithm for the large gradient and weight collectives of training. The condition that reverses it is the buffer-size-to-rank-count ratio; when S/n falls below a few hundred kilobytes, latency terms take over and trees, or fusing the small collectives into larger ones, win.

The reversal condition: small buffers, where the ring's 2(n−1) latency term dominates and a tree wins. NCCL switches on its own, and NCCL_DEBUG=INFO prints which algorithm it chose, which is worth reading before tuning anything by hand.

What interviewers probe next

• "Why does a reduce-scatter cost half an all-reduce?" It is exactly phase 1: (n−1)/n × S per rank, which is why ZeRO-3 can replace an all-reduce with a reduce-scatter plus a later all-gather at the same total bytes.
• "How does a 2D torus change this?" Rings run along each dimension, so a 2D ring all-reduce does two smaller rings of √n ranks each, cutting the latency term to about 4(√n − 1) at the same bandwidth term.
• "What is the bandwidth in the formula when links are bidirectional?" The ring sends and receives at the same time on different links, so B is the per-direction figure; a "900 GB/s" NVLink number is bidirectional and the honest B is 450 GB/s.
• "Does the reduction arithmetic ever matter?" At n = 1,024 with bf16 buffers, yes: the sum order differs from a serial sum, so results are not bitwise reproducible across world sizes, and NCCL reduces in the buffer's dtype unless told otherwise.

Common mistakes

• Quoting 2S per rank without knowing it is 2(n−1)/n and why.
• Claiming ring all-reduce is "O(n)" in cost; the bytes are constant in n and only the latency term is linear.
• Forgetting the latency term entirely, then being unable to explain why NCCL has a tree algorithm.
• Using the bidirectional link figure as the per-direction bandwidth.

Key takeaways

• Reduce-scatter then all-gather, each (n−1)/n × S per rank; total 2(n−1)/n × S, which tends to 2S.
• Bandwidth-optimal: every rank must receive at least that much to hold the full sum.
• Full cost 2(n−1) α + 2(n−1)/n × S/B; the latency term wins for small S at large n, and NCCL switches to tree there.
• 16 GB at n = 64 over 50 GB/s is 0.63 s; the same at n = 8 over NVLink is 31 ms.