Yomitoki · PDF · Code · arXiv

Online normalizer calculation for softmax

Maxim Milakov, Natalia Gimelshein (NVIDIA)

arXiv preprint (April 2018) · 2018 ⭐⭐ Approachable: Undergraduate math + a comfort with GPU memory hierarchy 📖 ≈ 12 min

softmaxgpu-kernelscudamemory-bandwidthflash-attention-precursor

Prerequisites · brush up before reading

Safe softmax (numerical-stability trick)

Subtract the max from every logit before exponentiating to avoid overflow. Every DL framework's softmax does this. And it forces a separate pass over the input just to find the max, which is what this paper attacks.

GPU memory hierarchy & memory-bandwidth-bound kernels

Softmax is bandwidth-bound: arithmetic intensity is so low that performance is set by how many bytes you pull from DRAM, not by FLOPs. Cutting passes from 3 to 1 directly cuts wall-clock time.

Parallel reduction with an associative operator

If you have an associative binary operator ⊕, you can reduce an N-element array in log₂N tree levels in parallel. This paper's contribution is showing that the (max, normalizer) update is ⊕-shaped. So the whole thing parallelizes for free.

Welford's online variance algorithm

1962 algorithm that computes mean and variance in a single pass by maintaining running statistics that get updated as each new sample arrives. The paper explicitly names this as the inspiration for the online normalizer trick.

Kernel fusion (softmax + TopK)

Combining two kernels into one so intermediate values never round-trip to DRAM. The paper's second contribution is showing the online normalizer recurrence makes softmax+TopK fuseable, which alone saves 2.5× memory traffic on top of the 1.3× from going single-pass.

FlashAttention (downstream consumer)

Not a prerequisite for understanding the paper, but the paper's online normalizer recurrence is the algorithmic foundation FlashAttention (Dao et al., 2022) builds on to tile attention over Q-blocks without materializing the full softmax matrix. Worth knowing where this lands.

TL;DR

Mainstream frameworks compute Softmax with a 3-pass 'safe' version (find max, sum exp, normalize). 4 memory ops per element. This paper gives a single-pass recurrence that maintains max and normalizer together, dropping accesses to 3 (1.33×) at the cost of 2 extra flops per element. Because Softmax is bandwidth-bound, fewer accesses translate almost directly to speedup. Fused with TopK the saving compounds to 5×. The recurrence. maintain (max, normalizer) and correct on the fly. Later became the algorithmic kernel of FlashAttention.

Paper Overview

Problem

Softmax is everywhere. Output layer of every classifier, normalizer of every attention head. And it is bandwidth-bound on every GPU it runs on. The 'safe' formulation that every framework uses for numerical stability requires three sequential passes over the input vector: max, sum-of-exp, and divide. Each pass loads (and one of them stores) the full vector, so for a vocabulary of V floats the kernel moves ≈ 4V bytes through DRAM, almost all of it avoidable.

Background

Softmax turns a set of logits into a probability distribution. Language modeling, machine translation, and ASR all run softmax over a vocabulary of tens to hundreds of thousands at every step. That step is not cheap.

A decade of speedup work targets a different problem: Differentiated Softmax and SVD-Softmax replace the projection matmul; Hierarchical Softmax splits one big softmax into many small ones; Importance Sampling / NCE / Blackout sample a subset at training time; Self-Normalized Softmax modifies the loss to push the normalizer toward 1. The authors point out that with the exception of NCE (training only) and Self-Normalized Softmax (inference only), every method still runs the original safe softmax in the end. But nobody had optimized that.

The key performance lens: softmax has very low flops/byte (every loaded float gets only a couple of FP ops). On modern hardware that means bandwidth-bound. Fewer reads ≈ faster. The paper's whole bet is to not reduce computation, reduce memory accesses. Inspiration comes from Welford's 1962 online variance algorithm: maintain running statistics that absorb each new sample, with a small corrective term when the running aggregate moves.

