PagedAttention & continuous batching

1

Concept

KV-cache memory is dynamic. A prompt has known length at admission, but generated length is uncertain. Reserving a contiguous buffer for the maximum possible output wastes unused space. Reserving only current length requires growth, relocation, or many differently sized allocations. Across concurrent requests, these choices create internal and external fragmentation.

PagedAttention, introduced with vLLM in 2023, borrows the virtual-memory idea of fixed-size blocks. A sequence’s logical KV positions are divided into blocks. Physical blocks can live anywhere in the cache pool. A block table maps logical order to physical addresses, and an attention kernel follows that mapping while reading keys and values.

When a sequence grows past the current block, the allocator assigns another free physical block without moving earlier state. Waste is bounded mostly to unused positions in the last block rather than an entire maximum reservation. Block size creates a trade-off: large blocks reduce metadata and improve contiguous access but increase tail waste; small blocks pack tightly but add mapping overhead and less regular memory access.

Indirection also enables sharing. Parallel samples, beam candidates, or requests with a cached common prefix can point to the same read-only blocks. When one branch diverges, copy-on-write allocates a new block for changed positions. Reference counts determine when shared blocks can return to the pool. An ownership bug can leak capacity or expose one request’s state to another.

Allocation alone does not keep hardware busy. A static batch groups requests and runs until every member finishes. If one response is long and the others end early, their lanes remain empty. Continuous batching revisits the batch at iteration boundaries. Finished or canceled sequences leave; waiting sequences enter; active ones advance another token.

The scheduler works under several constraints: available KV blocks, maximum batch tokens, priorities, deadlines, adapter compatibility, and the mix of prefill and decode. It may chunk long prefills to avoid delaying decode. Preemption can evict or swap a low-priority sequence, but recomputation and transfers have costs. Fairness policies prevent bulk workloads from monopolizing cache.

Paged layouts make capacity visible as blocks rather than vague “free GPU memory.” Admission can estimate prompt blocks and a bounded output allowance. Still, optimistic overcommit needs a policy for exhaustion. Rejecting early with a clear error is often safer than admitting every request and failing deep in generation.

Performance depends on the kernel understanding the page table efficiently. Generic attention over copied contiguous tensors can erase the benefit. Prefix hashing, block metadata, and scheduler locks also consume CPU time at high request rates. End-to-end tests should vary prompt lengths, output lengths, cancellation, prefix sharing, and bursty arrivals.

Metrics include free and used blocks, allocation failures, fragmentation or tail waste, prefix hit rate, preemptions, queue delay, active sequences, batch tokens, TTFT, and inter-token latency. Percentiles should be sliced by request class so throughput does not hide starvation.

The durable mental model has two layers. Paged allocation solves where growing state lives: fixed blocks plus a logical directory. Continuous batching solves when each request runs: a batch whose membership changes every decoding step. Together they turn irregular, variable-length conversations into a workload the accelerator can pack efficiently without pretending every sequence has the same shape.