Continuous Batching: Iteration-Level Scheduling

9. The core mechanism

Illustrative static request-level batching dispatches work at whole-sequence granularity: once a batch of B requests enters the execution loop, the engine repeats forward passes across all B slots until every sequence completes by emitting an end-of-sequence token (<eos>) or reaching its configured token limit.

Continuous batching (formalized as iteration-level scheduling in Orca, Yu et al., OSDI 2022) shifts the scheduling boundary from the entire request lifecycle down to the individual execution step. At each discrete forward pass, the scheduler:

1. Evicts finished sequences: Identifies requests that emitted <eos> or reached stopping conditions, closes their response streams, and releases their unshared KV memory references.
2. Evaluates admission eligibility: Checks waiting queue candidates against remaining sequence slots, step token budgets, and allocatable physical KV blocks.
3. Assembles the next forward batch: Packs surviving decode tokens and newly admitted prefill tokens into a combined iteration batch.

       [ Iteration t ] -> Execute Forward Pass
                              |
       +----------------------+----------------------+
       |                                             |
[ Active Sequences ]                          [ Output Tokens ]
       |                                             |
       | Check completion                            v
       | (did request emit <eos>?)           Evaluate Stop Conditions
       |                                             |
       +------------+--------------------------------+
                    |
     +--------------+--------------+
     |                             |
[ Finished ]                  [ Running ]
     |                             |
Release unshared KV blocks    Retain KV blocks &
& close response stream       append generated token
     |                             |
     +--------------+--------------+
                    |
                    v
    Check Resource Budgets for Iteration t + 1:
      - Active sequences < Max sequence budget?
      - Candidate tokens <= Max token budget?
      - Free KV blocks >= Required immediate blocks?
                    |
     +--------------+--------------+
     |                             |
[ Admissible ]               [ Capacity Met ]
     |                             |
Admit pending request(s)      Defer waiting queue;
from queue into batch         dispatch active decodes
                    |
                    v
       [ Iteration t + 1 Forward Pass ]

Continuous scheduling removes the request-completion barrier of static batches, but it does not guarantee zero queue wait or full GPU silicon utilization. When the queue is empty, slots remain vacant; when memory is saturated, requests wait; and during memory-bound decode iterations, execution units remain memory-starved regardless of slot occupancy.

---

1. Request state machine and accounting conventions

To schedule iterations safely, an engine tracks each request through explicit lifecycle states:

                  +-----------------------------------------------------+
                  |                                                     |
                  v                                                     |
+---------+   admit    +---------+   prompt done   +---------+   finish |  +----------+
| WAITING | ---------> | PREFILL | --------------> | DECODE  | ------------> | FINISHED |
+---------+            +---------+                 +---------+             +----------+
     ^                      |                           |
     |                      | out of memory             | out of memory
     |                      v                           v
     |                +---------------------------------------+
     |                |               PREEMPTED               |
     |                +---------------------------------------+
     |                                    |
     +--- re-queue (recompute history) ---+

• WAITING: The request sits in the host admission queue. No private GPU KV blocks are allocated.
• PREFILL: The engine processes prompt input tokens. A full prompt pass consumes P input tokens and emits the first output token. Under chunked prefill, this occurs across multiple bounded iterations.
• DECODE: The sequence generates tokens autoregressively, processing 1 query token and emitting 1 new output token per forward pass. The KV cache stores consumed input positions; newly sampled output tokens gain KV cache entries when consumed as inputs during the subsequent forward pass.
• FINISHED: The sequence emitted <eos>, hit a stop sequence, or aborted. After in-flight GPU work completes, the engine decrements all KV references. Blocks still referenced elsewhere remain live; zero-reference blocks become free or reclaimable cached entries according to policy.
• PREEMPTED: When allocatable KV blocks are exhausted during generation, the scheduler halts the sequence. Under recompute policies, its private KV cache is discarded and the request returns to the queue. When re-admitted, the engine reprocesses full consumed token history (prompt plus previously generated outputs) to rebuild KV cache state without re-emitting duplicate output tokens to the client.

Step and token conventions

Across this lesson:

• P: Count of prompt input tokens.
• N_gen: Count of generated output tokens (including <eos>).
• Abstract iteration: One discrete forward pass of the model batch. Prefill iterations process multiple input tokens per sequence; decode iterations process 1 query token per sequence.
• Total iterations for an isolated sequence under unchunked prefill: 1 prompt prefill forward pass (consuming P prompt tokens and producing output token 1) + (N_gen - 1) decode passes (consuming output tokens 1 through N_gen - 1 and producing tokens 2, ..., N_gen), totaling N_gen forward passes.

---

2. Comparing static and continuous batching over matching horizons

Rigorous scheduling comparisons require an identical arrival timeline, concurrency limit, and evaluation horizon.

2.1 The evaluation workload

Let the serving engine have a maximum concurrency ceiling of B = 4 active sequence slots.

• Initial Batch (arrives at boundary t = 0, starts iteration 1):
  • Request 1: P = 10, N_gen = 20 (runs iterations 1–20; finishes at iteration 20).
  • Request 2: P = 10, N_gen = 50 (runs iterations 1–50; finishes at iteration 50).
  • Request 3: P = 10, N_gen = 80 (runs iterations 1–80; finishes at iteration 80).
  • Request 4: P = 10, N_gen = 200 (runs iterations 1–200; finishes at iteration 200).
