Priorities, Preemption and Queues

The idea in one minute#

A request’s memory need is unknown when it is admitted: nobody knows how long the answer will be. The scheduler therefore admits requests optimistically and deals with the consequences. If running requests grow until the KV cache is full, one of them is preempted: all its blocks are taken away, it goes back to the waiting queue, and when it is re-admitted it must compute everything again from its first token. To the client, a preemption is a stream that freezes and later resumes. This lesson covers who waits, who is evicted, what eviction costs, and the four settings that make it rare.

A picture#

flowchart LR
  subgraph Q["Waiting"]
    direction TB
    KH[("kv_holding_waiting<br/><small>drained first</small>")]
    WQ[("waiting<br/><small>deque (fcfs) or heap (priority)</small>")]
  end
  WQ -->|"admitted: slots, budget, whole prompt fits"| RUN[":i-zap: <b>running</b><br/><small>a list, in admission order</small>"]
  KH --> RUN
  RUN -->|"needs a block, pool empty"| V{"choose a victim"}
  V -->|"fcfs: last admitted"| PRE[":i-triangle-alert: <b>preempt</b><br/><small>free all blocks<br/>num_computed_tokens = 0</small>"]
  V -->|"priority: worst priority,<br/>then latest arrival"| PRE
  PRE -->|"front of the queue"| WQ
  RUN -->|"finished"| DONE[":i-check: <b>free blocks</b>"]
  class KH,WQ memory
  class RUN compute
  class V queue
  class PRE warn
  class DONE neutral

How it really works#

Two queues, one interface#

--scheduling-policy chooses the waiting queue’s data structure (vllm/v1/core/sched/request_queue.py):

The ordering for the heap is the request’s own comparison operator:

def __lt__(self, other: "Request") -> bool:
    if self.priority != other.priority:
        return self.priority < other.priority
    if self.arrival_time != other.arrival_time:
        return self.arrival_time < other.arrival_time
    ...

A client sets "priority": <int> in the request body. The default is 0, and any non-zero value is an error unless the server was started with --scheduling-policy priority. vLLM does not authenticate who may claim which priority; a gateway in front must decide that.

The running list is the same under both policies: a plain list in admission order.

What priority does and does not do#

Priority affects exactly two decisions:

1. Which waiting request is considered next (the heap’s order).
2. Which running request is evicted when memory runs out.

It does not make a waiting high-priority request evict a running low-priority one. Pass 2 of the scheduler never preempts; if the request at the head of the queue does not fit, admission simply stops for this step. A burst of high-priority requests therefore waits for memory to free up naturally. Priority here is about ordering and about who loses when memory is short, not about interruption on arrival.

It also does not reorder the token budget inside a step. Running requests are served in admission order, whatever their priority.

When preemption happens#

Only in pass 1, only when a running request needs another block and the pool cannot provide one:

new_blocks = self.kv_cache_manager.allocate_slots(request, num_new_tokens, ...)
if new_blocks is not None:
    break                                   # fine
# The request cannot be scheduled.
# Preempt the lowest-priority request.
if self.policy == SchedulingPolicy.PRIORITY:
    preempted_req = max(self.running, key=lambda r: (r.priority, r.arrival_time))
else:
    preempted_req = self.running[-1]
...
self._preempt_request(preempted_req, scheduled_timestamp, ...)
preempted_reqs.append(preempted_req)
if preempted_req == request:
    # No more request to preempt. Cannot schedule this request.
    break

The victim:

• under FCFS, the last element of running — the request admitted most recently, which has typically done the least work;
• under priority, the request with the numerically largest priority value, breaking ties by latest arrival.

The loop repeats until the allocation succeeds or the victim is the very request that needed memory. In the second case that request evicts itself.

Under the priority policy the victim may already have been scheduled earlier in this same step. The code then unwinds that decision — removes it from the scheduled list and returns its tokens to the budget — before evicting it.

What preemption does to the victim#

def _preempt_request(self, request, timestamp, drop_stale_output=False):
    self._free_request_blocks(request)
    self.encoder_cache_manager.free(request)
    request.status = RequestStatus.PREEMPTED
    request.num_computed_tokens = 0
    request.num_preemptions += 1
    ...
    # Put the request back to the waiting queue.
    self.waiting.prepend_request(request)

