1 of 6

Scheduling and continuous batching

Batching multiple requests together lets an engine amortize the cost of streaming model weights through memory across all of them at once, which is exactly the decode-time bottleneck described in the KV cache. But requests do not arrive together, and they do not finish together: a naive scheme that groups requests into a fixed batch and waits for every member to finish either stalls new requests in a queue or pads short sequences out to the length of the longest one in the batch, wasting both compute and memory. Production engines instead run continuous batching, which the vLLM paper describes as iteration-level scheduling: after each step of the model, completed sequences are removed from the batch and new ones are added, so a fresh request only waits for a single iteration rather than for the whole batch to drain.

The idea has a specific origin. Orca, the OSDI 2022 system that introduced iteration-level scheduling, framed the failure of earlier servers as an inflexible scheduling mechanism that cannot change the batch being processed: requests that finish earlier than the rest of their batch cannot return to the client, and new arrivals wait until the current batch completely finishes. Orca’s scheduler instead invokes the execution engine to run only a single iteration of the model at a time. Applying batching and iteration-level scheduling to a Transformer at the same time required a second technique, selective batching, which applies batching only to a selected set of operations, since the requests sharing an iteration no longer line up the way a fixed batch does. On a GPT-3 175B model, the combination gave Orca a 36.9 times throughput improvement over NVIDIA FasterTransformer at the same level of latency.

Continuous batching alone does not solve the memory side of the problem. Each request’s KV cache grows one token at a time and its final length is not known when the request starts, so systems that store it as one contiguous tensor have to reserve space for the worst case up front. That reservation is why prior serving systems left most of their KV cache memory unused: profiling in the PagedAttention paper found only 20.4 to 38.2 percent of allocated KV cache memory actually held token state, the rest lost to padding for an unreached maximum length and to fragmentation between differently sized reservations. Paged attention fixes this by dividing the KV cache into fixed-size blocks that can live anywhere in memory, addressed indirectly the way an OS page table addresses physical pages. Because every block is the same size, allocating one on demand as a sequence grows leaves no external fragmentation, and because blocks are addressed indirectly, several sequences that share a prefix, such as the beams in a beam search, can point at the same block instead of duplicating it.

Request-level batching versus continuous batching. The same four requests on three batch slots, one column per model step. A fixed batch holds every slot until its longest member finishes, so B's and A's slots sit idle and D waits for the drain. Continuous batching admits D the step after B ends and finishes the same work in eight steps instead of eleven.Illustrative numbers

Mixing phases inside one batch creates a tension continuous batching does not resolve on its own. A prefill iteration processes the whole prompt in parallel, so it has high latency but saturates GPU compute; a decode iteration produces a single token per request, so it is fast but leaves compute idle. Interleaving the two means every prefill admitted into a running batch delays the decodes sharing it, which makes high throughput and low latency hard to achieve together. Sarathi-Serve resolves this with chunked prefills and stall-free schedules: a prefill is split into near equal sized chunks, and new requests join the batch without pausing ongoing decodes, while the resulting uniform batches also reduce the iteration imbalance that causes pipeline bubbles. Under tail latency constraints this raised serving capacity 2.6 times for Mistral-7B on a single A100 and up to 5.6 times for Falcon-180B served with pipeline parallelism, both relative to vLLM.

The scheduler can also be smarter about what it throws away. In existing engines the KV cache of a request is discarded once the request completes, so two calls that share a long prefix, a system prompt, a few-shot template, or the earlier turns of a chat, each pay to recompute it. SGLang’s RadixAttention instead maintains an LRU cache of the KV cache for all requests within a radix tree, so matching, insertion, and eviction are efficient and a cache-aware scheduling policy can steer requests toward their cached prefixes. On workloads built from multi-call programs, agents, reasoning chains, and multi-turn chat, this and the runtime’s other optimizations reach up to 6.4 times higher throughput than existing inference systems.

Source

Iteration-level scheduling, PagedAttention, and the throughput and memory-waste figures above are from Efficient Memory Management for Large Language Model Serving with PagedAttention (Kwon et al., 2023), the vLLM paper. Iteration-level scheduling, selective batching, and the 36.9× figure from Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu et al., OSDI 2022). Chunked prefills, stall-free scheduling, and the capacity figures from Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve (Agrawal et al., OSDI 2024). RadixAttention and the 6.4× figure from SGLang: Efficient Execution of Structured Language Model Programs (Zheng et al., 2024). More engines and the papers they build on are in Scheduling and continuous batching and KV cache systems in the reading list.