Allocating Slots: One Call, Traced

The idea in one minute#

Every time the scheduler wants to give a request some tokens, it makes one call: kv_cache_manager.allocate_slots(request, num_new_tokens, …). The answer is either a list of new block IDs or None. Everything about memory admission is decided inside that call: whether a new request’s whole prompt fits, whether a safety margin is respected, how many blocks a cache hit saved, when blocks receive their hashes, and when “no” turns into a preemption. The scheduler never counts free blocks itself. This lesson follows a single request through that function from its first call to its last.

A picture#

flowchart TB
  C["<b>allocate_slots(request, num_new_tokens, ...)</b>"] --> F{"new request and<br/>full_sequence_must_fit?"}
  F -- "yes" --> G{"blocks for the WHOLE prompt<br/>+ watermark ≤ free?"}
  G -- "no" --> NO[":i-ban: return None"]
  G -- "yes" --> RM
  F -- "no" --> RM["free blocks no longer needed<br/><small>e.g. outside a sliding window</small>"]
  RM --> N["blocks needed =<br/>ceil((computed + new + lookahead) / 16) − blocks held"]
  N --> A{"needed + watermark ≤<br/>free − reserved?"}
  A -- "no" --> NO
  A -- "yes" --> T["touch cache-hit blocks<br/><small>ref_cnt + 1, leave the free queue</small>"]
  T --> P["pop new blocks from the free queue<br/><small>evicting hashes as needed</small>"]
  P --> H["give hashes to blocks that are now full<br/><small>up to request.num_tokens</small>"]
  H --> OK[":i-check: return the new blocks"]
  class C neutral
  class F,G,A queue
  class RM,N,T,P,H memory
  class NO warn
  class OK neutral

How it really works#

Three layers#

The call passes through three classes, each with one job:

Below them sits the BlockPool. For an ordinary model there is one group, the coordinator is the trivial UnitaryKVCacheCoordinator, and the three layers behave as one.

The layout the function reasons about#

The function’s docstring draws the token range it is dealing with:

----------------------------------------------------------------------
| < comp > | < new_comp > | < ext_comp >  | < new >  | < lookahead > |
----------------------------------------------------------------------
                                          |   < to be computed >     |
----------------------------------------------------------------------
                          |            < to be allocated >           |
----------------------------------------------------------------------

For a plain request with no cache hit, no connector and no speculative decoding, only comp and new are non-zero, and the function reduces to: do I have enough blocks to hold comp + new tokens?

Stage 0: does the whole thing fit? (new requests only)#

if full_sequence_must_fit:
    # First check and fail if the full request sequence won't fit.
    full_num_tokens = min(request.num_tokens, self.max_model_len)
    num_blocks_to_allocate = self.coordinator.get_num_blocks_to_allocate(
        request_id=request.request_id, num_tokens=full_num_tokens, ...
    )
    required_blocks = num_blocks_to_allocate + watermark_blocks
    if required_blocks > self.block_pool.get_num_free_blocks():
        return None

The scheduler passes full_sequence_must_fit=True only when admitting from the waiting queue. The check is on request.num_tokens, the prompt (plus any output a preempted request has already produced), with cache-hit blocks already discounted. Nothing is reserved by this check; it only refuses admission when the answer is obviously no.

The watermark is added only in a narrow case:

# 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

Stage 1: give back what is no longer needed#

# Free the blocks that are skipped during the attention computation
# (e.g., tokens outside the sliding window).
# We can do this even if we cannot schedule this request due to
# insufficient free blocks.
# Should call this function before allocating new blocks to reduce
# the number of evicted blocks.
self.coordinator.remove_skipped_blocks(request.request_id, ...)

For full attention this does nothing: every past token is needed forever. For layers that only look at a recent window it returns the blocks that have fallen out of view, replacing them in the request’s table with the null block. Doing it before allocating means the request may satisfy its own need with the memory it just released.

Stage 2: count#

num_tokens_main_model = total_computed_tokens + num_new_tokens
num_tokens_need_slot = min(num_tokens_main_model + num_lookahead_tokens, self.max_model_len)

num_blocks_to_allocate = self.coordinator.get_num_blocks_to_allocate(
    request_id=request.request_id, num_tokens=num_tokens_need_slot, ...
)
# 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

For full attention, the count is simple arithmetic:

blocks needed = ceil(num_tokens_need_slot / 16)
              − blocks already in the request's table
              − cache-hit blocks about to be added
              + cache-hit blocks that are currently in the free queue

The last line is subtle. A cache-hit block with ref_cnt == 0 is sitting in the free queue and is counted in “free”. Touching it will remove it from the queue, so it must be counted as a block this request consumes, even though no new memory is involved. Hit blocks that another request is already holding cost nothing.

A request that is generating needs a new block only when it crosses a block boundary: fifteen calls out of sixteen return an empty list after a couple of integer operations.

Stage 3: commit#

Only now does anything change. Cache-hit blocks are touched and appended to the request’s table; then new blocks are taken from the front of the free queue:

self.coordinator.allocate_new_computed_blocks(...)   # the cache hit: touch()
new_blocks = self.coordinator.allocate_new_blocks(...)  # block_pool.get_new_blocks()

The order — check everything, then commit everything — means a refused allocation leaves no trace. There is nothing to roll back.

Stage 4: hashes#

# NOTE(woosuk): We want to commit (cache) up to num_local_computed_tokens
# + num_external_computed_tokens + num_new_tokens, but must exclude
# "non-committable" tokens (e.g., draft tokens that could be rejected).
# Therefore, we cap the number at `request.num_tokens`, ensuring only
# "finalized" tokens are cached.
num_tokens_to_cache = min(total_computed_tokens + num_new_tokens, request.num_tokens)
self.coordinator.cache_blocks(request, num_tokens_to_cache)

Every block that this step fills completely receives its hash and enters the prefix cache now, at scheduling time. The cap at request.num_tokens keeps speculative tokens out: a block containing a guessed token that may be rejected must not be offered to other requests.

What the worker does with the answer#

The new block IDs travel to the worker in the SchedulerOutput. Before the forward pass the worker does two housekeeping steps the scheduler requested:

• Zeroing. new_block_ids_to_zero lists blocks freshly taken from the pool. Their old contents belong to some finished request. The source explains why they are cleared: “preventing stale NaN/data from corrupting attention or SSM computation.”
• Copy-on-write copies. kv_cache_block_copies lists (source, destination) pairs for partial-block cache hits (see Prefix Caching).

None and what follows#

allocate_slots returning None means different things depending on the caller:

The function itself never evicts a request. It evicts cached blocks, implicitly, by popping them from the free queue. Deciding that a live request must lose its memory is the scheduler’s responsibility.

Reading usage correctly#

vllm:kv_cache_usage_perc is 1 − free / (total − 1). “Free” includes every block in the free queue, hashed or not. So:

• Usage counts only blocks held by live requests.
• A server at 30% usage may have its other 70% full of cached prefixes. That is healthy: those blocks are free for the taking and useful until taken.
• Usage near 100% means live requests occupy nearly everything, the prefix cache has been squeezed out, and preemption is close.

Code#

allocate_slots for a full-attention model, with the whole-prompt check, the watermark and a lookahead. The trace follows one request: admission with a cache hit, a chunked prefill, then decoding across a block boundary.

package main

import "fmt"

const blockSize = 16

type pool struct {
	total, free int
	watermark   int // blocks kept free when admitting
}

type request struct {
	numTokens int // prompt + output known so far
	computed  int
	blocks    int // length of the block table
	waiting   bool
}

func ceilDiv(a, b int) int { return (a + b - 1) / b }

// allocateSlots returns the number of new blocks, or -1 for "None".
// hitBlocksFree: cache-hit blocks that sit in the free queue and will be touched.
func (p *pool) allocateSlots(r *request, newTokens, hitTokens, hitBlocksFree, lookahead int, othersScheduled bool) int {
	wm := 0
	if r.waiting && othersScheduled {
		wm = p.watermark
	}
	hitBlocks := hitTokens / blockSize

	// Stage 0: a new request must fit in full.
	if r.waiting {
		full := ceilDiv(r.numTokens, blockSize) - hitBlocks + hitBlocksFree
		if full+wm > p.free {
			return -1
		}
	}

	// Stage 2: blocks for this step.
	needSlot := r.computed + hitTokens + newTokens + lookahead
	need := ceilDiv(needSlot, blockSize) - r.blocks - hitBlocks + hitBlocksFree
	if need < 0 {
		need = 0
	}
	if need+wm > p.free {
		return -1
	}

	// Stage 3: commit.
	p.free -= need
	r.blocks = ceilDiv(needSlot, blockSize)
	r.computed += hitTokens // the hit is adopted; the scheduler advances the rest
	r.waiting = false
	return need - hitBlocksFree // truly new blocks, excluding touched cache blocks
}

