A reduction tree combines many values into a single result through successive layers of partial results. For example, a sum of eight values can combine pairs in parallel, then combine the four partial sums, and finally combine the remaining two. The tree takes log₂(N) stages for N values, rather than N sequential accumulation steps. section 4.3 section 4.0
On a GPU, the tree is also a communication plan. Lanes within a warp exchange values through register shuffles; warps within a block use shared memory and a barrier; separate program instances coordinate through global memory, usually across kernel launches. These boundaries ensure that partial results are available before they are combined. section 4.3 section 4.0
In Triton, the reduction scope determines the implementation:
- Use tl.sum, tl.max, or another reduction primitive to combine values within one program instance’s tile. The axis selects a tile dimension, not the entire tensor. section 4.3
- For a row processed in column blocks, maintain per-lane accumulators across blocks, then reduce them within the tile. Masked lanes need the operation’s neutral value: zero for a sum and negative infinity for a maximum. section 4.1.2
- For a grid-wide reduction, write one partial result per program instance to global memory, then reduce the partials in another launch. Alternatively, tl.atomic_add combines partials at a shared address, with contention and potentially variable accumulation order. section 4.3 section 4.1.1
Figure 4.3 Two-pass reduction dataflow. The first kernel reduces tiles independently, writing one partial sum per program instance to global memory. The second kernel reduces those partials to a single output value
The two-pass dataflow shows where tile-local partial sums cross the program-instance boundary. section 4.1.2
Unfused softmax
An unfused softmax computes a maximum and a sum using separate reduction trees. Each kernel reduces a tile to a partial value; host-side loops repeatedly launch kernels over smaller arrays of partials. Intermediate results travel through global memory, so repeated memory traffic and launches make fusion important for performance. section 4.2.2
Floating-point addition is not associative: changing the tree, tile shape, or number of warps can change rounding, so results may be numerically close without being bitwise identical. Accumulating fp16 or bf16 inputs in fp32 reduces rounding error. For softmax, subtracting the row maximum before exponentiation is another stability measure. section 4.1.1 section 4.3
print((0.1 + 1e20) - 1e20) # 0.0 print(0.1 + (1e20 - 1e20)) # 0.1
This small calculation shows how regrouping the same additions changes the result. section 4.1.1


