A production LLM endpoint serving chat traffic has to keep the GPU saturated with useful work while every individual request still feels instantaneous. On 4xA100 80GB running a 70B-class model, that means sustaining 8,000+ tokens per second across 128 concurrent requests while keeping p99 time-to-first-token (TTFT) under 200ms. Get the batching strategy wrong and you either leave the GPU idle waiting for a full batch to form, or you let one slow request block every other request in the batch from returning a single token.

Think of a subway train that only opens its doors once every car is completely full, and refuses to open them again until every passenger currently on board has reached their final stop. Some passengers are going one stop, some are going twenty. The train sits at the platform, doors closed, mostly full, until the last twenty-stop passenger finally gets off - at which point the doors open, a fresh batch boards, and the whole cycle repeats. That is static batching for LLM inference: the server waits for max_batch_size requests to arrive, runs them all forward together until every sequence hits <eos> or a max length limit, and only then admits new requests. Most of the ride, that train is carrying two or three passengers who finished early but are stuck sitting there, seats empty, GPU idle.

The failure compounds because LLM output lengths are unpredictable. A batch of 32 requests with output lengths ranging from 20 to 800 tokens finishes its shortest sequences within the first few decode steps, but the GPU keeps executing the full batch shape until the longest sequence completes. Every step after the short sequences finish is wasted compute - profiling a naive static-batched serving loop typically shows 30-50% of decode steps running with more than half the batch already finished but still occupying GPU memory and compute slots. Meanwhile, new requests queue behind the entire batch instead of behind just the requests ahead of them in time, so an unlucky arrival right after a batch closes can wait seconds for its first token, not milliseconds.

The tension is between three forces competing for the same fixed GPU: throughput wants the largest possible batch running at all times so matrix multiplies stay compute-bound instead of memory-bandwidth-bound; latency wants a request to join the batch the instant it arrives and see its first token immediately, not wait behind a cohort that started earlier; and memory wants every sequence’s KV cache to fit inside a fixed HBM budget that gets tighter the longer a sequence runs and the more sequences are in flight at once. We need to solve for iteration-level scheduling that decides, at every single forward pass, which sequences are in the batch rather than committing to a fixed batch shape for its whole lifetime; memory-safe KV cache allocation that grows and shrinks per sequence without pre-reserving worst-case context length; and an admission and preemption policy that keeps GPU memory within budget under load without starving any one request indefinitely - simultaneously, on every iteration of the scheduler loop.

Requirements and Constraints

Functional requirements:

• Admit a new request into the currently in-flight decode batch at the next scheduler iteration, not after the current batch fully drains
• Free a completed sequence’s KV cache blocks and compute slot immediately on <eos> or max-length, without waiting for other sequences in the batch to finish
• Support chunked prefill: split a long prompt’s prefill into token-budget-sized chunks that interleave with ongoing decode steps for other sequences, instead of blocking decode for the entire prefill duration
• Preempt (evict) running sequences when the KV cache pool is exhausted, using either recompute (drop KV state and re-prefill later) or swap (move blocks to host memory and restore later) depending on sequence length and swap bandwidth
• Enforce configurable admission limits: max_num_seqs (concurrent sequence cap) and max_num_batched_tokens (per-iteration token budget spanning both prefill and decode)
• Stream tokens back to each client independently over SSE as soon as they are produced, regardless of what other sequences in the batch are doing

Non-functional requirements:

• Throughput: sustain 8,000+ output tokens/second aggregate across 128 concurrent sequences on 4xA100 80GB running a 70B-class model
• Latency: p50 TTFT under 80ms, p99 TTFT under 200ms for prompts up to 1,024 tokens; p50 time-per-output-token (TPOT) under 16ms at full batch occupancy
• Capacity: KV cache footprint must stay within gpu_memory_utilization (default 0.90) of total HBM, with weights, activations, and CUDA graph workspace all fitting in the remaining headroom
• Fairness: no admitted sequence should wait more than one scheduler iteration behind another sequence of equal priority; preemption victim selection must not repeatedly starve the same sequence
• Cost: cost per 1M output tokens under $0.50 on spot-priced 4xA100 hardware at target batch occupancy

Constraints:

• Model assumed: a 70B-class dense transformer (Llama-3 70B class) in BF16, grouped-query attention with 8 KV heads, head_dim 128, 80 layers
• Hardware assumed: single node, 4x A100 80GB with NVLink, tensor-parallel degree 4
• Out of scope: multi-node pipeline parallelism, speculative decoding (a complementary but separate technique), quantized KV cache (FP8/INT8), and disaggregated prefill/decode pools (discussed briefly in the comparison table but not designed here)

High-Level Architecture

Six components form the serving path. The Request Queue buffers incoming generation requests the instant they arrive, ordered by arrival time and priority class. The Admission Controller decides, on every scheduler tick, which waiting requests can join the running batch without exceeding max_num_seqs or the KV cache watermark. The Iteration Scheduler is the core loop: it builds the exact batch shape for the next forward pass, mixing decode tokens from already-running sequences with prefill chunks from newly admitted ones. The KV Cache Block Manager implements PagedAttention-style block allocation, handing sequences fixed-size blocks of KV cache on demand instead of reserving a worst-case context length up front. The Model Executor runs the actual forward pass across the four tensor-parallel GPU shards. The Output Streamer pushes completed tokens back to each client over SSE the moment they are produced, independent of what else is happening in the batch.

