acceptodds
Under review as a conference paper at ICLR 2027

Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce

Abstract

Ring All-Reduce is a widely used protocol within large-scale distributed training for aggregating gradients across workers in each iteration. For a system with workers, its normalized per-worker communication is . In this work we present a communication-efficient Ring All-Reduce (CERAR) protocol for “approximate” gradient aggregation. CERAR partitions each local gradient into components and crucially relies on linear encoding and decoding operations. It performs communication rounds over an -worker ring, yielding normalized communication rate and normalized storage rate . We present an explicit Vandermonde matrix based construction, whose approximation error can be made arbitrarily close to zero with communication and storage rates approaching one with increasing . However, this limit is achieved through ill-conditioned encoding matrices. Accordingly, we give an alternate construction whose error is , while the relevant condition numbers are , where . This naturally motivates a condition-number-constrained optimization formulation for trading off the competing objectives and obtaining numerically stable practical designs. Our numerical experiments demonstrate that when compared with the production-standard NCCL on NVIDIA A100 PCIe GPU Clusters with low-bandwidth PCIe interconnect, CERAR reduces the raw All-Reduce phase time by up to 47%, and for training a 1.4-billion-parameter Pythia model it reduces training time by about 17% for the same number of iterations while achieving essentially identical validation loss. On the other hand, for GPU clusters with high-bandwidth NVLink interconnects, CERAR performs worse on the All-Reduce phase time and slightly worse in terms of training. Nevertheless, the gap reduces with experiments that involve systems with larger parameter counts. In this scenario we expect the gains to manifest with more optimized implementations of the CERAR protocol.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
distributed training, ring all-reduce, least-squares, approximate gradient

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_39q2OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper develops a communication algorithm in a ring-shaped network for approximate gradient estimation that requires less communication but more local work. This algorithm may produce arbitrarily accurate gradients in exact arithmetic, but this worsens the conditioning of the encoder and decoder. Experiments are performed in both low and high bandwidth settings.

Critical strengths
  1. The main idea is creative, I am not aware of a similar communication routine (I am not very familiar with the literature though).
  2. Math looks solid and intuitive in most places.
  3. The authors make a good job in positioning this work: approximate vs exact gradient estimation, c>Nc>N is needed to get less communication, encoding and decoding is needed thus local work may increase, taking the accuracy ϵ\epsilon too small will interfere with exact arithmetic.
Critical weaknesses
  1. The proposed approach seems to require serious tuning of the accuracy ϵ\epsilon, equivalently the constraint C in (16). The authors do not seem to discuss this much.
  2. The 17% improvement against a very well optimized architecture feels a bit too good.
Questions for authors
  1. How do you choose the constraint CC in practice?
  2. How much extra local work is added by decoding and encoding compared to the vanilla ring-based algorithm?

Suggestion: The abstract is a bit too long and technical. Would be nicer if you transmit the high-level idea without all this math so early on.

Overall, despite that the implementation part can produce many questions, I think that the authors demonstrate a novel proof-of-concept successfully and I'm leaning towards acceptance.

5 comments
AuthorsOpenReview ↗

Response to Critical Weakness 1: Parameter Selection

Our construction gives an approximation error of Φ(U,R)=O(ϵ2)\Phi(U,R)=O(\epsilon^2) and a condition-number bound of κ2(Mi)=O(N ϵ−r⋆)\kappa_2(M_i)=O(\sqrt{N}\ \epsilon^{-r^\star}), where r⋆=⌈c/N⌉−1r^\star=\lceil c/N\rceil-1. Thus, decreasing ϵ\epsilon reduces the approximation error bound but increases the condition-number bound.

We chose c≈3Nc\approx 3N as a heuristic. The choice c=3Nc=3N gives r⋆=2r^\star=2, so the condition-number bound grows as O(N ϵ−2)O(\sqrt{N}\ \epsilon^{-2}). This choice reduces the communication volume while keeping the exponent at two. Choosing c>3Nc>3N would reduce the communication volume further, but would raise the exponent to at least three. We used c=12c=12 for N=4N=4 and c=20c=20 for N=8N=8, both of which give r⋆=2r^\star=2.

For the N=4N=4, c=12c=12 experiment, we used C=106C=10^6 in the matrix optimization. The resulting matrices gave Φ(U,R)=8.95×10−5≈(10−3)2\Phi(U,R)=8.95\times10^{-5} \approx (10^{-3})^2 and a maximum condition number of 5.72×105≈(10−3)−25.72\times10^5 \approx (10^{-3})^{-2}. The numerical results are thus consistent with the theoretical predictions.

