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

If you simplified this into request-granularity scheduling - the static batching approach - you lose the ability to interleave a straggler’s tail with fresh admissions, and you are back to the subway problem. The failure mode this loop specifically handles is prefill monopolization: without step 3’s budget cap, a single 4,000-token prompt would consume the entire iteration and every running sequence would see zero decode progress that step, spiking TPOT for every connected client at once.

Admission Control and max_num_seqs

Here’s the job this component does: gatekeep which waiting requests get pulled into the running queue each iteration, bounded by both the sequence-count cap and the KV cache the request would actually consume.

The non-obvious part is that max_num_seqs alone is not sufficient. A smart engineer might assume a sequence-count limit is the whole story, but a single enormous prompt can blow the token or KV-block budget for an iteration even when the sequence count has plenty of headroom left. Admission control has to check capacity in both dimensions - count and bytes - before letting anything in.

@dataclass
class AdmissionDecision:
    admit: bool
    reason: str

class AdmissionController:
    """
    Gatekeeper that runs before a waiting sequence is allowed to enter the
    running queue. Checks sequence-count and KV-block capacity together -
    a watermark of free blocks is reserved so that a preemption can always
    complete even if every running sequence is simultaneously growing.
    """
    def __init__(self, block_manager: "BlockManager", max_num_seqs: int, watermark: float = 0.02):
        self.block_manager = block_manager
        self.max_num_seqs = max_num_seqs
        self.watermark = watermark

    def can_admit(self, seq: Sequence, num_running: int) -> AdmissionDecision:
        if num_running >= self.max_num_seqs:
            return AdmissionDecision(False, "max_num_seqs reached")

        needed_blocks = self.block_manager.blocks_needed(seq.prompt_len)
        free_blocks = self.block_manager.num_free_blocks()
        reserved = int(self.block_manager.total_blocks * self.watermark)

        if free_blocks - needed_blocks < reserved:
            return AdmissionDecision(False, "below KV cache watermark")

        return AdmissionDecision(True, "ok")

Chunked Prefill: Mixing Prefill and Decode in the Same Batch Step

Here’s the job this component does: cap how many prefill tokens can enter a single iteration so a large incoming prompt never monopolizes a forward pass and stalls decode for every other sequence.

The naive approach runs an entire prefill as one big forward pass before the sequence ever joins the decode loop - “prefill this whole 4,000-token prompt in one shot.” During that pass, every currently-running sequence gets zero decode progress, which shows up to users as a visible stutter in their streaming output. Chunked prefill fixes this by capping each iteration’s total token budget (max_num_batched_tokens, for example 2048) and splitting large prefills into chunk_size-token pieces that share the iteration with ongoing decode work.

def pack_iteration_batch(
    running: list[Sequence],
    waiting: list[Sequence],
    token_budget: int,
    max_num_seqs: int,
) -> dict[str, int]:
    """
    Greedy bin-packing for one iteration: decode tokens are non-negotiable
    and are placed first, then remaining budget fills prefill chunks in
    priority + FCFS order. O(n log n) per call, dominated by the sort.
    """
    batch: dict[str, int] = {}
    budget = token_budget

    for seq in running:
        if budget == 0:
            break
        batch[seq.seq_id] = 1
        budget -= 1

    waiting_sorted = sorted(waiting, key=lambda s: (s.priority, s.arrival_time))
    seats_left = max_num_seqs - len(running)
    for seq in waiting_sorted:
        if seats_left == 0 or budget == 0:
            break
        chunk = min(seq.prompt_len - seq.num_computed_tokens, budget)
        if chunk <= 0:
            continue
        batch[seq.seq_id] = chunk
        budget -= chunk
        seats_left -= 1

    return batch

This is like letting a delivery truck unload its pallets between customer transactions instead of blocking the entire checkout line while it unloads everything at once. Without chunking, adding one more large prompt to your traffic mix directly degrades TPOT for every unrelated user in the batch; with chunking, that prompt’s prefill spreads across several iterations and decode continues uninterrupted the whole time.

The KV Cache Block Manager (PagedAttention)

Here’s the job this component does: allocate and free small, fixed-size KV cache blocks per sequence on demand, instead of reserving max_seq_len worth of contiguous memory for every sequence up front.