A request’s journey looks like this: it lands in the request queue, the admission controller checks it against current KV cache pressure and priority, the iteration scheduler slots its first prefill chunk into the next forward pass alongside decode steps for other sequences, the model executor runs that mixed batch across all four GPUs, and any tokens produced - including this request’s first token, once its prefill chunk completes - stream back immediately. The sequence then rides along in the running batch, contributing exactly one new token per iteration, until it hits <eos> or its length limit, at which point its KV blocks return to the free pool for the next request.

The end-to-end token flow for a single request, including the alternate path taken when it gets preempted mid-generation, looks like this:

Component Deep Dives

The Iteration Scheduler Loop

Here’s the job this component does: on every GPU forward pass, decide exactly which tokens - decode continuations and prefill chunks - go into that pass, subject to the token budget and the KV cache budget.

A smart engineer’s first assumption is usually that the scheduler is a thin loop that just “runs whatever is next in the queue.” In practice it is solving a constrained bin-packing problem, every 15-20ms, with two competing kinds of work: decode tokens that must not be skipped (skipping one stalls that sequence’s TPOT for a full iteration) and prefill chunks that are elastic and can be split across several iterations. Getting the priority order between those two wrong is the single most common continuous batching bug.

The mechanism is like an airport gate agent scanning the line at every boarding call: rebook whoever is ready, never bump someone who is already seated unless the flight is genuinely full, and let new passengers join right up until the doors close. Concretely, decode tokens for the running queue get scheduled unconditionally first; only the token budget left over after that is offered to waiting sequences as prefill chunks.

import time
from dataclasses import dataclass, field
from enum import Enum

class SeqStatus(Enum):
    WAITING = "waiting"
    RUNNING = "running"
    PREEMPTED = "preempted"
    FINISHED = "finished"

@dataclass
class Sequence:
    seq_id: str
    prompt_len: int
    output_len: int = 0
    max_output_len: int = 1024
    status: SeqStatus = SeqStatus.WAITING
    priority: int = 0                # lower value = higher priority
    num_computed_tokens: int = 0     # prefill tokens already processed
    block_table: list[int] = field(default_factory=list)
    arrival_time: float = field(default_factory=time.time)

    @property
    def is_prefill_incomplete(self) -> bool:
        return self.num_computed_tokens < self.prompt_len


class IterationScheduler:
    """
    Continuous batching scheduler. Called once per forward pass.
    Decides the exact set of (sequence, num_tokens) pairs for this iteration
    under a combined token budget and KV block budget.
    """
    def __init__(
        self,
        block_manager: "BlockManager",
        max_num_seqs: int = 128,
        max_num_batched_tokens: int = 2048,
        chunk_size: int = 512,
    ):
        self.block_manager = block_manager
        self.max_num_seqs = max_num_seqs
        self.max_num_batched_tokens = max_num_batched_tokens
        self.chunk_size = chunk_size
        self.waiting: list[Sequence] = []
        self.running: list[Sequence] = []
        self.preempted: list[Sequence] = []

    def schedule_step(self) -> dict[str, int]:
        """
        Returns {seq_id: num_tokens_this_iteration} for the next forward pass.
        Decode tokens for running sequences are scheduled first (latency
        priority); leftover budget fills prefill chunks for waiting sequences.
        """
        batch: dict[str, int] = {}
        token_budget = self.max_num_batched_tokens

        # 1. Resume preempted sequences ahead of fresh admissions (fairness)
        for seq in list(self.preempted):
            if len(self.running) >= self.max_num_seqs:
                break
            if self.block_manager.can_allocate(seq):
                self.block_manager.allocate(seq)
                self.preempted.remove(seq)
                seq.status = SeqStatus.RUNNING
                self.running.append(seq)

        # 2. Decode step for every already-running sequence: 1 token each, always first
        for seq in self.running:
            if token_budget <= 0:
                break
            batch[seq.seq_id] = 1
            token_budget -= 1

        # 3. Admit waiting sequences and give them a prefill chunk with leftover budget
        self.waiting.sort(key=lambda s: (s.priority, s.arrival_time))
        for seq in list(self.waiting):
            if len(self.running) >= self.max_num_seqs or token_budget <= 0:
                break
            remaining_prefill = seq.prompt_len - seq.num_computed_tokens
            chunk = min(self.chunk_size, remaining_prefill, token_budget)
            if chunk <= 0:
                continue
            if not self.block_manager.can_allocate(seq, extra_tokens=chunk):
                continue  # not enough free KV blocks this iteration
            self.block_manager.allocate(seq, extra_tokens=chunk)
            if seq.status == SeqStatus.WAITING:
                self.waiting.remove(seq)
                self.running.append(seq)
                seq.status = SeqStatus.RUNNING
            batch[seq.seq_id] = chunk
            token_budget -= chunk

        return batch