• Subsequent Arrivals:
  • Request 5 arrives at step boundary t = 20 (P = 10, N_gen = 40).
  • Request 6 arrives at step boundary t = 50 (P = 10, N_gen = 40).

2.2 Trace under static request-level batching

Static batching locks slots 1 through 4 into Batch 1 until the longest sequence (N_gen = 200) completes.

Iteration: 1         20             50             80                       200
Req 1:     [=========][------------------ PADDING / DUMMY COMPUTE ----------]
Req 2:     [========================][------------- PADDING / DUMMY --------]
Req 3:     [======================================][--- PADDING ------------]
Req 4:     [===============================================================]
Req 5:     (Arrives t=20) ---------------- WAITS IN QUEUE ----------------> [Runs t=201]
Req 6:     (Arrives t=50) ---------------- WAITS IN QUEUE ------------> [Runs t=201]

• Horizon t in [1, 80] (80 iterations):
  • Allocated capacity: 4 slots * 80 iterations = 320 slot-iterations.
  • Useful tokens produced:
    • Req 1: 20 tokens (iterations 1–20; iterations 21–80 are masked padding).
    • Req 2: 50 tokens (iterations 1–50; iterations 51–80 are masked padding).
    • Req 3: 80 tokens (iterations 1–80).
    • Req 4: 80 tokens (iterations 1–80).
    • Total useful tokens = 20 + 50 + 80 + 80 = 230.
  • Slot occupancy on [1, 80]: 230 / 320 = 71.875% (slot waste: 28.125%).
• Full Batch Horizon t in [1, 200] (200 iterations):
  • Allocated capacity: 4 slots * 200 iterations = 800 slot-iterations.
  • Useful tokens produced: 20 + 50 + 80 + 200 = 350.
  • Wasted padding slot-iterations: 800 - 350 = 450.
  • Slot occupancy on [1, 200]: 350 / 800 = 43.75% (slot waste: 56.25%).
• Queue Delays for New Arrivals:
  • Req 5 arrives at boundary 20. It waits through boundary 200 (180 elapsed boundary ticks) and executes its first iteration in interval 200..201 (iteration index 201).
  • Req 6 arrives at boundary 50. It waits through boundary 200 (150 elapsed boundary ticks) and executes its first iteration in interval 200..201 (iteration index 201).

2.3 Trace under continuous iteration-level batching

Under continuous batching, the scheduler inspects completion at each iteration boundary:

Iteration: 1         20   21        50   51        60        80             200
Req 1:     [=========]
Req 5:                [P5][==== Gen (tokens 2..40) ====][-- IDLE --]
Req 2:     [========================]
Req 6:                               [P6][==== Gen (tokens 2..30) ====]
Req 3:     [======================================]
Req 4:     [===============================================================]

1. Iterations 1 to 20: Requests 1, 2, 3, and 4 run concurrently. Useful tokens: 20 * 4 = 80.
2. At boundary 20: Request 1 finishes and releases Slot 1. Request 5 is at the head of the queue.
3. Iteration 21: Request 5 is admitted into Slot 1, executing prefill (P_5 = 10) and emitting token 1. Requests 2, 3, and 4 execute decode step 21. Useful tokens: 4.
4. Iterations 22 to 50 (29 iterations): Requests 5, 2, 3, and 4 decode concurrently. Useful tokens: 29 * 4 = 116.
5. At boundary 50: Request 2 finishes and releases Slot 2. Request 6 is waiting.
6. Iteration 51: Request 6 is admitted into Slot 2, executing prefill (P_6 = 10) and emitting token 1. Requests 5, 3, and 4 execute decode step 51. Useful tokens: 4.
7. Iterations 52 to 60 (9 iterations): Requests 5, 6, 3, and 4 decode concurrently. Useful tokens: 9 * 4 = 36.
8. At boundary 60: Request 5 completes token 40 and finishes. Because no replacement request is waiting in queue, Slot 1 idles from iteration 61 to 80 (20 idle slot-iterations).
9. Iterations 61 to 80 (20 iterations): Slots 2, 3, and 4 run Requests 6, 3, and 4. Request 6 produces tokens 11 through 30 (30 total output tokens produced by step 80). Request 3 completes token 80 at step 80. Useful tokens: 20 * 3 = 60.

Total useful tokens on [1, 80] under continuous batching:

• Initial cohort (Req 1..4): 20 + 50 + 80 + 80 = 230 tokens.
• Request 5: 40 tokens.
• Request 6: 30 tokens (tokens 1 to 30 of its 40-token target).
• Sum: 230 + 40 + 30 = 300 useful tokens.
• Slot occupancy on [1, 80]: 300 / 320 = 93.75% (slot waste: 6.25%, caused solely by queue starvation on Slot 1 between steps 61 and 80).

Scheduling Policy	Useful Tokens (Steps 1–80)	Slot Occupancy (Steps 1–80)	Req 5 Admission Delay	Req 6 Admission Delay
Static Request-Level Batching	230 / 320	71.88%	180 elapsed ticks (runs at 201)	150 elapsed ticks (runs at 201)
Continuous Batching (Finite Arrivals)	300 / 320	93.75%	0 elapsed ticks (runs at 21)	0 elapsed ticks (runs at 51)

