PagedAttention, continuous batching and scheduling

Why it matters

A serving engine's throughput is decided by how many sequences it keeps in flight. Prompt and output lengths differ and KV caches grow with every generated token, so batching and memory management must adapt at every step. Iteration-level batching and paged KV-cache management are the two ideas behind modern engines, and they lead straight to scheduling questions about admission, preemption, fairness and prefix sharing.

Core ideas

From static to iteration-level batching. With request-level batching, a batch runs until its longest sequence finishes: finished slots idle and new requests queue. Orca schedules at the granularity of one model iteration instead: after every step, finished sequences leave and waiting ones join. Token-wise operations (linear layers, normalization) are batched across all sequences, while attention is computed per sequence because lengths differ, which Orca calls selective batching.

Paged KV cache. Reserving a contiguous buffer for each request's maximum length wastes memory on unused reservations and gaps between buffers, which caps the batch size. PagedAttention splits each sequence's cache into fixed-size blocks allocated on demand and records them in a block table, the analogue of a page table; the attention kernel follows the table. Waste is limited to the partly filled last block. Blocks can be shared across sequences with reference counts and copy-on-write, serving parallel sampling, beam search and common prefixes.

When memory runs out. The scheduler admits a request only if enough free blocks exist. If running sequences need more blocks than are free, some must be preempted: swap their blocks to host memory and back, paying transfer bandwidth, or drop them and recompute later, paying another prefill. The vLLM paper serves requests first-come-first-served and evicts all blocks of a sequence group together.

Prefill-decode interference. Adding a long prompt to a batch makes that iteration slow, stalling every decoding sequence and causing inter-token latency spikes. Chunked prefill, as in Sarathi-Serve, splits long prompts into pieces processed alongside decodes under a per-iteration token budget. Disaggregation, as in DistServe, runs prefill and decode on separate GPU pools and transfers the KV cache between them.

Prefix caching. When requests share an exact prefix (system prompt, conversation history, agent scaffolding), their KV blocks can be identified by content and reused, skipping that part of prefill. Cached blocks compete with active requests for memory and are evicted under pressure.

Common misconceptions

• "Continuous batching means bigger batches." It means batch membership changes every iteration; batch size is still capped by KV memory and latency targets.
• "PagedAttention makes the attention math faster." Its main gain is memory efficiency, which allows more concurrent sequences; following block tables adds some kernel overhead.
• "Preemption is cheap." Swapping costs host-device bandwidth and recomputation repeats prefill; either shows up in tail latency.
• "Prefix caching always helps." It needs exact shared prefixes at block granularity and spare memory to keep them.

How to approach it

Simulate first: a toy scheduler with a fixed number of KV blocks, requests with random prompt and output lengths, and both static and iteration-level batching; compare throughput and waiting time. Then run a real engine, vary its batching limits, toggle chunked prefill and prefix caching, and measure latency percentiles under open-loop load. When asked to design a scheduler, state the objective (throughput, SLO attainment, fairness), the admission rule and the preemption policy before details.