Two Papers That Changed LLM Serving: FlashAttention and PagedAttention
Published: Last Updated:
Modern large language models are expensive to run. Not because the math is hard — it’s just matrix multiplies — but because moving data around is slow and memory is scarce. Two papers tackled these problems from completely different angles, and together they form the backbone of how LLMs are served today.
The Two Bottlenecks
To understand why these papers matter, you need to understand two distinct bottlenecks in LLM inference.
The first is compute-side: the attention mechanism itself requires reading and writing enormous intermediate matrices to GPU memory, even though the GPU has plenty of arithmetic throughput to spare. Attention is memory-bandwidth bound, not compute bound.
The second is system-side: when serving many concurrent requests, each one needs a key-value (KV) cache that grows dynamically as tokens are generated. Existing systems pre-allocated contiguous memory for the maximum possible sequence length, wasting 60–80% of GPU memory on fragmentation.
FlashAttention solves the first. PagedAttention solves the second.
FlashAttention: Making Attention IO-Aware
The Problem with Standard Attention
Standard attention computes three steps:
- Score matrix: $S = QK^\top$ (an $N \times N$ matrix)
- Softmax: $P = \operatorname{softmax}(S)$ row-wise
- Output: $O = PV$
Each step materializes a full N×N matrix in GPU HBM (high-bandwidth memory), reads it back, and writes the next one. That’s three round trips to slow memory for matrices that grow quadratically with sequence length. The GPU spends most of its time waiting on memory, not doing math.
The Idea: Fuse Everything, Never Materialize N×N
FlashAttention restructures the computation using tiling. It splits Q, K, V into small blocks that fit in fast on-chip SRAM, computes partial attention results there, and accumulates the output — all within a single fused CUDA kernel. The full N×N score matrix never exists in HBM.
But there’s a catch. Softmax is a global operation — you need the maximum and sum of exponentials across the entire row of scores before you can normalize. If you’re only looking at a tile of keys at a time, how can you compute softmax correctly?
The Online Softmax Trick
This is the algorithmic heart of FlashAttention. It relies on the fact that you can compute softmax incrementally and correct your running estimate as new data arrives.
Say you’ve processed the first tile of keys and computed:
- A running row-wise maximum $m_1$
- A running sum of exponentials $\ell_1$
- A partial output $O_1 = \exp(S_1 - m_1) V_1$
Now a new tile of keys arrives, giving you new partial scores $S_2$ with a new local maximum $m_2$. You combine the old and new statistics:
\[\begin{aligned} m_{\text{new}} &= \max(m_1, m_2) \\ O_1 &\leftarrow O_1\,\exp(m_1 - m_{\text{new}}) \\ \ell_1 &\leftarrow \ell_1\,\exp(m_1 - m_{\text{new}}) \\ e_2 &= \exp(S_2 - m_{\text{new}}) \\ O_{\text{new}} &= O_1 + e_2 V_2 \\ \ell_{\text{new}} &= \ell_1 + \operatorname{rowsum}(e_2) \end{aligned}\]The key identity is simple:
\[\exp(x - m_{\text{old}})\,\exp(m_{\text{old}} - m_{\text{new}}) = \exp(x - m_{\text{new}}).\]Small numeric example: if $m_1=2$ and $m_2=5$, then $m_{\text{new}}=5$ and the rescale factor is $\exp(2-5)=e^{-3}$. So any old contribution like $\exp(x-2)$ is corrected to $\exp(x-2)e^{-3}=\exp(x-5)$ exactly. After all tiles are processed, one final division $O/\ell$ gives you the exact same result as standard attention.
No approximation. No information loss. Just a smarter order of operations.
What This Is Not
It’s worth being precise about what kind of “tiling” FlashAttention uses, because the term appears in several unrelated contexts in computer architecture.
Classical GEMM tiling breaks a single matrix multiply into cache-friendly blocks for data reuse. Hardware features like Intel AMX or NVIDIA Tensor Cores accelerate small tile multiplies directly in silicon. FlashAttention operates at a higher level — it tiles across the entire attention operation (matmul → softmax → matmul) to avoid materializing intermediates. The novelty is fusing across the non-linear softmax, not speeding up any individual matmul. In fact, FlashAttention uses Tensor Cores and optimized GEMM kernels internally for the actual arithmetic.
The Result
The total FLOPs are identical to standard attention. But HBM traffic drops from $O(N^2)$ to $O(N)$, and memory usage follows. In practice this means 2–4× wall-clock speedup and the ability to train with much longer contexts that would previously have run out of memory.
PagedAttention: Borrowing from Operating Systems
A Different Problem Entirely
FlashAttention makes attention fast. PagedAttention makes serving efficient. When you’re running an LLM server handling hundreds of concurrent requests, each request maintains a KV cache — the stored keys and values from all previously generated tokens, needed for autoregressive decoding.
The challenge is that KV caches grow dynamically (you don’t know how long the response will be) but GPU memory requires pre-allocation. Existing systems reserved contiguous blocks for the maximum possible sequence length per request. A request that only generates 20 tokens still occupied memory for 2048. The result was enormous internal fragmentation.
The Insight: Virtual Memory for KV Caches
The PagedAttention paper observed that this problem is structurally identical to one the operating systems community solved decades ago: how to give processes the illusion of contiguous memory when physical memory is fragmented.
The solution mirrors OS virtual memory almost exactly. Instead of storing each request’s KV cache in one contiguous block, PagedAttention divides it into fixed-size blocks (analogous to memory pages). These blocks can be scattered anywhere in GPU memory. A block table (analogous to a page table) maps each request’s logical KV cache positions to physical block locations. The attention kernel is rewritten to look up this mapping when reading keys and values.
Memory is allocated one block at a time, on demand, as new tokens are generated. When a request finishes, its blocks are freed immediately for reuse.
Copy-on-Write and Memory Sharing
The OS analogy goes further. Requests that share a common prefix — say, the same system prompt — can point to the same physical KV blocks. The blocks are shared read-only, and only duplicated (copy-on-write) when one request diverges from another. This is directly analogous to how fork() works in Unix: parent and child share memory pages until one writes to them.
For workloads like chatbots (where every request starts with the same system prompt) or beam search (where candidates share a long common prefix), this sharing dramatically reduces memory consumption.
The Result
Near-zero memory waste. The freed-up memory translates directly into higher batch sizes, which means more concurrent requests, which means 2–4× throughput improvement over previous serving systems. The implementation, vLLM, became the de facto open-source LLM serving engine.
Two Halves of a Whole
These papers are complementary, not competing. FlashAttention answers: given that we must compute attention, how do we do it without wasting memory bandwidth? PagedAttention answers: given that we must store KV caches for many requests, how do we do it without wasting memory capacity?
One operates at the level of a single attention kernel. The other operates at the level of a serving system managing hundreds of requests. vLLM uses FlashAttention-style kernels internally — you get both optimizations simultaneously.
Together, they represent a broader trend in ML systems: the biggest wins aren’t coming from new model architectures or training tricks, but from understanding the hardware and applying well-known systems principles — IO-aware algorithms, virtual memory, paging — to the specific access patterns of modern models. The math hasn’t changed. We just got smarter about where the bytes go.