The naive approach - pre-allocate the maximum context length’s worth of KV cache per sequence, contiguously - wastes enormous amounts of memory because most sequences finish far short of the maximum length. At 8K max context but a 2K average actual length, roughly 75% of every sequence’s reserved KV memory sits empty. On a fixed HBM budget, that fragmentation is what caps you at 20-30 concurrent sequences instead of 128.

The mechanism is directly analogous to an operating system’s virtual memory paging: a fixed page size, a page table that maps logical pages to arbitrary physical frames, and no external fragmentation because any free frame can satisfy any request regardless of where it sits in physical memory.

class BlockManager:
    """
    PagedAttention-style KV cache allocator. Hands out fixed-size blocks
    (16 tokens each) from a shared pool instead of reserving max_seq_len
    contiguous memory per sequence.
    """
    BLOCK_SIZE = 16

    def __init__(self, total_blocks: int):
        self.total_blocks = total_blocks
        self.free_blocks: list[int] = list(range(total_blocks))
        self.block_tables: dict[str, list[int]] = {}

    def blocks_needed(self, num_tokens: int) -> int:
        return (num_tokens + self.BLOCK_SIZE - 1) // self.BLOCK_SIZE

    def num_free_blocks(self) -> int:
        return len(self.free_blocks)

    def can_allocate(self, seq: Sequence, extra_tokens: int = 1) -> bool:
        current_blocks = len(self.block_tables.get(seq.seq_id, []))
        current_tokens = current_blocks * self.BLOCK_SIZE
        needed_total = self.blocks_needed(current_tokens + extra_tokens)
        additional_blocks = needed_total - current_blocks
        return additional_blocks <= len(self.free_blocks)

    def allocate(self, seq: Sequence, extra_tokens: int = 1) -> None:
        table = self.block_tables.setdefault(seq.seq_id, [])
        current_tokens = len(table) * self.BLOCK_SIZE
        needed_total = self.blocks_needed(current_tokens + extra_tokens)
        while len(table) < needed_total:
            table.append(self.free_blocks.pop())
        seq.block_table = table

    def free(self, seq_id: str) -> None:
        table = self.block_tables.pop(seq_id, [])
        self.free_blocks.extend(table)

What breaks if you simplify this away: without block-based indirection, appending one token to a sequence’s KV cache either requires the cache to already have contiguous room reserved (the wasteful static-allocation approach) or requires copying the whole cache to a larger contiguous region on every growth step, which is an O(context_length) memory-bandwidth cost paid every single decode step.

Preemption and Eviction: Recompute vs Swap

Here’s the job this component does: when the KV cache pool is exhausted and a sequence needs more blocks than are free, choose a victim to evict and decide whether to recompute its state later or swap it to host memory.

The tradeoff most engineers get wrong on the first pass is assuming one strategy is always better. Swap avoids repeating prefill compute but costs PCIe bandwidth and host RAM proportional to the victim’s KV cache size in bytes. Recompute avoids touching host memory at all but repeats prefill work proportional to however many tokens the victim had already generated. For a sequence with only 80 accumulated tokens, recompute is nearly free; for a sequence with 6,000 accumulated tokens, recomputing that much context can cost more wall-clock time than a swap round-trip.

class PreemptionPolicy:
    """
    Chooses a victim to evict when the block manager cannot satisfy a new
    allocation, and decides recompute vs swap based on how much KV cache
    the victim has already accumulated.
    """
    RECOMPUTE_THRESHOLD_TOKENS = 512  # below this, recompute is cheaper than swap

    def __init__(self, block_manager: "BlockManager", swap_bandwidth_gbps: float = 12.0):
        self.block_manager = block_manager
        self.swap_bandwidth_gbps = swap_bandwidth_gbps  # PCIe Gen4 effective bandwidth

    def select_victim(self, running: list[Sequence]) -> Sequence:
        # Evict the most-recently-admitted, lowest-priority sequence first -
        # this bounds how many times any one sequence can be preempted,
        # since older sequences become protected once they're running.
        candidates = sorted(running, key=lambda s: (-s.priority, -s.arrival_time))
        return candidates[0]

    def choose_strategy(self, victim: Sequence) -> str:
        computed_tokens = victim.num_computed_tokens + victim.output_len
        kv_bytes = computed_tokens * 320_000  # ~320KB/token across 4 GPUs
        swap_time_ms = (kv_bytes / 1e9) / self.swap_bandwidth_gbps * 1000
        recompute_time_ms = computed_tokens * 0.20  # ~0.2ms/token amortized prefill cost

        if computed_tokens < self.RECOMPUTE_THRESHOLD_TOKENS:
            return "recompute"
        return "swap" if swap_time_ms < recompute_time_ms else "recompute"

