Describe how continuous batching interacts with the KV cache

**Continuous batching** is the request-level scheduling pattern that powers every modern LLM serving stack. ### Static batching (the old way) A fixed set of N requests starts together. Every decode iteration runs the model on all N in lockstep. The batch finishes when the slowest request hits EOS or max tokens. Until then, slots for requests that finished early sit idle, consuming GPU memory but producing nothing. KV-cache lifetime: tied to the slowest request. If 7 requests finish at 50 tokens but one runs to 2000, the cache for all 7 stays alive (or gets wastefully shifted) until the long one finishes. Memory utilization is awful. ### Continuous batching (the modern way) The scheduler picks the active batch fresh at every iteration. Finished requests leave immediately and free their KV. Newly arrived requests can join at the next iteration. The batch composition changes step by step. KV-cache lifetime: tied to each individual request, not to the batch. A request's KV is allocated when it joins, written each decode step, and freed the instant it finishes. ### Why PagedAttention is the natural pairing If every request has its own KV with independent lifetime, you need cheap per-request allocation and freeing. PagedAttention's paged allocation does exactly that: fixed-size physical blocks in a pool, allocate on demand per request, free immediately on request completion. Without paging you would need contiguous per-request buffers, which fragment terribly under continuous batching. ### Throughput win The GPU never idles waiting for the slowest sequence. Short requests free their pages quickly, long requests keep streaming, the scheduler keeps the batch as full as memory allows. Aggregate throughput is 5-10x higher than static batching on realistic mixed-length workloads.

In **static (request-level) batching**, a fixed set of N requests starts together, runs decode steps in lockstep, and finishes together. The slowest request pins the batch. The KV cache for the whole batch lives for the duration of the longest sequence, leaving GPU memory occupied by finished sequences and idle slots. **Continuous batching** (also called iteration-level batching, popularized by Orca and shipped in vLLM, TGI, TensorRT-LLM) schedules at the iteration granularity. At every decode step the scheduler picks the set of active requests; finished requests leave the batch immediately and freshly arrived requests can join the next step. The batch composition changes step by step. **For the cache, each request owns its own KV state.** When a request finishes (hits EOS or max tokens), its KV pages are freed right then and become available for the next request to allocate. **Paged KV (PagedAttention) is the natural pairing**: the cache is split into fixed-size pages with a per-request page table, so allocating and freeing per request is cheap and avoids the fragmentation a contiguous per-request buffer would cause. The scheduler maintains a free pool of physical blocks; admit a request when free_blocks >= initial_need; release blocks the moment the request completes. **Throughput rises** because the GPU never idles waiting for the slowest sequence in a fixed batch. Short requests free their pages quickly, long requests keep streaming, and the scheduler keeps the per-step batch as full as memory allows. Production deployments report 5-10x throughput improvements on mixed-length workloads.