Continuous batching achieves 93.75% slot occupancy on this finite trace—not 100%—because Slot 1 remains empty once Request 5 finishes at step 60. Continuous scheduling eliminates bubble waste from completed requests only when replacement work exists in the admission queue.

---

3. Assembling the mixed-phase forward tensor

This independent tensor example uses a 512-token prompt and three decoders; its sequence labels and prompt length differ from the abstract finite-arrival trace above.

In continuous batching, an execution pass routinely combines multi-token prefills with single-token decodes in a mixed-phase forward pass.

3.1 Packed activations and query offsets

To evaluate variable-length sequences without tensor padding, engines pack all active query tokens into contiguous activation buffers:

• Token IDs: A 1D integer tensor input_ids of shape [total_query_tokens].
• Hidden States: An unpadded 2D activation tensor of shape [total_query_tokens, hidden_dim].
• Attention Projections: Linear projections map hidden states to multi-head query, key, and value tensors. In Grouped-Query Attention (GQA), the count of query heads (H_q) differs from key/value heads (H_kv), yielding shapes [total_query_tokens, H_q, head_dim] for queries and [total_query_tokens, H_kv, head_dim] for keys and values.

To identify sequence boundaries along the flattened query dimension, the runtime constructs query offsets (conceptual metadata name):

cu_seqlens_q = [0, 512, 513, 514, 515]

Here, sequence 0 (prefill) spans query rows 0 to 511. Sequences 1, 2, and 3 (decodes) occupy query rows 512, 513, and 514 respectively.

3.2 Query segments versus historical KV memory

cu_seqlens_q describes query tokens in the current forward pass. It does not describe historical context. Decode requests execute 1 query token, but their attention layers attend over their entire past key-value history:

Step Query Tokens [515, hidden_dim]
  Seq A (512 queries)  | Seq B (1 query) | Seq C (1 query) | Seq D (1 query)
          |                    |                 |                 |
    Causal Attention           |                 |                 |
    over own 512 tokens        |                 |                 |
          |                    v                 v                 v
          |           +---------------------------------------------------+
          |           | Historical KV Context (Retrieved via Block Table) |
          |           |   Req 2: Attends to 51 cached KV tokens           |
          |           |   Req 3: Attends to 81 cached KV tokens           |
          |           |   Req 4: Attends to 21 cached KV tokens           |
          +---------->|   Req 5: Appends 512 new KV tokens to memory pool |
                      +---------------------------------------------------+

To resolve historical keys and values without copying buffers, attention kernels receive conceptual metadata:

• context_lens: A 1D integer tensor recording total context length (past tokens plus current query tokens) for each sequence.
• block_tables: A 2D mapping linking each sequence’s logical KV blocks to physical block identifiers in memory.

A full transformer forward pass typically dispatches multiple GPU kernels (GEMMs for projections, normalization, attention kernels, and activation functions); no single monolithic kernel executes all phases.

---

4. Compute and memory dynamics of mixed iterations

Co-scheduling prompt prefill with token decodes alters arithmetic intensity. We examine this using an analytical model of linear projections and weight streaming.

4.1 Nominal analytical model

Consider an 8B parameter model in FP16 precision:

• Parameter count: N_params = 8.0e9.
• Weight memory: M_weights = 8.0e9 * 2 bytes = 16.0 GB (decimal).
• Linear projection arithmetic: Standard matrix multiply heuristic evaluates to 2 FLOPs per parameter per token, giving 2 * 8.0e9 = 16.0e9 FLOPs = 16 GFLOP of linear matrix multiplication work per token.
• Hardware baseline (NVIDIA H100 SXM nominal ratings):
  • Memory bandwidth: BW_peak = 3.35 TB/s = 3.35e12 bytes/sec.
  • FP16 Tensor Core dense compute: R_peak = 989 TFLOP/s = 989e12 FLOP/s.
• Grouped-Query Attention (GQA) KV specification:
  • 32 layers, 8 KV heads (H_kv), head dimension 128, FP16 precision (2 bytes).
  • Bytes per cached token across all layers: 32 layers * 2 (K and V) * 8 heads * 128 dim * 2 bytes = 131,072 bytes/token (128 KiB/token).

Nominal model estimates versus runtime profiling

The calculations below represent idealized service-time estimates under this nominal model: t_step = max(t_mem, t_comp). They isolate parameter weight streaming and linear projection FLOPs. They omit quadratic attention operations, SRAM cache reuse, KV write traffic, kernel launch latency, and GPU execution efficiency. They demonstrate arithmetic shifts, not proof of measured bottlenecks or wall-clock ITL bounds.

4.2 Decode iteration versus mixed iteration

• Scenario A: Pure Decode Iteration (the same 3 decoders)
  • Linear compute: 16.0e9 * 3 = 48 GFLOPs.
  • Compute estimate: t_comp = 48e9 / 989e12 = 0.049 ms.
  • Memory estimate (weight streaming): t_mem = 16.0e9 / 3.35e12 = 4.78 ms.
  • Model estimate: max(4.78, 0.049) = 4.78 ms (memory-limited within this nominal model).