TTFT vs TPOT: Two Different Latency Budgets

TTFT (time-to-first-token) and TPOT (time-per-output-token) decompose independently, and continuous batching optimizes them through different mechanisms entirely. TTFT is dominated by queueing delay in the admission controller plus the latency of the prefill chunk(s) that produce the first token. TPOT is dominated by the decode iteration’s wall-clock time divided by however many sequences are actively decoding that step.

Data Model

-- One row per active or recently completed generation request
CREATE TABLE sequences (
    seq_id              UUID PRIMARY KEY,
    request_id          UUID NOT NULL,
    tenant_id           VARCHAR(64) NOT NULL,
    priority_tier        SMALLINT NOT NULL DEFAULT 2,   -- 0=premium, 1=standard, 2=best-effort
    prompt_tokens        INTEGER NOT NULL,
    max_output_tokens    INTEGER NOT NULL DEFAULT 1024,
    generated_tokens     INTEGER NOT NULL DEFAULT 0,
    num_computed_tokens  INTEGER NOT NULL DEFAULT 0,     -- prefill tokens processed so far
    status               VARCHAR(16) NOT NULL DEFAULT 'waiting', -- waiting|running|preempted|finished|aborted
    preemption_count     SMALLINT NOT NULL DEFAULT 0,
    num_kv_blocks        INTEGER NOT NULL DEFAULT 0,
    arrival_time         TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    admitted_at          TIMESTAMPTZ,
    completed_at         TIMESTAMPTZ,
    ttft_ms              FLOAT,
    tpot_p50_ms          FLOAT,
    model_version        VARCHAR(64) NOT NULL
);

-- Logical-to-physical block mapping per sequence (mirrors the in-memory block table)
CREATE TABLE kv_block_table (
    seq_id            UUID NOT NULL REFERENCES sequences(seq_id),
    logical_block_idx INTEGER NOT NULL,
    physical_block_id INTEGER NOT NULL,
    is_swapped        BOOLEAN NOT NULL DEFAULT FALSE,
    swap_host_offset  BIGINT,             -- byte offset in host swap region, if swapped
    PRIMARY KEY (seq_id, logical_block_idx)
);

-- Per-iteration telemetry, written async off the hot path
CREATE TABLE scheduler_iterations (
    iteration_id       BIGSERIAL PRIMARY KEY,
    recorded_at         TIMESTAMPTZ NOT NULL DEFAULT NOW(),
    num_decode_tokens   INTEGER NOT NULL,
    num_prefill_tokens  INTEGER NOT NULL,
    batch_size          INTEGER NOT NULL,
    free_kv_blocks      INTEGER NOT NULL,
    iteration_latency_ms FLOAT NOT NULL
);

-- Scheduler configuration (hot-reloadable admission and batching thresholds)
CREATE TABLE scheduler_config (
    config_id               SERIAL PRIMARY KEY,
    max_num_seqs            INTEGER NOT NULL DEFAULT 128,
    max_num_batched_tokens  INTEGER NOT NULL DEFAULT 2048,
    chunk_size              INTEGER NOT NULL DEFAULT 512,
    gpu_memory_utilization  FLOAT NOT NULL DEFAULT 0.90,
    kv_watermark_pct        FLOAT NOT NULL DEFAULT 0.02,
    updated_at              TIMESTAMPTZ NOT NULL DEFAULT NOW()
);

