Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read PAT algorithm gives all-gather and reduce-scatter logarithmic latency at any rank count.

desk verdict PAT is a plausible, clearly-motivated design for bounded-buffer all-gather and reduce-scatter, but its central claims are asserted rather than proven and need referee pressure for real validation. read the letter →

arxiv 2506.20252 v1 pith:BAH5ZRFO submitted 2025-06-25 cs.DC

Sylvain Jeaugey This is my paper · ORCID
classification cs.DC
keywords PATalgorithmall-gatherreduce-scattercollectivecommunicationNCCLbinomialtreelogarithmiclatencybuffermanagement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces PAT (Parallel Aggregated Trees), a new algorithm for all-gather and reduce-scatter collectives in the NCCL library. The claim is that PAT achieves a logarithmic number of network transfers for small operations on any number of ranks, avoids long-distance communication by reversing the order of dimensions, and requires only a logarithmic amount of intermediate buffering independent of total operation size. If true, PAT gives NCCL a practical alternative to the ring algorithm, whose linear latency becomes costly at scale and for small payloads. This matters because modern AI training at large scale frequently uses non-power-of-two rank counts where recursive doubling fails and Bruck's algorithm requires large user buffers.

What carries the argument

The central object is the parallel aggregated tree schedule, a set of shifted binomial trees whose aggregation depth is capped by the intermediate buffer size. The algorithm reverses the Bruck dimension order so far transfers happen first, then close transfers, which the paper says guarantees that every intermediate buffer is freed before it is needed again. This schedule yields a logarithmic number of steps when buffer size permits full aggregation, and a linear number of full-buffer transfers when it does not, bridging the latency of Bruck and the bandwidth of ring.

What would settle it

Simulate or run PAT with a small rank count and a buffer aggregation limit, for example 6 ranks with aggregation limit 2, and instrument buffer reuse; if any intermediate buffer is read after being overwritten, or the schedule deadlocks, the buffer bound is false. A cluster test with intentionally small intermediate buffers would expose the same failure.

Watch

Extended reading notes

Core claim

The central discovery is that the reversed-dimension Bruck algorithm can be modified to bound intermediate buffering by limiting aggregation to what fits in a fixed buffer and then completing each binomial tree through a linear schedule of full-size transfers. PAT organizes communication as parallel aggregated trees: the first steps are fully aggregated logarithmic steps, and once the aggregation limit is reached, the algorithm continues with a small number of parallel trees executing a linear number of steps. Because communication proceeds from far to near dimensions, intermediate buffers are emptied before they need to be reused, which the paper asserts keeps total buffer use logarithmic and independent of operation size. The paper claims this works for any number of ranks and applies symmetrically to reduce-scatter by reversing the tree.

Load-bearing premise

The far-to-near ordering guarantees that any intermediate buffer is emptied before it is needed again, so total buffer use stays bounded by the aggregation limit times a logarithmic factor, independent of operation size and rank count; if this scheduling property fails for some configuration, PAT could deadlock or require buffers that grow with scale.

Editorial extensions

If this is right

  • NCCL can run all-gather and reduce-scatter with logarithmic latency on arbitrary rank counts, removing the power-of-two constraint of recursive doubling.
  • For small message sizes, PAT should outperform ring at scale because its transfer count grows logarithmically rather than linearly.
  • The bounded buffer property means PAT can be used with fixed pre-registered intermediate buffers, avoiding expensive user-buffer registration.
  • The same schedule can implement reduce-scatter by reversing the binomial trees, so one algorithm covers both collective operations.
  • PAT's linear part uses full-size buffers, so bandwidth utilization stays high even when the algorithm falls back to a linear schedule.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The buffer-reuse property is stated but not proven; a formal proof or exhaustive schedule check for small rank counts would settle whether the logarithmic buffer bound always holds.
  • PAT's performance depends on the cost of the local linear part (packing, unpacking, and step computation); on NICs with very low latency and high message rate, the linear part may dominate before the logarithmic advantage shows.
  • The same parallel-aggregated-tree idea could be extended to other collectives such as all-to-all or broadcast, where bounded buffering and arbitrary rank counts are also desirable.
  • A testable implication is that on a large cluster with tapered fabric, PAT's far-first ordering should show less congestion than Bruck's last-hop long-distance transfers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes PAT (Parallel Aggregated Trees), a new algorithm for all-gather and reduce-scatter operations intended for the NCCL collective-communication library. The algorithm starts from a reversed-dimension Bruck all-gather schedule and inserts a limit on aggregation, so that once the amount of data aggregated for a remote rank would exceed the available intermediate buffer, the algorithm switches to a linear schedule within a bounded number of parallel trees. The abstract claims that PAT works on any number of ranks, has logarithmic transfer count for small sizes, minimizes long-distance communication, and uses a logarithmic amount of internal buffers independent of the total operation size. The paper describes all-gather, claims a mirror-image reduce-scatter variant, illustrates the tree shapes for 8 and 16 ranks, and discusses performance only qualitatively. No measurements, no pseudocode, and no formal proof of the central buffer-reuse property are provided.

