Overview: The hardware memory bottleneck of standard multi-head attention, tiled execution using GPU on-chip shared memory (SRAM), the mathematical derivation of online-softmax rescaling, thread block synchronization barriers, and scaling auxiliary VRAM from $\mathcal{O}(N^2)$ down to $\mathcal{O}(N)$ to prevent Out-Of-Memory crashes at 4K context.
Standard Multi-Head Attention is formulated as:
$$\text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^T}{\sqrt{d}}\right) V$$In a naive CUDA or PyTorch implementation, this is executed in three sequential kernels:
FlashAttention (Tri Dao et al., 2022) restructures attention to compute everything in small blocks directly inside fast on-chip Shared Memory (SRAM):
Global Memory (HBM: 6 GB, 192 GB/s)
│ ▲
│ Tile Load │ Final O only (N x d)
▼ │
Shared Memory (SRAM: 48 KB per SM, ~10 TB/s)
┌────────────────────────────────────────────────────────┐
│ Qi (Br x d) │ Kj (Bc x d) │ Vj (Bc x d) │ S │
│ Tiled Q │ Tiled K │ Tiled V │ BrxBc │
└────────────────────────────────────────────────────────┘
The core mathematical hurdle to tiling attention is softmax normalization. In standard softmax, you cannot compute the denominator $\sum_j e^{s_j}$ until you have seen every single column in the row.
FlashAttention solves this using the online softmax algorithm. As each new K/V tile $j$ arrives, it maintains running statistics: running row max $m$ and running denominator sum $l$.
For query row $i$, suppose we have processed tiles $0 \dots j-1$ with running max $m_{prev}$ and denominator $l_{prev}$, and we now process tile $j$ with local scores $S_{ij}$:
The previous output $O_{prev}$ was normalized by $l_{prev}$ using max $m_{prev}$. We rescale $O_{prev}$ to the new maximum $m_{new}$ and blend in the new tile's weighted value contribution $P_{ij} V_j$:
$$O_{new} = \frac{l_{prev} \cdot \alpha_{prev} \cdot O_{prev} + \alpha_{curr} \cdot (P_{ij} V_j)}{l_{new}}$$When the loop over all $T_c$ tiles finishes, $O$ is mathematically identical to standard global softmax attention!
__global__ void flash_attention_kernel(
const float* Q, const float* K, const float* V, float* O,
float* m, float* l,
int B, int NH, int N, int d, int Tc, int Tr, int Bc, int Br, float scale) {
int tx = threadIdx.x; // Thread index [0 .. Br-1]
// Shared Memory Pointers
extern __shared__ float smem[];
float* Qi = smem;
float* Kj = Qi + Br * d;
float* Vj = Kj + Bc * d;
float* S = Vj + Bc * d;
// Outer Loop: Over K/V Tiles (j = 0 .. Tc - 1)
for (int j = 0; j < Tc; j++) {
// Cooperatively load Kj and Vj into shared memory
for (int x = 0; x < d; x++) {
Kj[tx * d + x] = K[qkv_base + (j * Bc + tx) * d + x];
Vj[tx * d + x] = V[qkv_base + (j * Bc + tx) * d + x];
}
__syncthreads(); // BARRIER 1: All Bc rows of K/V are loaded in smem
// Inner Loop: Over Q Tiles (i = 0 .. Tr - 1)
for (int i = 0; i < Tr; i++) {
int q_row_global = i * Br + tx;
// 1. Load Qi row into shared memory
for (int x = 0; x < d; x++) Qi[tx * d + x] = Q[...];
// 2. Read running statistics from global memory
float m_prev = m[lm_base + q_row_global];
float l_prev = l[lm_base + q_row_global];
// 3. Compute dot products S = (Qi . Kj^T) * scale
// 4. Compute m_curr and l_curr
// 5. Update m_new and l_new
// 6. Rescale and update O[qkv_base + q_row_global * d + x]
m[lm_base + q_row_global] = m_new;
l[lm_base + q_row_global] = l_new;
}
__syncthreads(); // BARRIER 2: Prevent overwriting K/V before all inner loops finish
}
}
`cudaMalloc` does not zero-initialize. Furthermore, initializing `d_m` to `0.0f` is fatal because any negative dot-product score from the first tile would be smaller than 0.0, clipping legitimate attention scores. We authored an initialization kernel `init_neg_inf` setting `d_m = -1e20f` across all entries.
A second `__syncthreads()` barrier at the end of the outer loop is mandatory. Without it, faster threads looping to tile $j+1$ would begin overwriting `Kj` and `Vj` in shared memory while slower threads in the same block were still reading tile $j$'s values.
In our head-to-head benchmark on identical random tensors (`attention_bench.cu` on RTX 3050 GPU):
| Sequence Length ($N$) | Standard Attention (Global HBM) | FlashAttention (SRAM Tiled) | Speedup | Max Absolute Diff | Auxiliary VRAM Scaling |
|---|---|---|---|---|---|
| 128 | 1.69 ms | 1.25 ms | 1.35x | $1.49 \times 10^{-6}$ | Standard: 0.5 MB vs Flash: 1 KB |
| 256 | 4.10 ms | 2.62 ms | 1.56x | $1.90 \times 10^{-6}$ | Standard: 2.1 MB vs Flash: 2 KB |
| 512 | 11.60 ms | 6.19 ms | 1.87x | $2.38 \times 10^{-6}$ | Standard: 8.4 MB vs Flash: 4 KB |
| 1024 | 37.43 ms | 16.33 ms | 2.29x | $2.86 \times 10^{-6}$ | Standard: 33.6 MB vs Flash: 8 KB |
| 2048 | 141.33 ms | 51.12 ms | 2.76x | $3.57 \times 10^{-6}$ | Standard: 134.2 MB vs Flash: 16 KB |
| 4096 | CUDA OutOfMemory (Tried 6.0 GB) | 180.87 ms | Infinite (Prevents Crash) | -- | $\mathcal{O}(N^2) \to \mathcal{O}(N)$ |
Numerical Precision: The maximum absolute difference between FlashAttention and Standard Attention was $< 4 \times 10^{-6}$, confirming pure float32 numerical equivalence.