How Block Tiling and Incremental Softmax Compute Exact Attention Without Storing Intermediate Matrices

Large language models process long contexts by computing exact attention without storing intermediate N-by-N matrices in accelerator memory. They achieve this through a technique called FlashAttention, which fuses the attention operation into a single GPU kernel by tiling the computation and using an incremental softmax algorithm.[1]

By keeping all intermediate calculations in the GPU's ultra-fast, on-chip SRAM, this approach eliminates the need to read and write massive matrices to the slower High Bandwidth Memory (HBM). The result is a mathematically exact attention output that runs significantly faster and uses a fraction of the memory.[1]

Before this IO-aware approach, scaling the context window of a Transformer model was severely bottlenecked by memory bandwidth. As the sequence length grows, the size of the attention matrix grows quadratically, meaning an 8,192-token sequence requires a 67-million element matrix per attention head.[1]

FlashAttention solved this by restructuring the algorithm to minimize data movement. As the authors of the original 2022 paper noted, "We argue that a missing principle is making attention algorithms IO-aware -- accounting for reads and writes between levels of GPU memory."[1]

The Memory Wall in Standard Attention

The standard attention mechanism computes the relationship between every token in a sequence by multiplying a Query matrix by a Key matrix. This produces a raw score matrix of size N-by-N, which represents the unnormalized attention weights for the entire sequence.[1]

In a naive implementation, this N-by-N matrix is written out to the GPU's HBM. For a standard 8,192-token sequence with a head dimension of 128 in 16-bit precision, this intermediate matrix alone consumes roughly 134 megabytes per head.[1][4]

The algorithm then reads this matrix back from HBM to apply the softmax function, which converts the raw scores into probabilities. This creates a second N-by-N matrix, which is again written to HBM and then read back to multiply against the Value matrix.[1]

This constant shuttling of data back and forth across the GPU's memory bus creates a massive bottleneck. The tensor cores, which perform the actual matrix multiplication, operate orders of magnitude faster than the HBM can supply them with data.[1]

The SRAM vs HBM Divide

To understand why data movement is so expensive, one must look at the memory hierarchy of modern AI accelerators like the NVIDIA A100 or H100. These GPUs feature a massive pool of High Bandwidth Memory, typically 40 to 80 gigabytes, which serves as the main storage for model weights.[1][3]

However, they also contain a much smaller, ultra-fast memory pool called Static Random-Access Memory (SRAM), which is distributed across the streaming multiprocessors. An A100 GPU has only about 20 megabytes of SRAM in total, or roughly 192 kilobytes per multiprocessor.[1]

While the HBM on an A100 offers a bandwidth of 1.5 to 2.0 terabytes per second, the on-chip SRAM delivers a staggering 19 terabytes per second. If an algorithm can keep its working data inside the SRAM, it can run nearly ten times faster.[1]

Standard attention fails to utilize this hierarchy effectively because the N-by-N matrices are far too large to fit into the SRAM. Consequently, the algorithm is forced to spill its intermediate results out to the slower HBM, rendering the operation heavily memory-bound.[1]

Tiling the Attention Matrix

FlashAttention overcomes this memory wall through a technique called block tiling. Instead of computing the entire N-by-N attention matrix at once, the algorithm divides the Query, Key, and Value matrices into smaller blocks that comfortably fit into the GPU's SRAM.[1]

The GPU loads a block of Queries and a block of Keys from HBM into SRAM, computes the attention scores for that specific block, and multiplies the result by the corresponding block of Values. The intermediate N-by-N scores never leave the SRAM.[1]

Once the final output for that block is computed, only the resulting N-by-d matrix is written back to the HBM. By fusing the matrix multiplication, softmax, and value multiplication into a single kernel, FlashAttention drastically reduces the total volume of memory reads and writes.[1]

For an 8,192-token sequence, this tiled approach reduces the HBM traffic from over 545 megabytes per head down to just 8.4 megabytes. This 65-fold reduction in data movement allows the GPU's tensor cores to operate at much higher utilization rates.[1][4]

The Softmax Denominator Problem

While block tiling is a standard optimization in high-performance computing, applying it to the attention mechanism was long considered impossible due to the mathematical properties of the softmax function. Softmax requires normalizing each score by the sum of all exponentiated scores in that row.[1][2]

To compute the true denominator for the softmax function, the algorithm must have access to every element in the row. If the computation is tiled, the GPU only sees a small chunk of the row at a time, making it seemingly impossible to calculate the correct probabilities.[1]

Furthermore, to prevent numerical overflow when exponentiating large numbers, standard safe softmax implementations subtract the maximum value in the row from every element before exponentiation. This traditionally requires a full pass over the data just to find the maximum value.[2]

In a naive tiled implementation, finding the maximum and computing the sum would require writing partial results to HBM and reading them back multiple times. This constant memory swapping would completely defeat the purpose of keeping the data in SRAM.[1][2]

The Incremental Softmax Trick

The breakthrough that made FlashAttention possible was the integration of an online normalizer calculation, an algorithmic trick first published in 2018 by Maxim Milakov and Natalia Gimelshein. In their paper, the authors demonstrated that "Online normalizer calculation reduces the number of memory accesses for the Softmax and Softmax+TopK functions."[2]

The algorithm maintains two running variables in SRAM: the maximum value seen so far, and the sum of the exponentiated values seen so far. When a new block of Keys is processed, the algorithm finds the local maximum for that specific block.[1][2]

If the new block's maximum is higher than the previous running maximum, the algorithm updates the running maximum. Crucially, it then scales the old running sum down by multiplying it by the exponentiated difference between the old and new maximums, before adding the new block's sum.[2][4]

This mathematical equivalence ensures that the final attention output is exactly the same as if the entire row had been processed at once. The model incurs no loss of accuracy or approximation, yet the memory footprint remains entirely bounded by the SRAM capacity.[1][2]

Work Partitioning in FlashAttention-2

While the original FlashAttention algorithm solved the memory bandwidth bottleneck, it still only achieved 25 to 40 percent of the theoretical maximum floating-point operations per second (FLOPs/s) on an A100 GPU. The tensor cores were no longer starved for data, but the work distribution remained suboptimal.[3]

In 2023, the architecture was refined into FlashAttention-2. As the paper explained, "We observe that the inefficiency is due to suboptimal work partitioning between different thread blocks and warps on the GPU, causing either low-occupancy or unnecessary shared memory reads/writes."[3]

The updated algorithm parallelized the attention computation across the sequence length dimension, rather than just across the batch and head dimensions. This increased the occupancy of the GPU, ensuring that all streaming multiprocessors were fed with work even when processing long sequences with small batch sizes.[3]

These kernel-level optimizations yielded a 2x speedup over the original implementation, pushing the hardware utilization to between 50 and 73 percent of the theoretical maximum FLOPs/s. This brought the efficiency of exact attention remarkably close to that of highly optimized, dense matrix multiplication.[3]