PagedAttention and the vLLM serving model

Summary

PagedAttention resolves logical KV positions through per-sequence tables pointing to fixed-size physical blocks. This permits scattered allocation and compatible-prefix sharing without changing the intended logical attention sequence. It reduces allocation waste relative to some contiguous reservation policies, but does not eliminate tail waste or guarantee higher throughput.

The mechanism

For token position $p$ and block capacity $b$, lookup is:

Allocate blocks as sequences grow; the kernel gathers K/V in logical order with the same masks and position conventions. For the pictured tables, use hypothetical $b=4$, ten valid positions per request, and shared positions zero through seven. A has table [7,1,5]; B has [7,1,3]. Position nine has logical block two and offset one: A reads P5[1], B reads P3[1].

Six logical blocks alias four physical blocks, reserving sixteen token slots rather than twenty-four without sharing. There are twelve distinct valid KV positions: eight shared and two private per request. Private tails still waste four slots total; sharing reserves sixteen slots, not twelve.

Prefix sharing

After A’s outstanding uses finish, release P5 and decrement P7/P1 reference counts from two to one. B’s prefix must remain valid; a shared block is freed only after all live owners and in-flight uses are gone. Matching visible prompt text is insufficient: tokenization, model/adapters, positions, and relevant cache state must be compatible.

Append into a Shared Partial Tail

New task: Two requests share six positions in four-token blocks, then diverge.

Picture and change: Copy the two valid entries of shared logical block one before A appends at offset two. Redirect A’s table entry and decrement the old block’s reference count before its private write.

Check: B’s position six remains absent and B’s existing bytes are unchanged.

Use when: A shared writable tail branches; directly mutating the shared block would corrupt isolation.

Use Larger Blocks

New task: Change a unique ten-token request from four-token to eight-token blocks.

Picture and change: Rebuild table indexing and allocator units together without changing logical positions.

Check: Reserved slots rise from twelve to sixteen; tail waste rises from two to six. Generally, one unshared sequence wastes $\lceil S/b\rceil b-S\le b-1$ slots.

Use when: Measured lookup costs justify additional tail waste; fewer table entries alone do not establish faster execution.