Continuous Batching and Request Scheduling in Production LLM Serving: Comparing Orca, FastServe, Sarathi-Serve, and vLLM Architecture, Preemption Policies, Chunked Prefill Interleaving, and TTFT-TBT Trade-Offs

Autoregressive large language model serving exhibits a fundamental architectural tension between compute utilization and latency guarantees. Standard deep learning inference pipelines rely on static request-level batching, where incoming queries are grouped into a fixed tensor, executed across forward passes until all sequences finish, and evicted simultaneously. In transformer-based text generation, static batching collapses serving efficiency. Because sequence lengths vary widely and token generation ceases non-deterministically at an end-of-sequence (EOS) token, static batches suffer from severe padding bubbles, wasting 50% to 80% of peak accelerator compute. Furthermore, new requests arriving while a batch is executing are blocked until every sequence in the active batch completes.

Modern LLM inference engines solve this bottleneck through iteration-level scheduling, commonly known as continuous batching or in-flight batching. By decoupling batch composition from request lifecycles, schedulers operate at the granularity of individual forward passes. This architectural shift, formalized in systems like Orca at USENIX OSDI 2022, FastServe at USENIX OSDI 2023, Sarathi-Serve at USENIX OSDI 2024, and modern engines such as vLLM and SGLang, forms the runtime foundation of high-throughput production serving.

Continuous Batching and Request Scheduling Architecture

The Structural Failure of Static Request Batching

The execution profile of transformer inference comprises two distinct computational phases:

The Prefill Phase (Prompt Processing): The model processes all input prompt tokens in parallel. This phase is compute-bound, exhibiting high arithmetic intensity governed by matrix-matrix multiplications (GEMM).
The Decode Phase (Autoregressive Generation): The model generates one token per sequence per iteration. Because each step loads the entire model weight tensor from high-bandwidth memory (HBM) to compute a single output vector per request, decoding is memory-bandwidth bound, governed by matrix-vector operations (GEMV).

When serving heterogeneous workloads under static batching, three structural failure modes emerge:

Padding and Early-Exit Bubbles: If request A generates 20 tokens and request B generates 500 tokens, static batching forces request A to occupy allocated memory slots and padding overhead for 480 empty iterations.
Head-of-Line Queuing Delay: Incoming requests must wait in an external queue until the longest active sequence finishes, causing Time to First Token (TTFT) to spike during high load.
Underutilized Memory Bandwidth: Batches containing few active decoding sequences underutilize GPU memory bus bandwidth, driving down effective tokens per second per dollar.

Orca and Iteration-Level Scheduling

The continuous batching paradigm was established by Orca (Yu et al., OSDI 2022). Orca abandoned request-level execution by restructuring the inference engine into an iteration-level state machine.

Instead of running a multi-step loop within a single framework call, the serving engine executes a single forward pass per iteration across an actively managed batch pool. After every forward iteration:

Requests that emit an EOS token or reach their maximum generation length are immediately evicted from the batch.
Resources (such as key-value cache allocations) associated with finished requests are reclaimed.
Pending requests in the waiting queue (either new prefills or previously preempted decodes) are dynamically injected into the batch for the subsequent iteration.

To make continuous batching mathematically and computationally viable across heterogeneous sequences, Orca introduced selective batching. In a standard transformer layer, linear projections (Q, K, V projections and MLP feed-forward networks) do not require cross-token interactions; their tokens can be flattened into a single batch dimension regardless of sequence origin. For multi-head self-attention, where operations depend on sequence-specific positions and cached KV states, the runtime applies batching selectively or routes attention computations through jagged-tensor indexing.

Evaluation on GPT-3 175B demonstrated that iteration-level scheduling improved serving throughput by up to 36.9x compared to NVIDIA FasterTransformer baselines at equivalent latency budgets.

Preemptive Scheduling and MLFQ: FastServe

While Orca resolved execution bubbles, it operated under a non-preemptive First-Come, First-Served (FCFS) policy. Under heavy traffic, long generation jobs cause head-of-line blocking for shorter interactive queries, inflating average and tail Job Completion Time (JCT).

FastServe (Wu et al., 2023) introduced fine-grained preemptive scheduling for LLM inference using a Skip-Join Multi-Level Feedback Queue (MLFQ).

Classic MLFQ schedulers minimize completion time in information-agnostic workloads by placing new tasks into the highest-priority tier and demoting them across tiers as they accumulate compute time. In LLM inference, the workload is semi-information-agnostic: the input prompt length is known upon arrival, whereas the output generation length is unknown.

Because processing a long input prompt requires substantial initialization time ( $t_{\text{init}}$ ), placing long prompts directly into the highest-priority queue would monopolize the GPU and starve existing high-priority short decodes. FastServe resolves this with skip-join mechanics:

The scheduler profiles the incoming request to calculate its expected initialization time based on input token count.
Instead of entering priority queue $Q_0$ , the request "skip-joins" the lowest priority queue $Q_i$ whose assigned time quantum $q_i$ is sufficient to complete the prefill phase without mid-phase preemption.
Once the initial token is generated, subsequent decode steps follow standard MLFQ demotion rules based on accumulated token count.

To support preemption without exhausting GPU memory, FastServe implemented proactive key-value cache management, asynchronously swapping KV cache blocks between GPU HBM and host DRAM over PCIe to overlap data movement with forward-pass execution.

Chunked Prefill and Stall-Free Scheduling: Sarathi-Serve

Continuous batching systems initially separated prefill-dominated iterations from decode-dominated iterations. However, mixing raw prefills and decodes introduces a severe latency anomaly known as prefill-decode interference.

