The scheduler: states, admission, preemption

Your Llama-3-8B server has been healthy for an hour. Then the p99 TTFT goes from 300 ms to 9 s, output tokens/s drops by 40%, and the log starts repeating one line:

            msg_prefix = (
                "KV cache pool is full. Retract requests. "
                if kv_full_retract_flag
                else "Testing retraction. "
            )
            msg_details = f"#retracted_reqs: {len(retracted_reqs)}, #new_tokens_gained: {new_token_gained}"
            if mamba_num_gained is not None:
                msg_details += f", #mamba_num_gained: {mamba_num_gained}"
            if kv_full_retract_flag:
                msg_details += (
                    f", #new_token_ratio: {old_ratio:.4f} -> {new_token_ratio:.4f}"
                )
            logger.warning(msg_prefix + msg_details)

vLLM prints the same symptom more quietly — a counter appended to the periodic stats line, and a Prometheus counter named vllm:num_preemptions:

        if self.num_preemptions > 0:
            log_parts.append("Preemptions: %d")
            log_args.append(self.num_preemptions)

Preemption is an expected recovery path, not proof that every request will complete: overload, timeouts, cancellation, or worker errors can still fail requests. What has happened is that the engine ran out of KV cache blocks for sequences it had already admitted, threw some of them out, and will now redo their prefill. The tokens you paid for once, you are paying for again. This chapter is about the machine that makes that call: what states a request can be in, what admission actually tests, who gets evicted, and what happens to the evicted sequence's KV.

A serving engine is a queueing system with one unusual property: admission is reversible. A request that has been running for 400 decode steps can be thrown back into the queue, and the only cost is the work already done. That single property is what separates an LLM scheduler from a thread scheduler. Everything else — queues, budgets, priorities — is standard. The reversibility is where the engineering is.

vLLM makes the state machine explicit. Every request carries a RequestStatus, and the enum is short enough to read in full:

class RequestStatus(enum.IntEnum):
    """Status of a request."""

    WAITING = enum.auto()
    WAITING_FOR_STRUCTURED_OUTPUT_GRAMMAR = enum.auto()
    WAITING_FOR_REMOTE_KVS = enum.auto()
    WAITING_FOR_STREAMING_REQ = enum.auto()
    RUNNING = enum.auto()
    PREEMPTED = enum.auto()
    # Note: anything after PREEMPTED will be considered
    # as a finished status.
    FINISHED_STOPPED = enum.auto()
    FINISHED_LENGTH_CAPPED = enum.auto()
    FINISHED_ABORTED = enum.auto()
    FINISHED_IGNORED = enum.auto()
    FINISHED_ERROR = enum.auto()
    FINISHED_REPETITION = enum.auto()

    def __str__(self) -> str:
        return self.name

    @staticmethod
    def is_finished(status: "RequestStatus") -> bool:
        return status > RequestStatus.PREEMPTED

Note the trick in is_finished: terminality is encoded in the ordering of the enum, not in a set membership test. Anything numerically greater than PREEMPTED is done. That is why the comment above FINISHED_STOPPED is load-bearing — inserting a new non-terminal state below that line would silently classify that new non-terminal state as finished.

Three of the four waiting states are not really "waiting for the GPU" — they are waiting for something external (a compiled grammar, a remote KV transfer, the next chunk of a streamed input). vLLM keeps them in a second queue, skipped_waiting, so they cannot block the head of the real admission queue. SGLang has no status enum at all: a request's state is implied by which container holds it (waiting_queue, running_batch.reqs, the disaggregation queues) plus two booleans, is_retracted and finished(). Both designs work; the vLLM one is far easier to assert on, which is why its scheduler is full of assert request.status == ....

Admitting a request is not one test. It is four, and every one of them can be the binding constraint on a given step. Using vLLM's names:

            while (self.waiting or self.skipped_waiting) and token_budget > 0:
                if input_budget <= draft_slots:
                    break
                # Paused streaming sessions (WAITING_FOR_STREAMING_REQ) are not
                # in `running` but still hold a model-runner request slot.
                num_running = len(self.running) + self.num_waiting_for_streaming_input
                if num_running >= self.max_num_running_reqs:
                    break