The partitioning key for sequences and kv_block_table in a multi-replica deployment is seq_id, but the sharding boundary that actually matters is the replica itself: a sequence’s block table only ever lives on the one GPU node that admitted it, since KV cache blocks are physical GPU memory addresses, not something you can shard across nodes without a network hop. scheduler_iterations is written asynchronously and indexed by recorded_at for time-series dashboards - it is never read on the hot path, only by the SLA monitor described later.

Key Algorithms and Protocols

Token-Budget Bin Packing for Iteration Scheduling

The pack_iteration_batch function shown earlier is the algorithmic core of continuous batching. Its edge case worth calling out: if max_num_batched_tokens is ever configured below max_num_seqs, a full running batch alone can exceed the token budget, meaning the tail of the running queue gets zero decode progress on some iterations - a subtle misconfiguration that silently degrades TPOT for whichever sequences happen to sort last. The invariant to enforce at config-load time is max_num_batched_tokens >= max_num_seqs.

PagedAttention Block Table Lookup

The attention kernel itself has to read K/V through the block table indirection rather than assuming a contiguous cache. This is a kernel-level change, not merely an allocator change - a standard attention kernel written for contiguous memory has no way to consume a scattered set of physical blocks without an explicit gather step.

def gather_kv_for_attention(
    block_table: list[int],
    physical_kv_cache: "torch.Tensor",  # shape: [num_blocks, block_size, num_kv_heads, head_dim]
    seq_len: int,
    block_size: int = 16,
) -> "torch.Tensor":
    """
    PagedAttention's core trick: attention reads K/V through a block table
    indirection instead of requiring the sequence's cache to be contiguous.
    Cost is O(num_blocks) index lookups, not O(seq_len) memory copies.
    """
    import torch
    num_full_blocks = seq_len // block_size
    remainder = seq_len % block_size

    gathered = []
    for i in range(num_full_blocks):
        physical_block_id = block_table[i]
        gathered.append(physical_kv_cache[physical_block_id])

    if remainder:
        physical_block_id = block_table[num_full_blocks]
        gathered.append(physical_kv_cache[physical_block_id, :remainder])

    return torch.cat(gathered, dim=0)  # [seq_len, heads, dim]

Complexity is O(ceil(seq_len / block_size)) index operations, each O(1), versus a naive contiguous relayout that would cost O(seq_len) memory bandwidth on every block appended. The memory math bounds internal fragmentation tightly: with block_size=16 and roughly 320KB of KV cache per token across four GPUs, a block is 5.12MB, and the worst-case waste per sequence is block_size - 1 unused token-slots, or about 4.8MB - regardless of how long the sequence runs. Static pre-allocation, by contrast, wastes (max_seq_len - actual_len) * 320KB per sequence, often gigabytes.

Watermark-Based Deadlock Avoidance

Without a reserved watermark of free blocks, a subtle livelock is possible: every running sequence wants to grow by one block on the next decode step, the pool is at 100% allocation, and no sequence can proceed because none can allocate - but nothing can be preempted either, because preemption itself needs at least one free block to make progress bookkeeping simple. Reserving a small watermark percentage guarantees at least one preemption can always complete and free blocks, even if every running sequence is simultaneously requesting growth.

Scaling and Performance

Horizontally, the system scales by adding replica nodes behind a router that tracks per-replica queue depth and KV cache pressure, routing new requests to the least-loaded replica. What does not scale horizontally is a single sequence’s context: a request’s KV cache blocks are physical GPU memory addresses on the one node that admitted it, and there is no cheap way to migrate a running sequence to another node without a full swap-and-restore across the network. A single node’s total KV cache pool is likewise a hard ceiling on how many concurrent sequences that node alone can serve, independent of how many replicas exist elsewhere in the fleet.

Given:
  - 4x A100 80GB, gpu_memory_utilization = 0.90
  - Llama-3 70B class in BF16 = 140 GB weights, sharded 4-way (35 GB/GPU)
  - KV cache: 8 KV heads, head_dim 128, 80 layers, BF16, GQA sharded across 4 GPUs

Usable HBM: 0.90 * 80GB * 4 = 288 GB total
Remaining after weights: 288 - 140 = 148 GB
Activation / CUDA graph workspace reserve: ~8 GB total
KV cache budget: 148 - 8 = 140 GB

