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
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:
| Workload | Scale | Impact |
|---|---|---|
| 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 request | The 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 token | Small 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) / dWhy 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_V4 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_VWhy 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 resultA 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]| Variant | Memory ops / element | V100 speedup vs Safe+TopK separate |
|---|---|---|
| Safe Softmax + TopK, separate | 5 | 1.0× (baseline) |
| Safe Softmax + TopK, fused | 2 | ~2.5× |
| Online Softmax + TopK, fused | 1 | 5× 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
__fdivideffor 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.
| Kernel | Memory ops / element | Best V100 speedup | Conditions |
|---|---|---|---|
| Naive Softmax | 3 | ≈ same as Online for V < 1000 | Unsafe (overflow risk) |
| Safe Softmax (baseline) | 4 | 1.00× (baseline) | Used by every DL framework |
| Online Softmax | 3 | 1.30× | Large batch (4000 vectors), V ≥ 4000 |
| Online Softmax | 3 | 1.15× | Small batch (10 vectors), V ≥ 1000 |
| Safe + TopK, separate | 5 | 1.00× (baseline) | Two kernels |
| Safe + TopK, fused | 2 | ≈ 2.5× | Eliminates round-trip between kernels |
| Online + TopK, fused | 1 | 5.0× | K = 5, V = 25000, large batch |
| Online + TopK, fused | 1 | 1.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
| Method | Passes over input | Memory ops / elem | Numerically safe? | Parallel-reducible? |
|---|---|---|---|---|
| Naive softmax | 2 | 3 | No (overflow) | Trivially |
| Safe softmax | 3 | 4 | Yes | Yes, but two separate reductions |
| Online softmax (this paper) | 2 | 3 | Yes (proved) | Yes, single ⊕-reduction |
| Online softmax + TopK fused | 1 | 1 | Yes | Yes, 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.
Detail Why does the paper bother proving the operator is commutative when associative alone is enough for tree reduction?
Principle Online softmax does more FP ops per element than safe softmax (extra multiply + extra exp). Why does it run faster?
Detail Why does the fused softmax+TopK speedup collapse from 5× at K=5 to 1.4× at K=30?
Principle FlashAttention is famously much harder to implement than online softmax. Both build on the same recurrence. What's the extra work?
Detail Why store (m, d) in a single 8-byte-aligned struct instead of two separate float arrays?
__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?
Detail What happens to the recurrence in the degenerate case where every x_j is identical (no max ever changes)?
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.
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) / dGiven 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?
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.