CS Paper Radar

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

Sifat Munim, Aditya Ramamoorthy

cs.IT ·submitted 2026-09-20 22:10 UTC · v2

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_\star})$, where $r_\star=\lceil c/N\rceil-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.

Comment
21 pages, 1 figure

Closest papers

Nearest neighbours by meaning across the whole index.

Linear Network Coding for Sum All-Reduce over Ring Networks

cs.IT ·2026-11-16 ·Yi Chen, Zhuoqi Tu, Shenghao Yang
publishedtheory similarity 0.70
Abstract

Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with $N\geq 3$ nodes and unit-capacity links, where each node holds a vector containing $K$ symbols, we prove that the number of time units $T$ required by any feasible linear code satisfies $T\ge\max\bigl\{K+N-2,\ \lceil\frac{2(N-1)}{N}K\rceil\bigr\}$, giving a rate $K/T$ of at most $N/(2(N-1))$. The bound is tight over every field. When $K\ge N$, an interleaved reduce--multicast code achieves the bound; when $K<N$ and $K$ divides $N$, a reduce--partial-multicast code does. When $K<N$ and $K$ does not divide $N$, no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.

0.41

Deterministic Distributed Linearly Separable Computation via Nested Cyclic Codes

cs.IT ·2026-10-13 ·Anu Mathew, M. Nikhil Krishnan
similarity 0.64
Abstract · 13 pages, 1 figure

We study the $(K,N,S,M,K_c)$ distributed linearly separable computation (DLSC) setting, where a master employs $N$ workers with a per-worker computation load of $M$ to recover $K_c$ deterministic linear combinations of $K$ messages in the presence of up to $S$ stragglers. We propose a DLSC framework based on nested cyclic codes that achieves $M=\frac{K}{N}(S+K_c)$. For sufficiently large $K$, we establish the matching converse $M\geq\frac{K}{N}(S+K_c)$, proving the asymptotic computation load optimality of the proposed framework. By instantiating cyclic locally recoverable codes (LRCs) as base codes in the framework, the master can recover the desired $K_c$ linear combinations by contacting fewer than $N-S$ workers under many straggler scenarios. This essentially softens the straggler threshold without increasing the computation load or communication cost. Finally, we extend the construction to reduce the per-worker communication load by a factor of $m$, while achieving an asymptotically optimal computation load of $M=\frac{K}{N}(S+mK_c)$.

0.20

Binary Cyclic Gradient Coding: Exact Recovery and Robustness to Compression

cs.IT ·2026-10-14 ·Hassan Ou-azzou, Imad Kissami, El Houcine Bergou
theory similarity 0.61
Abstract

We introduce binary cyclic gradient coding (BCGC), an exact gradient coding scheme for $n$ workers and up to $s$ stragglers. Its encoding matrix is binary, circulant when $(s+1)\mid n$ and nearly circulant otherwise, and the master decodes by a single summation. Like the fractional repetition coding scheme (FRC) and its generalized version (GFRC), BCGC splits the workers into $s+1$ classes that each cover the whole dataset, but it assigns the data through cyclic supports. Its encoding matrix has rank $n-s$, and $n-s-1$ workers keep the balanced load $s+1$, which is the largest possible number. We prove that encoding matrix of BCGC is not permutation-equivalent to those of FRC and GFRC schemes. Moreover, We also prove that a binary coded scheme with compression is equivalent to an uncoded compressed scheme on a coarser partition of the data. This explains why binary schemes remain stable under compression, whereas the large decoding coefficients of MDS codes amplify the compression error and lead to divergence in our experiments. For every contractive compressor, the standard convergence guarantee of compressed gradient descent holds on each coarse partition. FRC, GFRC and BCGC therefore share the same convergence guarantee and differ only in their partitions, with one partition for FRC, two for GFRC and $s+1$ distinct partitions for BCGC. Choosing among these partitions can recover the exact gradient in cases where FRC and GFRC cannot. Experiments on four datasets confirm the theory. BCGC matches GFRC, keeps its accuracy under top $κ$ sparsification while the MDS codes diverge, and on heterogeneous data its partition diversity reduces the compression error and improves the accuracy.

