Why does naïve attention become slow at long context?

Naïve attention scales quadratically with sequence length N. For a large N (e.g., 8,192), the N x N score matrix is too large to fit in SRAM, forcing the system to perform multiple HBM round-trips. This makes the operation fully bandwidth-limited, where the time spent moving data between HBM and the GPU cores dwarfs the actual compute time. FlashAttention solves this by tiling K and V through SRAM, reducing HBM traffic to O(Nd) and shifting the bottleneck from memory bandwidth to compute.