Significance. If the claimed properties hold, PAT would be a practically relevant alternative to ring-based all-gather and reduce-scatter in NCCL, especially for small payloads and large rank counts. The paper correctly identifies real weaknesses of Bruck and recursive doubling: their late steps send large amounts of data across long fabric distances, and recursive doubling requires powers of two. The idea of reversing dimension order and capping aggregation to fit intermediate buffers is plausible and worth reporting. However, the manuscript currently provides no proof of the scheduling invariant that underlies the bounded-buffer claim, no general specification for arbitrary rank counts, and no empirical evidence. The paper's value is therefore conditional on a rigorous invariant argument and, for a systems venue, at least microbenchmark evidence.

major comments (3)
  1. [The PAT algorithm (paragraph beginning "When the size per rank is larger than the buffer size...")] The central buffer-reuse claim is asserted rather than proved. The sentence "This has a fundamental property which guarantees that we will always be able to use intermediate buffers as we will have emptied them before we need to communicate on that same dimension" is the only support for the abstract's claim of a logarithmic number of internal buffers. For arbitrary rank counts, especially non-powers of two, and for aggregation caps that are not powers of two, the truncated binomial trees and split steps can change the order in which chunks arrive and must be forwarded; no invariant maps each buffer slot to the chunk occupying it at each step. Please provide a formal invariant and proof for all N and all buffer caps, or give a concrete counterexample if the property fails.
  2. [Performance] The Performance section contains no measurements, no simulation, and no analytical latency model. The statement that "there is always a scale at which the linear part will become predominant" and the claim that the performance factor depends on "how much faster the linear part is" are qualitative. Since the abstract motivates PAT by improving NCCL performance, the practical benefit is not established. Add benchmark comparisons against ring and Bruck on at least a few representative rank counts and message sizes, or explicitly state that the paper reports an algorithmic design and that evaluation is future work.
  3. [The PAT algorithm (general description, Figures 5-10)] The algorithm is specified only through prose and illustrative examples for N=8 and N=16, both powers of two. The only non-power-of-two example in the paper, Figure 4, illustrates plain Bruck, not PAT with a buffer cap. Therefore the claim that PAT "works on any number of ranks" is not demonstrated, and the text does not give enough detail for an independent implementation. Please provide pseudocode or a precise step schedule specifying, for arbitrary N and buffer size, the send/receive pairs and the chunk indices exchanged at each step.
minor comments (4)
  1. [The PAT algorithm] There is a typo in the first sentence of this section: "developped" should be "developed". Also, "allgather" appears without a hyphen in one place; use "all-gather" consistently.
  2. [Performance] The phrase "In nature, the algorithm is also linear on two fronts" is unclear; it likely means "In essence" or "By construction". Please rephrase.
  3. [Figures] The figures are referenced only as "the example below" or "the next 3 figures" without formal captions, and the red/blue distinction in Figure 5 is described only in the text. Add numbered captions and cite all figures explicitly in the text.
  4. [Notation] The paper uses N, "buffer size", "aggregation limit", and "chunk" without formal definitions. Define these quantities and state how the aggregation limit is derived from the buffer size; this would also make the proof obligation in the major comments precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: PAT is a qualitative algorithm design with no fitted parameters, no equations, and no self-citations used as evidence; the central claims rest on an asserted scheduling property, which is an evidence gap rather than a circular reduction.

full rationale

PAT is a design/algorithm paper rather than a quantitative derivation, so there are no equations to identify as equal by construction and no fitted parameters renamed as predictions. The claims—logarithmic transfer count for small operations, far-to-near ordering, and O(log) buffer bound—are argued from the described schedule of the Bruck-derived tree. The only self-reference is to the author's NCCL library ([1]) as the intended implementation target, not as evidence for the algorithm's properties, so self-citation is not load-bearing. The paper does contain an evidentiary gap: the 'fundamental property' in the paragraph beginning 'When the size per rank is larger than the buffer size...' is asserted without proof or pseudocode, and the Future work section concedes 'the algorithm is implemented in NCCL 2.23 for 1 rank per node, as only the inter-node part is implemented' and 'the complexity of the current algorithm is currently high.' These are support and verification deficits, not circular reductions: the buffer bound is not assumed as an input to derive itself, and no quantity is fitted to data and then re-predicted. The stated limitations are explicitly weighed here, but they do not make any step of the argument self-definitional, fitted-as-predicted, or dependent on a self-citation chain. Therefore the honest finding is no significant circularity, score 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The algorithm introduces no new physical entities and fits no data. Its central claims rest on an unproven buffer-reuse property and on standard background from the Bruck algorithm. The buffer size (aggregation limit) is a hand-chosen parameter that directly controls complexity.

