# Efficient AllReduce with Stragglers

arXiv: https://arxiv.org/abs/2505.23523 · HTML: https://mlsanity.com/paper/2505.23523/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 97 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 30 of 45)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Scaling Instruction-Finetuned Language Models](https://mlsanity.com/paper/2210.11416/) (2022)
- [Qwen2 Technical Report](https://mlsanity.com/paper/2407.10671/) (2024)
- [Phi-3 Technical Report: A Highly Capable Language Model Locally on Your Phone](https://mlsanity.com/paper/2404.14219/) (2024)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://mlsanity.com/paper/1910.02054/) (2019)
- [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://mlsanity.com/paper/2104.04473/) (2021)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Tutel: Adaptive Mixture-of-Experts at Scale](https://mlsanity.com/paper/2206.03382/) (2022)
- [Beyond Data and Model Parallelism for Deep Neural Networks](https://mlsanity.com/paper/1807.05358/) (2018)
- [MegaScale: Scaling Large Language Model Training to More Than 10,000 GPUs](https://mlsanity.com/paper/2402.15627/) (2024)
- [TorchTitan: One-stop PyTorch native solution for production ready LLM pre-training](https://mlsanity.com/paper/2410.06511/) (2024)
- [1-bit Adam: Communication Efficient Large-Scale Training with Adam's Convergence Speed](https://mlsanity.com/paper/2102.02888/) (2021)
- [ASTRA-sim2.0: Modeling Hierarchical Networks and Disaggregated Systems for Large-model Training at Scale](https://mlsanity.com/paper/2303.14006/) (2023)
- [Breaking the Computation and Communication Abstraction Barrier in Distributed Machine Learning Workloads](https://mlsanity.com/paper/2105.05720/) (2021)
- [TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches](https://mlsanity.com/paper/2111.04867/) (2021)
- [Blink: Fast and Generic Collectives for Distributed ML](https://mlsanity.com/paper/1910.04940/) (2019)
- [SparCML: High-Performance Sparse Communication for Machine Learning](https://mlsanity.com/paper/1802.08021/) (2018)
- [An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems](https://mlsanity.com/paper/2101.10761/) (2021)
- [Synthesizing Optimal Collective Algorithms](https://mlsanity.com/paper/2008.08708/) (2020)
- [TopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed Training Jobs](https://mlsanity.com/paper/2202.00433/) (2022)
- [Fine-tuning Language Models over Slow Networks using Activation Compression with Guarantees](https://mlsanity.com/paper/2206.01299/) (2022)
- [Straggler Mitigation in Distributed Optimization Through Data Encoding](https://mlsanity.com/paper/1711.04969/) (2017)
- [Near-Optimal Sparse Allreduce for Distributed Deep Learning](https://mlsanity.com/paper/2201.07598/) (2022)
- [Epidemic Learning: Boosting Decentralized Learning with Randomized Communication](https://mlsanity.com/paper/2310.01972/) (2023)
- [A Communication-Efficient Distributed Gradient Clipping Algorithm for Training Deep Neural Networks](https://mlsanity.com/paper/2205.05040/) (2022)
- [MGG: Accelerating Graph Neural Networks with Fine-grained intra-kernel Communication-Computation Pipelining on Multi-GPU Platforms](https://mlsanity.com/paper/2209.06800/) (2022)

## Built on by (most cited first, 1 of 1)

- [Don't Let a Few Network Failures Slow the Entire AllReduce](https://mlsanity.com/paper/2606.01680/) (2026)

## Abstract (arXiv)

Distributed machine learning workloads use data and tensor parallelism for training and inference, both of which rely on the AllReduce collective to synchronize gradients or activations. However, AllReduce algorithms are delayed by the slowest GPU to reach the synchronization barrier before the collective (i.e., the straggler). To address this challenge, we propose StragglAR: a parallel algorithm for AllReduce that accelerates distributed training and inference by exploiting natural variation in GPU execution times. StragglAR implements a ReduceScatter among the remaining GPUs during the straggler-induced delay, and then executes a novel collective algorithm to complete the AllReduce once the final GPU reaches the synchronization barrier. StragglAR achieves a 2x theoretical speedup over popular bandwidth-efficient algorithms for large GPU clusters, surpassing the lower bound for bandwidth-optimal synchronous AllReduce by leveraging the asymmetry in when GPUs reach the synchronization barrier. On an 8-GPU server, StragglAR provides a 25% speedup over state-of-the-art AllReduce algorithms.