The kernels under everything: flash and paged attention

Attention was a memory problem, not an arithmetic one

The naive implementation of attention computes a score matrix of size sequence length squared, writes it to memory, applies softmax, reads it back, and multiplies by the values. At 8,192 tokens that intermediate matrix is 67 million entries per head per layer. Writing and re-reading it dominates the cost entirely: the multiplications themselves are a small fraction of the time.

FlashAttention never materialises that matrix. It processes the sequence in tiles small enough to live in the GPU’s fast on-chip memory, computing partial softmax results and combining them with a running normalisation as it goes. The output is mathematically identical; the memory traffic falls by an order of magnitude.

Two consequences that matter to you directly. Memory use becomes linear in sequence length instead of quadratic, which is what made long context practical at all. And quantised KV cache kernels in llama.cpp are generally built on top of it, which is why --cache-type-k q8_0 requires --flash-attn and is silently ignored without it.

Turn it on:

llama-server -m model.gguf --flash-attn -c 32768 \
  --cache-type-k q8_0 --cache-type-v q8_0

It is a strict improvement where available, so the only reason not to use it is a backend that lacks the kernel for your hardware.

PagedAttention: the cache as virtual memory

The second idea addresses a different waste. A conventional implementation allocates a contiguous KV cache for each sequence, sized for the maximum it might reach. A request that could grow to 32,768 tokens reserves that much, whether it uses 200 tokens or all of it. On a 24 GB card that limits you to a handful of concurrent sequences regardless of what people actually send.

PagedAttention stores the cache in fixed-size blocks (typically sixteen tokens) with a block table mapping each sequence’s logical positions to physical blocks. Blocks are allocated as the sequence grows and freed when it ends. The analogy to operating-system paging is exact, down to the block table being a page table.

The gains:

• Almost no internal fragmentation. At worst you waste part of one block per sequence rather than the whole unused reservation.
• Many more concurrent sequences on the same card. This is most of vLLM’s throughput advantage.
• Sharing becomes possible. Two sequences with the same prefix can point at the same physical blocks, with copy-on-write when they diverge. That is the machinery prefix caching runs on, and it is also what makes parallel sampling from one prompt cheap.

The kernel is a real part of your performance

A point worth making explicitly, because it surprises people who think of a model file as the thing that determines speed. The same weights, the same quantisation and the same card can differ several-fold depending on which kernel reads them.

A 4-bit model loaded with a kernel that dequantises each tensor to fp16 before multiplying pays fp16 memory traffic plus unpacking work, and can be slower than fp16. The same file with a fused kernel (Marlin and its relatives) reads packed 4-bit data and multiplies directly, and is several times faster. When somebody reports that quantisation gave them no speed-up, this is nearly always the explanation, and the fix is a flag or a newer engine rather than a different quant.

Similarly, engines choose among several attention backends at startup depending on the card, the head dimension and the data type. When one is unavailable it falls back silently to a slower path. Reading the startup log for the backend it selected is a thirty-second check that occasionally explains everything.

What you actually do with this

You will not write these kernels. What the knowledge buys you is diagnostic:

1. Enable flash attention wherever it exists; check the log confirms it.
2. If quantised cache flags appear to do nothing, flash attention is probably off.
3. If a quantised model is not faster than fp16, look for the fused kernel rather than blaming the format.
4. If concurrency is far below what memory suggests should fit, the engine is reserving worst-case cache per sequence rather than paging it.
5. Read the startup log. Engines announce which attention backend and which quantisation kernel they chose, and that line is the difference between a supported fast path and a fallback.

Each of those is a two-minute check that can be worth more than a hardware upgrade.