TL;DR
- FlashAttention computes exact attention (no approximation) while cutting memory from O(N²) to O(N) by never writing the full N×N score matrix to HBM.
- It tiles Q, K, and V into blocks small enough to live in fast on-chip SRAM, computes attention block-by-block, and fuses the softmax into the same kernel.
- An online softmax — a running max and running sum rescaled as new blocks arrive — preserves the dense attention formula within floating-point tolerance.
- The paper reports workload-specific gains, including 15% faster BERT-large training and 3× faster GPT-2 training against its stated baselines, plus longer feasible contexts. These are measured results in the paper’s experiments, not universal speedup guarantees.
The memory wall of attention
The paper’s standard attention baseline forms the full N×N score matrix, applies softmax over each row, and multiplies by V. That intermediate matrix is quadratic in sequence length and lives in slow high-bandwidth memory (HBM). In the paper’s studied regime, attention is memory-bound: the GPU spends most of its time moving the score matrix to and from HBM, not computing.
Tiling: keep the work in SRAM
FlashAttention splits Q, K, and V into blocks and walks the grid of (Q-block, K-block) tiles, loading only the few blocks it needs into SRAM. The full score matrix is never assembled — each tile is consumed and discarded once its contribution is accumulated.
Online softmax makes it exact
Processing keys block-by-block would normally break the row-wise softmax normalization. FlashAttention keeps a running max m and running sum ℓ; when a new block raises the max, it rescales both the denominator and the unnormalized weighted-value sum by exp(m_old − m_new). The final result follows the same dense softmax formula. “Exact” distinguishes it from approximate attention; different reduction orders can still change floating-point rounding.
Implementation
The schematic above uses value 1 for every key. The executable forward reference below uses varied values to check the part that matters: the maximum correction must rescale both accumulated mass and accumulated values. After that numerical check, we can separate the algorithm’s correctness from its hardware impact.
Authored seeded offline CPU forward algebra, using NumPy float64, synthetic Q/K/V and no dropout. It checks the original online recurrence with tail blocks, causal masks and extreme logits. It is not a native GPU kernel, backward implementation, SRAM residency demonstration, HBM traffic measurement or timing benchmark.
The notation below maps the unnormalized accumulator to normalized O in Algorithm 1. Masking is grounded in Appendix B. Hardware IO analysis is separate: Theorem 2 gives Θ(N²d²/M) HBM accesses for d≤M≤Nd, with M measured in elements. Linear row statistics do not imply linear total traffic.
1. Declare scaled scores and tail blocks
Original paper
Partition Q separately from K and V; the last blocks may be smaller.
Math and tensor shapes
The paper displays unscaled QK. This authored reference adds standard 1/√D scaling, equivalently absorbing the factor into Q before Algorithm 1. Unequal lengths, independent value width and nondividing blocks are explicit generalizations of its square N×d exposition. Block sizes are CPU test parameters, not SRAM capacity estimates.
Q [Nq,D], K [Nk,D], V [Nk,Dv]; smoke: 7/9 rows, D=4, Dv=3
Python implementation
def tiled_attention(q, k, v, br=3, bc=4, causal=False, key_order=None,
query_offset=0, key_offset=0):
"""Return output, row max and denominator using float64 CPU tiles.
Global causal indices allow key j only if key_offset+j <= query_offset+i.
An entirely masked row returns zero output, m=-inf and l=0 by convention.
key_order is a permutation of tile indices, for traversal checks only.
"""
_validate(q, k, v, br, bc, causal, query_offset, key_offset)
q, k, v = (x.astype(np.float64, copy=False) for x in (q, k, v))
nq, d = q.shape
nk, dv = v.shape
query_starts = range(0, nq, br)
key_starts = list(range(0, nk, bc))
order = list(range(len(key_starts))) if key_order is None else key_order
if (not isinstance(order, (list, tuple))
or any(type(index) is not int for index in order)
or sorted(order) != list(range(len(key_starts)))):
raise ValueError("key_order must permute all key tiles exactly once")
scale = 1.0 / math.sqrt(d)2. Carry one state per query row
Original paper
Original Algorithm 1 holds each K/V block while visiting all Q blocks.
Math and tensor shapes
Algorithm 1 carries normalized O. Here a is the unnormalized weighted-value accumulator: rowwise a=ℓO. This substitution permits one final division. The default loop retains the original K-outer, Q-inner traversal; a reversed key order tests the same algebra with different rounding. Python arrays say nothing about hardware residence.
m [Nq], ℓ [Nq], a [Nq,Dv]
Python implementation
m = np.full(nq, -np.inf, dtype=np.float64)
l = np.zeros(nq, dtype=np.float64)
a = np.zeros((nq, dv), dtype=np.float64)
# Original Algorithm 1: outer K/V loop, inner Q loop.
for tile in order:
j = key_starts[tile]
kj, vj = k[j:j + bc], v[j:j + bc]
for i in query_starts:
rows = slice(i, min(i + br, nq))3. Score only the current tile and apply the mask
Original paper
A score tile couples the current query rows with the current key rows.
Math and tensor shapes
Causal comparisons use global positions, including tail tiles and unequal query/key lengths. Offsets declare the alignment rather than silently choosing a framework convention. Masked scores become −∞ before the reduction. Inputs and unmasked scores must be finite; overflowing score products are rejected.
Sij [actual Br,actual Bc]; qu=query_offset+u, kv=key_offset+v
Python implementation
scores = (q[rows] @ kj.T) * scale
if not np.isfinite(scores).all():
raise ValueError("Scaled score computation overflowed")
if causal:
qi = query_offset + np.arange(i, rows.stop)
ki = key_offset + np.arange(j, j + len(kj))
scores = np.where(ki[None, :] <= qi[:, None],
scores, -np.inf)4. Change the reference maximum safely
Original paper
All prior contributions must move to the same new exponential scale.
Math and tensor shapes
For a finite old maximum, α rescales prior state. Before any valid key, α is defined as zero. An entirely masked tile may leave both maxima at −∞; the code never subtracts −∞ from −∞. A zero safe reference then makes every masked exponential zero without manufacturing NaNs.
m⁺ [actual Br], α [actual Br]
Python implementation
old_m = m[rows]
new_m = np.maximum(old_m, scores.max(axis=1))
# Never evaluate -inf - (-inf), even for an initially masked tile.
finite_old = np.isfinite(old_m)
alpha = np.zeros_like(old_m)
alpha[finite_old] = np.exp(old_m[finite_old]
- new_m[finite_old])
safe_m = np.where(np.isfinite(new_m), new_m, 0.0)5. Update the denominator at the new scale
Original paper
Combine old and new exponential mass rather than tile-normalized averages.
Math and tensor shapes
P here is unnormalized, evaluated directly relative to m⁺. The paper first uses a tile maximum and then rescales its probabilities; composing the two exponentials gives this equivalent formula. The reduction sums all keys in each row. Fully masked tiles contribute zero mass.
Pij [actual Br,actual Bc], ℓ⁺ [actual Br]
Python implementation
p = np.exp(scores - safe_m[:, None])
l[rows] = alpha * l[rows] + p.sum(axis=1)6. Rescale the value sum by the same factor
Original paper
The weighted-value numerator needs exactly the same change of scale as ℓ.
Math and tensor shapes
Substituting a=diag(ℓ)O into Algorithm 1 line 12 removes its per-tile normalization and gives this recurrence. Rescaling ℓ alone corrupts the result whenever the maximum rises. Averaging separately normalized tile outputs is also incorrect because their denominators differ.
Pij @ Vj [actual Br,Dv] → a⁺ [actual Br,Dv]
Python implementation
a[rows] = alpha[:, None] * a[rows] + p @ vj
m[rows] = new_m7. Normalize once and check a dense oracle
Original paper
The final row state recovers the dense softmax weighted sum.
Math and tensor shapes
A wholly masked row returns zero output, ℓ=0 and m=−∞ by the authored API convention, since ordinary softmax on an all−∞ row is undefined. Tests use an independent scalar oracle as well as the separate dense implementation. Exact means mathematical equivalence; float64 comparisons use 1e−12 tolerances, not bitwise identity.
O [Nq,Dv]; m and ℓ retain their row statistics
Python implementation
output = np.divide(a, l[:, None], out=np.zeros_like(a),
where=l[:, None] > 0)
return output, m, l
def dense_attention(q, k, v, causal=False, query_offset=0, key_offset=0):
"""Independent dense stable softmax oracle; not used by tiled forward."""
_validate(q, k, v, 1, 1, causal, query_offset, key_offset)
scores = (q.astype(np.float64) @ k.astype(np.float64).T)
scores /= math.sqrt(q.shape[1])
if causal:
mask = (key_offset + np.arange(len(k))[None, :]
<= query_offset + np.arange(len(q))[:, None])
scores = np.where(mask, scores, -np.inf)
maximum = scores.max(axis=1)
shifted = scores - np.where(np.isfinite(maximum), maximum, 0)[:, None]
weights = np.exp(shifted)
sums = weights.sum(axis=1, keepdims=True)
probabilities = np.divide(weights, sums, out=np.zeros_like(weights),
where=sums > 0)
return probabilities @ v.astype(np.float64)Actual smoke JSON records source SHA-256, seed, shapes, reductions, six dense and reverse-traversal comparisons, row-state ranges, extreme logits and a fully masked fixture. These are numerical observations, not GPU performance evidence.
flashattention.pyrequirements-flashattention.txt
python -m pip install -r requirements-flashattention.txt python flashattention.py --smoke --seed 7
Why it mattered
FlashAttention reframed attention as an IO problem. By optimizing for bytes moved rather than FLOPs, it delivered exact attention that is both faster and far more memory-efficient, making long-context training and inference practical. In PyTorch 2.12 scaled dot-product attention, eligible CUDA inputs can use a FlashAttention backend; automatic selection depends on inputs, backend availability and enabled settings. It is not a universal default for every device or shape. Later FlashAttention variants extend this IO-aware approach to other execution regimes and hardware.
Related Reading
- Attention Is All You Need — the scaled dot-product attention whose HBM cost FlashAttention eliminates
- Data Movement Is All You Need — the data-movement analysis whose tiling-and-fusion philosophy FlashAttention applies to attention itself
- PagedAttention (vLLM) — the serving-side counterpart that manages KV-cache memory efficiently at inference
- Optimizing Transformer Inference — broader survey of the efficiency techniques FlashAttention sits within