Three facts follow.

Everything is recomputed. num_computed_tokens = 0. There is no partial preemption and no swapping to CPU memory. When re-admitted, the gap is the whole of num_tokens: the prompt and every output token generated so far must go through the model again as a prefill.

It goes to the front. Under FCFS a preempted request is placed ahead of everything that was already waiting, so it is the first to return. (Under the priority policy “front” has no meaning; it re-enters the heap at its priority.)

The output is kept. The tokens already streamed to the client stay in the request. Nothing is generated twice; the model re-reads them, it does not re-sample them. The client sees a pause, then the stream continues from where it stopped.

And one fact about the step as a whole: if anything was preempted, pass 2 is skipped (if not preempted_reqs and ...). The scheduler does not evict one request and admit another in the same breath.

The prefix cache softens the blow#

Freeing a block does not erase it. A freed block that is full keeps its hash and joins the back of the free queue (Blocks and the Pool). When the preempted request is re-admitted, the scheduler performs the ordinary prefix-cache lookup, and every block of the victim that has not been reused in the meantime is a cache hit:

preempted with 3,000 tokens computed  →  187 full blocks freed, hashes intact
re-admitted 40 ms later               →  cache lookup finds, say, 150 of them
recompute                              →  600 tokens instead of 3,000

How much is recovered depends on how much of the pool was reused between eviction and return. Under sustained memory pressure — the situation that caused the preemption — the answer is often “not much”, because other requests were hungry for exactly those blocks.

How to see it#

• Each preemption records a PREEMPTED event with a timestamp on the request; the API server turns these into the vllm:num_preemptions counter (Metrics).
• For a client it appears as an inter-token gap far above the usual, in the middle of a stream.
• vllm:kv_cache_usage_perc sitting at or near 1.0 is the leading indicator.

A handful of preemptions per hour is harmless. A steady rate means the server is admitting more than its memory can carry.

Four ways to make it rare#

The watermark is applied in allocate_slots, and its condition is narrow:

# 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

It never blocks a running request from growing, and it never blocks the only request in the system. It is purely an admission margin.

The default admission rule already helps: scheduler_reserve_full_isl refuses a request whose whole prompt does not fit. What it cannot know is the length of the answer. Preemption is the price of not reserving the worst case for every request — and What vLLM Is and Why It Exists showed how much capacity that reservation would cost.

The second waiting queue#

There are really two waiting queues:

# Requests holding KV blocks are always drained first.
request_queue = self.kv_holding_waiting or self.waiting

A request can be “waiting” while still holding blocks: for example one that has received KV data from another machine and is about to resume, or a streaming-input session between chunks. Those sit in kv_holding_waiting and are admitted before anything in the ordinary queue, because they are occupying memory and the fastest way to release it is to let them run.

Requests that are not ready (grammar still compiling, KV still arriving) are skipped, not blocked on: they are set aside during the pass and put back at the front afterwards, in their original order.

Code#

Six identical requests, a cache that cannot hold them all at full length, and a varying max_num_seqs. The program counts preemptions, the tokens computed more than once, and the longest freeze any client saw.

package main

import "fmt"

const (
	blockSize   = 16
	totalBlocks = 48 // 768 tokens of KV cache
)

type req struct {
	id                       string
	prompt, maxNew           int
	output, computed, blocks int
	lastToken                int // step at which it last produced a token
}

func (r *req) total() int { return r.prompt + r.output }

func blocksFor(tokens int) int { return (tokens + blockSize - 1) / blockSize }