AuthorsOpenReview ↗

Response to Critical Weakness 2: Training Time Improvement

The reported 17% improvement is a reduction in training time over the same 1,800 optimizer steps on four A100 PCIe GPUs.

At each training step, we averaged the gradient-reduction times measured on the four GPUs. Averaged over all 1,800 steps, the result was 6.238 s per step for NCCL and 4.863 s for CERAR. The measured time ratio, 6.238/4.863≈1.2836.238/4.863 \approx 1.283, is close to the ratio of the communication volumes for standard Ring All-Reduce and CERAR, (6/4)/(14/12)≈1.286(6/4)/(14/12) \approx 1.286. Thus, CERAR saved about 1.37 s per step on gradient reduction, and these savings accumulated over the run. The total training time decreased from 13,647.7 s to 11,287.1 s, a 17.3% reduction, with similar validation losses at step 1,800 (1.4218 for NCCL and 1.4213 for CERAR).

AuthorsOpenReview ↗

Response to Question 1: Choosing the Constraint C

We choose CC to balance approximation accuracy and numerical stability. If CC is too small, the condition-number constraint is strong and the optimization may not produce a sufficiently small approximation error. If CC is too large, the optimization can obtain a smaller approximation error, but the resulting matrices may be more sensitive to floating-point roundoff errors. Thus, we choose CC large enough to obtain a small approximation error while avoiding excessive numerical sensitivity. This tradeoff also follows from our theoretical results. In particular,

Φ(U,R)=∑i=0N−1∥MiRi−T∥F2=O(ϵ2),\Phi(U,R)=\sum_{i=0}^{N-1}\left\lVert M_iR_i-T\right\rVert_F^2=O(\epsilon^2),

whereas

\qquad r^\star=\left\lceil\frac{c}{N}\right\rceil-1.$$ Therefore, decreasing $\epsilon$ reduces the approximation error but increases the condition number. For $c=3N$, as in our $N=4,c=12$ experiment, $r^\star=2$, and hence $$\Phi(U,R)=O(\epsilon^2), \qquad \kappa_2(M_i)=O\left(\sqrt{N}\ \epsilon^{-2}\right).$$ In the optimization, we set $C=10^6$. The resulting matrices satisfied $$\Phi(U,R)=8.95\times10^{-5}, \qquad \max_i\kappa_2(M_i)=5.72\times10^5.$$ Small rounding errors can become larger during decoding. The FP32 unit roundoff is approximately $5.96\times10^{-8}$. Multiplying it by the largest condition number gives $$\left(5.96\times10^{-8}\right) \left(5.72\times10^5\right) \approx 3.4\times10^{-2}.$$ This suggests that small rounding errors could become larger during decoding. This calculation is only a conservative estimate and does not directly predict the resulting gradient error. In our training experiment, the measured relative gradient error was approximately 1.6%–2.9% at the three evaluated steps, while the final validation loss remained essentially unchanged.
Reviewer_ZoVLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents CERAR, an approximate Ring All-Reduce protocol for distributed training. It allows a small, controllable error in gradient aggregation and relies on linear encoding and decoding to reduce the communication load of gradient aggregation. The paper reports significant speedups on low-bandwidth clusters, but introduces numerical stability issues in the encoding and decoding matrices. The paper provides theoretical analysis, matrix constructions, and a constrained optimization formulation, and validates them through experiments.

Critical strengths
  1. The problem perspective is novel and insightful. The theoretical analysis is relatively complete, with extensive formulas and derivations.
  2. The reporting is honest and the work is reproducible. The authors honestly report the negative results in the NVLink setting and release their code.
Critical weaknesses
  1. The experimental evidence is insufficient to support the main speedup claims. The experiments compare only against a single baseline, NCCL, and lack a comparison with an exact Ring All-Reduce under the same implementation, so it is impossible to tell whether the gains come from the encoding itself or from implementation differences. As an approximate method, CERAR is also not compared with other approximate methods. The authors need to explain whether the 47% speedup on PCIe clearly exceeds the upper bound estimated from the communication rate, and whether the measured bandwidth of the NCCL baseline falls below the nominal PCIe bandwidth. In addition, the experimental scale is small: there is only a single node with 4 to 8 GPUs, and training uses only one model and one dataset. The evidence on gradient error is also limited, since Table 3 reports data for only 3 steps.
  2. The writing needs improvement. The abstract is too long and contains many formulas and experimental details. The notation is dense, and some symbols are used inconsistently. Related Work is too short and lacks sufficient discussion.
