PagedAttention

PagedAttention is an attention algorithm that stores a sequence’s keys and values in fixed-size non-contiguous blocks, addressed through a per-request block table, so KV-cache memory can be allocated, shared, and freed at block granularity.

Why It Exists

Autoregressive serving is memory-bound: KV cache grows with every generated token, and pre-reserving contiguous chunks wastes 60-80% of KV memory through reserved, internal, and external fragmentation. PagedAttention makes KV memory behave like OS virtual memory so waste is bounded and freed blocks are reusable.

How It Works

The sequence’s KV cache is partitioned into blocks of $B$ tokens each (default 16). A logical block $j$ holds $K_j$ and $V_j$ and maps through the request’s block table to an arbitrary physical block. Attention computes blockwise:

\[A_{ij} = \frac{\exp(q_i^\top K_j / \sqrt{d})}{\sum_{t=1}^{\lceil i/B \rceil} \exp(q_i^\top K_t \mathbf{1}/\sqrt{d})}, \quad o_i = \sum_{j=1}^{\lceil i/B \rceil} V_j A_{ij}^\top.\]

The kernel fetches each block separately, and a new physical block is allocated only when the previous one fills — bounding per-request waste to at most one block.

Tradeoffs

Block size trades kernel parallelism against fragmentation: larger blocks read more positions in parallel but waste more on short sequences. The kernel pays extra overhead for block-table indirection and variable sequence lengths.

Common Confusions

PagedAttention vs. RadixAttention: PagedAttention pages memory at fixed block size and shares via reference counts; SGLang’s RadixAttention additionally organizes cached prefixes in a radix tree for finer-grained reuse.
PagedAttention vs. FlashAttention: FlashAttention optimizes the attention compute (tiling, IO); PagedAttention optimizes the KV storage (paging). They are orthogonal and both appear in vLLM.

Where It Appears

vLLM: PagedAttention Serving Framework — The original paper insight: memory waste analysis, block tables, copy-on-write, scheduling.
vLLM Continuous Batching — How paged KV-slot allocation gates per-iteration admission in the V1 scheduler.
vLLM Block Table Management — The V1 code stack that implements paging: block pool, per-group managers, prefix caching, and worker block-table tensors.
Grouped-Query Attention in Llama 2 — Explains why Llama 2 uses grouped-query attention for its 34B and 70B models: it cuts KV-cache pressure like multi-query.
Multi-Query Attention: One Write-Head is All You Need — Replaces per-head key/value projections with a single shared K/V pair across all attention heads, eliminating the heads.
FlashAttention-2: Better Parallelism and Work Partitioning — FlashAttention-2 algorithm: reduced non-matmul overhead, sequence-parallel attention blocks, warp-level work partitioning, and.
FlashAttention-4: Blackwell Attention Kernel Co-Design — FlashAttention-4 algorithm and kernel-pipeline techniques for faster exact attention on NVIDIA Blackwell GPUs.
FlashAttention: IO-Aware Exact Attention — Original FlashAttention algorithm: tiled exact attention, online softmax, recomputation, IO complexity, block-sparse extension.
The Transformer: Attention Is All You Need — The foundational paper that introduced the Transformer architecture, dispensing with recurrence and convolutions entirely in.
DSpark: Confidence-Scheduled Speculative Decoding — DeepSeek’s DSpark speculative decoding framework, combining semi-autoregressive draft generation with hardware-aware confidence.
Sarathi: Chunked Prefills for Efficient LLM Inference — Sarathi improves LLM serving by splitting prefills into compute-sized chunks and piggybacking decode tokens on them to raise.
SGLang: Structured Language Model Programs — SGLang framework architecture, programming model, runtime optimizations, and evaluation results for efficient structured LLM.
Triton in Practice: How vLLM and vllm-ascend Use Triton — A codebase-driven tour of Triton kernel development in vLLM (NVIDIA GPU) and vllm-ascend (Ascend NPU), covering infrastructure.
vLLM — vLLM serving framework pages: PagedAttention paper, continuous batching, and Kimi K3 code.
vLLM Architecture and Code Organization Overview — A top-down code-reading map of the vLLM repository at commit a0c092ee72c0: how the V1 serving engine, model executor, config.
DeepSeek-V4: Million-Token Context via Hybrid Compressed Attention — DeepSeek-V4 introduces hybrid Compressed Sparse Attention (CSA) and Heavily Compressed Attention (HCA), Manifold-Constrained.

KV Cache — The stored keys/values that PagedAttention pages.
Block Table — The logical-to-physical mapping PagedAttention relies on.
Continuous Batching — The iteration-level scheduling that consumes paged capacity.