• Scenario B: Mixed Iteration (1 prefill of 512 tokens + 3 decodes = 515 tokens)
  • Linear compute: 16.0e9 * 515 = 8.24 TFLOPs.
  • Compute estimate: t_comp = 8.24e12 / 989e12 = 8.33 ms.
  • Memory estimate (weight streaming): Assume weights are read once and reused across all 515 tokens: t_mem = 4.78 ms.
  • Model estimate: max(4.78, 8.33) = 8.33 ms (compute-limited within this nominal model).

In Scenario A, the iteration estimate is governed by weight transit under this nominal model. In Scenario B, admitting 512 prompt tokens increases linear work over a hundredfold, pushing the compute service estimate past the weight transit estimate.

4.3 Why mixed steps cause ITL jitter

For an ongoing decode client, Inter-Token Latency (ITL) is the wall-clock time between successive tokens. When an unchunked prompt enters the batch, the forward step duration stretches to accommodate the dense matrix multiplications of the prefill tokens. Decode streams sharing that forward pass pause until the full mixed step completes.

Quantifying exact jitter requires profiler traces (e.g., PyTorch Profiler or NVIDIA Nsight Systems) to capture kernel launch delays, attention scaling, and memory contention. The nominal model motivates a prefill-interference hypothesis; a measured increase in mixed-step duration is needed to attribute actual ITL variance.

---

5. Scheduler budget invariants and preemption policies

Per-iteration sequence, query-token and KV budgets protect resource limits. Avoiding starvation additionally requires a fairness policy.

5.1 Resource invariants and block requirement math

Let block_size be the number of tokens held in one physical KV block (e.g., 16 tokens). For an unshared sequence with cached_tokens already stored, adding input_tokens requires:

new_blocks = ceil((cached_tokens + input_tokens) / block_size) - ceil(cached_tokens / block_size)

If cached_tokens = 14, input_tokens = 1, and block_size = 16:

• old_blocks = ceil(14 / 16) = 1.
• new_blocks = ceil(15 / 16) - 1 = 0. The decode step appends to the unallocated tail of the existing block without consuming a new physical block.

The scheduler enforces:

1. Sequence budget (B_seq): Total active sequences cannot exceed slot capacity.
2. Token budget (B_tok): Total tokens (decode query tokens + admitted prefill tokens) cannot exceed the per-step threshold.
3. KV block budget (B_kv): Allocatable physical blocks must cover the plan’s checked reservations, including shared-tail copies. A runtime may additionally keep a policy-defined headroom threshold; that heuristic is not a capacity guarantee.

5.2 Fairness, starvation, and cancellation

• Decode-First Priority and Starvation: Prioritizing decode iterations protects their scheduling opportunities, though iteration duration and actual ITL still depend on context lengths and other work. However, if active decodes continually saturate the token or block budget, waiting prefills starve indefinitely. Engines mitigate this by reserving a minimum prefill token share or applying queue aging policies.
• Client Cancellation: When a client disconnects, cancellation takes effect at the iteration boundary after in-flight GPU execution completes the current step, after which the scheduler releases its unshared KV block references.
• Preemption Options:
  • Recomputation: The engine frees the victim’s allocated KV blocks and requeues the request. Upon readmission, the engine recomputes historical tokens up to the current position. vLLM V1 documentation designates recomputation as its primary preemption strategy.
  • Host Swapping: The engine offloads KV blocks to host system memory over PCIe and swaps them back when GPU memory frees. Swapping avoids duplicate computation but incurs bus transfer latency and requires pinned host memory pools.

---

6. Concise scheduler algorithm

The continuous batching scheduling cycle operates in phase-safe stages: snapshot completions, construct a transactional reservation plan, dispatch forward kernels, commit consumed input KV, and sample outputs.

# Conceptual pseudocode; not executable code or a specific engine API.
Function schedule_iteration(requests, pool, budgets):
    await_previous_gpu_completion()
    retire_finished_or_cancelled_from_snapshot(requests)
    # Retirement decrements ALL references; reclaim only blocks with no readers.

    ready_decodes = snapshot(requests where phase == DECODE)
    pending_prefills = snapshot(requests where phase in {WAITING, PREFILL, RECOMPUTE})
    plan = new_transactional_plan(pool, budgets)

    For req in ready_decodes followed by policy_order(pending_prefills):
        If req already in plan: Continue
        n = 1 if req.phase == DECODE else min(req.remaining_inputs, plan.tokens_left)
        If n <= 0 or plan.sequence_slots_left == 0: Defer req; Continue
        # Include a new block, tail CoW, sharing and existing reservations.
        needed = pool.blocks_for_consumed_inputs(req, n)
        If not plan.can_reserve(sequence_slots=1, query_tokens=n, blocks=needed):
            Defer req; Continue
        plan.reserve(req, n, needed)  # Does not modify live request phase or queues

    If plan is empty:
        plan.rollback()
        victim = policy_select_safe_preemption_victim(requests)
        If victim exists:
            # No submitted plan references its buffers; previous GPU work is done.
            preserve_full_consumed_history_and_emitted_count(victim)
            drop_all_kv_references(victim)  # Shared blocks may remain resident
            queue_for_recompute(victim)
        Return DEFERRED  # Next call replans; no unbounded retry loop

    If not pool.atomically_commit(plan):
        plan.rollback()
        Return DEFERRED
    outputs = dispatch_forward_kernels(plan)
    await_gpu_completion(outputs)
    For req, n in plan:
        req.commit_consumed_input_kv(n)
        If req.phase == DECODE or req.finished_fresh_prefill():
            sample_and_emit_next_token(req, outputs)
            req.phase = DECODE
        Else if req.finished_recompute():
            # Rebuild only history already consumed; retain the pending last output.
            # Resume with that pending input next step; never emit old outputs twice.
            req.phase = DECODE
            req.rebuilding_history = False
        Else:
            req.phase = RECOMPUTE if req.rebuilding_history else PREFILL
    retire_finished_or_cancelled_from_snapshot(requests)