That is the token budget (max_num_batched_tokens, how many token positions this forward pass may contain) and the slot budget (max_num_seqs, how many rows the persistent input batch has). The third test is the block budget, and it lives one layer down, in the KV cache manager. From the scheduler's point of view the entire block allocator is a predicate: it either hands back blocks or it hands back None.

        # Keep `reserved_blocks` free for other in-flight sequences, and an
        # additional watermark of headroom for waiting/preempted admissions.
        available_blocks = self.block_pool.get_num_free_blocks() - reserved_blocks
        required_blocks = num_blocks_to_allocate + watermark_blocks
        if required_blocks > available_blocks:
            # Cannot allocate new blocks
            return None

The fourth test is the watermark — the reason this chapter exists rather than being a paragraph in the last one. It is deliberately asymmetric:

        watermark_blocks = 0
        # The watermark is applied to waiting/preempted requests only, and only
        # when there's at least one request already scheduled.
        if has_scheduled_reqs and request.status in (
            RequestStatus.WAITING,
            RequestStatus.PREEMPTED,
        ):
            watermark_blocks = self.watermark_blocks

A running request asking for its next block is never watermarked; only a new admission is. The watermark is a tax on growing the batch, not on keeping it alive. Its size comes straight from config, and the default is off:

    watermark: float = Field(default=0.0, ge=0.0, lt=1.0)
    """Fraction of total KV cache blocks to keep free (the watermark) when
    admitting waiting or preempted requests into the running queue. This headroom
    helps avoid frequent KV cache eviction and the resulting repeated preemption
    of requests when GPU memory is scarce. Must be in the range [0.0, 1.0); 0.0
    (the default) disables the watermark."""

Working the numbers on Llama-3-8B

Llama-3-8B: $L = 32$ layers, $h_{kv} = 8$ KV heads, $d_h = 128$ head dim, bf16 (2 bytes). KV bytes per token (the formula is derived in §2.1):

§0.1 budgets an “80 GB” H100 — $79.65$ GiB as the device actually presents it — at $0.92 \times 79.65 - 14.96 - 6 \approx 52.32$ GiB of KV pool. This chapter works with a round 40 GiB instead — deliberately conservative, and chosen because it makes the block counts below exact rather than approximate. Every figure that follows scales linearly, so read 40 GiB as a floor and §0.1's 52.32 GiB as the ceiling for the same card. Derived: a 40 GiB pool holds

Now the tension is visible. With --max-num-seqs 256 and an 8k-token average context, a full batch would need $256 \times 8192 = 2{,}097{,}152$ token-slots — 6.4× what exists. The slot budget says 256; the block budget says 40. The block budget always wins, and the scheduler discovers this the hard way, one allocate_slots call at a time.

How fast does the pool drain once it is full? Each running sequence needs one new block every block_size = 16 decode steps. With 40 running sequences, derived demand is $40/16 = 2.5$ blocks per step — about 5 MiB per forward pass. With watermark = 0.0, the very first step where demand exceeds supply preempts. With --watermark 0.01 you reserve $0.01 \times 20480 = 204$ blocks, which buys $204 / 2.5 \approx 82$ decode steps of runway before the running set has to evict anyone. That is the entire function of the watermark: convert a cliff into a slope.

vLLM's ordering policy is one file, two classes, and two options:

class SchedulingPolicy(Enum):
    """Enum for scheduling policies."""

    FCFS = "fcfs"
    PRIORITY = "priority"

FCFSRequestQueue is literally a deque subclass; PriorityRequestQueue is a heapq over Request.__lt__. The comparison is the whole fairness story for the priority path:

    def __lt__(self, other: "Request") -> bool:
        """
        Compare two requests based on priority, arrival time, and request ID.
        Used in priority scheduling.
        """
        if self.priority != other.priority:
            return self.priority < other.priority
        if self.arrival_time != other.arrival_time:
            return self.arrival_time < other.arrival_time
        if self.request_id != other.request_id:
            return self.request_id < other.request_id
        return id(self) < id(other)

Ties break on arrival time, then request ID, then object identity, so the order is total and deterministic — which matters because a non-total heap order makes victim selection non-reproducible.

SGLang went the other way. It has six policies, split by whether they need to consult the radix tree:

class CacheAwarePolicy(Enum):
    """Scheduling policies that are aware of the tree cache."""

    LPM = "lpm"  # longest prefix match
    DFS_WEIGHT = "dfs-weight"  # depth-first search weighting


