FlashAttention, Part 1: Making softmax safe
Before we make attention fast, let's make sure its numbers behave.
Attention looks pretty compact on paper: multiply some matrices, apply softmax, multiply again. But behind that little equation are two questions: where do all the intermediate numbers live, and can we actually represent them safely?
Let's take this one part at a time. This post covers the attention setup and making softmax safe, including the three-pass algorithm and a worked example. Online softmax gets its own post next, and the block-matrix diagrams come in Part 3.
Before we start. The prerequisites for the series are basic linear algebra (matrix multiplication and transposes), high-school calculus (derivatives), a basic understanding of attention, and patience. We won't need the derivatives in this first part, but we'll come back to them for the backward pass.
The attention equation, without skipping the heads
First, the scaled dot-product attention formula:
For head , apply the learned query, key, and value projections:
Then put the heads together and apply the output projection:
That's the multi-head setup. For the rest of the post, we only need to follow one head.
An important detail: from here on, , , and are already projected through their respective , , and . We aren't applying those projections again inside the calculations below.
For the self-attention example, take : tokens and features per head. We use the same value dimension to keep the shapes simple. We'll leave masks and dropout out of this first explanation.
Keep an eye on the matrix dimensions
To focus on the matrix shapes, let's temporarily suppress the factor and write
For actual scaled attention, replace by . The shapes and the softmax argument below stay the same.
Here are the two shape checks written out:
The score in row , column is , where and are the query and key vectors viewed as columns. Softmax turns each row of scores into weights over all the keys.
Notice what hasn't changed: softmax takes a matrix and returns a matrix. It changes the entries, not the dimensions. Each row now sums to one.
Why memory matters here
The inputs and output have entries each. But and each have entries. Those intermediate matrices grow quickly as we increase the sequence length.
For this computation, there are two important places to keep data:
- HBM: high-bandwidth memory. This is DRAM used for GPU global memory in the hardware picture we're considering.
- Shared memory. Much smaller, on-chip storage, closer to where the GPU does the work.
The key idea is to calculate parts of the matrix multiplication using the smaller workspace, then copy the needed results back. We'll develop the actual block calculations in Part 3. First, let's make the softmax itself safe.
Where softmax gets into trouble
Given , softmax is
Exponentiate each number, then divide by the sum. Straightforward—until the vector contains large values and those exponentials get too large to represent.
A floating-point warning. Formats such as float32 and float16 have a limited range. The problem here is specifically overflow in the intermediate exponentials: they may be unrepresentable even though the final probabilities are perfectly reasonable.
Let's sneak a constant into the exponent
We can multiply the numerator and denominator by the same positive constant without changing the ratio. Here's the full chain:
Same softmax, different exponent. We use for this constant so it doesn't get confused with the key matrix .
The shift is ours to choose. To prevent any positive exponent, we need for every . Equivalently, must be at least as large as the maximum input. So the smallest shift that keeps every exponent nonpositive is:
With this choice, the largest input becomes zero, so its exponential is exactly one. Every other exponent is also nonpositive, which keeps every exponential at most one and the normalizer at least one. A larger shift would avoid overflow too, but would push every exponential lower than necessary. That gives us
This avoids exponential overflow and guarantees a nonzero denominator. Very small contributions can still underflow or be rounded away, so we're not claiming perfect floating-point arithmetic.
The trick: subtract the maximum before exponentiating. The probabilities don't change. The size of the intermediate exponentials does.
What does the safe algorithm actually do?
For an score matrix, do the following for each row. Each row is a vector with values.
| Pass through one row | Work | Input reads |
|---|---|---|
| 1. Find the maximum | ||
| 2. Calculate the normalization factor | ||
| 3. Normalize every element |
Each pass costs per row, so all three passes together are still per row, or for softmax over the whole matrix. The last pass also writes output values. These are logical input reads; if a row stays on chip, a new pass needn't mean another read from HBM.
The indexed version makes the order explicit:
First finish finding , then use that final maximum for all the exponentials. The output is called here so we don't confuse the original inputs with their probabilities.
And here's the same three-pass algorithm in pseudocode:
maximum = -infinity
for value in values:
maximum = max(maximum, value)
normalizer = 0
for value in values:
normalizer += exp(value - maximum)
for index in range(length(values)):
output[index] = exp(values[index] - maximum) / normalizer
Let's walk through the example:
Step 1: find the maximum. For , we have .
Step 2: calculate the normalization factor.
Step 3: divide each shifted exponential by the same total.
Numerically,
The biggest input gets the biggest weight. All four weights sum to one. And none of the exponentials needed to be larger than one.
That's Part 1: safe before fast
We now have the attention shapes, the memory motivation, the full constant-shift derivation, and a safe softmax we can compute by hand.
Next: can we do fewer than three passes? That's Part 2. We'll try calculating the maximum and normalizer together, see exactly where the obvious attempt breaks, and repair it without starting over.