finished_fresh_prefill() means all prompt inputs have been consumed and rebuilding_history is false. finished_recompute() means the consumed history has been restored while that flag is true. The flag persists across partial rebuild chunks; both completed paths transition to DECODE.

The planner defers work it cannot reserve and may return without dispatching. A real engine also needs a policy that ensures progress: fair candidate ordering, bounded retries, overload rejection and preemption rules that avoid repeatedly rebuilding the same request. Decode-first ordering alone does not provide those guarantees.

---

7. Concrete implementation: a deterministic scheduling simulator

The following self-contained Python 3 program simulates slot occupancy over the identical finite arrival workload. One abstract slot tick produces one output token, including the first prefill output; prompt length does not affect tick duration. A separate helper checks fresh, unchunked admission against sequence, query-token and private-block limits. These are two teaching models, not an integrated phase/KV scheduler or a wall-clock simulation.

Setup and execution

Save the script as scheduler_sim.py and run using standard Python 3:

python3 scheduler_sim.py

Expected output:

Static batching [1, 80] useful tokens: 230 / 320 (71.88%)
Continuous batching [1, 80] useful tokens: 300 / 320 (93.75%)
All scheduler assertions verified deterministically.

"""
Continuous vs Static Batching Scheduling Simulator.
Demonstrates:
1. Slot occupancy derivation over identical horizons [1, 80] and [1, 200].
2. Admission delay tracking under discrete boundary arrivals.
3. Resource budget evaluation across sequences, tokens, and KV blocks.
"""

import math
from dataclasses import dataclass
from enum import Enum
from typing import List, Optional, Dict, Tuple


class RequestState(Enum):
    WAITING = "WAITING"
    PREFILL = "PREFILL"
    DECODE = "DECODE"
    PREEMPTED = "PREEMPTED"
    FINISHED = "FINISHED"


@dataclass
class Request:
    req_id: int
    arrival_boundary: int
    prompt_len: int
    target_gen_len: int
    state: RequestState = RequestState.WAITING
    admitted_at: Optional[int] = None
    finished_at: Optional[int] = None
    tokens_generated: int = 0
    cached_tokens: int = 0


def calculate_new_blocks_needed(cached_tokens: int, input_tokens: int, block_size: int = 16) -> int:
    """
    Computes physical blocks required to append input_tokens to an unshared sequence.
    Requires non-negative inputs. Assumes private unshared block tails.
    """
    assert cached_tokens >= 0 and input_tokens >= 0 and block_size > 0
    old_blocks = math.ceil(cached_tokens / block_size) if cached_tokens > 0 else 0
    new_blocks = math.ceil((cached_tokens + input_tokens) / block_size) if (cached_tokens + input_tokens) > 0 else 0
    return new_blocks - old_blocks


def check_admission_eligibility(
    candidate: Request,
    active_seq_count: int,
    current_step_tokens: int,
    free_blocks: int,
    max_seqs: int,
    max_tokens: int,
    block_size: int = 16
) -> Tuple[bool, str]:
    """
    Standalone eligibility helper evaluating admission against scalar limits.
    Requires non-negative inputs. Assumes unshared private blocks.
    """
    assert active_seq_count >= 0 and current_step_tokens >= 0 and free_blocks >= 0
    if active_seq_count + 1 > max_seqs:
        return False, "DEFERRED_SEQUENCE_BUDGET"
    if current_step_tokens + candidate.prompt_len > max_tokens:
        return False, "DEFERRED_TOKEN_BUDGET"
    blocks_needed = calculate_new_blocks_needed(candidate.cached_tokens, candidate.prompt_len, block_size)
    if free_blocks < blocks_needed:
        return False, "DEFERRED_KV_BUDGET"
    return True, "ADMITTED"