class CacheAgnosticPolicy(Enum):
    """Scheduling policies that are not aware of the tree cache."""

    FCFS = "fcfs"  # first come first serve
    LOF = "lof"  # longest output first
    RANDOM = "random"
    ROUTING_KEY = "routing-key"  # prioritize by routing key frequency in running batch

This is a genuine design difference, not a feature-count difference. vLLM's waiting queue is ordered once, at insertion. SGLang's is re-sorted on every prefill pass by SchedulePolicy.calc_priority(self.waiting_queue, running_batch), which is what makes cache-aware ordering possible at all: lpm sorts the queue so that requests sharing the longest prefix with the radix tree go first, turning admission order into a prefix-cache hit-rate optimiser (§2.4 owns the tree itself). The cost is $O(n \log n)$ plus $n$ tree lookups per step, and SGLang knows it:

    def _determine_active_policy(self, waiting_queue: List[Req]) -> Policy:
        if self.policy == CacheAwarePolicy.LPM and len(waiting_queue) > 128:
            # Turn off the expensive prefix matching and sorting when the #queue is large.
            return CacheAgnosticPolicy.FCFS
        return self.policy

Above 128 queued requests, the clever policy switches itself off. That threshold is a hard-coded constant, and it is exactly the sort of thing that makes a benchmark look different from production: at low load you measure LPM, at high load you measure FCFS.

SGLang's admission test is an object rather than a predicate. PrefillAdder accumulates a running budget and reports one of three verdicts per request:

class AddReqResult(Enum):
    CONTINUE = auto()  # Continue to add requests
    NO_TOKEN = auto()  # No token left
    OTHER = auto()  # Other reasons to stop adding requests

    def budget_state(self):
        no_token = self.rem_total_tokens <= 0 or self.cur_rem_tokens <= 0
        if not no_token and self.is_hybrid_swa:
            no_token = self.rem_swa_tokens <= 0
# ...
        if no_token:
            return AddReqResult.NO_TOKEN

        if self.rem_input_tokens <= 0:
            return AddReqResult.OTHER
# ...
            if self.rem_chunk_tokens is not None and self.rem_chunk_tokens <= 0:
                return AddReqResult.OTHER

        return AddReqResult.CONTINUE

The critical difference from vLLM: rem_total_tokens is not "free blocks now". It is free-plus-evictable minus a forward-looking reservation for every request already running, and that reservation is scaled by a learned conservatism factor:

    def _get_running_request_total_token_offset(self, req: Req) -> int:
        return (
            min(
                (req.sampling_params.max_new_tokens - len(req.output_ids)),
                CLIP_MAX_NEW_TOKENS,
            )
            * self.new_token_ratio
        )

Read that as: "assume each running request will generate new_token_ratio of its remaining max_new_tokens, and do not admit anyone whose worst case would collide with that." At 1.0 the scheduler is fully pessimistic and admits almost nobody; at the floor it is nearly as optimistic as vLLM. SGLang moves the value dynamically — §7.

In vLLM, preemption is not a separate pass. It is a retry loop wrapped around the allocator, inside the loop over running requests:

            # Schedule newly needed KV blocks for the request.
            with record_function_or_nullcontext("schedule: allocate_slots"):
                while True:
                    new_blocks = self.kv_cache_manager.allocate_slots(
                        request,
                        num_new_tokens,
                        num_lookahead_tokens=self.num_lookahead_tokens,
                    )

                    if new_blocks is not None:
                        # The request can be scheduled.
                        break

                    # The request cannot be scheduled.
                    # Preempt the lowest-priority request.

Victim selection is two lines under FCFS and a dozen under priority:

                    if self.policy == SchedulingPolicy.PRIORITY:
                        preempted_req = max(
                            self.running,
                            key=lambda r: (r.priority, r.arrival_time),
                        )
# ...
                    else:
                        preempted_req = self.running.pop()

                    self._preempt_request(
                        preempted_req,
                        scheduled_timestamp,
                        drop_stale_output=self.requires_kv_delivery,
                    )
                    preempted_reqs.append(preempted_req)
                    if preempted_req == request:
                        # No more request to preempt. Cannot schedule this request.
                        break