Questions for authors
  1. Does the speedup on PCIe exceed the margin allowed by the ratio of communication rates? Could the authors provide more detailed configuration information and runtime comparisons?
  2. Could the authors show how the gradient error evolves over the entire training process, and add gradient error data for the PCIe configuration?
  3. What is the basis for choosing the parameters used in the experiments? I suggest that the authors clarify this.
6 comments
AuthorsOpenReview ↗

Response to critical weakness 1

We have added a comparison with our implementation of exact Ring All-Reduce, which we call Basic Ring All-Reduce. Both Basic Ring All-Reduce and CERAR use point-to-point sends and receives through PyTorch's NCCL backend. In both implementations, communication and local computation run sequentially, without overlap. Basic Ring All-Reduce uses the standard reduce-scatter and all-gather phases, while CERAR uses coded exchanges with encoding, intermediate updates, and decoding.

The table below reports runtimes on eight A100 PCIe GPUs with FP32 inputs. We compute each percentage gain as the runtime saved divided by the baseline runtime.

Runtime comparison on eight A100 PCIe GPUs.

Elements per GPUNCCL All-Reduce (ms)Basic Ring All-Reduce (ms)CERAR (ms)Gain over NCCLGain over Basic Ring All-Reduce
100M1,775.91,309.7940.147.1%28.2%
500M8,611.26,342.64,651.046.0%26.7%
1B17,954.412,671.59,558.646.8%24.6%

For this configuration, the normalized communication volume is 2(N−1)/N=1.752(N-1)/N=1.75 for exact Ring All-Reduce and L/c=26/20=1.30L/c=26/20=1.30 for CERAR. Assuming the same effective bandwidth and negligible computation overhead, the expected runtime reduction is

(1−1.301.75)×100\left(1-\frac{1.30}{1.75}\right)\times 100\\% \approx 25.7\\%.

The measured runtime reductions over Basic Ring All-Reduce are 28.228.2\\%, 26.726.7\\%, and 24.624.6\\%, respectively, close to the 25.725.7\\% predicted from the reduction in communication volume.

NCCL All-Reduce was slower than Basic Ring All-Reduce on this system, which explains why the measured gains over NCCL are larger. The 25.725.7\\% prediction assumes equal effective bandwidth across implementations. Differences in the selected communication algorithm, protocol, channel count, or how data moves between GPUs may contribute to the runtime gap. Comparing achieved bandwidth with nominal PCIe bandwidth would require measurements of traffic on the PCIe links.

We also provide the relative gradient error over the full training run. At each step, CERAR produces the computed gradient, and a separate NCCL All-Reduce on the same local gradients gives the true gradient up to floating-point roundoff. On each GPU, we divide the ℓ2\ell_2 norm of the difference between the two gradients by the ℓ2\ell_2 norm of the true gradient. We report the largest relative error across the four GPUs at each step. The error peaks at approximately 3.53.5\\%.

To the best of our knowledge, no prior work uses linear coding within the ring exchanges to approximate All-Reduce while reducing the number of transmitted values relative to standard Ring All-Reduce at the same numerical precision. CGX [1] uses quantization to reduce the number of bits per transmitted value, while PowerSGD [2] compresses gradients into low-rank factors and aggregates those factors using All-Reduce. CERAR changes the ring exchanges themselves by sending coded combinations of gradient blocks. These approaches reduce communication in different ways, and combining them with CERAR is a direction for future evaluation.

We wish to reiterate that the core contribution of our paper is the striking theoretical result that the communication load within All-Reduce can approach the lower bound of 1, when approximate recovery is allowed. Our work first establishes that exact recovery is impossible with a lower load than 2(N−1)/N2(N-1)/N, and then goes on to provide an explicit construction of a scheme where the communication load can be driven arbitrarily close to 11. Furthermore, following academic and scientific norms we have provided an "honest" assessment of the drawbacks of the explicit scheme, and followed this up with a precise analysis of the quantitative tradeoff between the relative error and condition number of our scheme. While it is true that our explicit scheme has this particular quantitative tradeoff, this does not rule out the existence of better schemes. Our work has pointed out that there is no fundamental theoretical obstruction to obtaining a communication load of 1.

We acknowledge that the scale of our experiments is limited by GPU availability. However, access to a large number of GPUs is rather difficult especially in an academic setting, and despite our best efforts, we were unable to obtain a configuration with more than 8 GPUs.