def simulate_static_batching(
    initial_requests: List[Request],
    arriving_requests: List[Request],
    max_slots: int = 4
) -> Dict[str, float]:
    """
    Simulates request-level static batching across identical arrival timelines.
    """
    if not initial_requests:
        return {"occupancy_80": 0.0, "occupancy_full": 0.0}

    batch = [
        Request(r.req_id, r.arrival_boundary, r.prompt_len, r.target_gen_len)
        for r in initial_requests[:max_slots]
    ]
    max_batch_len = max(r.target_gen_len for r in batch)

    useful_tokens_80 = 0
    total_slots_80 = max_slots * 80

    useful_tokens_full = 0
    total_slots_full = max_slots * max_batch_len

    for r in batch:
        useful_tokens_full += r.target_gen_len
        useful_tokens_80 += min(r.target_gen_len, 80)

    queue_delays_boundary = {}
    index_diff_first_exec = {}
    for r in arriving_requests:
        queue_delays_boundary[r.req_id] = max_batch_len - r.arrival_boundary
        index_diff_first_exec[r.req_id] = (max_batch_len + 1) - r.arrival_boundary

    return {
        "useful_tokens_80": useful_tokens_80,
        "total_slots_80": total_slots_80,
        "occupancy_80": useful_tokens_80 / total_slots_80,
        "useful_tokens_full": useful_tokens_full,
        "total_slots_full": total_slots_full,
        "occupancy_full": useful_tokens_full / total_slots_full,
        "queue_delays_boundary": queue_delays_boundary,
        "index_diff_first_exec": index_diff_first_exec,
    }


def simulate_continuous_batching(
    all_requests: List[Request],
    horizon: int = 80,
    max_slots: int = 4
) -> Dict[str, float]:
    """
    Simulates iteration-level continuous batching over an identical horizon.
    """
    req_pool = [
        Request(r.req_id, r.arrival_boundary, r.prompt_len, r.target_gen_len)
        for r in all_requests
    ]
    active_slots: List[Optional[Request]] = [None] * max_slots
    waiting_queue: List[Request] = []

    useful_tokens = 0
    total_slots = max_slots * horizon
    first_execution_step: Dict[int, int] = {}

    for step in range(1, horizon + 1):
        # 1. Admit new arrivals available at prior step boundary
        for r in req_pool:
            if r.arrival_boundary == step - 1:
                waiting_queue.append(r)

        # 2. Evict finished requests
        for i in range(max_slots):
            curr = active_slots[i]
            if curr is not None and curr.tokens_generated >= curr.target_gen_len:
                curr.state = RequestState.FINISHED
                curr.finished_at = step - 1
                active_slots[i] = None

        # 3. Admit waiting requests into vacant slots
        for i in range(max_slots):
            if active_slots[i] is None and waiting_queue:
                candidate = waiting_queue.pop(0)
                candidate.state = RequestState.PREFILL
                candidate.admitted_at = step
                first_execution_step[candidate.req_id] = step
                active_slots[i] = candidate

        # 4. Execute forward pass across occupied slots
        for i in range(max_slots):
            curr = active_slots[i]
            if curr is not None:
                useful_tokens += 1
                curr.tokens_generated += 1
                if curr.state == RequestState.PREFILL:
                    curr.state = RequestState.DECODE

    return {
        "useful_tokens_80": useful_tokens,
        "total_slots_80": total_slots,
        "occupancy_80": useful_tokens / total_slots,
        "first_execution_step": first_execution_step,
    }


def run_checks():
    # Setup initial batch: lengths [20, 50, 80, 200]
    initial = [
        Request(1, arrival_boundary=0, prompt_len=10, target_gen_len=20),
        Request(2, arrival_boundary=0, prompt_len=10, target_gen_len=50),
        Request(3, arrival_boundary=0, prompt_len=10, target_gen_len=80),
        Request(4, arrival_boundary=0, prompt_len=10, target_gen_len=200),
    ]
    # Subsequent arrivals
    arrivals = [
        Request(5, arrival_boundary=20, prompt_len=10, target_gen_len=40),
        Request(6, arrival_boundary=50, prompt_len=10, target_gen_len=40),
    ]

    # 1. Static Batching Verification
    s_res = simulate_static_batching(initial, arrivals, max_slots=4)
    assert s_res["useful_tokens_80"] == 230
    assert s_res["total_slots_80"] == 320
    assert abs(s_res["occupancy_80"] - 0.71875) < 1e-5
    assert s_res["useful_tokens_full"] == 350
    assert s_res["total_slots_full"] == 800
    assert abs(s_res["occupancy_full"] - 0.4375) < 1e-5
    assert s_res["queue_delays_boundary"][5] == 180
    assert s_res["index_diff_first_exec"][5] == 181

    # 2. Continuous Batching Verification
    c_res = simulate_continuous_batching(initial + arrivals, horizon=80, max_slots=4)
    # Useful tokens: Req 1(20) + Req 2(50) + Req 3(80) + Req 4(80) + Req 5(40) + Req 6(30) = 300
    assert c_res["useful_tokens_80"] == 300
    assert c_res["total_slots_80"] == 320
    assert abs(c_res["occupancy_80"] - 0.9375) < 1e-5
    assert c_res["first_execution_step"][5] == 21
    assert c_res["first_execution_step"][6] == 51

    # 3. Resource Eligibility Verification
    # Test block math: append within existing unallocated tail requires 0 new blocks
    assert calculate_new_blocks_needed(cached_tokens=14, input_tokens=1, block_size=16) == 0
    assert calculate_new_blocks_needed(cached_tokens=16, input_tokens=1, block_size=16) == 1
    assert calculate_new_blocks_needed(cached_tokens=0, input_tokens=10, block_size=16) == 1

    # Test admission constraints deterministically
    cand = Request(7, arrival_boundary=0, prompt_len=50, target_gen_len=10)
    # Exceed sequence budget
    ok, reason = check_admission_eligibility(cand, 4, 100, 20, max_seqs=4, max_tokens=512)
    assert not ok and reason == "DEFERRED_SEQUENCE_BUDGET"
    # Exceed token budget
    ok, reason = check_admission_eligibility(cand, 2, 480, 20, max_seqs=4, max_tokens=512)
    assert not ok and reason == "DEFERRED_TOKEN_BUDGET"
    # Exceed KV block budget (needs ceil(50/16)=4 blocks, only 2 free)
    ok, reason = check_admission_eligibility(cand, 2, 100, 2, max_seqs=4, max_tokens=512)
    assert not ok and reason == "DEFERRED_KV_BUDGET"
    # Admitted case
    ok, reason = check_admission_eligibility(cand, 2, 100, 10, max_seqs=4, max_tokens=512)
    assert ok and reason == "ADMITTED"

    print(f"Static batching [1, 80] useful tokens: {s_res['useful_tokens_80']} / {s_res['total_slots_80']} ({s_res['occupancy_80']:.2%})")
    print(f"Continuous batching [1, 80] useful tokens: {c_res['useful_tokens_80']} / {c_res['total_slots_80']} ({c_res['occupancy_80']:.2%})")
    print("All scheduler assertions verified deterministically.")