KV cache per token (2 KV heads/GPU * 128 dim * 2 bytes * 80 layers * 2 (K+V)):
  81,920 bytes/GPU/token = 80 KB/GPU/token -> 320 KB/token across all 4 GPUs

block_size = 16 tokens -> 16 * 320 KB = 5.12 MB per logical block
Total block pool: 140 GB / 5.12 MB = ~27,340 blocks

At average 2,048-token context (typical chat turn):
  Blocks per sequence: 2048 / 16 = 128 blocks
  KV cache per sequence: 128 * 5.12 MB = 655 MB

Max concurrent sequences (memory-derived ceiling):
  140 GB / 655 MB = ~218 sequences

Configured max_num_seqs = 128 (below the memory ceiling by design -
  the gap is intentional headroom for preemption slack and TPOT variance,
  not wasted capacity)

Throughput at 128 concurrent decoding sequences, ~16ms/iteration (compute-bound
  region of the batch-size curve at this scale):
  128 tokens / 0.016s = 8,000 tokens/second

At 128 concurrent sequences, the node is comfortably inside its memory-derived ceiling of roughly 218 - the configured cap is a throughput and tail-latency control, not a hard memory limit. Prefix caching is the dominant caching strategy on top of this: when many requests share a common prefix (a system prompt, a few-shot template), the KV blocks for that shared prefix are computed once, marked immutable and reference-counted, and reused across every sequence that shares it, skipping prefill compute entirely for the cached portion. The read/write ratio on those shared prefix blocks is extremely read-heavy, which is exactly the case block-based sharing was designed for; the hot spot is that one shared prefix’s blocks, accessed by every concurrent sequence in a multi-tenant app using the same system prompt.

Cost and Token Economics

Configuration	Tokens/sec (4xA100)	GPU cost / 1M tokens	TTFT p99	TPOT p50
Static batching, bs=32	3,200	$0.71	~1,800ms	19ms
Continuous batching, no chunked prefill	6,200	$0.37	~450ms (prefill spikes)	17ms
Continuous batching + chunked prefill	8,000+	$0.28	<200ms	15ms
Managed API (GPT-4-class, blended)	n/a (rate-limited)	~$12.00	~300-800ms (provider-side)	20-40ms (variable)

Pricing assumes a $8.20/hr 4xA100 80GB spot node. The jump from static batching to continuous batching is the largest single lever - a 94% cost reduction per token purely from eliminating straggler idle time and reducing queueing delay. Chunked prefill on top of that is a smaller but still meaningful additional 24% cost reduction, entirely from removing decode stalls that were previously capping sustained throughput below the compute-bound ceiling.

Enabling chunked prefill with max_num_batched_tokens=2048 raised sustained throughput from 6,200 to 8,000+ tokens/sec (a 29% gain) with zero additional hardware - the only change was capping how much prefill work could enter a single iteration and letting decode work always go first.

Quality, Evaluation, and Guardrails

A continuous batching scheduler fails softly: throughput dashboards can look perfectly healthy in aggregate while a specific tenant or priority tier quietly experiences degraded latency, because the aggregate numbers average over exactly the variance the scheduler is supposed to control. Offline evaluation means running a load-test harness at target concurrency (128 simulated concurrent sequences, mixed prompt lengths matching production traffic shape) and measuring the full TTFT/TPOT percentile distribution, not just the mean. Online signals mean per-tenant and per-priority-tier p99 dashboards, preemption rate, and queue wait time by tier, refreshed continuously rather than sampled.

The deploy gate for any scheduler change is a latency regression test against the previous scheduler build, not just a throughput check:

import numpy as np

