Request Interleaving

Unlike traditional batching which groups requests for an entire forward pass, request interleaving makes scheduling decisions per model iteration. This allows the scheduler to:

• Dynamically adjust the active batch composition at each token generation step.
• Insert new requests into the batch as soon as previous requests finish, eliminating idle cycles.
• Remove completed sequences immediately, freeing resources for others. This fine-grained control is the core mechanism enabling high GPU utilization despite variable request lengths and arrival times.

A primary goal of interleaving is to eliminate head-of-line blocking, a major inefficiency in static batching. In a static batch, a single long sequence delays the completion of all other sequences in the batch. Interleaving addresses this by:

• Allowing shorter sequences to complete and exit the batch independently.
• Preventing long sequences from monopolizing batch slots for their entire duration.
• Enabling new, potentially short requests to join the batch and be processed alongside the remaining long sequence. This results in dramatically improved tail latency (p95, p99) for interactive applications.

Request interleaving is specifically designed to handle the inherent variability in sequence lengths found in real-world inference workloads (e.g., different prompt lengths, generation limits). It optimizes for this by:

• Using ragged tensors or specialized kernels to group sequences of different lengths with minimal padding overhead.
• Balancing the computational load across iterations, as the effective 'batch size' in terms of total tokens is kept more constant.
• This is a key advancement over variable-length batching, which reduces padding but still suffers from head-of-line blocking at the request level.

Interleaving treats the prefill phase and decode phase of autoregressive generation as distinct scheduling problems due to their different resource profiles:

• Prefill (Compute-Bound): Processes the entire input prompt. The scheduler may batch multiple prefills together for high throughput.
• Decode (Memory-Bound): Generates tokens iteratively. This is where interleaving is most active, managing many concurrent decoding sequences. The scheduler must efficiently manage the transition of requests from the prefill queue into the interleaved decode pool, ensuring both phases are optimally utilized.

Efficient interleaving is intrinsically linked to the management of the Key-Value (KV) Cache. As requests are interleaved, their cached attention states must be:

• Dynamically allocated in GPU memory as new requests join.
• Persisted and efficiently retrieved for the correct sequence at each iteration.
• Swiftly evicted when a request completes to free memory for new requests. Poor KV cache management can negate the benefits of interleaving by causing excessive memory fragmentation or GPU out-of-memory (OOM) errors.

The ultimate metric driving request interleaving is GPU utilization. It targets the reduction of idle cycles where streaming multiprocessors (SMs) have no work. It achieves this by:

• Ensuring there is almost always a sufficient number of active sequences (in terms of total tokens) to keep the hardware saturated.
• Overlapping memory-bound decoding operations with compute-bound prefill operations where possible.
• Minimizing kernel launch overhead by maintaining persistent, optimally sized batches across iterations. This directly translates to higher throughput (tokens/second) and lower inference cost per request.

The scheduler is the central component that implements interleaving. It maintains a priority queue of active requests and makes fine-grained decisions at each model iteration. Key responsibilities include:

• Request Admission: Evaluating incoming requests against system capacity and SLAs.
• Iteration-Level Grouping: Determining which requests to execute together in the next forward pass.
• Resource Arbitration: Managing contention for GPU memory (especially KV Cache) and compute cycles.
• Completion Handling: Detecting when requests have finished generation and freeing their resources. This architecture moves beyond static or time-window dynamic batching to enable true iteration-level multiplexing.

Interleaving's efficiency is tightly coupled with Key-Value (KV) Cache management. Each request's attention states are stored in GPU memory during generation. The scheduler must:

• Allocate Cache Slots: Dynamically assign portions of a fixed-size KV cache buffer to active sequences.
• Handle Variable Lengths: Efficiently pack sequences of different lengths to minimize fragmentation.
• Implement Cache Eviction: Apply policies (e.g., LRU - Least Recently Used) when the cache is full, potentially pausing requests or swapping states to CPU memory. Poor cache management under interleaving can lead to thrashing, where excessive cache swaps destroy the performance benefits.

Interleaving allows operators to tune the scheduler along the latency-throughput Pareto frontier. Key levers include:

• Maximum Batch Size: Limits how many requests can run concurrently per iteration, affecting throughput and iteration time.
• Batch Timeout / Scheduling Window: How long the scheduler waits to accumulate requests, trading off tail latency for larger, more efficient batches.
• Preemption Policies: Whether a new, high-priority request can pause a lower-priority one mid-generation, improving its latency at the cost of overall efficiency. The optimal configuration depends on the workload mix (e.g., chat vs. summarization) and Service Level Objectives (SLOs).

Request interleaving is the enabling mechanism for continuous batching (also called iteration-level scheduling). The system continuously:

1. Joins: Injects new requests into the active set as soon as resources are available, without waiting for a batch to finish.
2. Interleaves: Executes the mixed set of requests through a shared forward pass.
3. Exits: Removes completed sequences from the active set and returns results immediately. This eliminates idle cycles and head-of-line blocking inherent in static batching, allowing the GPU to be nearly constantly utilized.

Implementing interleaving introduces system complexity and overheads:

• Scheduling Overhead: The logic to select requests each iteration adds CPU-side computation.
• Kernel Launch Overhead: More frequent, smaller batches can increase the relative cost of launching GPU kernels.
• Complex State Management: Tracking the progress, cache location, and priority of dozens to hundreds of interleaved requests is non-trivial.
• Fairness and Starvation: Without careful design, long-running requests can monopolize resources, causing short requests to wait excessively (starvation). Effective implementations use hybrid policies like shortest-job-first or weighted fair queueing.

Iteration-level scheduling is the fine-grained decision-making process that occurs at each step of token generation. It is the mechanism that executes request interleaving. At every iteration, the scheduler decides:

• Which requests are active in the batch.
• How to group variable-length sequences to minimize padding.
• When to evict finished sequences to make room for new ones. This granular control allows the system to adapt to real-time load and prioritize requests based on policy, balancing throughput and tail latency.

Head-of-line (HOL) blocking is a critical performance problem that request interleaving and continuous batching are designed to mitigate. In a naive batch, if one request has a very long output sequence, all other requests in that batch are forced to wait for it to complete, increasing their latency. Interleaving addresses this by allowing other requests to finish and exit the batch independently. Advanced schedulers may implement policies to detect and potentially preempt or isolate exceptionally long-running requests to prevent them from degrading the performance of the entire system.

Dynamic batching is a predecessor and simpler form of request scheduling often conflated with continuous batching. The core difference is granularity:

• Dynamic Batching: Groups requests waiting in a request queue based on a fixed batch window or size. The formed batch is then processed to completion. It improves over static batching but can still suffer from HOL blocking.
• Request Interleaving / Continuous Batching: Makes scheduling decisions at the iteration time level. It is a superset of dynamic batching, providing the ability to add and remove requests from an already executing batch. Dynamic batching is a policy; interleaving is an execution model enabled by continuous batching.

The orchestrator or scheduler within an inference server (e.g., vLLM, TGI, TensorRT-LLM) is the software component that implements request interleaving. It is responsible for the entire lifecycle:

• Request Admission Control: Deciding whether to accept, queue, or reject incoming queries based on load.
• Queue Management: Holding requests in a request queue before scheduling.
• Interleaving Execution: Applying the batching policy to decide on batch composition at each iteration.
• Resource Governance: Enforcing backpressure, load shedding, and batch timeout policies to maintain system stability and meet latency SLAs.