if __name__ == "__main__":
    run_checks()

---

8. Incident diagnosis: diagnosing queue collapse and ITL spikes

Hypothetical teaching case

Consider a hypothetical teaching scenario modeled on real-world failure patterns in an LLM serving cluster.

Observed symptoms

During a sudden traffic increase:

• Client-observed P99 Inter-Token Latency (ITL) jumps from 15 ms to over 160 ms.
• API gateways begin logging HTTP 504 gateway timeouts on streaming connections.
• GPU device memory registers near 100% capacity.
• Overall completed token throughput drops by 60%.

[ Normal State ]
ITL: 15 ms  |  Active Decodes: 128  |  Free KV Blocks: 35%  |  Throughput: 3,200 tok/s

[ Incident Progression ]
12:00:00 - Traffic burst: 20 unchunked 4K-token document queries arrive.
12:00:02 - Scheduler admits large prompts into active mixed iterations.
12:00:03 - Forward step compute expands; ITL spikes across streaming clients.
12:00:08 - Influx of 4K KV tokens depletes free physical block pool.
12:00:10 - Scheduler triggers PREEMPTION, evicting active decoders.
12:00:12 - Under Recompute policy, evicted requests re-enter queue and re-run prefills.
12:00:20 - Redundant prefill thrashing causes throughput collapse.

Disambiguating competing hypotheses

A surge in ITL paired with high memory utilization permits multiple distinct root causes. The triage team checks specific runtime counters:

+---------------------------------------------------------------------------------------+
| Diagnostic Triage Matrix                                                              |
+---------------------------------------------------------------------------------------+
| Hypothesis 1: Compute Saturation via Unchunked Prefills                               |
|   - Counter to Check: `forward_step_duration` plotted against `step_tokens`.          |
|   - Signature: Step duration correlates directly with admitted prompt token count.   |
|                                                                                       |
| Hypothesis 2: Memory Exhaustion and Recompute Thrashing                               |
|   - Counter to Check: `num_preemptions` and `recomputed_token_ratio`.                 |
|   - Signature: Spikes in preemption counter paired with repetitive prompt passes for  |
|     previously active request IDs.                                                    |
|                                                                                       |
| Hypothesis 3: Hardware Throttling or Driver Stalls                                    |
|   - Counter to Check: GPU clock frequencies, PCIe replay counters, thermal state.     |
|   - Signature: Step duration increases while batch token count remains constant.      |
+---------------------------------------------------------------------------------------+

Worked remediation decisions

1. Bound Per-Step Query Tokens via Token Budgets: Configure a maximum query token budget (e.g., conceptual max_num_batched_tokens = 512) to enforce chunked prefill. While this bounds linear projection FLOPs per step, it does not cap all compute or eliminate all ITL variance because attention cost scales with historical context lengths.
2. Enforce Per-Step Block Reservations and Context Limits: A free-block watermark heuristic alone does not guarantee memory safety. Rigorous safety requires enforcing per-step KV block reservations against hard sequence context limits, rejecting or deferring admissions before cumulative worst-case requirements exceed physical pool capacity.
3. Handle Client Disconnects: Attach cancellation callbacks to network connection drops. Cancellation releases unshared KV blocks at the step boundary after in-flight GPU execution completes the current pass.

What remains unknown without kernel profiling: The exact split between attention kernel latency and linear projection GEMMs, CPU-to-GPU dispatch overhead, and the impact of host PCIe transfers if swapping is enabled.

---

10. Key Takeaways

Key takeaways