func main() {
	p := &pool{total: 100, free: 40, watermark: 5}
	r := &request{numTokens: 300, waiting: true}

	show := func(what string, got int) {
		if got < 0 {
			fmt.Printf("%-44s -> None                 free %2d\n", what, p.free)
			return
		}
		fmt.Printf("%-44s -> %2d new block(s)      free %2d   table %2d blocks\n",
			what, got, p.free, r.blocks)
	}

	// A 300-token prompt whose first 128 tokens hit the cache. Six of those eight
	// blocks are idle in the free queue; two are held by another running request.
	fmt.Println("admission: 300-token prompt, 128 tokens cached, budget allows 100 this step")
	show("  allocate_slots(new=100, hit=128)", p.allocateSlots(r, 100, 128, 6, 0, true))
	r.computed += 100

	fmt.Println("\nprefill continues")
	show("  allocate_slots(new=72)", p.allocateSlots(r, 72, 0, 0, 0, true))
	r.computed += 72

	fmt.Println("\ndecoding: one token per step")
	for i := 0; i < 6; i++ {
		r.numTokens++ // a token was sampled
		show(fmt.Sprintf("  token %d: allocate_slots(new=1)", r.numTokens), p.allocateSlots(r, 1, 0, 0, 0, true))
		r.computed++
	}

	fmt.Println("\nthe next step, with a speculative-decoding lookahead of 16 slots")
	r.numTokens++
	show("  allocate_slots(new=1, lookahead=16)", p.allocateSlots(r, 1, 0, 0, 16, true))

	fmt.Println("\na second request arrives: 600 tokens, nothing cached")
	r2 := &request{numTokens: 600, waiting: true}
	got := p.allocateSlots(r2, 100, 0, 0, 0, true)
	fmt.Printf("  needs %d blocks + %d watermark, %d free -> ", ceilDiv(600, blockSize), p.watermark, p.free)
	if got < 0 {
		fmt.Println("None: stays in the waiting queue")
	} else {
		fmt.Println("admitted")
	}
}

In the trace, the admission step takes 13 blocks from the free count although only 7 are truly new: six cached blocks left the free queue by being touched. The prefill’s second chunk needs only 4 more. Decoding then allocates nothing for several tokens, one block on crossing a boundary, and a lookahead makes the request take its next block well before its real tokens reach the boundary.

Remember this#

• allocate_slots is the only place memory admission is decided; it returns blocks or None.
• It checks first and commits afterwards, so a refusal changes nothing.
• A new request is checked against its whole prompt; a running request only against this step.
• The watermark applies only when admitting waiting or preempted requests while others are scheduled.
• Cache-hit blocks that were idle count against “free” when touched, though no memory is newly used.
• Blocks get hashes at scheduling time, capped at request.num_tokens so draft tokens are never cached.
• None in pass 1 causes preemption; in pass 2 it stops admission.
• KV usage counts live requests only; cached-but-free blocks do not raise it.

Try it#

1. Set watermark to 0 and rerun. Is the second request admitted? What would happen to the first request’s next block boundary if it were?
2. Change hitBlocksFree in the admission call from 6 to 0 (all eight hit blocks are held by another running request). How many blocks does admission consume now?
3. Give the first request a lookahead of 16 on every decode step. How many more blocks does it hold on average? This is the standing memory cost of a proposer that writes its own KV.

Check yourself#

1. Why is remove_skipped_blocks called before the allocation rather than after?
2. A cache hit lands on eight blocks, all idle in the free queue. By how much does the free count drop, and how much new memory is used?
3. Why are blocks containing speculative draft tokens not given hashes?

Sources#

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

• vllm/v1/core/kv_cache_manager.py — allocate_slots and its docstring
• vllm/v1/core/kv_cache_coordinator.py
• vllm/v1/core/single_type_kv_cache_manager.py — get_num_blocks_to_allocate
• vllm/v1/core/sched/output.py — new_block_ids_to_zero, kv_cache_block_copies