When a large prefill request (e.g., 4,000 tokens) enters a running batch, its execution can stall GPU compute for 100 to 300 milliseconds. Every concurrent decode sequence sharing the batch experiences an identical latency stall, creating extreme spikes in Time Between Tokens (TBT / inter-token latency).

Sarathi-Serve (Agrawal et al., OSDI 2024) and SplitFuse (Patel et al., 2024) resolved this interference through Chunked Prefill and Decode-Maximal Batching:

Chunked Prefills: The scheduler slices incoming prompt sequences into fixed-size token chunks (e.g., 512 tokens). A long prompt is processed over multiple iterations rather than a single monolithic forward pass.
Decode-Maximal Piggybacking: In each iteration, the scheduler pairs exactly one prefill chunk with all active decode requests.
Compute-Memory Complementarity: The prefill chunk provides sufficient arithmetic intensity to saturate the GPU's Tensor Cores (GEMM), while the decode requests "piggyback" on the execution to utilize available memory bandwidth (GEMV).

By standardizing iteration computational load, Sarathi-Serve eliminated pipeline bubbles and flattened TBT variance, boosting end-to-end serving capacity by 2.6x on Mistral-7B and up to 5.6x on large models running with pipeline parallelism.

Architectural Comparison of Production Schedulers

Modern inference frameworks integrate iteration-level scheduling alongside distinct memory allocators and execution kernels.

1. vLLM

Scheduling Model: Iteration-level continuous batching tightly coupled with PagedAttention.
Prefill Handling: Supports optional chunked prefill (--enable-chunked-prefill) to co-schedule prefill chunks and decode tokens up to a configured --max-num-batched-tokens budget.
Preemption Policy: When physical KV block memory is exhausted, vLLM preempts the lowest-priority (or most recently arrived) sequences using either swap-to-host DRAM or abort-and-recompute policies.
Engine V1 Architecture: Recent revisions separate the scheduler thread into an asynchronous orchestrator, eliminating Python runtime overhead from the GPU execution critical path.

2. SGLang

Scheduling Model: Prefix-tree aware continuous batching driven by RadixAttention.
Prefill Handling: Dynamic chunking integrated with radix cache lookup. Reusable system prompts and multi-turn prefixes bypass prefill computation via tree-structured KV cache sharing.
Memory Management: LRU eviction on prefix tree nodes. Requests that reuse cached prefixes avoid recomputation, significantly reducing prefill scheduling load.

3. TensorRT-LLM

Scheduling Model: Native C++ in-flight batching engine with static and dynamic tensor memory management.
Prefill Handling: Sliced prefill scheduling and micro-batch pipelining optimized for NVIDIA Hopper and Blackwell tensor architectures via Cutlass and FlashInfer kernels.
Execution Mode: Direct execution graph integration with lower scheduling overhead, suitable for strict sub-millisecond per-step serving SLAs.

Production Trade-Offs, Metrics, and SLA Management

Deploying continuous batching in high-throughput enterprise systems requires balancing competing latency and throughput metrics:

+-----------------------------------------------------------------------------+
|                     Production Serving Metric Trade-offs                    |
+-----------------------------------------------------------------------------+
| Metric                 | Optimization Vector      | Bottleneck Trade-off    |
+------------------------+--------------------------+-------------------------+
| Time to First Token    | Prioritize large prefill | Degrades TBT for active |
| (TTFT)                 | batches immediately      | streaming connections   |
+------------------------+--------------------------+-------------------------+
| Time Between Tokens    | Enforce small, uniform   | Reduces prefill batch   |
| (TBT / Inter-token)    | chunked prefill bounds   | throughput density      |
+------------------------+--------------------------+-------------------------+
| Overall Throughput     | Maximize concurrent      | Increases KV cache      |
| (Tokens/sec/GPU)       | batch token limits       | preemption probability  |
+------------------------+--------------------------+-------------------------+

The TTFT vs. TBT Pareto Frontier

Prioritizing prefill throughput minimizes TTFT for batch workloads (e.g., document extraction, offline evaluation) but causes unacceptable jitter for real-time conversational streaming. Setting --max-num-batched-tokens (in vLLM) or chunk size parameters creates an explicit trade-off:

Smaller chunk sizes (256-512 tokens) guarantee tight, consistent TBT distributions below 25ms per token at the expense of slightly higher TTFT.
Larger chunk sizes (1024-2048 tokens) maximize overall throughput and reduce TTFT for long-context tasks but increase per-token generation latency variance.

Preemption Mechanics: Swap vs. Recompute

When GPU KV cache memory fills under burst traffic, the scheduler must evict active sequences:

Swapping (Host Transfer): Transfers KV cache pages across the PCIe bus to host DRAM. While preserving generated tokens, PCIe transfer latency ( $C_{\text{layers}} \times 2 \times D_{\text{model}} \times L_{\text{seq}}$ ) can saturate the PCIe link and delay execution.
Recomputation (Drop and Restart): Frees the KV blocks entirely and re-runs the prefill phase when memory becomes available. In high-bandwidth inference servers where prompt prefill is fast, recomputation frequently outperforms PCIe swap overhead, especially for sequences with short prefix lengths.

Production Configuration Guidelines

For stable production deployments:

Enable chunked prefill with a token budget aligned to GPU compute saturation thresholds (typically 512 to 2048 tokens depending on model size and GPU generation).
Set KV cache memory allocation headroom (e.g., gpu_memory_utilization = 0.90) to reserve space for dynamic activation tensors and CUDA graph allocations.
Implement queue admission control at the gateway layer to reject or route excess requests before scheduler memory saturation triggers cascading preemption loops.