Standard Transformer self-attention computes S = QK^T / sqrt(d), P = softmax(S), and O = PV. At sequence length N = 32,768 with 32 attention heads in FP16, materializing S and P in GPU HBM requires 32 * 32,768^2 * 2 bytes = 68.7 GB per layer—exceeding an 80 GB NVIDIA H100/A100 GPU and saturating HBM memory bandwidth. Design and implement an exact, IO-aware tiled attention algorithm in Python/PyTorch (reference kernel logic) that reduces HBM memory from O(N^2) to O(N) while remaining mathematically identical to standard attention.
From patterns to decisions.
Standard Transformer self-attention computes S = QK^T / sqrt(d), P = softmax(S), and O = PV. At sequence length N = 32,768 with 32 attention heads in FP16, materializing S and P in GPU HBM requires 32 * 32,768^2 * 2 bytes = 68.7 GB per layer—exceeding an 80 GB NVIDIA H100/A100 GPU and saturating HBM memory bandwidth. Design and implement an exact, IO-aware tiled attention algorithm in Python/PyTorch (reference kernel logic) that reduces HBM memory from O(N^2) to O(N) while remaining mathematically identical to standard attention.
Implementation & Guardrails (1).
Standard attention writes/reads O(N^2) matrices S and P to HBM, exhausting 80 GB VRAM and bottlenecking on HBM bandwidth.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Materializing S and P is simple to implement via `torch.matmul` + `F.softmax`, but scales quadratically in VRAM. |
Compute S and P memory
B H N N 2 bytes.
Step 2
Compare HBM3 bandwidth (3.35 TB/s) vs Tensor Core compute (989 TFLOPS) — softmax/masking have ~1 FLOP/byte arithmetic intensity.
Alternative 1
Gradient checkpointing reduces layer-to-layer activation memory, but still OOMs if a single layer's N x N matrix exceeds VRAM.
Failure Mode 1
CUDA OutOfMemoryError during long-context prefill or training.
def attention_hbm_bytes(batch: int, heads: int, seq_len: int, dtype_bytes: int = 2) -> int:
# Both S and P (N x N) are materialized in HBM
return 2 * batch * heads * seq_len * seq_len * dtype_bytes
Implementation & Guardrails (2).
Tiled FlashAttention-2 forward pass keeping Q_i in the outer loop, K_j/V_j in the inner loop, and FP32 online softmax accumulators.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Deferring division by l_i to the end of the K/V loop (FlashAttention-2) removes B_r * d divisions per inner step. | |
| Trade-off 2 | Saving L (shape N) instead of P (shape N x N) reduces saved backward state by N / 1. |
Step 1
Partition Q into B_r-row tiles and K, V into B_c-row tiles.
Step 2
Initialize FP32 O_i, l_i, and m_i = -inf for each Q_i tile.
Step 3
Stream K_j, V_j; compute S_ij, update m_new and l_i, rescale O_i by exp(m_i - m_new), and add P_tilde @ V_j.
Step 4
Normalize O_i /= l_i once after the inner loop and store L_i = m_i + log(l_i).
Alternative 1
FlashAttention-3 on Hopper (H100) uses TMA asynchronous copy and WGMMA warp-group overlap to hide softmax latency.
Failure Mode 1
Using FP16 for O_i and l_i accumulation causes severe precision drift when N > 4096.
import numpy as np
def flash_attention_v2_forward(
Q: np.ndarray, K: np.ndarray, V: np.ndarray,
B_r: int = 64, B_c: int = 64, causal: bool = True
) -> tuple[np.ndarray, np.ndarray]:
N, d = Q.shape
scale = 1.0 / np.sqrt(d)
O = np.zeros((N, d), dtype=np.float32)
L = np.zeros(N, dtype=np.float32)
for i_start in range(0, N, B_r):
i_end = min(i_start + B_r, N)
Q_i = Q[i_start:i_end].astype(np.float32)
rows = i_end - i_start
O_i = np.zeros((rows, d), dtype=np.float32)
l_i = np.zeros(rows, dtype=np.float32)
m_i = np.full(rows, -np.inf, dtype=np.float32)
j_limit = i_end if causal else N
for j_start in range(0, j_limit, B_c):
j_end = min(j_start + B_c, N)
K_j = K[j_start:j_end].astype(np.float32)
V_j = V[j_start:j_end].astype(np.float32)
S_ij = (Q_i @ K_j.T) * scale
if causal and j_end > i_start:
q_idx = np.arange(i_start, i_end)[:, None]
k_idx = np.arange(j_start, j_end)[None, :]
S_ij = np.where(k_idx > q_idx, -np.inf, S_ij)
m_ij = np.max(S_ij, axis=1)
m_new = np.maximum(m_i, m_ij)
alpha = np.exp(m_i - m_new)
P_tilde = np.exp(S_ij - m_new[:, None])
l_i = alpha * l_i + np.sum(P_tilde, axis=1)
O_i = alpha[:, None] * O_i + (P_tilde @ V_j)
m_i = m_new
O[i_start:i_end] = O_i / l_i[:, None]
L[i_start:i_end] = m_i + np.log(l_i)
return O, L
Putting Q in the outer.
Putting Q in the outer loop gives each thread block exclusive ownership of O_i, eliminating cross-block atomic writes to HBM.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Q-outer loop parallelizes across (batch * heads * N / B_r), maximizing SM occupancy during prefill/training. |
Step 1
In FA-1 (K/V outer), different thread blocks updated the same O_i rows, forcing HBM atomic/sync overhead.
Step 2
In FA-2 (Q outer), each SM owns O_i in registers/SRAM and writes it to HBM exactly once.
Alternative 1
FlashDecoding splits along K/V when N_q = 1 (decode phase) because Q-outer only spawns batch * heads blocks.
Failure Mode 1
Under-utilizing 132 H100 SMs during batch=1 autoregressive decode without FlashDecoding split-K.
def max_kv_tile_size(sram_bytes: int, d: int, B_r: int = 128) -> int:
# Q_i (FP16) + O_i (FP32) + K_j,V_j (FP16) + S_ij (FP32)
fixed = B_r * d * 2 + B_r * d * 4
per_kv_row = (2 * d * 2) + (B_r * 4)
return max(16, (sram_bytes - fixed) // per_kv_row)
Ring Attention distributes Q, K.
Ring Attention distributes Q, K, V chunks across GPUs in a ring topology and merges partial (O_i, l_i, m_i) blocks via online softmax.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Overlaps NVLink/InfiniBand KV communication with Tensor Core compute, scaling context length linearly with GPU count. |
Step 1
Shard sequence N across P GPUs (each holds N/P tokens of Q, K, V).
Step 2
Compute local FlashAttention while asynchronously P2P-passing K, V blocks around the ring.
Step 3
Merge incoming block (O_block, L_block) into local (O_acc, L_acc) using log-sum-exp rescaling.
Alternative 1
Context Parallelism (Megatron-Core) with all-gather of KV when interconnect bandwidth is high.
Failure Mode 1
Load imbalance under causal masking if blocks are assigned contiguously; mitigated by Zig-Zag / Striped Ring Attention.
def merge_ring_attention(O_acc: np.ndarray, L_acc: np.ndarray, O_new: np.ndarray, L_new: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
L_max = np.maximum(L_acc, L_new)
w_acc = np.exp(L_acc - L_max)
w_new = np.exp(L_new - L_max)
denom = w_acc + w_new
O_merged = (O_acc * w_acc[:, None] + O_new * w_new[:, None]) / denom[:, None]
L_merged = L_max + np.log(denom)
return O_merged, L_merged
PagedAttention stores K/V caches in.
PagedAttention stores K/V caches in non-contiguous fixed-size blocks (e.g., 16 tokens/block) and passes a block_table indirection array to the FlashAttention kernel.
| Choice | What it buys | What it costs |
|---|---|---|
| Trade-off 1 | Eliminates internal KV-cache fragmentation (saving 60–80% HBM) with < 5% kernel overhead for block-table indirection. |
Step 1
Replace contiguous K/V pointer arithmetic with block_table[seq_idx, logical_block_idx] lookup.
Step 2
Gather K_j, V_j pages into SM SRAM on the fly without defragmenting HBM.
Alternative 1
Contiguous pre-allocated max_seq_len KV buffers for static batch sizes.
Failure Mode 1
Small block sizes (< 8 tokens) reduce coalesced HBM memory reads.
def resolve_kv_physical_block(block_table: np.ndarray, seq_id: int, token_pos: int, block_size: int = 16) -> tuple[int, int]:
logical_block = token_pos // block_size
offset = token_pos % block_size
return int(block_table[seq_id, logical_block]), offset
Theory & Tips and Tricks
Practical heuristics & interview traps
- 01Interview anchor: FlashAttention never materializes the N x N attention matrix in slow HBM; it fuses matmul, softmax, and value projection inside fast on-chip SRAM using running max (m) and sum-exp (l) statistics.
- 02Trade-off tip: Q-outer loop parallelizes across (batch heads N / B_r), maximizing SM occupancy during prefill/training.
- 03Watch out for: Load imbalance under causal masking if blocks are assigned contiguously; mitigated by Zig-Zag / Striped Ring Attention.
Flashattention Io Aware Attention — Normal → Load / Fault → Recovery
FlashAttention never materializes the N x N attention matrix in slow HBM; it fuses matmul, softmax, and value projection inside fast on-chip SRAM using running max (m) and sum-exp (l) statistics.
Putting FlashAttention: IO-Aware Exact Attention Together
FlashAttention never materializes the N x N attention matrix in slow HBM; it fuses matmul, softmax, and value projection inside fast on-chip SRAM using running max (m) and sum-exp (l) statistics.
Putting FlashAttention: IO-Aware Exact Attention Together
- Partition Q into B_r-row tiles and K, V into B_c-row tiles.
- Initialize FP32 O_i, l_i, and m_i = -inf for each Q_i tile.
- Stream K_j, V_j; compute S_ij, update m_new and l_i, rescale O_i by exp(m_i - m_new), and add P_tilde @ V_j.
- Normalize O_i /= l_i once after the inner loop and store L_i = m_i + log(l_i).
Interview Readiness Check
Ring Attention distributes Q, K, V chunks across GPUs in a ring topology and merges partial (O_i, l_i, m_i) blocks via online softmax.
Walk through bottlenecks, back-of-the-envelope math, and failure recovery.
Make the trade-off yourself.
Practice Check
Test your understanding
When is ACID Transaction Fundamentals the right default for a production team?
FlashAttention: IO-Aware Exact Attention
FlashAttention never materializes the N x N attention matrix in slow HBM; it fuses matmul, softmax, and value projection inside fast on-chip SRAM using running max (m) and sum-exp (l) statistics.