Under FCFS the victim is self.running.pop() — the last element of the running list, which is admission order, so the victim is the most recently admitted request. This is LIFO eviction, and it is the right choice for two reasons. It maximises the age of the surviving set (older requests may contain more accumulated work, although age does not establish remaining output length), and it makes the eviction self-limiting: the request that just caused the pressure is the first to go.

The termination condition is the interesting line. if preempted_req == request: break — if the loop has eaten its way through the running list until the only remaining candidate is the request we were trying to serve, it stops. A single request whose next block cannot be allocated even with an empty pool is simply not scheduled this step; it is never left in an inconsistent state.

What happens to the victim's blocks:

        assert request.status == RequestStatus.RUNNING, (
            "Only running requests can be preempted"
        )
        self._free_request_blocks(request)
        self.encoder_cache_manager.free(request)
        self._inflight_prefills.discard(request)
        request.status = RequestStatus.PREEMPTED
        request.num_computed_tokens = 0
# ...
        # Put the request back to the waiting queue.
        self.waiting.prepend_request(request)
        self.reset_preempted_req_ids.add(request.request_id)

Three things happen: the blocks go back to the pool, num_computed_tokens resets to zero (the request will re-prefill from scratch as far as the scheduler is concerned), and the victim is prepended to the waiting queue — it goes to the front, not the back. Under FCFS that means it is the very next candidate for admission. Under PRIORITY, prepend_request is documented as a plain heap push, so the victim re-enters ordered by (priority, arrival_time) and its old arrival time still wins ties against newer arrivals.

SGLang calls the same operation retraction, and structures it as a separate pass that runs when the decode-memory check fails:

    def retract_decode(
        self, server_args: ServerArgs
    ) -> Tuple[List[Req], float, List[Req]]:
        """Retract the decoding requests when there is not enough memory."""
        sorted_indices = self._get_decode_retraction_order(self.reqs, server_args)

        retracted_reqs = []
        reqs_to_abort: List[Req] = []
        first_iter = True
        while first_iter or (
            not self.check_decode_mem(selected_indices=sorted_indices)
        ):
            if len(sorted_indices) == 1:
                # Always keep at least one request
                break

            first_iter = False
            idx = sorted_indices.pop()
            req = self.reqs[idx]
            # release memory and don't insert into the tree because we need the space instantly
            if self.release_req(idx, len(sorted_indices), server_args):
                retracted_reqs.append(req)

The victim order is not LIFO. It is a sort key:

        """Return indices ordered from most-preferred to least-preferred to keep.

        The retraction loop pops from the end of this list, so the least-preferred
        request is retracted first.
        """
        sorted_indices = list(range(len(reqs)))

        # TODO(lsyin): improve retraction policy for radix cache

        def length_key(req: Req) -> Tuple[int, int]:
            return (len(req.output_ids), -len(req.origin_input_ids))

Sorted descending, the last element — the first retracted — is the request with the fewest output tokens and, as a tiebreak, the longest input: throw away the one that has generated the least, and among those, the one whose long prompt is the biggest single memory win. vLLM's LIFO rule usually picks the same request for a different reason, but they diverge under bursty arrivals where an old request had a long stall.

SGLang also has a proactive preemption path, PrefillAdder.preempt_to_schedule (python/sglang/srt/managers/schedule_policy.py:L1437-L1441), which evicts running requests to make room for a higher-priority arrival, gated by --priority-scheduling-preemption-threshold (default 10) so marginal priority differences cannot trigger churn. vLLM has no equivalent: its PRIORITY policy changes who gets evicted when memory runs out, never whether eviction happens.

Once a victim's blocks are freed, its KV must come back somehow. There are exactly two mechanisms. Recompute: run prefill over the whole sequence again. Swap: copy the KV to host memory over PCIe and copy it back on resume. Let us cost both for a preempted Llama-3-8B request at $S = 8192$ tokens.

Swap

Bytes to move, one direction, using $b_{tok} = 131{,}072$ B from §3:

PCIe Gen5 x16 is 32 GT/s over 16 lanes, i.e. 64 GB/s per direction at the raw link rate (128 GB/s aggregate); real pinned-memory copies land lower, but 64 GB/s is the generous bound. Derived:

Recompute (cold)

Prefill FLOPs for $S$ tokens over an $N$-parameter dense model, with the causal-attention term written out ($d = 4096$ is the model dim):

