TL;DR
- A running maximum and a rescaled sum of exponentials compute the stable softmax normalizer in one traversal, even when a later logit raises the maximum.
- Chunk summaries merge at a shared maximum, enabling parallel reduction; floating-point reduction orders can still produce small numerical differences.
- Computing the normalizer online does not make the full softmax vector a one-pass output. Discarded logits must be revisited, while rows retained on chip can be reused.
- Consumers such as TopK and attention can use the normalizer without materializing every probability. The saving depends on which outputs the consumer actually needs.
- The review separates calculated examples and CPU reference checks from the paper's historical V100 measurements; reduced memory traffic alone does not establish a runtime speedup.
Why the denominator is difficult to stream
A softmax probability depends on every logit in its row. That makes a streaming implementation awkward: a logit arriving near the end can change the maximum used for numerical stability, as well as the denominator shared by all outputs. The useful question is whether the work done on earlier logits can survive that change of scale.
Milakov and Gimelshein's answer is a two-number summary: a running maximum and a sum of exponentials measured relative to that maximum. Whenever the maximum increases, a single multiplier converts the old sum to the new scale. The maximum and denominator can then be computed in one traversal. Producing the full softmax vector still requires the logits after the final denominator is known. Paper, Algorithm 3
This review follows arXiv v2, revised July 28, 2018. The three explorers use deterministic arithmetic on authored inputs. Their values and memory counts are calculated examples, not recorded GPU results. The downloadable Python reference checks the equations on a CPU; the paper's hardware measurements are discussed separately.
Start with a stable denominator
For a row of N logits, softmax divides each exponential by the sum of all exponentials. Adding the same constant to every logit multiplies the numerator and denominator by the same factor, which cancels. This freedom lets us subtract the largest logit before exponentiation:
Consider logits [1000, 1001, 999]. Directly exponentiating them overflows ordinary double-precision arithmetic. Subtracting 1001 gives exponents [−1, 0, −2], with exactly the same mathematical probabilities. Every exponential is at most one, and a maximum contributes one. Very small contributions can still underflow to zero; subtracting the maximum does not remove floating-point rounding or recover information already lost in the input representation.
A straightforward implementation first reads the row for its maximum, reads it again for the shifted denominator, then reads it a third time to write normalized outputs. This is the storage schedule of the paper's Algorithm 2. It is not a requirement that every stable-softmax kernel load from device memory three times: a kernel that retains a whole row on chip can reuse those values. We will return to that distinction after deriving the recurrence.
Change the scale without revisiting the past
After j logits, define the summary by its meaning:
When the next logit raises the maximum, every previous exponential needs the same correction. For an earlier value x, rewriting its mass at the new maximum gives
The multiplier does not depend on which earlier logit produced the term, so it can be applied to their sum. The update is therefore
Try the “A later maximum” stream and advance to x3 = 4. The previous maximum was 2. The old sum must shrink by exp(−2) before adding the new contribution of one. Compare that with “Maximum first,” where later steps leave the scale unchanged.
Keep the old mass in the new maximum’s units
Watch each input arrive, the old masses shrink when the maximum rises, and the new contribution enter the sum.
The input row is waiting. The empty summary is m = −∞, d = 0.
- Seen / incorporated
- 0 / 0
- Current exponential scale m
- −∞
- Completed prefix d
- 0.0000
- Old mass multiplier
- —
Shifted exponential masses
Gray: mass before this update. Color: mass now. Each full track represents one.
Read first, then add. Only the completed Add stage satisfies the prefix invariant.
The denominator need not increase at every step, because its unit of measurement can change. What remains true is its definition as a shifted sum over the entire observed prefix. For finite logits in exact arithmetic, that gives 1 ≤ d_j ≤ j: all j contributions are at most one and at least one is exactly one. Forgetting the rescaling factor breaks the prefix invariant even if the output values still look plausible.
Initialization uses m0 = −∞ and d0 = 0. The first finite logit sets the maximum, clears the empty accumulated mass through a zero multiplier, and contributes one. The reference deliberately accepts finite logits. A production masked-softmax implementation also needs an explicit policy for masked entries and completely masked rows; blindly subtracting −∞ from −∞ creates NaN. An empty reduction chunk is handled as an identity below, not passed through that subtraction.
A chunk can stand in for its entire history
Processing one scalar after another is useful for understanding the invariant, but a GPU needs parallel work. Suppose chunk A has summary (mA, dA), and chunk B has (mB, dB). Choose the larger maximum, rescale both sums to it, and add:
The resulting pair describes the union of both chunks. Nothing about the proof depends on how either chunk was partitioned earlier. That is why a tree of summary merges produces the same real-number result as the sequential recurrence. A single logit starts with (x, 1), making the scalar update a special case of the same operation. Paper, §3.1, Equations 3–4
Move the split in the next figure. The local sums change, but conversion to the shared maximum keeps their merged summary fixed.
Merge summaries, not independently normalized probabilities
Choose a split, then play the scale conversion. Both contributions must use the shared maximum before their bars can be added.
Two chunks arrive with their own maxima. Their local sums use different scales.
A: [2, 1, 4]1.1851
B: [0, 5, 3]1.1421
Shared-scale sumempty
Teal: A × 0.3679. Amber: B × 1.0000. Add only after both scale corrections.
- Chunk A maximum
- 4
- Chunk B maximum
- 5
- Chosen shared maximum
- —
- Completed denominator
- —
Adding the unscaled local sums gives 2.3272. That is valid only when both maxima match; at this split the final denominator is 1.5781.
Associativity here is a statement about exact arithmetic. Floating-point additions and exponentials can round differently under another tree or input order. Tests should check agreement within a meaningful tolerance, not demand bitwise equality. The empty-chunk identity is (−∞, 0); explicit branches return the other chunk before evaluating any exponential when one side is empty.
The authors' CUDA implementation uses a two-float MD structure and a custom CUB reduction. Its merge selects the larger maximum, keeps that side's sum unchanged, and rescales only the other side. This is the same formula with one multiplier known to be one. Each thread accumulates its assigned inputs, the block reduces the summaries, and a later loop writes probabilities. Pinned official implementation, reduce_md_op and online_softmax
One normalizer pass is not one full-softmax pass
Once the final pair (mN, dN) is known, each output is exp(xi − mN) / dN. Two scalars cannot also remember the individual numerator for every position. If the implementation has discarded each input after updating the summary, it must revisit those inputs to emit the full output vector. If it retained the row on chip, it can reuse the retained values.
Under the paper's rereading schedule, the conventional stable implementation makes three input reads and one output write per element. The online version makes two reads and one write. For FP32, that is 16N versus 12N payload bytes, a 25% reduction. A 4/3 ratio of traffic does not by itself establish a 4/3 ratio of runtime.
Choose a schedule and change the row length. The “Row on chip” case changes the storage assumption as well as the pass count.
Count passes and say which memory they cross
Follow one full-row payload at a time between device memory and compute. The counter advances when a logical read or write completes.
The row is in device memory. No logical payload has crossed into compute yet.
One packet represents the full row.
- Completed reads / writes
- 0N / 0N
- Completed payload
- 0 KiB
0 of 3 full-row transfers completed.
| Schedule | Reads | Writes | Payload |
|---|---|---|---|
| Three-pass safe softmax | 3N | 1N | 64 KiB |
| Online normalizer + output | 2N | 1N | 48 KiB |
| Whole row retained on chip | 1N | 1N | 32 KiB |
The online schedule uses 12N bytes versus 16N in the three-pass schedule: 25% fewer payload bytes. The 4/3 traffic ratio is not a promised speedup. Whole-row residency is a separate storage assumption.
This is why “online softmax beats fused softmax” is not a conclusion that follows from the recurrence. A fused kernel may load a short row once, compute its maximum and denominator using on-chip reductions, and write once without an online recurrence. The official Triton fused-softmax tutorial demonstrates that whole-row approach. Its feasibility depends on row size and resource use. Long rows, register pressure, spills, occupancy and the consumer's needs can motivate a different schedule.
The traffic model also does not count a separate allocation for exponentials or a chain of unfused framework operators. Such implementations have different intermediate reads and writes. A useful comparison states the exact baseline, what stays on chip, which memory boundary is counted, the row length and batch size, and whether timing covers the kernel or the full call.
A consumer that needs only TopK changes the problem
Softmax preserves the order of finite logits. If a consumer needs only the largest K probabilities and their indices, it can retain the largest K logits while accumulating the normalizer over all N inputs. Once the denominator is final, only those retained logits need to be normalized. No full N-element probability vector needs to be written or reread. This is the fusion opportunity developed in Algorithm 4.
For the authored row [2, 1, 4, 0, 5, 3], the top two logits are 5 and 4. Their probabilities still use contributions from the other four logits in the denominator. Taking softmax of just [5, 4] instead would renormalize a different distribution. Likewise, if the caller needs only indices, the softmax denominator is unnecessary: ranking the logits already supplies them.
Keeping K candidates introduces its own work and state. The reference uses a heap and specifies a lower-index tie rule; the paper uses insertion into a small ordered candidate array. Neither supports a universal speedup as K grows. The saving comes from meeting the consumer's actual output contract with fewer materialized intermediates.
Read the source, equations and implementation together
Each row pairs an original-PDF excerpt with the corresponding equation and a generated region of the executable reference. The full-softmax wrapper materializes a Python tuple to support its output pass. Only the normalizer and the TopK routine can consume their input iterator once without retaining the full row.
1. Establish the maximum-first reference
Original paper
Algorithm 2 computes the maximum, shifted sum and output in three input passes.
Math and tensor shapes
The reference uses math.fsum for its denominator, giving the online implementation an independently accumulated comparison. For finite logits, all shifted exponents are nonpositive and at least one exponential is one. Very small terms can still underflow to zero.
Python implementation
def stable_softmax(values):
"""Subtract the final maximum before exponentiation."""
values = finite_values(values)
maximum = max(values)
denominator = math.fsum(math.exp(x - maximum) for x in values)
return [math.exp(x - maximum) / denominator for x in values]2. Update the maximum and denominator together
Original paper
Algorithm 3, lines 1–6, is a single-pass calculation of the normalizer.
Math and tensor shapes
The old denominator is expressed relative to the old maximum. Multiplying by the correction puts it on the new scale. For a first finite input, exp(−∞) is zero and the new contribution is one. The function accepts an iterator and retains just two scalars.
Python implementation
def online_normalizer(values):
"""Consume finite logits once, keeping just a maximum and shifted sum."""
maximum, denominator = -math.inf, 0.0
for value in values:
if not math.isfinite(value):
raise ValueError("Finite logits required")
next_maximum = max(maximum, value)
denominator = (
denominator * math.exp(maximum - next_maximum)
+ math.exp(value - next_maximum)
)
maximum = next_maximum
return maximum, denominator3. Turn the recurrence into a parallel reduction
Original paper
Section 3.1, Equations 3–4, defines the binary summary operation.
Math and tensor shapes
A chunk is represented by its maximum and sum of exponentials at that maximum. Empty chunks use (−∞, 0), with explicit identity branches to avoid an undefined infinity subtraction. Associativity holds in real arithmetic; floating-point merge trees need tolerance-based comparison.
Python implementation
def merge(left, right):
"""Merge summaries; (-inf, 0) is the empty-chunk identity."""
left_max, left_sum = left
right_max, right_sum = right
if left_sum == 0:
return right
if right_sum == 0:
return left
maximum = max(left_max, right_max)
denominator = (
left_sum * math.exp(left_max - maximum)
+ right_sum * math.exp(right_max - maximum)
)
return maximum, denominator4. Revisit each logit to write the full output
Original paper
Algorithm 3, lines 7–9, retains a separate output loop after the normalizer finishes.
Math and tensor shapes
Two scalars summarize the denominator, but do not retain every numerator. This wrapper materializes input values so a second traversal is possible. A GPU implementation can reread global memory or keep a suitably small row on chip. These storage choices have different costs.
Python implementation
def online_softmax(values):
"""The final probabilities still require access to every input logit."""
values = finite_values(values)
maximum, denominator = online_normalizer(values)
return [math.exp(x - maximum) / denominator for x in values]5. Retain only the outputs a TopK consumer needs
Original paper
Algorithm 4 keeps the top logits while updating the full normalizer, then writes K probabilities and indices.
Math and tensor shapes
The Python reference uses a heap rather than the paper’s insertion array. It never materializes the full probability vector and selects lower indices on ties. Every input still contributes to d; these selected probabilities generally sum to less than one. Renormalizing only the selected logits would compute a different distribution.
Python implementation
def online_topk(values, k):
"""Read once; retain k logits and normalize with the ALL-logit sum."""
if not isinstance(k, int) or isinstance(k, bool) or k < 1:
raise ValueError("A positive integer k is required")
maximum, denominator = -math.inf, 0.0
selected = []
for index, value in enumerate(values):
if not math.isfinite(value):
raise ValueError("Finite logits required")
maximum, denominator = merge((maximum, denominator), (value, 1.0))
# Smaller original indices win ties in this teaching reference.
heapq.heappush(selected, (value, -index))
if len(selected) > k:
heapq.heappop(selected)
if len(selected) < k:
raise ValueError("k must not exceed the input length")
return [(-index, math.exp(value - maximum) / denominator)
for value, index in sorted(selected, reverse=True)]Original excerpts: Maxim Milakov and Natalia Gimelshein, arXiv v2 (July 28, 2018). The source manifest records the PDF hash, page rectangles and image hashes. Snippets are generated from the downloadable reference; finite_values is its input-validation helper.
Download online_softmax.py and run it with Python 3.10 or later. The README explains the input contract and omissions; requirements lists no external packages. Its checks cover large offsets, equal logits, singletons, every two-way partition of deterministic test vectors, empty summary identities, and selected probabilities against a full reference. --json emits the six-logit trace used by the browser checks. No accelerator or model checkpoint is involved.
Read the measurements with their workload attached
The paper benchmarks FP32 CUDA implementations on a Tesla V100 PCIe with 16 GB, using CUDA 9.1 and CUB 1.8.0, with ECC and persistence enabled. It tests batches of 4,000 rows and 10 rows. For large batches, online softmax reaches roughly 1.3× over the paper's safe-softmax baseline once rows are sufficiently wide; the smaller batch sees about 1.15× in the reported wide-row regime. The one-block-per-row implementation leaves only ten blocks in the smaller case, limiting utilization. Paper, §5.1 and Figures 1–2
The larger up to 5× result concerns fused softmax plus TopK, with K = 5, against safe softmax followed by a separate TopK operation. It includes the benefit of eliminating the intermediate probability vector and cannot be assigned to standalone softmax. The paper also reports lower benefits as K grows. These are historical measurements from the cited implementation and workloads, not benchmarks reproduced by this page or predictions for a current framework kernel. Paper, §5.2 and Figures 3–4
The connection to FlashAttention
The reusable idea is a summary whose accumulated quantities can change scale together. In attention, the consumer does not need a materialized row of softmax probabilities; it needs their weighted sum of value vectors. An unnormalized weighted-value accumulator can be rescaled by the same factor as the denominator when a later score tile raises the maximum. After all tiles, dividing the accumulator by the denominator produces the attention output.
FlashAttention combines that mechanism with tiled matrix products and an attention-specific memory schedule. It is a later algorithm, not another name for this 2018 softmax kernel. The normalizer explains how changing score maxima can be handled incrementally; avoiding the full attention matrix additionally depends on consuming each tile's contributions before discarding it. FlashAttention, Algorithm 1
I would read this paper by tracing a late-arriving maximum, then merging two chunks with different maxima. Once those calculations agree with a conventional reference, I would inspect the surrounding producer and consumer before optimizing memory traffic. The next useful question is which outputs must actually exist in memory. Making Deep Learning Go Brrrr develops that performance perspective, while GPU memory hierarchy explains why retaining a row on chip and rereading it from device memory are different implementation choices.
