TL;DR: Standard attention materializes the full N×N scores matrix in slow GPU memory (HBM), so for long sequences it is bottlenecked by memory traffic, not compute. FlashAttention computes attention in tiles that stay in fast on-chip SRAM, using online softmax to avoid ever writing the full matrix to HBM. It is exact (same result), just IO-aware, giving large speedups and O(N) memory instead of O(N²).
How to approach it
Establish the key fact first: GPUs have abundant compute but limited memory bandwidth, and attention's bottleneck is the latter. Then explain what standard attention wastes (round-trips of the N×N matrix to HBM) and how FlashAttention removes them while staying mathematically identical. The distinction that earns the offer is exact versus approximate.
A strong answer
Why memory-bound. A GPU has a steep memory hierarchy: small, very fast on-chip SRAM and large, slower HBM. Standard attention computes S = QKᵀ (an N×N matrix), writes it to HBM, reads it back to apply softmax, writes the result, reads it again to multiply by V. For sequence length N, that N×N matrix dominates: the operation moves O(N²) data to and from HBM, and since HBM bandwidth is the constraint, the GPU sits idle waiting on memory while its compute units are underused. So attention is memory-bandwidth-bound, and its memory footprint is O(N²), which is what blows up for long context.
What FlashAttention does. It restructures the computation to be IO-aware: tile Q, K, V into blocks small enough to fit in SRAM, and compute attention block by block entirely on-chip, never materializing the full N×N matrix in HBM. The challenge is that softmax needs a global normalization over the whole row, but FlashAttention uses online softmax (a running max and running sum, rescaling partial results as new blocks arrive) so it accumulates the correct softmax incrementally without seeing the whole row at once. The output is exact, identical to standard attention, not an approximation. By fusing the QKᵀ, softmax, and ·V steps into one kernel that keeps intermediates in SRAM, it slashes HBM traffic, runs much faster, and uses O(N) memory instead of O(N²), which is what enables long context.
The line that signals depth: this is not a cheaper approximation of attention (like sparse or linear attention); it computes the same function more cleverly with respect to the memory hierarchy.
Key takeaways
- For long N, attention is memory-bandwidth-bound, not compute-bound; the N×N HBM round-trips are the cost.
- FlashAttention is exact, not an approximation: same output, fewer HBM trips via tiling and kernel fusion.
- Online softmax (running max and normalizer) is what makes block-wise computation correct without the full row.
- It turns O(N²) memory into O(N), which is what makes long context feasible.
What interviewers probe next
- "Exact or approximate?" Exact. Sparse/linear/sliding-window attention approximate to cut the O(N²); FlashAttention keeps full attention but removes the IO waste.
- "What is online softmax?" Compute softmax incrementally with a running max and running normalizer, rescaling accumulated outputs as each block is processed, so you never need the full row in memory.
- "Where does the speedup come from if FLOPs are similar?" From eliminating HBM round-trips (kernel fusion plus tiling keep data in SRAM); the bottleneck was memory traffic, not arithmetic.
- "How does this relate to long-context serving?" O(N) memory and IO efficiency make long sequences feasible; combine with KV-cache tricks (PagedAttention) for inference.
Common mistakes
- Saying attention is compute-bound; for long N it is memory-bandwidth-bound.
- Calling FlashAttention an approximation; it is exact.
- Forgetting the online-softmax mechanism that makes block-wise computation possible.
- Confusing it with sparse/linear attention, which change the math to cut O(N²).