With $N = 8.0\times10^9$, $L = 32$, $S = 8192$, $d = 4096$: the matmul term is $2 \times 8.0\times10^9 \times 8192 = 1.311\times10^{14}$ and the attention term is $2 \times 32 \times 8192^2 \times 4096 = 1.759\times10^{13}$, so $F_{prefill} = 1.487\times10^{14} = 148.7$ TFLOP. An H100 SXM peaks at 989 TFLOP/s bf16 dense (NVIDIA datasheet, no sparsity); assume 400 TFLOP/s achieved, a conservative ~40% MFU for a batched prefill. Derived:

So on raw arithmetic, swap wins by 11×. The crossover prefill rate is where the two are equal:

No 8B model on any current GPU prefills at 244k tok/s. By this analysis, every engine should swap. Both engines chose recompute. The analysis is wrong, and finding out why is the point.

Why the analysis is wrong

Recompute is not paid in full, because the victim's blocks are still in the prefix cache. When vLLM frees blocks, hashed blocks are not unhashed — they are appended to the tail of the free queue and only lose their hash when actually handed out again:

        # Identify blocks with hash (LRU cache) and without it (never match APC)
        blocks_to_evict_last = []
        blocks_to_evict_first = []
        for block in ordered_blocks:
            block.ref_cnt -= 1
            if block.ref_cnt == 0 and not block.is_null:
                if block.block_hash is None or not self.enable_caching:
                    # LIFO reuse of non-cached blocks for better GPU locality.
                    blocks_to_evict_first.append(block)
                else:
                    # FIFO reuse of cached blocks for LRU eviction behavior.
                    blocks_to_evict_last.append(block)

        # Blocks to reuse first are prepended to the front of the free queue.
        self.free_block_queue.prepend_n(blocks_to_evict_first)
        # Blocks to reuse last are appended to the end of the free queue.
        self.free_block_queue.append_n(blocks_to_evict_last)

A preemption typically frees hundreds of blocks to satisfy a demand of one. Our 8192-token victim releases 512 blocks; the surviving decodes consume perhaps 3 of them before the victim is re-admitted from the front of the waiting queue. The other 509 still carry their hashes, so the resumed request's prefix lookup hits them and re-prefills only the tail. Let $f$ be the fraction of the victim's tokens recovered from the prefix cache. Then:

Setting them equal gives the survival threshold at which the two strategies tie:

Under this simplified linear-prefill/constant-transfer-bandwidth model, recompute beats round-trip swap when $(1-f)t_{\rm cold}<2Sb_{\rm tok}/\beta_{\rm link}$. The approximately 91% threshold is illustrative, not a measured engine property. Here $f$ must describe a reusable contiguous prefix, not an arbitrary fraction of surviving blocks. Warm suffix attention still reads the prefix, and fixed overheads, queueing, and bandwidth contention alter the crossover.

SGLang is the more interesting case, because it kept swap for exactly one deployment shape:

    """Returns False when the KV backup failed and the request cannot be resumed."""
    if hisparse_coordinator is not None and not req.finished():
        hisparse_coordinator.retract_req(req)

    # In decode disaggregation the retracted KV is offloaded to host so it can be
    # restored later without recompute (see resume_retracted_reqs/load_kv_cache).
    # Callers that will recompute the KV instead (PD true-retraction rebootstrap)
    # pass offload_kv=False to skip the wasteful device->host copy.
    backup_saved = True
    if server_args.disaggregation_mode == "decode" and offload_kv:
        backup_saved = retraction_backup(
            req,
            tree_cache,
            req_to_token_pool,
            token_to_kv_pool_allocator,
            get_disagg().disaggregation_decode_retraction_backup,
        )
    # TODO (csy): for preempted requests, we may want to insert into the tree
    release_kv_cache(req, tree_cache, is_insert=False)

The quoted SGLang path supports host backup for a disaggregated decode worker whose deployed execution path cannot locally prefill. This is an implementation/deployment limitation, not a physical inability of that GPU to run prefill. Other offload paths and configurations should not be inferred from this call site alone.

The flag is_insert=False suppresses insertion of new request KV during this release. It does not erase an already indexed shared prefix or imply a cold resume. Both engines' resumable prefix lengths depend on ownership, eviction, and surviving ancestor blocks; the previously assumed 99%-versus-0% comparison is not established by the excerpts.

