---
date: '2026-05-27'
description: block-paged KV cache, virtual-memory-style page tables, hot blocks on device, cold blocks spill to host.
id: attention-paged
modified: 2026-06-06 01:38:36 GMT-04:00
seealso:
- '[[thoughts/Attention|Attention]]'
- '[[thoughts/radix attention|radix attention]]'
- '[[thoughts/vllm]]'
- '[[thoughts/Continuous batching]]'
- '[[@kwon2023efficient]]'
tags:
- ml
- llm
- technical
title: Paged Attention
created: '2026-05-27'
published: '2026-05-27'
pageLayout: default
noCite:
- '@kwon2023efficient'
slug: thoughts/paged-attention
permalink: https://aarnphm.xyz/thoughts/paged-attention.md
generator:
quartz: v4.6.0
hostedProvider: Cloudflare
baseUrl: aarnphm.xyz
full: https://aarnphm.xyz/llms-full.txt
---
idea: borrow virtual-memory paging for the KV cache \[@kwon2023efficient\]. Partition each sequence’s cache into fixed-size **KV blocks** of $B$ tokens, then let a block manager map logical blocks to physical GPU blocks through a page table, the way an OS maps virtual pages to physical frames. Implemented in [[thoughts/vllm|vLLM]] alongside [[thoughts/Continuous batching|continuous batching]]; hot blocks stay on device and cold blocks spill to host.
> Paging drops the need to reserve a contiguous, max-length buffer per sequence: physical blocks live anywhere and the cache grows one block at a time. Internal fragmentation stays under one block, and the external fragmentation a contiguous allocator suffers disappears. See [[lectures/3/infer-0.3.pdf|this workshop]] for more.
For longer contexts, [[thoughts/KV compression|KV compression]] shrinks each block’s footprint further.
Given:
- each block contains KV vectors for fixed number of tokens, denoted as block size $B$.
- Key block $K_j= (k_{(j-1)B+1}, \ldots, k_{jB})$
- Value block $V_j= (v_{(j-1)B+1}, \ldots, v_{jB})$
$$
A_{ij} = \frac{\exp(q_i^{\top} K_j / \sqrt{d})}{\sum_{t=1}^{\lfloor i/B \rfloor} \exp(q_i^{\top} K_t / \sqrt{d})}, \quad o_i = \sum_{j=1}^{\lfloor i/B \rfloor} V_j A_{ij}^{\top}
$$
where $A_{ij}=(a_{i,(j-1)B+1}, \ldots, a_{i,jB})$ is the row vector of attention scores over the $j$-th KV block.
source code
Block size $B = 4$; logical blocks map to scattered physical blocks through the block table, and the dashed cell is a slot reserved for the next token (the last block of a sequence is the only one allowed to sit partly empty).
```jsx imports={Zoomable,PagedKVTable}
```
