# PAT: a new algorithm for all-gather and reduce-scatter operations at scale

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2025.

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

- [Collective Communication for 100k+ GPUs](https://mlsanity.com/paper/2510.20171/) (2025)
- [ScaleAcross Explorer: Exploring Communication Optimization for Scale-Across AI Model Training](https://mlsanity.com/paper/2605.24326/) (2026)

## Abstract (arXiv)

This paper describes a new algorithm called PAT, for Parallel Aggregated Trees, and which can be used to implement all-gather and reduce-scatter operations. This algorithm works on any number of ranks, has a logarithmic number of network transfers for small size operations, minimizes long-distance communication, and requires a logarithmic amount of internal buffers, independently from the total operation size. It is aimed at improving the performance of the NCCL library in cases where the ring algorithm would be inefficient, as its linear latency would show poor performance for small sizes and/or at scale.