Two failure modes bracket every scheduler. A long request that is repeatedly evicted and never finishes; and a long request that never starts because short ones keep jumping ahead.

Repeated eviction. vLLM's defence is structural. The victim is the last-admitted request, so newer running requests are chosen before the oldest under FCFS; the victim is prepended to the waiting queue so it is first back in; and no new request is admitted on a step where a preemption happened. Together these provide an ordering property, not a general starvation-freedom guarantee under overload: the head of the running list can only be preempted after every request behind it has been. request.num_preemptions is incremented on every eviction and is exported per-request, so a rising value on one request ID is the signal that the guarantee is being stressed.

SGLang's defence is a feedback controller instead. After every retraction it recomputes the conservatism factor from what actually happened, and decays it back on every step that did not retract:

    def decay_step(self) -> None:
        self.current = max(self.current - self.decay, self.min)

    def reset(self) -> None:
        self.current = self.init

    @staticmethod
    def estimate_new_token_ratio_after_retract(reqs: Sequence[Req]) -> float:
        total_decoded_tokens = sum(len(r.output_ids) for r in reqs)
        total_max_new_tokens = sum(r.sampling_params.max_new_tokens for r in reqs)

        new_estimate_ratio = (
            total_decoded_tokens + envs.SGLANG_RETRACT_DECODE_STEPS.get() * len(reqs)
        ) / (
            total_max_new_tokens + 1
        )  # avoid zero division
        new_estimate_ratio = min(1.0, new_estimate_ratio)
        return new_estimate_ratio

A retraction snaps new_token_ratio up towards the observed generation fraction — making the PrefillAdder reserve more per running request and admit fewer new ones — and then it decays linearly back towards min over SGLANG_NEW_TOKEN_RATIO_DECAY_STEPS. This is additive-increase / additive-decrease congestion control applied to KV admission. It is why --schedule-conservativeness (which scales the initial ratio) is the first knob SGLang's own help text tells you to raise "if you see requests being retracted frequently".

Head-of-line starvation. vLLM's answer is to accept head-of-line blocking on purpose. In the waiting phase the scheduler calls peek_request(), and when the head does not fit it executes break, not continue — it does not scan past the big request looking for a small one that fits. The one place it does skip is inside the running phase, and the code apologises for it: "NOTE(woosuk): Here, by doing continue instead of break, we do not strictly follow the FCFS scheduling policy" (vllm/v1/core/sched/scheduler.py:L630-L632).

SGLang, whose waiting queue is re-sorted every pass by a policy that may not be FCFS at all, cannot make that guarantee — lpm ordering can genuinely starve a request with no cached prefix. Its answer is a hard deadline:

    def _abort_on_waiting_timeout(self):
        if (timeout_s := envs.SGLANG_REQ_WAITING_TIMEOUT.get()) <= 0:
            return

        deleted_reqs = set()
        deadline = time.perf_counter() - timeout_s
        for req in self.waiting_queue:
            entry_time = req.time_stats.wait_queue_entry_time
            if 0 < entry_time < deadline:
                if self.enable_hicache_storage:
                    # Release prefetch events associated with the request
                    self.tree_cache.release_aborted_request(req.rid)

The abort carries HTTP 503 and the message "Request waiting timeout reached.". It is off by default. That is the honest tradeoff: a cache-aware policy buys throughput and gives up a starvation-freedom proof, so the mitigation is a timeout rather than an ordering invariant.

Use an intentionally small illustrative pool with 2049 usable blocks, excluding any reserved null block. Four live requests each hold 512 blocks, leaving one allocatable block. This replaces the 20,480-block capacity example: four 8k requests would occupy only about 2048 blocks there, and finished cached blocks with zero references are reclaimable. For the following boundary-crossing trace, each request starts at exactly 8192 cached tokens; a new token needs a new block.

The function call order, in vLLM: Scheduler.schedule() → KVCacheManager.allocate_slots() returns None → Scheduler._preempt_request() → Scheduler._free_request_blocks() → BlockPool.free_blocks() → the while True retries allocate_slots() → SchedulerOutput is built with preempted_req_ids=self.reset_preempted_req_ids so the runner drops D's row from the persistent batch → next step, phase 2 calls _select_waiting_queue_for_scheduling() → _get_local_prefix_cache_hit() → allocate_slots() → D lands in scheduled_resumed_reqs rather than scheduled_new_reqs, which is how the runner knows to reuse its slot.

