{
  "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.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.23898",
  "author_total": 2,
  "authors": [
    {
      "name": "Sifat Munim"
    },
    {
      "name": "Aditya Ramamoorthy"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/dkqg4x8b6s8g6.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.23898",
  "fulltext_url": null,
  "id": "dkqg4x8b6s8g6",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.23898",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.IT"
    ],
    [
      "arxiv",
      "math.IT"
    ],
    [
      "openalex",
      "1708|Parallel Computing and Optimization Techniques"
    ]
  ],
  "openalex": "W7214057709",
  "pdf_url": "https://arxiv.org/pdf/2609.23898",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-26",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/dkqg4x8b6s8g6.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:25:17Z",
      "native_id": "2609.23898",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.23898"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.IT",
      "subfield": "general"
    }
  ],
  "title": "Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce",
  "title_text": "Communication-Efficient Distributed Training via Ring-Based Coded Approximate All-Reduce",
  "type": "preprint",
  "updated_at": "2026-10-30T12:25:17Z",
  "url": "https://research.draconitic.com/paper/dkqg4x8b6s8g6",
  "venue": "arXiv",
  "versions": []
}