0.18

DualColl: Throughput-Optimal Bandwidth-Bound Collective Communications via Fractional Tree Packing

cs.DC cs.DScs.NI ·2026-10-11 ·Namir Ballan, Reuven Cohen
similarity 0.60
Abstract · 20 pages, 3 figures

Large-scale distributed training increasingly makes collective communication bandwidth-bound. In modern GPU clusters, communication libraries such as NCCL implement collectives including AllReduce over heterogeneous interconnects such as NVLink, InfiniBand, and Ethernet, making efficient use of available network bandwidth a central systems challenge. ForestColl showed that collective communication on such fabrics can be formulated using fractional tree packing; its scalable polynomial-time construction is developed for AllGather, with AllReduce obtained by composing AllGather and ReduceScatter. We present DualColl, which targets bandwidth-bound AllReduce directly. Under the tree-based AllReduce model, DualColl applies a Garg--Könemann-style multiplicative-weights algorithm and, for any $0<ε<1$, computes a feasible schedule whose throughput is at least $(1-ε)^2$ of the optimal AllReduce throughput. Its key component is an exact minimum-cost collective-tree oracle that projects physical-link dual prices onto a logical graph of participating ranks, reducing each iteration to shortest-path computations followed by a minimum spanning tree. We further extend the framework to local equal-next-hop packet-sprayed routing and to networks without explicit per-tree bandwidth control. For the latter, we introduce a tree-coupled max-min bandwidth-sharing model and show that tree duplication approximates an explicit fractional allocation with a provable accuracy-complexity tradeoff. Finally, we extend the fractional-packing framework to additional collective operations and multiple concurrent collective groups.

0.26

Cache-Aided Linear Function Computation

cs.IT ·2026-10-14 ·Xiaohong Cai, Ruze Zhang, Laigang Guo, Raymond W. Yeung
theory similarity 0.59
Abstract · 11 pages, 2 figures. A shorter version has been submitted to the 2027 IEEE Information Theory Workshop (ITW)

We study cache-aided linear computation in distributed systems where each source generates and stores its own data. An external receiver requests a linear combination of these data, and the sources use information cached before the request is known to reduce the communication needed to recover the requested result. In our model, each of the $N$ sources stores its own independent file over a finite field and has an additional cache of normalized size $M$. The receiver must recover any requested linear combination with zero error from the messages sent by the sources over separate noiseless links. We establish a lower bound on the worst-case communication rate over any finite field by analyzing several requests under the same cache placement. This bound determines the optimal rate when no additional cache is available. For binary files, we propose parity-aided placement (PAP), a coded-placement scheme that combines cached parities with uncoded symbols. For every $N\geq3$, we characterize its communication rate for each request and optimize its placement parameters to obtain a closed-form worst-case rate. The resulting achievable rate meets the lower bound for $0\leq M\leq1/(2N-1)$ and $M\geq(N-1)/N$, establishing the optimal memory--rate tradeoff in these two ranges.

0.22

Communication-Efficient Agnostic Federated Learning via Faster Convergence and Compression

cs.LG ·2026-09-29 ·Haomin Bai, Junyan Sun, Sifan Yang, Bo Xue, Lijun Zhang
similarity 0.58
Abstract · 30 pages, 3 figures

Agnostic federated learning (AFL) seeks a model that performs reliably across $m$ heterogeneous workers, but communication remains a bottleneck. We improve communication efficiency by reducing the number of synchronization rounds via faster convergence and the communication cost per round via compression. We first propose AFL-BR, which updates the dual weights over workers using online mirror ascent with KL divergence and blockwise restarts. It achieves an $O((\log m)^{1/4}T^{-1/8})$ stationarity rate after $T$ update rounds, reducing the $m$-dependence of the synchronization rounds required for convergence from polynomial to logarithmic order. Building on AFL-BR, we develop AFL-Com by applying bidirectional compression with error feedback (EF). Instead of compressing local gradients, workers apply EF to their dual-weighted gradients, enabling direct control of the aggregated compression error under time-varying weights. We then establish an $O((δ^{-1}+(\log m)^{1/4})T^{-1/8})$ stationarity rate for AFL-Com under general $δ$-approximate compressors and improve the $δ$-dependence from $δ^{-1}$ to $δ^{-1/2}$ for additive-and-idempotent compressors with shared randomness (SR). With suitable compression levels, AFL-Com retains the same convergence rate as AFL-BR at a lower per-round communication cost, yielding reductions in total communication complexity by factors of $(\log m)^{1/4}$ with Top-$k$ and $(\log m)^{1/2}$ with Rand-$k$ and SR. Experiments validate the improved synchronization and communication efficiency of our methods.

