← Blog · 02 Nov 2026

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 x=[3,2,5,1]x=[3,2,5,1] handy; it's about to expose a bug in the most obvious attempt.

Everything works... until a bigger number arrives

Read the first value, 33. Our maximum is 33, and our normalizer is e3−3=1e^{3-3}=1:

m1=3,ℓ1=e3−3=1.m_1=3,\qquad \ell_1=e^{3-3}=1.

Read the next value, 22. The maximum stays at 33, so we can just add e2−3e^{2-3}:

m2=max⁡(3,2)=3,ℓ2=ℓ1+e2−3=1+e−1.m_2=\max(3,2)=3,\qquad \ell_2=\ell_1+e^{2-3}=1+e^{-1}.

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 55. The maximum changes:

m3=max⁡(3,5)=5.m_3=\max(3,5)=5.

If we just add the next exponential, we get the wrong normalizer:

ℓ3wrong=ℓ2+e5−5=e3−3+e2−3⏟wrong shift for the old terms+e5−5.\ell_3^{\text{wrong}}=\ell_2+e^{5-5}=\underbrace{e^{3-3}+e^{2-3}}_{\text{wrong shift for the old terms}}+e^{5-5}.

The old total is using a shift of 33, not 55.

What we’ve already addede³⁻³ + e²⁻³shifted by the old maximum: 3+The new terme⁵⁻⁵shifted by the new maximum: 5
We can't add these and call it the correct normalizer: the shifts don't match.

Do we need to go back and recompute everything? Nope. We can repair the old total with one multiplication:

(e3−3+e2−3)⏟old totale3−5⏟correction=e3−5+e2−5.\underbrace{\left(e^{3-3}+e^{2-3}\right)}_{\text{old total}}\underbrace{e^{3-5}}_{\text{correction}}=e^{3-5}+e^{2-5}.

Here's the whole repair, including the new term:

ℓ3=ℓ2e3−5⏟former max minus current max+e5−5=(e3−3+e2−3)e3−5+e5−5=e3−3+3−5+e2−3+3−5+e5−5=e3−5+e2−5+e5−5.\begin{aligned} \ell_3&=\ell_2\underbrace{e^{3-5}}_{\text{former max minus current max}}+e^{5-5}\\ &=\left(e^{3-3}+e^{2-3}\right)e^{3-5}+e^{5-5}\\ &=e^{3-3+3-5}+e^{2-3+3-5}+e^{5-5}\\ &=e^{3-5}+e^{2-5}+e^{5-5}. \end{aligned}

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 11, so the maximum stays at 55:

m4=max⁡(5,1)=5,ℓ4=ℓ3e5−5⏟=1+e1−5.m_4=\max(5,1)=5,\qquad \ell_4=\ell_3\underbrace{e^{5-5}}_{=1}+e^{1-5}.

Here we don't need to fix anything. The correction factor is one; just add the new contribution.

read 3max: 3total: 1.000read 2max: 3total: 1.368read 5max: 5total: 1.185read 1max: 5total: 1.203rescale!
The running state for [3,2,5,1][3,2,5,1], rounded to three decimals. The total can decrease when its reference maximum changes.

The whole update, in two lines

Let mim_i be the maximum after reading ii values, and let ℓi\ell_i be their shifted exponential sum. Start with m0=−∞m_0=-\infty and ℓ0=0\ell_0=0. Then:

mi=max⁡(mi−1,xi),ℓi=ℓi−1emi−1−mi+exi−mi.\begin{aligned} m_i&=\max(m_{i-1},x_i),\\ \ell_i&=\ell_{i-1}e^{m_{i-1}-m_i}+e^{x_i-m_i}. \end{aligned}

The last loop then writes

yk=exk−mNℓN,k=1,…,N.y_k=\frac{e^{x_k-m_N}}{\ell_N},\qquad k=1,\ldots,N.

We call the output yy rather than overwriting the symbol xx 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 e0=1e^0=1.

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 O(N)O(N) space.

One more example: the maximum changes twice

The first example only needed one repair. Let's try x=[2,4,1,6,3]x=[2,4,1,6,3], where the maximum goes up twice, to see that the corrections compose.

Each row applies the update ℓi=ℓi−1emi−1−mi+exi−mi\ell_i=\ell_{i-1}e^{m_{i-1}-m_i}+e^{x_i-m_i}:

Read New max mim_i Correction emi−1−mie^{m_{i-1}-m_i} Total ℓi\ell_i
x1=2x_1=2 22 (nothing to rescale yet) e2−2=1e^{2-2}=1
x2=4x_2=4 44 e2−4≈0.13534e^{2-4}\approx0.13534 1⋅0.13534+e4−4=1.135341\cdot0.13534+e^{4-4}=1.13534
x3=1x_3=1 44 e4−4=1e^{4-4}=1 1.13534+e1−4=1.185121.13534+e^{1-4}=1.18512
x4=6x_4=6 66 e4−6≈0.13534e^{4-6}\approx0.13534 1.18512⋅0.13534+e6−6=1.160391.18512\cdot0.13534+e^{6-6}=1.16039
x5=3x_5=3 66 e6−6=1e^{6-6}=1 1.16039+e3−6=1.210181.16039+e^{3-6}=1.21018

The total went down at the fourth step. That's expected: when the reference maximum rises from 44 to 66, every old term gets smaller.

Look at what happened to the very first term. It was rescaled twice, and the two corrections multiplied together:

e2−2⏟when read⋅e2−4⏟max 2→4⋅e4−6⏟max 4→6=e2−6.\underbrace{e^{2-2}}_{\text{when read}}\cdot\underbrace{e^{2-4}}_{\text{max }2\to4}\cdot\underbrace{e^{4-6}}_{\text{max }4\to6}=e^{2-6}.

The exponents telescope, so the middle value 44 cancels and the term ends up with the final maximum 66, exactly as if we'd known 66 from the start. Written out, the final normalizer is

ℓ5=e2−6+e4−6+e1−6+e6−6+e3−6≈1.21018.\ell_5=e^{2-6}+e^{4-6}+e^{1-6}+e^{6-6}+e^{3-6}\approx1.21018.

That's the same sum the three-pass algorithm would compute, and dividing each shifted exponential by it gives

softmax⁡(x)≈[0.01513,  0.11183,  0.00557,  0.82633,  0.04114].\operatorname{softmax}(x)\approx[0.01513,\;0.11183,\;0.00557,\;0.82633,\;0.04114].

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:

mN=max⁡1≤j≤Nxj=xmax⁡,ℓN=∑j=1Nexj−xmax⁡.m_N=\max_{1\leq j\leq N}x_j=x_{\max},\qquad \ell_N=\sum_{j=1}^{N}e^{x_j-x_{\max}}.

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 N=1N=1. For a finite x1x_1,

m1=max⁡(−∞,x1)=x1=xmax⁡,ℓ1=0⋅e−∞+ex1−x1=1=∑j=11exj−xmax⁡.\begin{aligned} m_1&=\max(-\infty,x_1)=x_1=x_{\max},\\ \ell_1&=0\cdot e^{-\infty}+e^{x_1-x_1}=1=\sum_{j=1}^{1}e^{x_j-x_{\max}}. \end{aligned}

Here e−∞=0e^{-\infty}=0 is the limiting value used in the initialization.

Now assume it works for NN inputs. Does it still work for N+1N+1? The maximum is straightforward:

mN+1=max⁡(mN,xN+1)=max⁡1≤j≤N+1xj.m_{N+1}=\max(m_N,x_{N+1})=\max_{1\leq j\leq N+1}x_j.

For the normalizer, keep every step visible:

ℓN+1=ℓNemN−mN+1+exN+1−mN+1=(∑j=1Nexj−mN)emN−mN+1+exN+1−mN+1=∑j=1Nexj−mN+1+exN+1−mN+1=∑j=1N+1exj−mN+1.\begin{aligned} \ell_{N+1}&=\ell_N e^{m_N-m_{N+1}}+e^{x_{N+1}-m_{N+1}}\\ &=\left(\sum_{j=1}^{N}e^{x_j-m_N}\right)e^{m_N-m_{N+1}}+e^{x_{N+1}-m_{N+1}}\\ &=\sum_{j=1}^{N}e^{x_j-m_{N+1}}+e^{x_{N+1}-m_{N+1}}\\ &=\sum_{j=1}^{N+1}e^{x_j-m_{N+1}}. \end{aligned}

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 O(N)O(N) work overall. The two running statistics use constant auxiliary space; the output vector still has NN 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.