# Near-Optimal Sparse Allreduce for Distributed Deep Learning

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 57 references that are in the map.
- First posted on arXiv 19 Jan 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour](https://mlsanity.com/paper/1706.02677/) (2017)
- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [Large Batch Optimization for Deep Learning: Training BERT in 76 minutes](https://mlsanity.com/paper/1904.00962/) (2019)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Horovod: fast and easy distributed deep learning in TensorFlow](https://mlsanity.com/paper/1802.05799/) (2018)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Memory-Efficient Pipeline-Parallel DNN Training](https://mlsanity.com/paper/2006.09503/) (2020)
- [DAPPLE: A Pipelined Data Parallel Approach for Training Large Models](https://mlsanity.com/paper/2007.01045/) (2020)
- [Adaptive Gradient Sparsification for Efficient Federated Learning: An Online Learning Approach](https://mlsanity.com/paper/2001.04756/) (2020)
- [Chimera: Efficiently Training Large-Scale Neural Networks with Bidirectional Pipelines](https://mlsanity.com/paper/2107.06925/) (2021)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [Understanding Top-k Sparsification in Distributed Deep Learning](https://mlsanity.com/paper/1911.08772/) (2019)
- [A Distributed Synchronous SGD Algorithm with Global Top-k Sparsification for Low Bandwidth Networks](https://mlsanity.com/paper/1901.04359/) (2019)
- [Asynchronous Decentralized SGD with Quantized and Local Updates](https://mlsanity.com/paper/1910.12308/) (2019)
- [SparCML: High-Performance Sparse Communication for Machine Learning](https://mlsanity.com/paper/1802.08021/) (2018)
- [Large-Batch Training for LSTM and Beyond](https://mlsanity.com/paper/1901.08256/) (2019)
- [An In-Depth Analysis of the Slingshot Interconnect](https://mlsanity.com/paper/2008.08886/) (2020)
- [Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations](https://mlsanity.com/paper/1908.04207/) (2019)
- [Breaking (Global) Barriers in Parallel Stochastic Optimization with Wait-Avoiding Group Averaging](https://mlsanity.com/paper/2005.00124/) (2020)
- [Building Efficient ConvNets using Redundant Feature Pruning](https://mlsanity.com/paper/1802.07653/) (2018)

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

- [VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projections](https://mlsanity.com/paper/2405.17991/) (2024)
- [CO2: Efficient Distributed Training with Full Communication-Computation Overlap](https://mlsanity.com/paper/2401.16265/) (2024)
- [Optimus-CC: Efficient Large NLP Model Training with 3D Parallelism Aware Communication Compression](https://mlsanity.com/paper/2301.09830/) (2023)
- [Overcoming the Communication-Performance Tradeoff in LLM Pretraining](https://mlsanity.com/paper/2508.15706/) (2025)
- [Communication-Efficient Large-Scale Distributed Deep Learning: A Comprehensive Survey](https://mlsanity.com/paper/2404.06114/) (2024)
- [HammingMesh: A Network Topology for Large-Scale Deep Learning](https://mlsanity.com/paper/2209.01346/) (2022)
- [Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities](https://mlsanity.com/paper/2302.07615/) (2023)
- [A2CiD2: Accelerating Asynchronous Communication in Decentralized Deep Learning](https://mlsanity.com/paper/2306.08289/) (2023)
- [Evaluation and Optimization of Gradient Compression for Distributed Deep Learning](https://mlsanity.com/paper/2306.08881/) (2023)
- [Accelerating Distributed Deep Learning using Lossless Homomorphic Compression](https://mlsanity.com/paper/2402.07529/) (2024)
- [Sparse-SignSGD with Majority Vote for Communication-Efficient Distributed Learning](https://mlsanity.com/paper/2302.07475/) (2023)
- [SignSGD with Federated Voting](https://mlsanity.com/paper/2403.16372/) (2024)
- [TACO: Efficient Communication Compression of Intermediate Tensors for Scalable Tensor-Parallel LLM Training](https://mlsanity.com/paper/2604.24088/) (2026)
- [STen: Productive and Efficient Sparsity in PyTorch](https://mlsanity.com/paper/2304.07613/) (2023)
- [SignSGD with Federated Defense: Harnessing Adversarial Attacks through Gradient Sign Decoding](https://mlsanity.com/paper/2402.01340/) (2024)
- [Efficient AllReduce with Stragglers](https://mlsanity.com/paper/2505.23523/) (2025)
- [SparDL: Distributed Deep Learning Training with Efficient Sparse Communication](https://mlsanity.com/paper/2304.00737/) (2023)
- [Quantize Once, Train Fast: Allreduce-Compatible Compression with Provable Guarantees](https://mlsanity.com/paper/2305.18627/) (2023)
- [MiCRO: Near-Zero Cost Gradient Sparsification for Scaling and Accelerating Distributed DNN Training](https://mlsanity.com/paper/2310.00967/) (2023)
- [Preserving Near-Optimal Gradient Sparsification Cost for Scalable Distributed Deep Learning](https://mlsanity.com/paper/2402.13781/) (2024)
- [In-Network Collective Operations: Game Changer or Challenge for AI Workloads?](https://mlsanity.com/paper/2601.19132/) (2026)
- [SCAPE: Accurate and Efficient LLM Training with Extreme Sparse Communication](https://mlsanity.com/paper/2607.01678/) (2026)
- [Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection](https://mlsanity.com/paper/2608.12573/) (2026)

## Abstract (arXiv)

Communication overhead is one of the major obstacles to train large deep learning models at scale. Gradient sparsification is a promising technique to reduce the communication volume. However, it is very challenging to obtain real performance improvement because of (1) the difficulty of achieving an scalable and efficient sparse allreduce algorithm and (2) the sparsification overhead. This paper proposes Ok-Topk, a scheme for distributed training with sparse gradients. Ok-Topk integrates a novel sparse allreduce algorithm (less than 6k communication volume which is asymptotically optimal) with the decentralized parallel Stochastic Gradient Descent (SGD) optimizer, and its convergence is proved. To reduce the sparsification overhead, Ok-Topk efficiently selects the top-k gradient values according to an estimated threshold. Evaluations are conducted on the Piz Daint supercomputer with neural network models from different deep learning domains. Empirical results show that Ok-Topk achieves similar model accuracy to dense allreduce. Compared with the optimized dense and the state-of-the-art sparse allreduces, Ok-Topk is more scalable and significantly improves training throughput (e.g., 3.29x-12.95x improvement for BERT on 256 GPUs).