0.50

Echo: Error-Compensated 4-Bit Tensor-Parallel Communication for LLM Training and Inference

cs.AI cs.LG ·2026-10-09 ·Xingyu Xie, Xiaoyong Xie, Zhouchen Lin, Kim-Chuan Toh
theory similarity 0.58
Abstract

Tensor parallelism ends every layer with an all-reduce that sits between two dependent matrix multiplications, so its cost cannot be hidden and grows as compute outpaces interconnect bandwidth. Sending 4-bit instead of 16-bit values would cut this cost by nearly 4x, but the all-reduce must add the values it carries, and rounding the sum injects an error at every call. Model quality depends on how these errors accumulate over layers, yet existing methods treat each call on its own. We present Echo, a 4-bit all-reduce for training and inference that controls the accumulated error. Echo moves data in 4 bits and sums in high precision, so each value is quantized at most twice per call for any number of GPUs. The summation reveals each injected error, and Echo feeds it back into later calls, so old errors cancel instead of accumulating. We prove that the accumulated error stays bounded independently of depth. On A100 GPUs, Echo is 2.09x faster than the 16-bit NCCL all-reduce on 1 GB messages. It speeds up the time to first token by up to 1.16x and the training step by up to 1.09x on an idle interconnect, and by up to 1.44x and 1.38x as background traffic grows. It keeps the average accuracy over seven benchmarks within 0.4 points of 16-bit inference on Qwen3-8B. In 10B-token pretraining, its final loss is less than 0.9% above that of 16-bit training. Echo needs no FP8 or FP4 hardware.

0.25

Optimal-Access Cooperative MSR Codes: Parity-Check Matrix Construction And a Unified Transformation

cs.IT ·2026-09-06 ·Yaqian Zhang, Jingke Xu, Ya-Feng Liu
theory similarity 0.57
Abstract

Cooperative MSR codes are a kind of storage codes which enable optimal-bandwidth repair of any $h\geq2$ node erasures in a cooperative way, while retaining the minimum storage as an $[n,k]$ MDS code. Each code coordinate (node) is assumed to store an array of $\ell$ symbols, where $\ell$ is termed as sub-packetization. To address the disk IO (input/output) capability, a cooperative MSR code is said to have optimal-access property, if during node repair, the amount of data accessed at each helper node meets a lower bound on this quantity. In this paper, we focus on reducing the sub-packetization level of optimal-access cooperative MSR codes. We propose new constructions of optimal-access cooperative MSR codes through two methods. At first, we propose a direct explicit construction by designing its parity-check matrix. Such parity-check matrix is built by repeatedly employing two crucial parity-check matrices as building blocks. Secondly, we propose a generic transformation framework. Starting from an arbitrary $[n+d-k,d]$ MDS scalar code, one can derive a final cooperative MSR code by systematically applying two basic transformations. Both approaches yield $(n,k,\ell=δ^m)$ optimal-access cooperative MSR codes with $δ=d-k+h$ and $m=\binom{n}{h}-\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)$. Compared with the state of the art (with $\ell=δ^{\binom{n}{h}}$), the derived codes can reduce the sub-packetization $\ell$ by a fraction of $1/δ^{\lfloor\frac{n}δ\rfloor(\binomδ{h}-1)}$, where $δ=d-k+h$. Moreover, we also show that some previous code structures of optimal-access cooperative MSR codes and optimal-access MSR codes with $h=1$ are included as special cases of our transformation construction. At last, we note that all of the constructions are built over a finite field of linear size $\geq n+d-k$.

0.30