FlashAttention, Part 2: Softmax on the fly
One running maximum, one running sum, and the correction that keeps them in sync.
Part 1 made softmax safe. We found the maximum, computed the shifted exponential sum, and divided by it. Three passes through each row. Now the question is: can we do fewer passes without letting the exponentials blow up?
We'll fuse the maximum and normalizer calculations. The final pass still writes the probabilities. Keep our example handy; it's about to expose a bug in the most obvious attempt.
Everything works... until a bigger number arrives
Read the first value, . Our maximum is , and our normalizer is :
Read the next value, . The maximum stays at , so we can just add :
If the vector ended here, we'd already have the correct maximum and normalizer. The failure only appears when a later value changes our reference maximum.
Then we hit . The maximum changes:
If we just add the next exponential, we get the wrong normalizer:
The old total is using a shift of , not .
Do we need to go back and recompute everything? Nope. We can repair the old total with one multiplication:
Here's the whole repair, including the new term:
Now all the terms use the new maximum. We're back in business.
This is the trick to remember. When the maximum increases, don't throw away the running total. Rescale it.
The last value is , so the maximum stays at :
Here we don't need to fix anything. The correction factor is one; just add the new contribution.
The whole update, in two lines
Let be the maximum after reading values, and let be their shifted exponential sum. Start with and . Then:
The last loop then writes
We call the output rather than overwriting the symbol for our input.
That's: find the new maximum, fix the old total, add the new term. If the maximum hasn't changed, the correction is .
Here's what it looks like in pseudocode for a nonempty vector of finite values:
maximum = -infinity
normalizer = 0
for value in values:
next_maximum = max(maximum, value)
correction = exp(maximum - next_maximum)
normalizer = normalizer * correction
normalizer += exp(value - next_maximum)
maximum = next_maximum
for index in range(length(values)):
output[index] = exp(values[index] - maximum) / normalizer
Two passes instead of three. The first gets both statistics; the second writes the probabilities.
A small but important catch: we're computing the normalizer online, not emitting final probabilities on the spot. A value we haven't seen yet can still change the denominator. We only need two running scalars, but storing the output still takes space.
One more example: the maximum changes twice
The first example only needed one repair. Let's try , where the maximum goes up twice, to see that the corrections compose.
Each row applies the update :
| Read | New max | Correction | Total |
|---|---|---|---|
| (nothing to rescale yet) | |||
The total went down at the fourth step. That's expected: when the reference maximum rises from to , every old term gets smaller.
Look at what happened to the very first term. It was rescaled twice, and the two corrections multiplied together:
The exponents telescope, so the middle value cancels and the term ends up with the final maximum , exactly as if we'd known from the start. Written out, the final normalizer is
That's the same sum the three-pass algorithm would compute, and dividing each shifted exponential by it gives
Same answer, one fewer pass. The proof below shows why this isn't a coincidence.
Let's prove it, not just hope it works
At the end of the first loop, we want two things to be true:
Let's use induction. That sounds more formal than it needs to: check one input, then check that adding one more keeps things correct.
Start with . For a finite ,
Here is the limiting value used in the initialization.
Now assume it works for inputs. Does it still work for ? The maximum is straightforward:
For the normalizer, keep every step visible:
That's the correct shifted sum for the longer vector. Both statements survive the update, so the algorithm works for every nonempty finite input vector in exact arithmetic.
Same math, different order of operations. Floating-point results can differ slightly from the three-pass version.
What we've gained
The maximum and normalizer now come from the same pass. Writing the probabilities takes one more pass, so we go from three traversals to two, with work overall. The two running statistics use constant auxiliary space; the output vector still has entries.
The point isn't just saving a loop. We can absorb new data and repair the normalization statistics without rereading everything we've already seen. In Part 3, we'll bring in matrix blocks so those new pieces can be tiles, not just individual values.
Where do we go next?
We now have a safe softmax and a way to update its normalization statistics online. Next, we'll bring in block matrix multiplication and see how tiles let us work on attention a small piece at a time.
The bigger roadmap. Still ahead in the series: tensor layouts, example CUDA kernels, block matrix multiplication, moving from CUDA to Triton, software pipelining, the FlashAttention forward pass, autograd, derivatives and gradients, gradients of matrix multiplication, gradients of softmax, and the FlashAttention backward pass. We'll take them one stop at a time rather than squeezing them into a single post.