References

[1] Markov et al., CGX: Adaptive System Support for Communication-Efficient Deep Learning.

[2] Vogels et al., PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization.

AuthorsOpenReview ↗

Response to critical weakness 2

We will shorten the abstract by moving detailed formulas and experimental settings to the main text. The revised abstract will focus on the motivation for CERAR, how it reduces communication, and the main empirical result: faster training on the tested PCIe system with a similar validation loss. We will also simplify the notation, define symbols at first use, and check that each symbol is used consistently throughout the paper. Finally, we will expand the Related Work section to discuss other compressed All-Reduce methods.

AuthorsOpenReview ↗

Response to Question 1: PCIe Speedup and Runtime Comparison

We agree that the measured runtime gain over NCCL exceeds the prediction based solely on communication volume. For the eight-GPU configuration, standard Ring All-Reduce has normalized communication volume 2(N−1)/N=1.752(N-1)/N=1.75, whereas CERAR has L/c=26/20=1.30L/c=26/20=1.30. Assuming the same effective bandwidth and negligible overhead, the expected runtime gain is (1−1.30/1.75)×100(1-1.30/1.75)\times100\\%\approx25.7\\%.

To address the reviewer's comment, we developed our own implementation of the standard Ring All-Reduce which we call Basic Ring All-Reduce. Both CERAR and basic Ring All-Reduce use point-to-point sends and receives through PyTorch's NCCL backend and perform communication and local computation sequentially, without overlap in these experiments. Basic Ring All-Reduce performs the standard reduce-scatter and all-gather phases, while CERAR performs its coded exchanges and the associated encoding, intermediate updates, and decoding.

The experiments use eight A100 PCIe 40GB GPUs with no active NVLink connections and NCCL version 2.28.9. The NCCL All-Reduce baseline calls dist.all_reduce, with automatic algorithm, protocol, and channel selection. All inputs are FP32. The table reports the median across measured runs of the slowest GPU's elapsed time. The timing excludes initialization, input generation, and the time GPUs spend waiting for one another before the run. GPU execution is synchronized at the timing boundaries.

Runtime comparison on eight A100 PCIe GPUs.

Elements per GPUNCCL All-Reduce (ms)Basic Ring All-Reduce (ms)CERAR (ms)Gain over NCCLGain over Basic Ring All-Reduce
100M1,775.91,309.7940.147.1%28.2%
500M8,611.26,342.64,651.046.0%26.7%
1B17,954.412,671.59,558.646.8%24.6%

CERAR's runtime gains over Basic Ring All-Reduce are 28.2%, 26.7%, and 24.6%, respectively, which are close to the 25.7% predicted from the reduction in communication volume. The corresponding gains over NCCL are 47.1%, 46.0%, and 46.8%.

NCCL All-Reduce was also slower than Basic Ring All-Reduce on this system. Consequently, the larger gain relative to NCCL cannot be attributed to communication-volume reduction alone. Differences in the selected communication algorithm, protocol, channel count, or how data is moved between GPUs may contribute to these differences.

Reviewer_d7coOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper introduces CERAR (Communication-Efficient Ring All-Reduce), a protocol that tries to speed up distributed training by aggregating gradients approximately rather than exactly. By splitting local gradients into chunks and using linear encoding/decoding across ring communication rounds, the protocol reduces communication volume.

Critical strengths

• Interesting Academic Trade-off: Looking at Ring All-Reduce through an approximate, information-theoretic lens is a compelling mathematical exercise.

• Good Performance on Weak Networks: The protocol works exactly as intended on bottlenecked PCIe setups, proving that communication volume drops.

• Transparent Profile Breakdown: The authors do a great job profiling their compute vs. communication breakdown (Table 4), which clearly exposes where the algorithm succeeds and fails.

Critical weaknesses

• Fails on Modern Hardware (NVLink) or Infiniband: The biggest red flag is that CERAR is 33% slower than NCCL on high-bandwidth NVLink clusters. NVLink/IB is the baseline standard for LLM training clusters today. An optimization that only helps low-bandwidth PCIe setups has almost no practical deployment target in modern deep learning workflows.

• Severe Compute Overhead: Table 4 reveals that the encoding, decoding, and update computations are incredibly expensive (taking ~215 ms on H200). When you have a fast network, this massive computational tax completely wipes out any communication savings.