• Continuous batching shifts scheduling decisions from request lifecycles to individual forward iterations, retiring completed sequences at safe iteration boundaries and admitting waiting requests without request-level barriers.
• Token slot occupancy is an accounting of active versus padded batch slots, not a guarantee of full GPU Tensor Core utilization or zero queuing delay; memory-bound decode iterations leave execution units largely idle.
• Mixed-phase steps pack prompt query tokens and decode query tokens into unpadded 2D activation tensors, using query offsets and paged block tables to retrieve historical KV context from memory.
• Large mixed-phase steps can increase ITL and KV pressure. Query-token budgets limit new work; context limits and checked per-step block reservations protect capacity. Their latency effects require measurement.

---

11. Exercises

Try it yourself

1. 01A batch of 4 requests with generated lengths [30, 60, 90, 150] executes under static batching. Calculate useful token slots, total allocated slot-iterations, and slot occupancy across: (a) the identical horizon [1, 90], and (b) the full batch lifetime [1, 150]. If Request 5 arrives at step boundary 30, state how many boundary steps it waits before admission under static batching versus continuous batching (assuming available replacement slots).

   Show a hint

   For [1, 90]: Useful slots = 30 + 60 + 90 + 90 = 270. Total slots = 4 * 90 = 360. Occupancy = 270 / 360 = 75.0%. For [1, 150]: Useful slots = 30 + 60 + 90 + 150 = 330. Total slots = 4 * 150 = 600. Occupancy = 330 / 600 = 55.0%. Request 5 arrives at boundary 30: under static batching it waits through boundary 150 (120 boundary steps) until Batch 1 completes and runs at 151; under continuous batching it is admitted at iteration 31 (0 boundary waiting steps, runs at iteration 31).

2. 02An engine has a physical block size of 16 tokens, a sequence slot limit of B_seq = 4, and 6 free physical blocks. Two active requests occupy slots: Request A has 28 tokens cached; Request B has 15 tokens cached (both unshared private blocks, no other reservations). (a) In the upcoming iteration, how many new physical blocks are required to generate 1 decode token for each active request? (b) If candidate Request C arrives with a prompt of 35 tokens and the engine has a token budget of 512, how many blocks does Request C require upon admission, and can it be admitted assuming a spare sequence slot exists?

   Show a hint

   (a) Request A has 28 tokens cached (ceil(28/16) = 2 blocks; unallocated tail holds 32 - 28 = 4 tokens). Appending 1 token reaches 29 tokens (ceil(29/16) = 2 blocks), requiring 0 new blocks. Request B has 15 tokens cached (ceil(15/16) = 1 block; unallocated tail holds 16 - 15 = 1 token). Appending 1 token reaches 16 tokens (ceil(16/16) = 1 block), requiring 0 new blocks. Both decodes proceed within unallocated tails of existing private blocks. (b) Request C prompt of 35 tokens requires ceil(35/16) = 3 blocks. Free blocks = 6 >= 3, active sequence count becomes 2 + 1 = 3 ≤ 4, and step query budget (2 decodes + 35 prefill = 37 ≤ 512) is satisfied. Request C is admitted, leaving 6 - 3 = 3 free blocks.

3. 03An inference engine configures a per-step token budget of B_tok = 512 tokens and currently has 500 active decode requests. Under strict decode-first scheduling, explain how prefill admission differs for an incoming request with a 30-token prompt under unchunked versus chunked prefill. What occurs if active decodes reach 512, and how do fairness policies address prefill starvation?

   Show a hint

   500 active decodes consume 500 tokens of step budget, leaving 512 - 500 = 12 tokens. Under unchunked prefill, a 30-token prompt cannot fit while this decode count persists and must wait for enough budget to become available. Under chunked prefill (assuming spare sequence slots and KV blocks), the prompt progresses across multiple steps in chunks (e.g., 12 + 12 + 6 tokens). If active decodes reach 512, 0 tokens remain for prefill; if decodes are continually backfilled, prefills starve completely. Schedulers mitigate this by enforcing reserved prefill token shares (e.g., reserving 128 tokens for prefill) or applying queue aging to temporarily prioritize prompt chunks, trading decode opportunities against prefill progress; actual TTFT and ITL still require measurement.

---

12. Sources and scope

Claim / Topic	Primary Source	Scope and Key Findings
Iteration-Level Scheduling	Yu et al., Orca, OSDI 2022	§1, §3.1–3.3. Formalizes iteration-level scheduling and selective batching before paged allocation, demonstrating dynamic addition and removal of sequences.
Paged Memory Integration	Kwon et al., PagedAttention, SOSP 2023	§4.1–4.3, §4.5. Integrates iteration scheduling with physical block mapping, block tables, and swap/recompute preemption mechanics.
Chunked Prefill & ITL Mitigation	Agrawal et al., Sarathi-Serve, OSDI 2024	§4.1–4.3. Analyzes ITL jitter from unchunked mixed steps and introduces chunked prefill budgets to balance compute across iterations.
vLLM V1 Engine Architecture	vLLM V1 Optimization Guide	Official documentation (accessed 2026-11-03). Documents decode-first token budgeting, chunked prefill, and recomputation default policy.

---

Related lessons

• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryPagedAttention: Virtual Memory for the KV Cache35 min
• Inference Optimisation & AI Infrastructure · Schedule Requests and Manage KV MemoryBatching and Throughput26 min
• Inference Optimisation & AI Infrastructure · Measure and Explain Inference PerformanceServing Workloads and Performance Metrics12 min