Force preemption deliberately and watch the counter move. The lever is the KV pool size, not the request rate:

vllm serve meta-llama/Meta-Llama-3-8B-Instruct \
  --gpu-memory-utilization 0.55 \
  --max-num-seqs 128 \
  --max-model-len 8192 \
  --watermark 0.0

# then, in another shell, saturate it:
vllm bench serve --model meta-llama/Meta-Llama-3-8B-Instruct \
  --dataset-name random --random-input-len 6000 --random-output-len 1000 \
  --max-concurrency 128 --num-prompts 512

# watch the counter:
curl -s localhost:8000/metrics | grep -E 'num_preemptions|kv_cache_usage'

Then re-run with --watermark 0.02 and with --max-num-seqs 32. Both should drive vllm:num_preemptions to zero; only one of them should keep your throughput. The SGLang counterpart is --schedule-conservativeness: set it to 0.3 to force retraction storms and to 2.0 to suppress them, and read the new_token_ratio transitions in the warning line quoted in §1.

To read the policy surface rather than measure it, the scheduler is pluggable: vllm/v1/core/sched/interface.py defines SchedulerInterface, and --scheduler-cls mod.MyScheduler (documented at vllm/config/scheduler.py:L117-L120) swaps in your own. The contract is one method:

    def schedule(self, throttle_prefills: bool = False) -> "SchedulerOutput":
        """Schedule the requests to process in this scheduling step.

        The scheduling decision is made at the iteration level. Each scheduling
        step corresponds to a single forward pass of the model. Therefore, this
        method is called repeatedly by a busy loop in the engine.

        Essentially, the scheduler produces a dictionary of {req_id: num_tokens}
        that specifies how many tokens to process for each request in this

That docstring is the best one-paragraph summary of the whole design: the scheduler's entire output is a map from request ID to token count. Everything else in SchedulerOutput is bookkeeping around that map.

• Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention (SOSP 2023) — §4.5 is the original recompute-vs-swap discussion and the source of the v0 PreemptionMode design that v1 has since removed.
• Zheng et al., SGLang: Efficient Execution of Structured Language Model Programs — the cache-aware scheduling argument behind lpm and dfs-weight.
• vLLM V1: A Major Upgrade to vLLM's Core Architecture — the design note that motivates the single-status-enum, single-schedule() rewrite this chapter reads.
• Yu et al., Orca: A Distributed Serving System for Transformer-Based Generative Models (OSDI 2022) — iteration-level scheduling, the idea both engines implement.
• In-repo: vllm/v1/core/sched/interface.py for the pluggable-scheduler contract, and python/sglang/srt/managers/schedule_policy.py for the richest policy set in either project.
• Next: §1.5 Chunked prefill explains why num_new_tokens is capped rather than set to the whole prompt, and §2.2 PagedAttention opens up allocate_slots, which this chapter treated as a black-box predicate. For a line-by-line read of the same scheduler from a code-structure angle, see §11.3.

The source traces above describe real engines. The standalone scheduler simulator makes a smaller set of contracts executable using only Python's standard library. Its integer clock measures synthetic ticks, not milliseconds; every dispatch costs one tick independent of batch shape. Use it to falsify accounting and lifecycle assumptions, not to estimate throughput, GPU utilization, or either engine's scheduling policy. The trace-replay lab supplies the complete experiment and expected output.

Three budgets that must not be conflated

For a request with P prompt tokens, exactly N requested output tokens and block size B, this model reserves ceil((P + N - 1) / B) blocks at admission. The final prefill produces output token one; only the next N - 1 sampled tokens require another forward pass. The last returned token is not written into KV. These semantics explain why a four-token prompt and a one-token response fit exactly one four-token block. There is no hidden extra decode pass.

Reservation is an admission credit, not an eager physical allocation. Pages are allocated as input tokens are actually processed. An admitted request with a one-token prompt and eight output tokens reserves two four-token blocks even before it has allocated its first page. A later request can therefore wait while the physical free list is nonempty: those pages are promised to future growth.

The capacity invariant is active reservation credits + draining physical pages <= usable capacity. A completed or cancelled request gives up its future-growth credits immediately, but its existing pages remain unavailable until the configured release delay expires. Null pages, watermarks and model workspace must already be excluded from capacity. In the scheduler experiment requests do not share pages; the allocator experiment tests sharing separately, without double-counting shared pages as private reservations.

Event ordering is part of the contract

1. A dispatch started at tick t completes at t + 1. Completion records output tokens and terminal state before events scheduled at that new boundary.
2. At a boundary, all arrivals are registered before cancellations at that same timestamp. Cancellation can therefore remove a just-arrived request before it is admitted. A cancellation after completion is an explicit cancel_ignored event.
3. Expired cleanup delays release pages; admission then scans a FIFO queue. A request larger than the entire pool is rejected. A temporarily non-fitting head request blocks later queue entries, deliberately exposing head-of-line blocking.
4. Decoding requests consume at most one input token each, with a rotating starting row. Remaining token budget goes to capped prefill chunks, also with a rotating starting row. Unfinished prefill emits no response token. A newly completed prefill cannot also decode in the same dispatch.

Cancellation is observed only at dispatch boundaries. There is no interruption of an in-flight kernel. The cleanup delay models storage retention after a terminal decision, not a measured CUDA event duration. The finite trace and conservative reservations guarantee progress for accepted requests once earlier work drains; this is not a starvation theorem for an unbounded stream of arrivals. Decode priority can delay prefills, and FIFO admission can leave usable space idle.

Read a failure without inventing a performance result

Compare admission_blocked, snapshot and dispatch records. A blocked admission with many free pages points to reservation credits; a blocked admission with draining pages points to cleanup; an admitted request that receives no work points to the token or row budget. None proves a bandwidth bottleneck. Run the same JSONL trace under --policy serial and --policy continuous to compare synthetic queue delay and iteration count while holding arrivals and requested lengths fixed. This compares serial service with iteration-level admission, not padded static batching against continuous batching.

The executable checks cover exact prefill/decode counts, one-token outputs, delayed release, queued and active cancellations, completion/cancellation races, over-capacity rejection, deterministic replay and 60 seeded finite workloads. The next extensions are preemption/recompute, cached-prefix-aware reservations, priority/deadline policies, static and dynamic batch formation, and a hardware-calibrated cost model. Those mechanisms are intentionally absent rather than silently approximated.

The conservative reservation simulator above does not preempt. Its companion CPU lifecycle model makes manual preemption and recovery executable without claiming to reproduce either engine's victim-selection policy. Keep scheduler_sim.py beside it, then follow the worked recomputation lab. All token IDs are stand-ins for KV rows, and call order is a serialized control-plane trace, not a timing model.

Retain logical progress, discard physical residency

For prompt [10, 11, 12] and emitted output [20, 21], only [10, 11, 12, 20] has entered the model. The newest sampled output, 21, is pending feedback. Recompute restores those four committed rows, emits nothing, and leaves 21 to be consumed exactly once on the next step. The client then receives one new output, not a replay of its previous response. Logical progress and page residency must therefore be separate fields.

The model's preemption transition releases the request's page-table references but keeps its prompt and emitted-token history. A failed reconstruction rolls back all partial allocations and leaves the request suspended. Repeated successful reconstruction adds to an explicit replay-row counter; it does not advance the output index. A cancelled request cannot resume, and repeated cancellation is harmless. These contracts are verified independently of any scheduling heuristic.

Why a selected victim may not provide capacity

A request owner is not necessarily the final owner of physical storage. Shared prefixes may still be referenced elsewhere, and an asynchronous transfer can pin both source and destination pages. In the four-page test, preempting the producer and aborting its transfer leaves zero free pages until a drain acknowledgement. Consequently, victim ranking by logical context length need not rank immediately recoverable capacity. Admission must inspect the allocator's reusable pool after ownership and transport obligations are resolved.

To extend this into an actual policy experiment, define a victim score, the dispatch cost of reconstruction, an admission order for resumed versus new requests, and a bound on repeated preemption. Record client-visible latency separately from successful and wasted reconstruction work. The current tests establish safety and deterministic state transitions, not starvation freedom, engine equivalence, or a throughput advantage. For output equivalence with a real model, add positions, masks, adapter identity, sampling-state restoration and speculative accepted-history tests.