• Inherent Numerical Instability: The underlying theory is structurally fragile. Pushing the approximation error down naturally drives the matrix condition numbers to infinity. Relying on an expensive, non-convex optimization heuristic just to generate valid encoding matrices for a specific cluster configuration is a major usability blocker.

• Lack of Real-World Scale: The training experiments are limited to a toy 1.4B model trained on the TinyStories dataset for a very brief number of steps (1,800 to 7,630). There is no evidence that the accumulation of O(ϵ\epsilon) gradient errors remains stable during massive, long-horizon pre-training runs.

Questions for authors
  1. Scalability of Matrix Generation: How long does the non-convex alternating least-squares optimization take to compute the UU and RR matrices as the number of workers NN scales up to 32, 64, or 128? Does this matrix generation become a bottleneck itself?

  2. Gradient Noise Impact: Did you evaluate the downstream model quality on a non-trivial benchmark? TinyStories validation loss is an incredibly low bar; does the accumulated gradient error cause degradation or divergence on standard downstream benchmarks (like GLUE, MMLU, etc.)?

  3. Hardware Adaptation: Is there any algorithmic way to strip down the O(ϵ−r∗)O(\epsilon^{-r^*}) computational overhead during the encoding/decoding phase, or is this heavy local processing an unavoidable tax of the protocol's math?

2 comments
AuthorsOpenReview ↗

Response to Critical Weaknesses 1–4

Critical Weakness 1

The reported 33% slowdown concerns the standalone H200 All-Reduce benchmark. In the NVLink training experiment, the end-to-end slowdown is 3.65% (Table 2), with essentially identical validation loss. On the A100 PCIe system, CERAR reduces training time by 17.3%, from 3.79 to 3.14 hours, while achieving validation losses of 1.4213 versus 1.4218 for NCCL. These results demonstrate a practical benefit on the tested PCIe configuration.

The relevant tradeoff is between communication time saved and additional local computation. Faster interconnects reduce the former, explaining the different outcomes. Our current implementation is a proof of concept with sequential communication and computation. Overlapping these operations where dependencies allow is a concrete opportunity for improvement. We report the NVLink limitation explicitly. InfiniBand was not evaluated, so the experiments do not establish a slowdown on InfiniBand systems.

Critical Weakness 2

The approximately 215 ms in Table 4 corresponds to processing 24 billion FP32 entries per GPU, or 96 GB of input per GPU. It includes encoding, decoding, intermediate updates, and the associated memory accesses. It should therefore be interpreted in the context of this tensor size.

Table 4 directly explains the H200 result: CERAR's communication phase takes approximately 306.5 ms, compared with 392.0 ms for NCCL's complete reduction. Adding approximately 215.8 ms of local computation brings CERAR's total to 522.6 ms. Thus, the current implementation's computation cost outweighs its communication savings in this setting. On A100 PCIe, however, local computation takes only 29–34 ms for 1 billion entries per GPU, compared with approximately 9.3–9.5 seconds of communication. The measured benefit therefore already includes the full computation overhead. Our current implementation performs communication and computation sequentially. Overlapping these operations where dependencies allow, as done in NCCL, could reduce the total reduction time and potentially enable CERAR to outperform NCCL even on high-bandwidth interconnects.

Critical Weakness 3

The error–conditioning tradeoff is explicitly characterized in our analysis and motivates the practical design in Section 2.4. The construction gives squared approximation error Φ(U,R)=O(ϵ2)\Phi(U,R)=O(\epsilon^2) and κ2(Mi)=O(Nϵ−r⋆)\kappa_2(M_i)=O(\sqrt{N}\epsilon^{-r^\star}). For practical use, Eq. (16) minimizes approximation error subject to the finite constraint κ2(Mi)≤C\kappa_2(M_i)\le C. The algorithm therefore operates at a chosen finite error and condition number.

The optimization is also not required to establish the existence of encoding and decoding matrices. Sections 2.2 and 2.3 provide explicit constructions and analyze their approximation error and conditioning. The optimization uses a construction as its initialization to improve the practical tradeoff.

Furthermore, matrix generation is performed once on a single device, and the resulting matrices are saved for reuse. They depend on the worker count and coding parameters, rather than the model size, gradient dimension, dataset, or physical interconnect. The same matrices can therefore be reused across training runs and hardware systems with the same coding configuration. Table 2 shows that training with CERAR's approximate gradients achieves essentially the same final validation loss as NCCL on both PCIe and NVLink.

Critical Weakness 4

