Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce
Abstract
Ring All-Reduce is a widely used protocol for aggregating gradients across workers in large-scale distributed training. For a system with N workers, its normalized per-worker communication is 2(N−1)/N. In this work we present a communication-efficient Ring All-Reduce (CERAR) protocol for ``approximate'' gradient aggregation. CERAR partitions each local gradient into c components and relies on linear encoding and decoding operations. It performs L=c+N−2 communication rounds over an N-worker ring, yielding normalized communication rate 1+(N−2)/c and normalized storage rate 1+N/c. We present an explicit Vandermonde matrix based construction whose approximation error can be made arbitrarily small, with communication and storage rates approaching one as c increases. However, this comes at the cost of ill-conditioned encoding matrices. We therefore give an alternate construction whose error is O(ε), while the relevant condition numbers are O(ε−r⋆), where r⋆=⌈ c/N⌉−1. This motivates a condition-number-constrained optimization formulation for obtaining numerically stable practical designs. Our experiments show that, compared with the production-standard NCCL on NVIDIA A100 PCIe GPU clusters with low-bandwidth PCIe interconnect, CERAR reduces raw All-Reduce time by up to 47\%. 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 GPU clusters with high-bandwidth NVLink interconnects, CERAR performs worse in the All-Reduce phase and slightly worse in overall training time. However, the gap narrows for larger model sizes, suggesting that further gains may be possible with more optimized CERAR implementations.
Related
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Distributed LLM Inference via Communication-Efficient Speculative Decoding
- Dynamic Regret and Tightened Constraint Violation for Communication-Efficient Distributed Online Bilevel Optimization
- A Moving-Horizon Approximate Branch-and-Reduce Method for Deep Classification Trees
- Topology Design for Distributed Consensus with Relay-Assisted Communication
BibTeX
@misc{munim2026communicationefficient,
title = {{Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce}},
author = {Sifat Munim and Aditya Ramamoorthy},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23898},
eprint = {2609.23898},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23898},
}
RIS
TY - UNPB
TI - Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce
AU - Sifat Munim
AU - Aditya Ramamoorthy
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.23898
UR - https://arxiv.org/abs/2609.23898
AB - Ring All-Reduce is a widely used protocol for aggregating gradients across workers in large-scale distributed training. For a system with N workers, its normalized per-worker communication is 2(N−1)/N. In this work we present a communication-efficient Ring All-Reduce (CERAR) protocol for ``approximate'' gradient aggregation. CERAR partitions each local gradient into c components and relies on linear encoding and decoding operations. It performs L=c+N−2 communication rounds over an N-worker ring, yielding normalized communication rate 1+(N−2)/c and normalized storage rate 1+N/c. We present an explicit Vandermonde matrix based construction whose approximation error can be made arbitrarily small, with communication and storage rates approaching one as c increases. However, this comes at the cost of ill-conditioned encoding matrices. We therefore give an alternate construction whose error is O(ε), while the relevant condition numbers are O(ε^−r_⋆), where r_⋆=⌈ c/N⌉−1. This motivates a condition-number-constrained optimization formulation for obtaining numerically stable practical designs. Our experiments show that, compared with the production-standard NCCL on NVIDIA A100 PCIe GPU clusters with low-bandwidth PCIe interconnect, CERAR reduces raw All-Reduce time by up to 47\%. 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 GPU clusters with high-bandwidth NVLink interconnects, CERAR performs worse in the All-Reduce phase and slightly worse in overall training time. However, the gap narrows for larger model sizes, suggesting that further gains may be possible with more optimized CERAR implementations.
ER -