// run serves six identical requests and reports how much work was repeated.
func run(maxSeqs int) (steps, computedTokens, preemptions, worstStall int) {
	var waiting, running []*req
	for i := 0; i < 6; i++ {
		waiting = append(waiting, &req{id: string(rune('A' + i)), prompt: 64, maxNew: 200})
	}
	free := totalBlocks

	for len(waiting)+len(running) > 0 {
		steps++
		scheduled := map[*req]int{}
		preempted := false

		// Pass 1: running requests. On allocation failure, preempt the most
		// recently admitted request (FCFS policy) and try again.
		for i := 0; i < len(running); i++ {
			r := running[i]
			n := r.total() - r.computed
			need := blocksFor(r.computed+n) - r.blocks
			evictedSelf := false
			for need > free {
				victim := running[len(running)-1]
				running = running[:len(running)-1]
				free += victim.blocks
				victim.blocks, victim.computed = 0, 0 // all of its KV is gone
				waiting = append([]*req{victim}, waiting...)
				preempted = true
				preemptions++
				if victim == r {
					evictedSelf = true
					break
				}
			}
			if evictedSelf {
				break
			}
			free -= need
			r.blocks += need
			scheduled[r] = n
		}

		// Pass 2: admit, unless this step had to preempt.
		for !preempted && len(waiting) > 0 && len(running) < maxSeqs {
			r := waiting[0]
			need := blocksFor(r.total()) // a resumed request re-reads prompt AND output
			if need > free {
				break
			}
			waiting = waiting[1:]
			running = append(running, r)
			free -= need
			r.blocks = need
			scheduled[r] = r.total()
		}

		keep := running[:0]
		for _, r := range running {
			if n, ok := scheduled[r]; ok {
				r.computed += n
				computedTokens += n
				if r.computed == r.total() {
					if r.output > 0 {
						worstStall = max(worstStall, steps-r.lastToken)
					}
					r.output++
					r.lastToken = steps
				}
			}
			if r.output == r.maxNew {
				free += r.blocks
				continue
			}
			keep = append(keep, r)
		}
		running = keep
	}
	return
}

func main() {
	const useful = 6 * (64 + 200 - 1) // every token computed exactly once
	fmt.Printf("KV cache: %d blocks. One request grows to %d blocks.\n\n", totalBlocks, blocksFor(264))
	fmt.Printf("%-12s %6s %12s %16s %8s %22s\n",
		"max_num_seqs", "steps", "preemptions", "tokens computed", "wasted", "longest gap in a stream")
	for _, seqs := range []int{2, 3, 4, 6} {
		steps, computed, pre, stall := run(seqs)
		fmt.Printf("%-12d %6d %12d %16d %7.0f%% %16d steps\n",
			seqs, steps, pre, computed, 100*float64(computed-useful)/float64(useful), stall)
	}
}

Read the table from top to bottom. With max_num_seqs = 2 nothing is ever evicted and every stream is perfectly smooth, but the work takes the most steps. Admitting more finishes sooner overall — the extra concurrency outweighs the repeated work in this run — while a third to a half of all computation is wasted and some client watches its stream freeze for over a hundred steps. Which row is “best” depends on whether you are selling throughput or a smooth stream.

Remember this#

• Preemption happens only when a running request needs a block and none is free.
• FCFS evicts the most recently admitted request; priority evicts the worst-priority, latest-arrived one.
• A preempted request loses all its blocks and recomputes its prompt and all its output so far.
• Surviving prefix-cache blocks can make that recomputation much smaller.
• A step that preempts admits nothing.
• Priority orders the waiting queue and chooses victims. It does not let a new arrival interrupt a running request.
• Lower max_num_seqs, a small watermark, a smaller max_model_len, or more KV memory make preemption rare.

Try it#

1. Change totalBlocks to 102 (six requests at full length). Confirm that preemptions vanish at every concurrency. That is the “more KV memory” row of the table.
2. Change the victim rule to evict the first element of running (the oldest request). What happens to wasted tokens, and why is the real rule the opposite?
3. On a test server, start with --num-gpu-blocks-override 200 --max-num-seqs 16 and send 16 long generations. Watch vllm:num_preemptions in /metrics. The override flag exists for exactly this experiment.

Check yourself#

1. Under FCFS, which running request is evicted, and why that one?
2. After a preemption, are the tokens the client already received generated again?
3. A high-priority request arrives while the cache is full of low-priority requests. What happens to it?

Sources#

Checked on 5 October 2026 against main at commit 0c16eee.

• vllm/v1/core/sched/scheduler.py — the preemption loop, _preempt_request
• vllm/v1/core/sched/request_queue.py
• vllm/v1/core/kv_cache_manager.py — where the watermark is applied
• vllm/config/scheduler.py