free parameters (1)
  • Aggregation limit (number of sub-trees)
    The PAT algorithm caps how many data chunks are aggregated in a step based on the available intermediate buffer size. This is a user/implementation-chosen parameter, not fitted to data, but it directly sets the trade-off between logarithmic and linear steps and the amount of intermediate buffering required.
assumptions (4)
  • standard math Bruck's shifted binomial-tree decomposition is a correct all-gather scheme for any number of ranks
    The paper builds directly on Bruck's algorithm [2] and its truncated-tree variant for non-powers of two, citing it without proving correctness.
  • domain assumption Long-distance network transfers on large fabrics are disproportionately slower than short ones due to static routing and tapered bandwidth
    The motivation for reversing dimensions rests on this; stated in the introduction and the PAT section, but never quantified.
  • domain assumption MPI semantics forbid libraries from overwriting the user's send buffer, so reduce-scatter requires intermediate buffers
    Used to justify why Bruck and recursive doubling cannot be used for reduce-scatter; cited as a standard MPI constraint.
  • ad hoc to paper The far-to-near schedule leaves intermediate buffers empty before reuse
    This is the core unproven claim on which the buffer bound rests; the paper calls it a 'fundamental property' but offers no proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of PAT: a new algorithm for all-gather and reduce-scatter operations at scale." pith.science (2026). https://pith.science/paper/BAH5ZRFO

@misc{pith2026250620252,
  author       = {Pith},
  title        = {Pith review of: PAT: a new algorithm for all-gather and reduce-scatter operations at scale},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BAH5ZRFO}},
  note         = {Machine review of arXiv:2506.20252}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2506.20252 by the authors.

Figure 1
Figure 1. Bruck algorithm If we now consider separately the data from each rank, and look at how that data gets broadcast, we can confirm that it follows a binomial tree. In the global algorithm, steps from different binomial trees get aggregated together to end up with a logarithmic total number of steps [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Bruck algorithm, broadcasting each rank’s data through a binomial [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Bruck algorithm, with farthest dimension first [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: Bruck algorithm, with nearest dimension first on a non-power-of-two [PITH_FULL_IMAGE:figures/full_fig_p004_4.png]
Figure 5
Figure 5. Figure 5: PAT algorithm with 8 ranks, limiting aggregation to 2 [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: PAT tree, limiting aggregation to 2 As the size of the operation increases, we will reduce the size of the logarithmic part and increase the size of the linear part. This should not be a problem for performance, given every transfer in the linear part is performed with…
Figure 7
Figure 7. Figure 7: PAT tree with 16 ranks and 8 trees, equivalent to dimension-reversed [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]
Figure 8
Figure 8. Figure 8: PAT tree with 16 ranks and 4 trees 7 [PITH_FULL_IMAGE:figures/full_fig_p007_8.png]
Figure 9
Figure 9. Figure 9: PAT tree with 16 ranks and 2 trees When the size per rank is larger than the buffer size, then we end up with a single tree which has a linear number of steps. The algorithm starts by sending data far, then progressively getting closer to the root. This has a fundament…
Figure 10
Figure 10. Figure 10: PAT Tree with 8 ranks, fully linear Conversion to reduce-scatter operations The algorithm was originally developed for reduce-scatter, as buffer constraints are higher, with the idea that an algorithm which works for reduce-scatter should also work for all-gather. The…
Figure 11
Figure 11. Figure 11: PAT Tree for reduce-scatter For reduce-scatter, we communicate with close dimensions first, then far, and we also reverse the tree. Each time we receive data, we also reduce it with the current accumulation buffer which will eventually be sent to a higher dimension, e…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Adaptive Space-efficient Collectives for Dynamic and Unstructured Sparsity on GPU Platforms

    cs.DC 2026-07 accept novelty 6.5 of 10

    Pici-backed adaptive sparse collectives on GPUs deliver up to 5.25×/2.5×/2.66× speedups over dense NCCL for all-gather/reduce-scatter/all-reduce at 99% sparsity.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · cited by 1 Pith paper

  1. [1]

    NVIDIA collective communication library

    “NVIDIA collective communication library.” https://github.com/NVIDIA/ nccl

    work page

  2. [2]

    Efficient algorithms for all-to-all communications in multi-port message-passing systems,

    J. Bruck, C.-T. Ho, S. Kipnis, and D. Weathersby, “Efficient algorithms for all-to-all communications in multi-port message-passing systems,” inProceedings of the sixth annual acm symposium on parallel algorithms and architectures, 1994, pp. 298–309

    work page 1994

  3. [3]

    Optimization of collective com- munication operations in mpich,

    R. Thakur, R. Rabenseifner, and W. Gropp, “Optimization of collective com- munication operations in mpich,”The International Journal of High Performance Computing Applications, vol. 19, no. 1, pp. 49–66, 2005. 11

    work page 2005

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.