Skip to main content

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

How FlashAttention computes exact attention with linear memory by tiling Q, K, and V into SRAM-resident blocks and fusing the softmax, avoiding the quadratic HBM cost of materializing the full attention matrix.

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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, lines 1–3 and 9 · Inputs and blocks

Partition Q separately from K and V; the last blocks may be smaller.

Math and tensor shapes

S=QK^{\mathsf T}/\sqrt D
T_r=\lceil N_q/B_r\rceil
T_c=\lceil N_k/B_c\rceil

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

1. Declare scaled scores and tail blocks
python
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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, lines 2 and 5–8 · State and loop order

Original Algorithm 1 holds each K/V block while visiting all Q blocks.

Math and tensor shapes

m=-\infty,\quad \ell=0,\quad a=0
a=\operatorname{diag}(\ell)O

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

2. Carry one state per query row
python
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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, line 9; Appendix B · Score and mask

A score tile couples the current query rows with the current key rows.

Math and tensor shapes

S_{ij}=Q_iK_j^{\mathsf T}/\sqrt D
S_{uv}=-\infty\quad\text{if }k_v>q_u

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

3. Score only the current tile and apply the mask
python
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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, lines 10–11 · Online maximum

All prior contributions must move to the same new exponential scale.

Math and tensor shapes

m^+=\max(m,\operatorname{rowmax}S_{ij})
\alpha=e^{m-m^+}

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

4. Change the reference maximum safely
python
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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, lines 10–11 · Normalizer

Combine old and new exponential mass rather than tile-normalized averages.

Math and tensor shapes

P_{ij}=\exp(S_{ij}-m^+)
\ell^+=\alpha\ell+\operatorname{rowsum}P_{ij}

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

5. Update the denominator at the new scale
python
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

Paper excerpt · PDF p. 5§3.1, Algorithm 1, line 12 · Output update

The weighted-value numerator needs exactly the same change of scale as ℓ.

Math and tensor shapes

a^+=\alpha a+P_{ij}V_j
a^+=\operatorname{diag}(\ell^+)O^+

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

6. Rescale the value sum by the same factor
python
a[rows] = alpha[:, None] * a[rows] + p @ vj
m[rows] = new_m

7. Normalize once and check a dense oracle

Original paper

Paper excerpt · PDF p. 5§3.1, Algorithm 1, line 16 and Theorem 1 · Exact forward

The final row state recovers the dense softmax weighted sum.

Math and tensor shapes

O_u=a_u/\ell_u\quad(\ell_u>0)
O=\operatorname{softmax}(S)V

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

7. Normalize once and check a dense oracle
python
    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.

If you found this paper review helpful, consider sharing it with others.

Mastodon