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. One criterion draws the line. Every operation that consumes model parameters batches token-wise, without any notion of which request a token came from, because batching those is exactly what amortizes the parameter reads. Attention is not associated with any model parameters, so batching it has no such benefit: there is no loaded weight to reuse across requests. Orca therefore inserts a Split before Attention, runs Attention on each request’s own keys and values separately, then Merges the results back into one tensor so the rest of the layer can go on batching. That is worth restating as the design principle it is: the one operation that cannot be batched across ragged requests is also the one with nothing to gain from it. 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.
What Orca leaves unsolved is where those per-request keys and values live. Its scheduler reserves memory the first time it admits a request, reading the request’s max_tokens attribute and reserving that many slots up front, a slot being the memory for one token’s attention key and value, with admission decided by comparing the running reservation against a pool size the operator tunes. The reservation is not careless. It is what guarantees an admitted request can always allocate room for its next token, which is what keeps the scheduler out of a deadlock where no request in the pool can proceed. But a guarantee sized to the maximum is paid for at the maximum, for the request’s whole lifetime, whether or not it ever gets there.
That reservation is the target of the next technique, and the PagedAttention paper names Orca as one of the two existing systems whose fragmentation it profiled. Storing a request’s KV cache in contiguous space means pre-allocating a chunk sized to the request’s maximum length, 2048 tokens in the paper’s example, which wastes memory in three distinct ways: the space reserved for future tokens the request has not reached, internal fragmentation from the tokens it will never emit, and external fragmentation between chunks that were each sized differently. The paper is precise that even foreknowledge of the final length would not fix it, because the chunk is held for the request’s whole lifetime and no shorter request can borrow the unused part. Profiling found only 20.4 to 38.2 percent of allocated KV cache memory actually holding token state. Paged attention fixes this by dividing the KV cache into fixed-size blocks that can live anywhere in memory, addressed through a per-request block table the way an OS page table addresses physical pages: blocks are pages, tokens are bytes, and requests are processes. 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. Each physical block carries a reference count, and a sequence that needs to write into a block someone else is still reading gets a private copy first, the same copy-on-write a kernel performs when a process forks. How much that sharing is worth depends on how much structure the decoding algorithm hands the runtime: on the paper’s Alpaca measurements it saves 6.1 to 9.8 percent of memory under parallel sampling, where only the prompt is common, and 37.6 to 55.2 percent under beam search, where the candidates share far more than the prompt.
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 relative to vLLM, and up to 5.6 times in end-to-end serving capacity for Falcon-180B served with pipeline parallelism.
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.
What the caller hands the engine#
None of this scheduling is visible in the API a caller uses. vLLM’s own offline batching example is a list of prompts, one sampling configuration, and a single call:
from vllm import LLM, SamplingParams
# Sample prompts.
prompts = [
"Hello, my name is",
"The president of the United States is",
"The capital of France is",
"The future of AI is",
]
# Create a sampling params object.
sampling_params = SamplingParams(temperature=0.8, top_p=0.95)
def main():
# Create an LLM.
llm = LLM(model="facebook/opt-125m")
# Generate texts from the prompts.
# The output is a list of RequestOutput objects
# that contain the prompt, generated text, and other information.
outputs = llm.generate(prompts, sampling_params)
# Print the outputs.
for output in outputs:
prompt = output.prompt
generated_text = output.outputs[0].text
print(f"Prompt: {prompt!r}")
print(f"Output: {generated_text!r}")
if __name__ == "__main__":
main()Nothing in that program names a batch. There is no batch size, no padding, and no grouping of the four prompts into anything. The quickstart describes what generate does with them: it adds the prompts to the engine’s waiting queue and then runs the engine. The list is a queue, and which of its members share an iteration is decided by the scheduler after every step. What the caller does own per request is SamplingParams, which travels with the request through whatever batches the scheduler assembles.
What the operator controls is the shape the scheduler is allowed to build. vLLM caps a single iteration two ways: max_num_batched_tokens is the maximum number of tokens processed in one iteration and max_num_seqs the maximum number of sequences. Sarathi-Serve’s chunked prefill is a flag on top of that pair: enable_chunked_prefill lets prefill requests be chunked against the tokens left over in max_num_batched_tokens, and long_prefill_token_threshold sets the prompt length past which a request counts as long. Order of service is scheduling_policy, either fcfs, requests handled in order of arrival, or priority, where a lower value is handled earlier and arrival time breaks ties. SGLang exposes the same decisions under its own names, defaulting to fcfs among seven policies, with a conservativeness float its documentation suggests raising when requests are being retracted frequently.
Those caps exist because the scheduler admits work against a KV cache budget it cannot know in advance, so it can over-commit. vLLM’s tuning guide documents what happens then: when cache space is insufficient for all batched requests, the engine preempts requests to free space and recomputes them when space returns, logging a warning that names the sequence group, the recompute preemption mode, and a cumulative preemption count. Every remedy the guide lists is a budget adjustment: raise gpu_memory_utilization, lower max_num_seqs or max_num_batched_tokens, or raise tensor or pipeline parallel size so weights consume less memory per GPU. Preemption is the visible edge of continuous batching: the scheduler is not filling slots, it is betting on how much cache the batch will end up needing.
The same loop in TensorRT-LLM#
vLLM and SGLang are not the only implementations of this loop. NVIDIA’s TensorRT-LLM wraps the same structure behind an LLM class that spawns a dedicated executor process on each rank, running a continuous background loop built from four named parts: a scheduler that decides which active requests are ready at each step, a KV cache manager that allocates and frees the cache, a model engine that runs the model on the GPU, and a sampler that turns logits into tokens under strategies such as greedy, top-k, top-p, or beam search. Every iteration fetches new requests from an internal queue, asks the scheduler which are ready, coordinates with the cache manager to allocate the blocks they need, invokes the model engine for one forward pass, then finalizes anything that finished. That is iteration-level scheduling written out as five steps, with the cache manager a first-class participant rather than an allocator buried inside the model.
Writing the loop out that way exposes where its time actually goes, and it is the host. TensorRT-LLM’s overlap scheduler launches the GPU work for step n+1 without waiting for the CPU to finish processing step n’s results, so stop-criteria checks and response updates for one batch run while the GPU is already executing the next; it costs one extra decoding step and is enabled by default. Kernel launch overhead is attacked with CUDA graphs, and because a captured graph is tied to a batch size, TensorRT-LLM pads an incoming batch up to the nearest larger captured size rather than falling back to eager execution. NVIDIA reports that padding as up to a 22 percent end-to-end throughput increase on certain models and hardware, a striking number for an optimization whose method is computing deliberately wasted tokens.
Where the three engines differ#
Sharing a loop does not make three projects interchangeable, and each states a different ambition in its own repository. vLLM calls itself a fast and easy-to-use library for LLM inference and serving, originally developed in the Sky Computing Lab at UC Berkeley and now built and maintained by dozens of academic institutions and companies across more than two thousand contributors. What that community buys is reach. The repository claims support for over 200 model architectures on Hugging Face and for NVIDIA, AMD and Intel GPUs alongside x86, ARM and PowerPC CPUs, with hardware plugins covering Google TPUs, Intel Gaudi, IBM Spyre, Huawei Ascend, Rebellions NPU and Apple Silicon, and it serves them all behind an OpenAI-compatible API server plus Anthropic Messages and gRPC endpoints. The same breadth shows up one level down, in a menu of kernel backends rather than a single implementation: FlashAttention, FlashInfer, TRTLLM-GEN, FlashMLA and Triton for attention, and CUTLASS, TRTLLM-GEN and CuTeDSL for GEMM and MoE. vLLM is the engine whose distinguishing bet is that one abstraction should run everywhere and dispatch to whatever is fastest underneath, which is also why this chapter reaches for its argument names whenever it needs a concrete knob to point at.
SGLang makes the opposite bet, and its paper says so as a criticism of the field: existing engines, vLLM and TensorRT-LLM among them, have been optimized for latency and throughput without direct knowledge of the workload, which makes them general and robust but leaves real inefficiency on any particular workload. Its answer is to acquire that knowledge rather than work around its absence, which is why the system ships as a frontend language and a co-designed backend runtime instead of a runtime alone. RadixAttention and the compressed finite state machine are both consequences of that co-design: neither optimization is available to a runtime that sees an undifferentiated stream of independent requests rather than a program with multiple calls and shared prefixes. The repository now leads with the runtime half, describing a high-performance serving framework for language and multimodal models, and reports a role no paper anticipated: a rollout backend for reinforcement learning post-training, with native integrations into frameworks including AReaL, slime and verl, running on more than 400,000 GPUs.
TensorRT-LLM is the one most likely to be misremembered, because its name still points at an ahead-of-time compiler and an opaque built artifact. That is not what the repository describes. Its news log records the project becoming fully open source with development moved to GitHub, it ships under Apache 2, and the current description is of a library architected on PyTorch, offering a high-level Python LLM API and designed to be modular and easy to modify: its PyTorch-native architecture is presented as the thing that lets developers experiment with the runtime, and several popular models are pre-defined and customizable in native PyTorch code. What distinguishes it is not a build step but provenance. It is the vendor’s own engine, carrying custom kernels for attention, GEMMs and MoE together with runtime-level optimizations such as prefill-decode disaggregation and wide expert parallelism, and its API is positioned to hand off to NVIDIA Dynamo and the Triton Inference Server. The engine most people picture as a compiler is a PyTorch library whose real advantage is that the kernels arrive from the same organization as the silicon.