Iteration-Level Scheduling

Unlike traditional static batching or even dynamic batching with a fixed window, iteration-level scheduling re-evaluates the active batch composition at every decoding iteration (i.e., for every new token generated). This allows:

• New requests to join the batch immediately after the current iteration.
• Completed sequences to exit the batch instantly, freeing resources.
• The batch size and shape to adapt in real-time to the changing workload.

A core motivation is to prevent head-of-line blocking, where a single long sequence stalls an entire batch. With iteration-level scheduling:

• Sequences generate tokens independently.
• A short sequence that finishes early does not wait for longer ones; it exits, and its GPU resources are immediately reclaimed.
• This directly improves tail latency (p95, p99) for interactive applications, as requests are not penalized by being batched with slower peers.

The scheduler's goal is to keep the Tensor Cores and memory bandwidth of the GPU saturated. It achieves this by:

• Continuously packing the batch with the maximum number of sequences that can fit in GPU memory (primarily constrained by the KV Cache).
• Ensuring that as soon as a slot opens up (a sequence finishes), a new queued request fills it for the next iteration.
• This turns the decoding phase from a series of small, inefficient batches into a near-continuous, full-batch computation.

Scheduling decisions are intrinsically linked to KV cache memory management. The scheduler must:

• Track the size of each sequence's KV cache in memory.
• Allocate and evict cache blocks efficiently as sequences enter and exit the batch.
• Use memory-aware policies to decide which queued request to admit next, based on its predicted cache footprint. Systems like vLLM with PagedAttention exemplify this tight integration.

Advanced schedulers can implement policies beyond simple FIFO (First-In, First-Out):

• Priority Scheduling: Serve high-priority requests first, even if they arrived later.
• Fair Queuing: Allocate GPU time proportionally among users or request classes.
• Request Interleaving: Mix sequences with different characteristics (e.g., sampling parameters, model paths) within the same batch. This requires the underlying engine to support heterogeneous execution contexts.

The scheduler acts as a gatekeeper to enforce Service Level Agreements (SLAs). It employs request admission control to:

• Reject or queue requests when the system is at capacity.
• Implement load shedding during traffic spikes to protect latency for accepted requests.
• Use batch timeouts to guarantee a maximum queue time, bounding latency at the potential cost of smaller batch sizes and lower throughput.

Continuous batching is the overarching inference optimization technique where the scheduler dynamically groups incoming requests into a batch for each model iteration. Unlike static batching, it allows:

• New requests to join the active batch as soon as resources are available.
• Completed sequences to exit the batch immediately, freeing their resources.
• This maximizes GPU utilization by eliminating idle cycles where the processor waits for an entire fixed batch to finish.

The prefilling phase (or prefill stage) is the initial, compute-intensive step in autoregressive generation where the model processes the entire input prompt for all sequences in a batch in parallel. This phase:

• Builds the initial key-value (KV) cache for the attention mechanism.
• Is highly parallelizable and compute-bound.
• Iteration-level scheduling must account for the significant latency of this first step before the iterative decoding phase begins.

The decoding phase is the iterative, token-by-token generation stage following prefill. This phase is characterized by:

• Being primarily memory-bound, as performance is limited by reading the KV cache and model weights.
• Having a much smaller computational footprint per iteration (forward pass) than prefill.
• Iteration-level scheduling operates most actively here, making fine-grained decisions about which requests remain in the batch for the next token generation step.

Head-of-line blocking is a critical performance problem that iteration-level scheduling aims to mitigate. It occurs when a single long-running or stalled request within a batch delays the processing and completion of all other requests in that same batch. Continuous batching with iteration-level scheduling reduces this by allowing finished sequences to exit, preventing them from being blocked by slower peers.

A request queue is the buffer in an inference server that holds incoming client queries. The iteration-level scheduler pulls from this queue when deciding which requests to admit into the next processing iteration. Key queue management concepts include:

• Request Admission Control: Policies for accepting or rejecting requests based on load.
• Batch Timeout: A maximum wait time for a request in the queue to bound latency.
• Load Shedding: Dropping requests under extreme load to preserve system stability.

Iteration time is the fundamental unit of scheduling measurement. It is the latency of a single forward pass of the model, which during decoding corresponds to the time to generate one token for each active sequence in the batch. The scheduler's goal is to minimize average iteration time and its variance by:

• Keeping batch sizes as large as possible without introducing excessive padding.
• Ensuring the GPU is fully utilized each iteration, avoiding idle cycles.
• This metric directly influences overall throughput and tail latency.