The experiments train a 1.4-billion-parameter language model on approximately 118 million tokens in the PCIe configuration and 1 billion tokens in the NVLink configuration. Within each configuration, CERAR and NCCL use the same initialization, data ordering, hyperparameters, and number of training steps. The comparison measures whether CERAR saves time while maintaining validation loss.

On PCIe, CERAR saves approximately 39 minutes over 1,800 steps, with final validation losses of 1.4213 and 1.4218 for CERAR and NCCL. Over 7,630 steps on NVLink, the corresponding losses are 1.1644902 and 1.1644904. These results provide evidence that the approximation preserves training quality over the evaluated runs.

The per-reduction O(ϵ)O(\epsilon) approximation result does not by itself imply that training error accumulates linearly with the number of steps. The effect on optimization must be evaluated through training behavior, as in these experiments. Our experiments demonstrate faster training at comparable validation loss on the tested PCIe system and preserved validation loss over one billion training tokens on NVLink. Access to GPU resources restricted our experiments to configurations with up to eight GPUs. Evaluating larger systems and longer pretraining runs is the next step in extending these results.

AuthorsOpenReview ↗

Response to Questions 1–3

Q1

The encoding and decoding matrices are computed once for a chosen configuration and saved for reuse. All workers' matrices are generated on a single device, so generating matrices for N=128N=128 workers does not require 128 GPUs. The same matrices are used at every training step and can also be reused across training runs with that configuration. Their generation depends on the worker count and coding parameters, but is independent of the model size, gradient dimension, and training data. Because training uses precomputed matrices, matrix generation does not add time to individual training steps. It is a one-time setup cost per configuration.

Q2

We were unable to do this owing to lack of access to larger GPU clusters and also because even the 8-GPU system was available to us only for a limited amount of time. Our response to this goes back to evaluating the core contributions of this manuscript. Please refer to the umbrella response we provide above.

Q3

The factor O(ϵ−r⋆)O(\epsilon^{-r^\star}) appears in the condition-number bound for the construction. For fixed cc and LL, the arithmetic cost of encoding and decoding is determined by the matrix dimensions. For an input of dd elements per GPU, dense encoding requires (2c−1)d(2c-1)d floating-point operations, and dense decoding requires (2L+1)d(2L+1)d. These counts are independent of ϵ\epsilon.

Reducing cc also reduces L=c+N−2L=c+N-2 and therefore lowers the local arithmetic cost, at the expense of sending more data. Another direction is to design sparse or structured encoding and decoding matrices that can be applied with fewer operations while preserving the desired approximation accuracy and numerical stability. The counts above describe the current dense implementation.

Reviewer_jy3ROpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces CERAR, a linearly coded ring protocol for approximate gradient aggregation. By partitioning each local gradient into c chunks and communicating over L=c+N-2 rounds, CERAR reduces the normalized per-worker communication volume from 2(N-1)/N to 1+(N-2)/c. The authors construct schemes whose communication rate approaches one while the reconstruction error vanishes, at the cost of increasingly ill-conditioned encoding matrices. They characterize this error–conditioning tradeoff and propose a constrained optimization approach to obtain practical encoding and decoding matrices.

Critical strengths
  1. The paper addresses a relevant problem in distributed training.
  2. The problem formulation is clear and well defined.
  3. The proposed approach is interesting.
  4. Experiments on a 1.4B-parameter model are encouraging, as well as the 17% reduction in training time with nearly unchanged validation loss on the tested PCIe system.
Critical weaknesses
  1. The paper is difficult to read. In general, it seems mainly like a long theoretical description of the proposed method. Moreover, notation is heavy and confusing: in some cases L is the loss function and in other cases it is the total number of rounds.
  2. The related work section provides limited discussion of existing communication-efficient training methods and how CERAR differs from them.
Questions for authors
  1. How do you justify the speedup of the proposed method in a low-bandwidth scenario while having a slowdown in a high-bandwidth one? Under what scenario the proposed method is relevant? Personally, I would have expected a speedup in both scenarios.
  2. What is the reasoning of using specifically c = 20 and L = 26 (or c = 12 and L = 14)? Why not other values?
  3. In the experiments you have used 4 and 8 workers. How does the result change when using 16, 32 and 64 workers?
  4. The paper mentions that the proposed paper is orthogonal to methods such as quantization or sparsification. Given its structure, how does the proposed method performs when combined with quantization and sparsification?

If all these questions are satisfactorily addressed, I would consider revising my score.