def check_latency_regression(
    baseline_ttft_p99: float,
    baseline_tpot_p50: float,
    candidate_ttft_samples: list[float],
    candidate_tpot_samples: list[float],
    ttft_regression_pct: float = 0.20,
    tpot_regression_pct: float = 0.15,
) -> dict:
    """
    Deploy gate for scheduler changes. A continuous batching scheduler can
    regress silently - throughput looks fine in aggregate while p99 tail
    latency for a subset of requests quietly gets worse (e.g. a preemption
    policy change that thrashes low-priority sequences more often).
    """
    candidate_ttft_p99 = float(np.percentile(candidate_ttft_samples, 99))
    candidate_tpot_p50 = float(np.percentile(candidate_tpot_samples, 50))

    ttft_delta = (candidate_ttft_p99 - baseline_ttft_p99) / baseline_ttft_p99
    tpot_delta = (candidate_tpot_p50 - baseline_tpot_p50) / baseline_tpot_p50

    return {
        "candidate_ttft_p99_ms": candidate_ttft_p99,
        "candidate_tpot_p50_ms": candidate_tpot_p50,
        "ttft_regression_pct": round(ttft_delta * 100, 1),
        "tpot_regression_pct": round(tpot_delta * 100, 1),
        "pass": ttft_delta <= ttft_regression_pct and tpot_delta <= tpot_regression_pct,
    }

Guardrails on the admission path: reject any single prompt whose token count alone exceeds max_num_batched_tokens, since a sequence that can never fit inside a single chunk would deadlock the scheduler waiting for a budget that never arrives; rate-limit per-tenant admission queue depth so one noisy tenant cannot push every other tenant’s queue wait past its SLA; and return backpressure (429) once queue wait for a priority tier exceeds its contracted threshold rather than silently accepting the request and violating the SLA later.

Failure Modes and Recovery

Failure	Detection	Impact	Recovery
GPU OOM mid-decode from KV growth outpacing the watermark	CUDA OOM exception on block allocation	Forward pass crash, entire in-flight batch lost	Watermark should prevent this; on trigger, force-preempt lowest-priority sequences and retry allocation before the batch executes
Preemption thrashing (same sequence repeatedly evicted and re-admitted)	Per-sequence preemption_count exceeds threshold in a rolling window	Sequence never accumulates enough progress to finish	Temporarily boost priority for thrashing sequences, or switch that sequence’s strategy from recompute to swap
Chunked prefill disabled or misconfigured, large prompt blocks decode	p99 TPOT spike correlated with large prefill events in scheduler logs	Visible stutter for every connected client during the stall	Alert if any iteration’s prefill token count exceeds a configured ceiling; auto-clamp max_num_batched_tokens
KV block leak on abrupt client disconnect mid-stream	Block manager’s allocated block count does not return to the free pool after N seconds of sequence inactivity	Gradual KV pool shrinkage, reduced max concurrency, eventual admission failures	Per-sequence watchdog timer; force-free blocks and mark FINISHED if the client has not acknowledged within the timeout
Swap bandwidth saturation from many simultaneous preemptions	PCIe transfer queue depth or swap latency percentile spike	Preempted sequences take far longer to resume than the cost model assumed	Cap concurrent swap operations; fall back to recompute once swap queue depth exceeds a threshold
Scheduler queue starvation under bursty load	Max wait time per priority tier tracked; alert if p99 queue wait for the lowest tier exceeds SLA	Silent fairness violation - some tenants get effectively no service during peak load	Aging policy that gradually raises priority the longer a sequence waits, guaranteeing eventual admission

Comparison of Approaches

Approach	Throughput	TTFT Impact	Complexity	Best Fit
Static batching	Low-medium (30-50% GPU idle to stragglers)	High and bursty - blocked behind full batch drain	Low	Offline/batch scoring jobs, not interactive chat
Continuous batching, no chunked prefill	Medium-high	Spiky - large prefills can stall decode for hundreds of ms	Medium	Interactive workloads with short, uniform prompts
Continuous batching + chunked prefill	High (8,000+ tok/s at 128 concurrent)	Stable, p99 under 200ms	Medium-high	Production chat and agent serving with mixed prompt lengths
Continuous batching + priority SLA classes	High, allocated by tier	Tunable per tier (premium under 100ms, best-effort unbounded)	High	Multi-tenant platforms with different latency contracts per customer
Disaggregated prefill/decode (separate GPU pools)	Highest at scale (zero prefill/decode interference)	Lowest and most stable	Very high (cross-node KV transfer)	Very large fleets (100+ GPUs) where isolating prefill and decode economics justifies network transfer cost