Solution

Maintain the running maximum and the running normalizer together in one sweep. Whenever a new element pushes the maximum up, multiply the partial normalizer by e^(old_max − new_max). That correction is the entire trick. The fused (max, normalizer) update is an associative + commutative binary operator on ℝ², which makes it drop straight into a parallel reduction primitive (CUB's BlockReduce in the reference implementation). The same recurrence also lets the TopK pass be folded into the softmax kernel, eliminating an extra full-vector traversal.

Main Contributions

  • The online normalizer recurrence (Algorithm 3). Computes the safe softmax denominator in one pass instead of two, reducing memory accesses from 4 to 3 per element.
  • Associativity + commutativity proof of the (m, d) update operator (Eq. 4), making the algorithm a drop-in for any parallel reduction primitive.
  • Softmax + TopK fusion (Algorithm 4). The running (m, d, top-K) tuple still composes under the same reduction operator, collapsing two kernels into one. Memory accesses drop from 5 to 1.
  • Open-source CUDA implementation at github.com/NVIDIA/online-softmax (CUB-based, V100-targeted).
  • Measured speedups on Tesla V100: ~1.3× for softmax alone (V ≥ 4000), 1.5–5× for fused softmax+TopK depending on V and batch size.
  • Algorithmic foundation later picked up by FlashAttention (2022) to tile attention over query blocks without materializing the full softmax.

Tech Timeline

1962
Welford: Online variance
The general 'maintain running statistics + one corrective term per step' pattern
2014
Sutskever et al.. Seq2Seq with softmax over vocab
Cements softmax-over-large-vocab as the bottleneck workload
2015
Hierarchical / Differentiated / Adaptive softmax
Decade of papers attacking the projection layer, not softmax itself
2018
Online Softmax (this paper)
Single-pass safe softmax; associative reduction; TopK fusion
2022
FlashAttention (Dao et al.)
Builds on this recurrence to tile attention over Q-blocks without materializing the full softmax matrix
2023
FlashAttention-2 / FlashDecoding / cuDNN attention
All inherit the same (m, d) update; the algorithmic core is unchanged

This work is highlighted; earlier nodes are prerequisites, later nodes are downstream consumers / follow-ups.

Where this matters

Softmax runs in the inner loop of every modern decoder LLM, in three places per generated token. Each place has a different size and a different optimization story. And the same recurrence wins in all three:

WorkloadScaleImpact
Attention softmax (over keys)32 layers × 32 heads × N tokens = ~8.4M softmaxes per forward pass at N=8K context; the (N, N) score matrix is the killer (~137 GB intermediate at fp16 for a 7B model)FlashAttention (Dao et al., 2022) tiles the attention into B_r × B_c blocks and uses this paper's online recurrence to merge partial (m, d) per tile. The full N×N matrix never materializes in HBM
Vocab softmax (LM head)Vocabulary V = 32K (Llama-2) to 256K (Gemma); one softmax per output position, every output token of every requestThe 2018 paper's original target. Online softmax cuts a 4-mem-op kernel to 3 (1.3× speedup). Fused with TopK for beam search: 5× total speedup
MoE router (over experts)E = 8 (Mixtral) to 256 (DeepSeek-V3); one router softmax per MoE layer per tokenSmall in absolute terms, but it's a softmax-then-TopK pattern. The exact case Algorithm 4 fuses. Saves a kernel launch per MoE layer per token

Core Method

1: Naive softmax. 2 passes, the textbook version

Pass 1 sums the exponentials. Pass 2 divides each x_i by the sum. 3 memory accesses per element: load (for the sum), load (for the divide), store (for the output).

\[ \text{Naive: } \quad y_i = \frac{e^{x_i}}{\sum_{j=1}^{V} e^{x_j}} \]

Pseudocode (Algorithm 1 in the paper):

d = 0
for j = 1..V:                       # pass 1: sum exponentials
    d = d + exp(x_j)
for i = 1..V:                       # pass 2: write outputs
    y_i = exp(x_i) / d

Why nobody ships this: exp(x_j) overflows for x_j around 88 in fp32 (because e^88 ≈ FLT_MAX) and underflows to zero for x_j around −88. Real logits routinely sit in that range. The naive version is fast but unsafe. Exactly one inferred 'inf' poisons the entire normalizer.

2: Safe softmax. 3 passes, what every framework runs

Subtract the running max from every logit before exponentiating. The output is mathematically identical to naive softmax, but every exponent is now ≤ 0, so e^(·) is in [0, 1] and can't overflow.

\[ \text{Safe: } \quad y_i = \frac{e^{x_i - m_V}}{\sum_{j=1}^{V} e^{x_j - m_V}}, \qquad m_V = \max_{k=1..V} x_k \]

The catch: you can't compute the denominator without first knowing m_V. So you sweep three times. Algorithm 2 in pseudocode:

m_0 = -inf
for k = 1..V:                       # pass 1: find max
    m_k = max(m_{k-1}, x_k)
d_0 = 0
for j = 1..V:                       # pass 2: build denominator (needs the global max)
    d_j = d_{j-1} + exp(x_j - m_V)
for i = 1..V:                       # pass 3: write outputs
    y_i = exp(x_i - m_V) / d_V

4 memory accesses per element (3 load + 1 store). Every DL framework (TensorFlow ≥ 1.7, PyTorch ≥ 0.4, MXNet, CNTK, Chainer) ships this version. This is the baseline the paper attacks.

Side-by-side: how the memory-access budget shrinks across the three variants the paper introduces.

flowchart TB
  subgraph A ["Safe Softmax (baseline) — 4 mem ops/elem"]
    direction LR
    A1["Pass 1
find max m_V"] --> A2["Pass 2
sum exp(x − m_V)"] --> A3["Pass 3
write y_i"] end subgraph B ["Online Softmax (this paper) — 3 mem ops/elem"] direction LR B1["Pass 1
update (m, d) jointly"] --> B2["Pass 2
write y_i"] end subgraph C ["Online + TopK fused — 1 mem op/elem"] direction LR C1["Single pass
update (m, d, u, p)
write only K outputs"] end A --> B --> C

3: Online softmax. 2 passes, the contribution

Maintain the running pair (m_j, d_j) jointly. When a new element arrives, update both at once:

\[ m_j = \max(m_{j-1},\, x_j), \qquad d_j = d_{j-1} \cdot e^{m_{j-1} - m_j} + e^{x_j - m_j} \]

Pseudocode (Algorithm 3 in the paper):

m_0 = -inf
d_0 = 0
for j = 1..V:                                   # single pass: max + denominator together
    m_j = max(m_{j-1}, x_j)
    d_j = d_{j-1} * exp(m_{j-1} - m_j) + exp(x_j - m_j)
for i = 1..V:                                   # output pass (unchanged)
    y_i = exp(x_i - m_V) / d_V

Why is the rescaling exact? The previous denominator d_{j-1} was ∑_{k<j} e^(x_k − m_{j-1}). If a new max appears (m_j > m_{j-1}), every term in that sum needs the same factor e^(m_{j-1} − m_j) to become e^(x_k − m_j). One multiply on d_{j-1} corrects them all at once. No per-term rewrite. Add e^(x_j − m_j) for the new element, and d_j is exactly what safe softmax would compute (induction on j, Theorem 1).

Why doesn't this slow things down? Two extra FP ops per element (one multiply, one exp on the rescaling). But softmax is bandwidth-bound, so those flops slot into time the kernel was already spending waiting for the DRAM load. The wall-clock speedup tracks the memory-access ratio: 4 ops/elem → 3 ops/elem = 1.33×.

Runnable Python with verification:

import numpy as np

def online_softmax(x):
    m, d = -np.inf, 0.0
    for xj in x:                                 # pass 1: maintain (m, d) together
        m_new = max(m, xj)
        d = d * np.exp(m - m_new) + np.exp(xj - m_new)   # rescale + accumulate
        m = m_new
    return np.exp(x - m) / d                     # pass 2: write outputs

def safe_softmax(x):
    m = x.max(); e = np.exp(x - m); return e / e.sum()

x = np.random.randn(10000).astype(np.float32) * 50   # blow up the range to provoke overflow
assert np.allclose(online_softmax(x), safe_softmax(x), atol=1e-6)

The proof also shows 1 ≤ d_j ≤ j for all j, so fp32 stays in range for any plausible V. Fp32 storage works up to V ≈ 1.7×10³⁷ elements.

4: Parallel version. The (m, d) update as an associative reduction

The single-thread loop is fine for tiny vectors, but a GPU thread block has hundreds of threads sitting idle while one of them iterates. The fix: lift the update to a binary operator on partial pairs.

\[ \begin{bmatrix} m_i \\ d_i \end{bmatrix} \oplus \begin{bmatrix} m_j \\ d_j \end{bmatrix} = \begin{bmatrix} \max(m_i, m_j) \\ d_i \cdot e^{m_i - \max(m_i, m_j)} + d_j \cdot e^{m_j - \max(m_i, m_j)} \end{bmatrix} \]

⊕ is both associative (so a tree-reduce works) and commutative (so threads can merge in any order. Useful for warp-shuffle reductions where the ordering depends on lane indexing). The reference implementation uses CUB's BlockReduce primitive with this operator as a tight C++ device function. Each thread sweeps a strided chunk of the input, accumulating a thread-local (m, d), then the block-reduce combines them in log₂(threads_per_block) levels.

Python sketch of the parallel pattern:

from functools import reduce

def merge(a, b):
    """The ⊕ operator: merge two partial (m, d) pairs."""
    (m_a, d_a), (m_b, d_b) = a, b
    m = max(m_a, m_b)
    d = d_a * np.exp(m_a - m) + d_b * np.exp(m_b - m)
    return (m, d)

def online_normalizer_parallel(x, nchunks=8):
    """Split into chunks → each chunk independent → tree-reduce.
    Result is order-invariant thanks to associativity + commutativity."""
    chunks = np.array_split(x, nchunks)
    partials = [(c.max(), np.exp(c - c.max()).sum()) for c in chunks]
    return reduce(merge, partials)               # any merge order → same result

A picture of the reduction tree on 8 elements:

flowchart TB
  x1["(x_1, 1)"] --> p12["⊕"]
  x2["(x_2, 1)"] --> p12
  x3["(x_3, 1)"] --> p34["⊕"]
  x4["(x_4, 1)"] --> p34
  x5["(x_5, 1)"] --> p56["⊕"]
  x6["(x_6, 1)"] --> p56
  x7["(x_7, 1)"] --> p78["⊕"]
  x8["(x_8, 1)"] --> p78
  p12 --> p1234["⊕"]
  p34 --> p1234
  p56 --> p5678["⊕"]
  p78 --> p5678
  p1234 --> root["⊕
= (m_V, d_V)"] p5678 --> root

This is the property FlashAttention (2022) inherits: tile the attention's Q × K^T into blocks, run online softmax per block to get partial (m, d), then merge across blocks with the same ⊕. The online normalizer paper is essentially the algorithmic kernel of FlashAttention.

5: Softmax + TopK fusion. 1 memory op per element

Auto-regressive decoding does logits → softmax → top-K on every step. Run separately, that's 4 memory ops/element for online softmax, plus another load/store pair for TopK ≈ 5 memory ops/element total.

Fusion plan: augment the running state from (m, d) to (m, d, u, p), where u holds the K largest values seen so far and p their indices. Each new element x_j: update m and d as before, then insertion-sort x_j into u (cost: O(K) per element. Fine for the small K that TopK actually uses).

Pseudocode (Algorithm 4 in the paper):

m_0 = -inf; d_0 = 0
u = [-inf] * (K+1);  p = [-1] * (K+1)
for j = 1..V:
    m_j = max(m_{j-1}, x_j)
    d_j = d_{j-1} * exp(m_{j-1} - m_j) + exp(x_j - m_j)   # online normalizer
    u[K+1] = x_j; p[K+1] = j                              # land new value at end
    k = K                                                  # single-pass insertion sort
    while k >= 1 and u[k] < u[k+1]:
        swap(u[k], u[k+1]); swap(p[k], p[k+1]); k -= 1
for i = 1..K:                                              # write K outputs only
    v_i = exp(u[i] - m_V) / d_V; z_i = p[i]
VariantMemory ops / elementV100 speedup vs Safe+TopK separate
Safe Softmax + TopK, separate51.0× (baseline)
Safe Softmax + TopK, fused2~2.5×
Online Softmax + TopK, fused15× at V = 25,000, K = 5

The 5× total decomposes cleanly: 2.5× from fusion (eliminating the round-trip between two kernels) and 2× from single-pass online softmax. The gain shrinks as K grows. At K = 30 the insertion-sort dominates and the speedup falls to 1.4×. The technique is best suited to beam-search-style decoding where K is small (5–10).

6: Implementation notes. CUDA + CUB

The reference kernel (in the open-source NVIDIA/online-softmax repo) is ~40 lines of CUDA. Key choices:

  • Struct layout: struct __align__(8) MD { float m; float d; }. 8-byte aligned so the GPU coalesces (m, d) loads into one transaction.
  • Reduction primitive: cub::BlockReduce<MD, THREADBLOCK_SIZE> with the (m, d) ⊕ operator passed as a __device__ __forceinline__ function.
  • Thread-local accumulation: each thread strides through the input with stride = THREADBLOCK_SIZE, accumulating its own partial (m, d). After the loop, the block-reduce merges all partials in log₂(threads) levels.
  • Output pass: once thread 0 holds (m_V, d_V) in shared memory, every thread reads (x_i, m_V, d_V) and writes y_i = e^(x_i − m_V) · (1 / d_V) using the precomputed reciprocal __fdividef for speed.
  • Hardware: benchmarks on Tesla V100, fp32, CUDA 9.1, CUB 1.8.

The whole machinery. Single-pass kernel, reduction operator, fused TopK. Fits in under 500 lines of CUDA. The 'algorithm' is essentially one C++ struct plus one device function.

Experiments

Online softmax matches the predicted 1.33× memory-access reduction (4 → 3 ops/elem) with a real ~1.3× wall-clock speedup on V100, and the fused softmax+TopK kernel runs up to 5× faster than the standard safe-softmax-then-TopK pipeline.

KernelMemory ops / elementBest V100 speedupConditions
Naive Softmax3≈ same as Online for V < 1000Unsafe (overflow risk)
Safe Softmax (baseline)41.00× (baseline)Used by every DL framework
Online Softmax31.30×Large batch (4000 vectors), V ≥ 4000
Online Softmax31.15×Small batch (10 vectors), V ≥ 1000
Safe + TopK, separate51.00× (baseline)Two kernels
Safe + TopK, fused2≈ 2.5×Eliminates round-trip between kernels
Online + TopK, fused15.0×K = 5, V = 25000, large batch
Online + TopK, fused11.4×K = 30 (TopK insert dominates)

Ablation highlights

  • K sweep for fused Online+TopK: K=5 → 5.0×, K=10 → 3.5×, K=15 → 2.0×, K=30 → 1.4×. The O(K) insertion-sort per element eats the savings for big K. Fusion only wins when TopK is small.
  • Vector size sweep: speedups start appearing at V ≥ 1000 (when L1/L2 thrashing pushes the kernel into DRAM-bound territory). Below 1000, all three variants are similar because the cache absorbs the extra passes.
  • Batch size effect: small batch (10 vectors) saturates the GPU less, so speedup is latency-limited at ~1.15× even at large V. Large batch (4000 vectors) hits the predicted 1.3× ceiling.
  • Practical implication noted by the paper: switching from naive to online improves numerical stability with no performance hit. Net free upgrade for kernels that were using naive softmax.

Methods Comparison

MethodPasses over inputMemory ops / elemNumerically safe?Parallel-reducible?
Naive softmax23No (overflow)Trivially
Safe softmax34YesYes, but two separate reductions
Online softmax (this paper)23Yes (proved)Yes, single ⊕-reduction
Online softmax + TopK fused11YesYes, augmented (m,d,u,p) tuple

Limitations, Use Cases, Open Questions

Limitations

  • Speedup is purely from saved memory bandwidth. Flop-bound workloads see nothing.

    Softmax is bandwidth-bound on every GPU generation since at least Pascal, and the bound has gotten worse with each generation (HBM bandwidth grows slower than FLOPs). The paper's gain is structural, not architecture-specific.

  • TopK fusion shrinks as K grows: 5× at K=5, only 1.4× at K=30 because insertion-sort per element dominates.

    Auto-regressive decoding with beam search uses K ≤ 10 routinely, so the design point matches the dominant use case. For large-K TopK other algorithms (radix-K, bitonic sort) win anyway.

  • No evaluation on CPUs or non-NVIDIA GPUs. The whole benchmark is V100 + CUB.

    The Discussion section conjectures similar speedups on CPU if the implementation vectorizes the running pair. The arithmetic claim (4 → 3 → 1 memory ops) is hardware-agnostic; only the absolute speedup depends on the bandwidth/latency mix of a specific chip.

  • The paper only fuses softmax with the layer after it (TopK). Fusing with the layer before (the matmul projection) is mentioned as future work but not done.

    The projection is compute-bound (matmul), and fusing memory-bound with compute-bound kernels is hard without sacrificing matmul's tiling. Subsequent work (cuBLAS/cuBLASLt epilogues, FlashAttention) eventually addressed this.

Where this is useful

  • Any large-vocabulary classifier output layer (language models, NMT, ASR).
  • Attention layers. The recurrence is the algorithmic core of FlashAttention 1 / 2 / 3 and every modern attention kernel.
  • Beam-search decoding (softmax + TopK fused into one kernel. 5× faster).
  • Any softmax sitting after a bandwidth-bound op where the L2 cache can't absorb the extra passes (typically V ≥ 1000).

Open questions

  • Can the (m, d) recurrence be extended to 'log-sum-exp + Top-K + sampling' as a single fused kernel for Gumbel-style sampling?
  • What is the speedup on Hopper (H100) where DRAM bandwidth is much higher but L2 is also larger. Does the V ≥ 1000 threshold for cache thrashing move?
  • Can fp8 / bf16 storage for the running d be made safe given the 1 ≤ d_j ≤ j bound, or does the rescaling factor's wide dynamic range force fp32?
  • Does the parallel ⊕ reduction lose any precision vs the sequential recurrence under finite arithmetic? The paper doesn't characterize this.

Deep Q&A

Open-ended questions to deepen understanding. Try to answer before clicking reveal. Badges show what kind of thinking each question is testing.

Principle Why is the rescaling factor e^(m_{j-1} − m_j) exact rather than approximate? Floating-point exp is not exact.
In real arithmetic the rescaling is exact algebraically: every term e^(x_k − m_{j-1}) in d_{j-1} gets multiplied by e^(m_{j-1} − m_j), giving e^(x_k − m_j), which is exactly what d_j should contain. The fp32 implementation does pick up rounding error from the exp() call, but it picks up the same rounding error that safe softmax would have picked up. Both algorithms compute e^(x_k − m_V) eventually. In fact the paper proves d_V from online softmax equals d_V from safe softmax in exact arithmetic; in fp32 they differ only by representational noise of comparable magnitude. The number-of-ops-per-element doubles for exp (one exp per update vs one per element in safe), but the operands are smaller in magnitude, so the rounding error doesn't get worse.
Detail Why does the paper bother proving the operator is commutative when associative alone is enough for tree reduction?
Tree reduction only requires associativity. You can fix any binary-tree shape and merge bottom-up. But many real GPU reductions don't fix a tree shape: warp-shuffle reductions exchange pairs along arbitrary lane patterns, and atomic-add-style reductions process partials in nondeterministic order. Commutativity buys you the freedom to use those faster patterns without worrying about deterministic ordering. The proof costs them one sentence and pays off in every fast-reduction kernel that consumes the operator.
Principle Online softmax does more FP ops per element than safe softmax (extra multiply + extra exp). Why does it run faster?
Because softmax is memory-bandwidth-bound, not flop-bound. A V100 has ~14 TFLOP/s of fp32 but only ~900 GB/s of HBM bandwidth. A ratio of ~16 flops per byte. Softmax does ≈ 2 flops per byte loaded. The kernel sits idle waiting on DRAM 90%+ of the time, and the extra flops slot into that idle time for free. The speedup tracks the memory-access ratio (4/3 ≈ 1.33×) almost perfectly, which is the cleanest possible evidence that bandwidth is the bottleneck.
Detail Why does the fused softmax+TopK speedup collapse from 5× at K=5 to 1.4× at K=30?
The TopK insert is implemented as an insertion sort against the K-element running buffer (Algorithm 4, lines 10–15). Per element absorbed, the cost is O(K) comparisons and shuffles. At K=5 that cost is negligible compared to the memory load; at K=30 it's substantial enough that the kernel becomes compute-limited rather than memory-limited, and the original memory-savings argument no longer applies. The paper's experimental table makes this transition explicit: K=10 → 3.5×, K=15 → 2.0×, K=30 → 1.4×. The takeaway is that fusion + online softmax is a beam-search optimization (small K), not a general TopK optimization.
Principle FlashAttention is famously much harder to implement than online softmax. Both build on the same recurrence. What's the extra work?
Three things FlashAttention has to handle that this paper doesn't: (1) the softmax input isn't a vector. It's a row of a Q × K^T matrix, so the recurrence has to advance per row across blocks of columns, not per element; (2) the softmax outputs get multiplied by V into a running output accumulator O_i, which has to be rescaled by e^(m_old − m_new) in lockstep with d (this is the extra recurrence FlashAttention adds. Same shape, applied to O); (3) backward pass requires recomputing softmax during gradient (FlashAttention saves only (m, d), not the full softmax matrix, to keep memory O(N) instead of O(N²)). The (m, d) ⊕ operator is reused unchanged in all three places. The original online-softmax paper is essentially the math; FlashAttention is the engineering of applying that math to a 2D structured workload.
Detail Why store (m, d) in a single 8-byte-aligned struct instead of two separate float arrays?
Coalesced memory access. On a GPU, threads in a warp issue loads simultaneously; if the addresses are contiguous and aligned, the memory system fuses them into one cache-line transaction. With (m, d) packed into a single 8-byte struct, a warp of 32 threads reading 32 consecutive structs hits 32 × 8 = 256 bytes. Exactly two 128-byte transactions. Two separate arrays would force two completely separate sets of transactions, doubling the number of memory requests issued. The __align__(8) attribute is what tells the compiler to keep these structs aligned in the shared-memory layout used by CUB's BlockReduce.
Principle The paper proves 1 ≤ d_j ≤ j. Why does this matter, and why doesn't it apply if we use the naive (non-safe) softmax?
It matters because it bounds the dynamic range of d, which determines whether fp32 storage is enough. d_j ≥ 1 because at least one term in the sum is e^(x_max − m) = e^0 = 1; d_j ≤ j because all V terms are e^(x_k − m) ≤ 1. So d_j stays in [1, V], and even for V = 1.7×10³⁷ (way past any practical vocabulary) it doesn't exceed the fp32 representable range. In naive softmax, d is a sum of unscaled e^x terms, and a single x near 88 makes d explode past fp32 max. That's the whole reason safe softmax exists. The online recurrence inherits the safe-softmax bound for free because it always rescales to the current running max.
Detail What happens to the recurrence in the degenerate case where every x_j is identical (no max ever changes)?
The rescaling factor e^(m_{j-1} − m_j) becomes e^0 = 1, so the update degenerates to d_j = d_{j-1} + e^(x_j − m_j). Plain accumulation, same as safe softmax's pass 2. There's no penalty for this case other than the wasted exp(0) computation, which is a single fp32 op. In practice the exp is computed unconditionally because branching on 'is the max changing?' would cost more than just doing the multiply with operand 1. The branch-free implementation is a clean example of choosing predictable throughput over minimum FLOP count on a bandwidth-bound kernel.

Self-Check Quiz

Imagine an interviewer who knows ML but hasn't read this paper. Answer aloud, then click to reveal a model answer.

Write the online softmax update in 5 lines of Python that processes x as a 1D NumPy array element by element. No NumPy vector ops. Just a Python loop.
Model answer.
m, d = -np.inf, 0.0
for xj in x:
    m_new = max(m, xj)
    d = d * np.exp(m - m_new) + np.exp(xj - m_new)
    m = m_new
# Second pass: y = np.exp(x - m) / d
Given two partial (m, d) pairs from chunks A and B of the input, write the merge formula. Why is this enough to parallelize the algorithm?
Model answer.
m_new = max(m_A, m_B)
d_new = d_A * exp(m_A - m_new) + d_B * exp(m_B - m_new)

This merge is associative. Merging (A ⊕ B) ⊕ C gives the same result as A ⊕ (B ⊕ C). So you can build a binary-tree reduction across any number of threads in log₂(T) steps. It's also commutative, so the tree doesn't need a fixed shape; warp-shuffle and unordered-atomic reductions both work.
On a memory-bandwidth-bound kernel, doing 1 extra multiply per element is free. Explain why, using rough numbers for a V100.
Model answer. V100 has ~14 TFLOP/s of fp32 throughput and ~900 GB/s of HBM bandwidth → ratio ≈ 15 flops per byte loaded. Online softmax does ~2 flops per byte (one add, one compare, plus the new multiply + exp). So the kernel is ~7× under-utilized in compute and pegged on memory. The extra multiply lands in those wasted compute cycles and adds zero wall-clock time. The wall-clock speedup is set entirely by the memory-access ratio: 4 ops/elem → 3 ops/elem = 1.33×, matching the measured 1.3×.
Sketch what changes if you want to fuse online softmax with TopK. Why doesn't the recurrence break?
Model answer. Augment the running state from (m, d) to (m, d, u, p), where u ∈ ℝ^K holds the K largest values seen and p ∈ ℤ^K their original indices. On each new element x_j: (a) update m and d with the standard recurrence; (b) insertion-sort x_j into u, updating p in lockstep. The ⊕ operator generalizes to merge (m_A, d_A, u_A, p_A) and (m_B, d_B, u_B, p_B): merge (m, d) as before; merge u via parallel select-K (or a small sort) on u_A ∪ u_B. The recurrence doesn't break because the (m, d) update is independent of the TopK update. They share only the input element. Memory accesses drop to 1 per element because the K outputs are written once at the end, not per element.

Focus

Focus 25:00

0 pomodoros today