7 comments
AuthorsOpenReview ↗

Response to Critical Weaknesses 1 and 2

Critical Weakness 1

We will revise the presentation so that readers can understand the algorithm before working through its analysis. We will start with a short overview of what each worker sends, how it updates the received message, and how it reconstructs the aggregate. We will also use L\mathcal{L} for the loss function and reserve LL for the total number of communication rounds. We will define symbols where they first appear and check their use throughout the paper.

Critical Weakness 2

We will expand the Related Work section to explain how existing methods reduce communication and how CERAR differs from them. PowerSGD [1] approximates a gradient matrix using two smaller matrices and uses All-Reduce to sum those factors. QSGD [2] represents gradient entries using fewer bits, and Deep Gradient Compression [3] communicates a sparse subset of the gradient updates. These methods reduce the amount of data used to represent the gradient. CERAR changes how workers aggregate their inputs over a ring. For example, CERAR could in principle replace the All-Reduce operations that PowerSGD uses to sum its factors.

CGX [4] is a more direct comparison at the collective level. Its ring variant keeps the standard reduce-scatter and all-gather phases and uses quantization to send fewer bits per value. CERAR changes which linear combinations of gradient chunks workers exchange, allowing them to send fewer values in total. We will make this distinction explicit in the revision.

[1] Vogels et al. PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization.

[2] Alistarh et al. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding.

[3] Lin et al. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training.

[4] Markov et al. CGX: Adaptive System Support for Communication-Efficient Deep Learning.

AuthorsOpenReview ↗

Response to Question 1: Runtime on PCIe and NVLink

Compared with standard Ring All-Reduce, our method sends fewer bytes while performing additional local computation for encoding, decoding, and intermediate updates. Let TcommT_{\mathrm{comm}} be the communication time savings and TcompT_{\mathrm{comp}} be the additional computation time owing to CERAR's usage. When communication and computation do not overlap, our method is faster if

Tcomp−Tcomm<0.T_{\mathrm{comp}}-T_{\mathrm{comm}}<0.

On the tested low-bandwidth PCIe system, the communication savings outweighed the extra computation, so our method was faster. On the tested high-bandwidth NVLink system, the communication savings were too small to offset the extra computation, so our method was slower. The current implementation is therefore most relevant for large reductions over bandwidth-limited links, where sending fewer bytes can save enough time to offset the added computation.

To examine this tradeoff, we also compare against our own implementation of standard Ring All-Reduce, which we call Basic Ring All-Reduce. Both this implementation and CERAR perform communication and local computation sequentially. The table below provides the communication and computation breakdowns on H200 NVLink and shows that CERAR reduces communication time relative to Basic Ring All-Reduce at all three tested tensor sizes. For example, with 24 billion elements per GPU on H200, communication time decreases from 393.239 ms to 306.516 ms, while computation increases from 49.691 ms to 215.830 ms. The communication savings therefore remain present, but the additional computation outweighs them under sequential execution. NCCL integrates communication and reduction within its collective kernels and completes this reduction in 392.020 ms, compared with 443.023 ms for Basic Ring All-Reduce and 522.542 ms for CERAR. Our current implementation is a proof of concept. Overlapping communication and computation where dependencies allow is expected to reduce total runtime. Since CERAR's communication phase already takes less time than NCCL's complete reduction in this setting, sufficient overlap could translate the communication savings into an overall speedup on high-bandwidth interconnects as well.

Runtime comparison and communication/computation breakdown on four H200 SXM GPUs connected through NVLink. All times are in milliseconds and are averaged across the four GPUs using their mean timings from the profiled runs. Tensor size is the number of FP32 elements per GPU. Communication includes waiting for peers. Total time also includes overhead outside the timed communication and computation phases.

Tensor sizeNCCL totalBasic Ring All-Reduce totalBasic Ring All-Reduce comm.Basic Ring All-Reduce comp.CERAR totalCERAR comm.CERAR comp.
9B147.254166.736147.70618.942197.360115.49281.675
15B245.015277.421245.81831.518327.976191.863135.924
24B392.020443.023393.23949.691522.542306.516215.830
AuthorsOpenReview ↗

Response to Questions 2–4: Parameters, Scale, and Gradient Compression

Q2

We choose cc by considering communication volume, approximation error, and numerical stability. A larger cc reduces communication volume, but it can make it harder to achieve a small approximation error without producing ill-conditioned matrices. Our construction gives