For most production chat and agent workloads, continuous batching with chunked prefill is the right default - it is well understood, ships production-ready in vLLM and TensorRT-LLM, and closes most of the gap to the compute-bound throughput ceiling without needing a second GPU pool. Priority SLA classes become worth the added complexity once paying tiers have genuinely different latency contracts, not before. Disaggregated prefill/decode is a fleet-scale optimization: it pays for the network hop to move KV cache between pools only when you have enough hardware that right-sizing separate compute-bound prefill and memory-bandwidth-bound decode pools actually changes your total GPU count.

Key Takeaways

• Continuous batching re-decides batch composition at every iteration rather than committing to a batch until it fully drains, which is what eliminates the straggler-waits-for-the-longest-sequence waste inherent to static batching.
• PagedAttention and continuous batching are complementary but distinct: block-based KV allocation solves memory fragmentation, iteration-level scheduling solves compute utilization and admission latency - hitting 8,000+ tokens/sec at 128 concurrent sequences requires both together.
• Chunked prefill is what keeps TPOT stable under mixed traffic; without it, one large incoming prompt can stall decode for every already-connected client for the duration of its entire prefill pass.
• max_num_seqs and gpu_memory_utilization are throughput and latency tuning knobs, not just safety limits - setting max_num_seqs below the memory-derived ceiling is often intentional headroom for preemption slack and TPOT variance control.
• Preemption should default to recompute for short contexts and swap for long ones, since recompute cost scales with tokens already generated while swap cost scales with KV cache bytes and PCIe bandwidth - the crossover point is a real threshold to tune, not a coin flip.
• TTFT and TPOT are optimized by different levers - TTFT is dominated by admission queueing and prefill chunk latency, TPOT by decode iteration latency at current batch occupancy, and a scheduler change that helps one can quietly hurt the other.
• Fairness requires an explicit aging policy - a pure priority queue will starve low-priority traffic indefinitely under sustained load; the fix is raising effective priority the longer a request waits.

The counter-intuitive lesson from this system is that the biggest throughput win doesn’t come from a smarter model or a bigger batch size - it comes from moving the unit of scheduling from “the whole request” down to “the next forward pass.” Once scheduling happens at that granularity, GPU idle time and per-request tail latency turn out to be two symptoms of the same root cause, and fixing one - through chunked prefill and iteration-level admission - fixes the other almost for free.

Frequently Asked Questions

Q: Why not just increase the static batch size instead of building a whole continuous batching scheduler?

A: Increasing batch size makes the straggler problem worse, not better. A larger batch has more sequences in it, which increases the variance in output lengths within that batch, which increases how long the GPU sits mostly-idle waiting for the single longest sequence to finish. It also increases the average wait time for a new request arriving right after the batch closes, since it now has to wait behind a bigger cohort before the next admission window opens. Static batching’s core problem is structural, not a sizing problem.

Q: Why not just prioritize decode over prefill unconditionally and delay all prefill indefinitely until the batch has spare capacity?

A: At sustained high concurrency, decode alone can consume nearly the entire token budget every iteration, meaning prefill chunks for new arrivals never get scheduled at all - TTFT for new requests would grow unbounded under load instead of staying stable. Chunked prefill’s fixed per-iteration reservation for prefill work is what keeps admission latency bounded even when the running queue is full; unconditional decode priority with no reservation defeats that guarantee entirely.

Q: How much does chunked prefill actually save versus a simpler continuous batching implementation, and is it worth the added complexity?

A: In the cost table above, plain continuous batching sustains 6,200 tokens/sec at $0.37 per 1M tokens; adding chunked prefill raises that to 8,000+ tokens/sec at $0.28 per 1M tokens - a 29% throughput gain and 24% cost reduction with no additional hardware. The implementation cost is a token-budget parameter and a chunk-size loop in the scheduler, which is modest compared to the ongoing dollar savings at any real production volume.

Q: How do you know the scheduler is being fair and not silently starving low-priority traffic?

A: Track p99 queue wait time per priority tier as a first-class dashboard metric, not just aggregate throughput. Starvation shows up as a specific tier’s queue wait growing unbounded while other tiers look healthy - aggregate throughput numbers average right over that signal. The fix is an aging policy that raises a sequence’s effective priority the longer it waits, which provides a provable upper bound on worst-case wait time regardless of how much higher-priority traffic keeps arriving.

Q: Isn’t continuous batching just another name for PagedAttention?