\qquad \kappa_2(M_i)=O\left(\sqrt{N}\ \epsilon^{-r^\star}\right), \qquad r^\star=\left\lceil\frac{c}{N}\right\rceil-1.$$ Thus, decreasing $\epsilon$ lowers the approximation error bound, while the condition-number bound grows at a rate controlled by $r^\star$. In general, choosing $c=3N$ gives $$r^\star=\left\lceil\frac{3N}{N}\right\rceil-1=2.$$ The squared approximation residual is then $O(\epsilon^2)$, and the condition-number bound is $O(\sqrt{N}\ \epsilon^{-2})$. This choice reduces communication volume while keeping the exponent at two. Choosing $c>3N$ would further reduce communication volume, but it would increase $r^\star$ to at least three. For $N=4$, we used this choice, giving $c=12$ and $L=14$. For $N=8$, we used $c=20$ as a test configuration, which also gives $r^\star=\lceil20/8\rceil-1=2$ and yields $L=26$. In both cases, $L$ is determined by $L=c+N-2$. For $(N,c)=(4,12)$, the resulting matrices achieved $\Phi=8.95\times10^{-5}$ and $\max_i\kappa_2(M_i)=5.72\times10^5$. For $(N,c)=(8,20)$, they achieved $\Phi=4.20\times10^{-3}$ and $\max_i\kappa_2(M_i)=8.13\times10^4$. **Q3** We wish to reiterate that the core contribution of our paper is the striking theoretical result that the communication load within All-Reduce can approach the lower bound of 1, when approximate recovery is allowed. Our work first establishes that exact recovery is impossible with a lower load than $2(N-1)/N$, and then goes on to provide an explicit construction of a scheme where the communication load can be driven arbitrarily close to $1$. Furthermore, following academic and scientific norms we have provided an "honest" assessment of the drawbacks of the explicit scheme, and followed this up with a precise analysis of the quantitative tradeoff between the relative error and condition number of our scheme. While it is true that our explicit scheme has this particular quantitative tradeoff, this does not rule out the existence of better schemes. Our work has pointed out that there is no fundamental theoretical obstruction to obtaining a communication load of 1. We acknowledge that the scale of our experiments is limited by GPU availability. However, access to a large number of GPUs is rather difficult especially in an academic setting, and despite our best efforts, we were unable to obtain a configuration with more than 8 GPUs. **Q4** Gradient quantization and sparsification are also well-known methods to reduce the communication time within distributed training. However, these methods operate by fundamentally reducing the number of bits required to even represent the gradients or partial gradients. Note that even systems that use quantization and/or sparsification require an all-reduce phase so that the workers can synchronize the overall gradient and hence the parameter for the next iteration. This is exactly where techniques like CERAR fit in. CERAR provides a technique for reducing the communication load of the all-reduce phase. Thus, it can be used in conjunction with quantization and/or sparsification, and is orthogonal to those techniques in this respect.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Response

We thank the reviewers for their efforts in reviewing our manuscript. There are several questions about how we chose the parameters in our work and how the gradient errors evolve in practice. There are also several questions about the performance on larger scale clusters and comments that are solely focused on criticizing the manuscript based on the experimental results.

At the outset we would like to sincerely reiterate that the core contribution of our paper is the striking theoretical result that the communication load within All-Reduce can approach the lower bound of 1, when approximate recovery is allowed. Our work first establishes that exact recovery is impossible with a lower load than 2(N−1)/N2(N-1)/N, and then goes on to provide an explicit construction of a scheme where the communication load can be driven arbitrarily close to 11. Furthermore, following academic and scientific norms we have provided an ``honest'' assessment of the drawbacks of the explicit scheme, and followed this up with a precise analysis of the quantitative tradeoff between the relative error and condition number of our scheme. While it is true that our explicit scheme has this particular quantitative tradeoff, this does not rule out the existence of better schemes. Our work has pointed out that there is no fundamental theoretical obstruction to obtaining a communication load of 1.

While Ring-All-Reduce is heavily used in distributed training, it is a bona fide algorithm in its own right, which is used in a variety of scenarios. Our results apply there as well.

We have also provided experimental results that support our theoretical results and have expanded on why these are valid in the responses to the various reviewers. However, we feel that it is unfair to penalize our manuscript only because we could not run experiments on 16, 32 and 64 GPUs and on the latest and greatest datasets and models. In many cases, such at-scale experiments can only be run in large companies or equivalent entities and scoring a manuscript low only based on this aspect is not grounded in academic and scientific best practices.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.