A: No - they solve different problems and are commonly confused because vLLM ships both together. PagedAttention is a memory allocation technique: block-based KV cache allocation that eliminates fragmentation. Continuous batching is a scheduling paradigm: deciding batch composition at iteration granularity instead of request granularity. You could in principle run continuous batching over a contiguous (non-paged) KV cache, just with worse memory efficiency and a lower achievable max_num_seqs; the combination of both is what makes modern serving engines hit both high throughput and high concurrency at once.

Q: What happens to tokens already streamed to a client when their sequence gets preempted and later recomputed?

A: Already-streamed tokens are not re-sent or altered - preemption only affects the server’s internal KV cache state, not what has already been delivered to the client. On resume, recompute treats the original prompt plus all previously-generated tokens as the new “prompt” to re-prefill, so the sequence’s internal state catches back up to where it left off and generation continues seamlessly from there, without duplicating or dropping any token the client already received.

Interview Questions

Q: Walk through what happens on a single scheduler iteration when the running queue is full, a new high-priority request arrives, and the KV cache pool has zero free blocks.

Expected depth: The candidate should trace the admission controller’s watermark check failing, triggering the preemption policy to select a victim (lowest priority, most recently admitted), the recompute-vs-swap cost model comparing the victim’s accumulated token count against the recompute/swap crossover threshold, the block manager freeing the victim’s blocks, and the new request’s blocks being allocated from that freed pool - all before the next forward pass is dispatched. Strong answers mention that this whole sequence must be atomic from the scheduler’s perspective and discuss the watermark’s role in guaranteeing the preemption itself doesn’t deadlock.

Q: Derive the maximum number of concurrent sequences a 4xA100 80GB node can hold at a given average context length, and explain why max_num_seqs is often configured below that memory-derived ceiling.

Expected depth: Walk through the KV memory math - per-token KV bytes from head count, head_dim, layer count, and GQA sharding across GPUs; block size and per-sequence block count at the given context length; total KV budget after weights and gpu_memory_utilization. At 2,048-token average context this lands near 218 sequences against a 140GB budget. The candidate should explain that the gap to a configured 128 is intentional: it reserves memory headroom for preemption slack and reduces per-iteration compute variance, which stabilizes TPOT, rather than representing wasted capacity.

Q: Two engineers disagree about whether to use chunked prefill or disaggregated prefill/decode (separate GPU pools) for a new deployment. What’s the actual decision criteria?

Expected depth: The answer should center on fleet scale and the cost of the cross-node KV transfer that disaggregation requires. Chunked prefill is the right default at small to medium GPU counts because it needs no network hop and captures most of the achievable throughput gain. Disaggregation only pays off once fleet size is large enough that right-sizing separate pools - compute-bound prefill hardware differently from memory-bandwidth-bound decode hardware - changes total GPU count enough to offset the network transfer cost and added operational complexity.

Q: A continuous batching server’s aggregate throughput dashboard looks perfectly healthy, but one enterprise customer keeps filing latency complaints. How do you debug this with only the scheduler’s iteration logs?

Expected depth: The candidate should immediately reach for per-tenant and per-priority-tier percentile breakdowns rather than trusting the aggregate. Look for that tenant’s queue wait time trend (starvation via missing aging), check whether their traffic pattern (for example, unusually long prompts) is repeatedly deprioritized behind other tenants in the chunked-prefill queue, and check that tenant’s sequences’ preemption counts specifically, since a tenant with longer-than-average contexts is statistically more likely to be selected as a preemption victim under the “most recently admitted, lowest priority” policy.

Q: Explain why PagedAttention’s block-based KV allocation required a kernel-level change and not just an allocator change, and what would break if you tried to retrofit block-based allocation onto a standard contiguous-KV attention kernel.

Expected depth: The attention kernel itself must gather K/V through the block table indirection at read time - a kernel written assuming contiguous memory has no mechanism to consume scattered physical blocks. Retrofitting block-based allocation onto such a kernel would require a defragmentation copy into contiguous memory before every attention call, which is an O(seq_len) memory-bandwidth cost paid every single decode step, erasing essentially all of the efficiency gain the block-based scheme was meant to deliver.