vLLM KV Cache Internals: Blocks, the Block Pool and the Free Queue

The idea in one minute#

All the KV cache memory a vLLM engine will ever use is allocated once, at startup, and cut into fixed-size blocks. From then on, “memory management” means moving small Python objects between three places: a free queue, the block tables of running requests, and a hash map of blocks whose contents are worth keeping. No GPU memory is allocated or released while serving; the engine core only decides which block numbers belong to whom. The data structure is a few hundred lines in block_pool.py, and one design choice in it — a freed block keeps its contents and its hash until someone else actually needs the space — is what turns a memory allocator into a cache.

A picture#

flowchart LR
  subgraph POOL["BlockPool"]
    direction TB
    ALL[(":i-layers: <b>blocks[0..N)</b><br/><small>one object per physical block</small>")]
    FQ[":i-recycle: <b>free_block_queue</b><br/><small>doubly linked list<br/>front = reuse first</small>"]
    MAP[(":i-search: <b>cached_block_hash_to_block</b><br/><small>hash to block</small>")]
  end
  FQ -->|"get_new_blocks(): pop front,<br/>drop its hash if any"| REQ[":i-zap: <b>Request block table</b><br/><small>[7, 12, 3, 40, ...] append-only</small>"]
  MAP -->|"touch(): cache hit,<br/>ref_cnt + 1"| REQ
  REQ -->|"free_blocks(): ref_cnt − 1"| DEC{"ref_cnt == 0?"}
  DEC -- "has a hash" --> BACK["append to the BACK<br/><small>keep as cache</small>"]
  DEC -- "no hash" --> FRONT["prepend to the FRONT<br/><small>reuse immediately</small>"]
  BACK --> FQ
  FRONT --> FQ
  REQ -->|"block becomes full"| MAP
  class ALL,MAP memory
  class FQ,DEC queue
  class REQ compute
  class BACK,FRONT neutral

How it really works#

What a block is#

Physically, a block is a slice of a large tensor on the GPU holding the attention keys and values of block_size consecutive tokens for every layer. block_size is 16 tokens by default (CacheConfig.DEFAULT_BLOCK_SIZE).

In the engine core, a block is this object (vllm/v1/core/kv_cache_utils.py):

Python

@dataclass(slots=True)
class KVCacheBlock:
    # Block ID, ranging from 0 to num_gpu_blocks - 1.
    block_id: int
    # Reference count.
    ref_cnt: int = 0
    # The hash key (block hash + group id) of the block, only available
    # when the block is full and cached.
    _block_hash: BlockHashWithGroupId | None = None
    # Used to construct a doubly linked list for free blocks.
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None
    # Whether the block is a null block that should never be cached.
    is_null: bool = False

The engine core never touches the tensor. It only does arithmetic on block_ids; the worker owns the memory. That separation is why the scheduler can run in a different process from the GPU code.

The pool#

BlockPool.__init__ creates every block object up front:

Python

# All kv-cache blocks.
self.blocks: list[KVCacheBlock] = [
    KVCacheBlock(idx, pool=self) for idx in range(num_gpu_blocks)
]
self.free_block_queue = FreeKVCacheBlockQueue(self.blocks)
self.cached_block_hash_to_block: BlockHashToBlockMap = BlockHashToBlockMap()

# To represent a placeholder block with block_id=0.
self.null_block = self.free_block_queue.popleft()
self.null_block.is_null = True

Two reasons for creating them all at once: Python object creation is slow enough to matter in a loop that runs a thousand times a second, and a fixed list means a block ID is also an index.

Block 0 is special. It is removed from the free queue at startup and never returned. It is the null block: a placeholder used in a request’s block table wherever a position needs no real memory — for instance, tokens that have slid out of a sliding-window attention layer’s view. Because of it, the usable capacity is num_gpu_blocks − 1, and the usage metric subtracts one:

Python

def get_usage(self) -> float:
    # Subtract 1 to account for null block.
    total_gpu_blocks = self.num_gpu_blocks - 1
    return 1.0 - (self.get_num_free_blocks() / total_gpu_blocks)

That return value is the vllm:kv_cache_usage_perc metric.

The free queue#

The free queue must support three operations quickly:

take from the front (allocate),
add at the back or the front (free),
remove from the middle (a cached block that is sitting in the free queue gets a hit).

A Python deque cannot do the third in constant time. So the queue is a doubly linked list whose links are stored inside the blocks themselves:

Python

class FreeKVCacheBlockQueue:
    """... We implement this class instead of using Python
    builtin deque to support removing a block in the middle of the queue
    in O(1) time. To close the performance gap to the builtin deque which is
    implemented in C++, this class does not allocate any Python objects when
    manipulating the linked list. Instead, this class manipulates the
    prev_free_block and next_free_block attributes of the given blocks.
    """

Two sentinel blocks (fake_free_list_head and fake_free_list_tail, both with ID −1) sit at the ends so that insertion and removal never need to test for an empty list.

The position of a block in this queue is the eviction policy. The front is reused first; the back is reused last.

Reference counts#

ref_cnt is the number of requests whose block table contains the block.

`ref_cnt`	Where the block is	Meaning
0	In the free queue	Available. It may still hold valid, hashed data.
1	In one request’s table	Owned exclusively
≥ 2	In several requests’ tables	A shared prefix: read by all, written by none

A shared block is never written. It became shared only because it was full and its contents were final; each request writes its own new tokens into blocks it owns alone.

Allocate: `get_new_blocks`#

Python

def get_new_blocks(self, num_blocks: int) -> list[KVCacheBlock]:
    if num_blocks > self.get_num_free_blocks():
        raise ValueError(f"Cannot get {num_blocks} free blocks from the pool")

    ret: list[KVCacheBlock] = self.free_block_queue.popleft_n(num_blocks)

    if self.enable_caching:
        for block in ret:
            self._maybe_evict_cached_block(block)
            assert block.ref_cnt == 0
            block.ref_cnt += 1
    ...
    return ret

Blocks come from the front. If one of them still carries a hash, this is the moment it is evicted: its hash is removed from the map and cleared. Eviction is lazy. Nothing is ever evicted “to make room in advance”; cached data is discarded only at the instant a specific block is handed to a new owner.

Hit: `touch`#

Python

def touch(self, blocks: Sequence[KVCacheBlock]) -> None:
    for block in blocks:
        # ref_cnt=0 means this block is in the free list (i.e. eviction
        # candidate), so remove it.
        if block.ref_cnt == 0 and not block.is_null:
            self.free_block_queue.remove(block)
        block.ref_cnt += 1

A cache hit on a block with ref_cnt == 0 pulls it out of the middle of the free queue — the operation the linked list exists for — and it is in use again. A hit on a block already in use just adds an owner.

Free: where a block goes back to#

This is the function that defines the cache’s behaviour:

Python

def free_blocks(self, ordered_blocks: Iterable[KVCacheBlock]) -> None:
    # 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)

Two classes of freed block, two destinations:

No hash (a partly filled last block, or caching disabled): it can never serve a cache hit, so it goes to the front and is the very next block handed out. Reusing the most recently used memory first also keeps the GPU’s own caches warm.
Has a hash: it goes to the back. It will be reused only after everything ahead of it, which gives it the longest possible chance of being hit again.

note

vLLM’s published design document describes an older rule in which all freed blocks are appended to the tail. The front/back split is what the code does today.

The scheduler passes a request’s blocks in reverse order — last block first:

Python

# Free in reverse order so that the tail blocks are evicted first.

Among hashed blocks appended to the back, the last block of a request therefore ends up ahead of its first block, and is evicted sooner. That is correct: a block deep in a sequence can only be hit by a request sharing that whole long prefix, while the first block is hit by anything that begins the same way — every request using the same system prompt, for instance.

Put together, the queue’s order is least recently used first, and within one request, deepest block first. A fixed-size LRU cache with a sensible tie-break, built from nothing but the order of a linked list.

Block tables are append-only#

Each request has a list of block IDs, its block table, and the worker keeps a copy as a tensor. A block ID, once placed in a table, is never replaced by another.

That has a visible consequence. Suppose two identical requests run at the same moment. Each fills its own block with the same tokens, and each block gets the same hash. vLLM does not merge them:

Python

"""
NOTE #1: We currently don't de-duplicate the blocks in the cache,
meaning that if a block becomes full and is cached, we don't check
if there is already an identical block in the cache. This is because
we want to make sure the allocated block IDs won't change so that
block tables are append-only.
"""

BlockHashToBlockMap therefore maps a hash to one or several blocks, and a lookup returns the first. The duplicate disappears when its owner finishes. The benefit of the rule is that the worker’s copy of a block table is updated by appending and never has to be rebuilt.

When a block gets its hash#

A block is given a hash, and entered in the map, when it is full — its 16 token IDs are known and final. KVCacheManager.allocate_slots ends with:

Python

# 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)

Notice when this runs: during scheduling, before the GPU has computed anything. A prompt’s full blocks are registered in the cache the moment they are scheduled. A second request with the same prompt that arrives one step later — or later in the same scheduling pass — finds them and shares them. That is safe because the forward passes run in order: the step that writes those blocks completes before any step that reads them.

When prefix caching is off#

--no-enable-prefix-caching makes enable_caching false. No hashes are assigned, the map stays empty, and every freed block goes to the front of the queue. The pool is then a plain last-in-first-out allocator. Prefix caching is on by default.

Clearing the cache#

reset_prefix_cache() drops every hash at once. It is reachable over HTTP as POST /reset_prefix_cache, one of the development endpoints that exist only when the server is started with VLLM_SERVER_DEV_MODE=1. It refuses to run while any request holds a block:

Python

num_used_blocks = self.num_gpu_blocks - self.get_num_free_blocks()
if num_used_blocks != 1:  # The null block is always marked as used
    logger.warning("Failed to reset prefix cache because some blocks (%d) are not freed yet", ...)
    return False

It exists for two cases: after model weights have been updated in place (cached KV from the old weights would be wrong), and before a benchmark that should start cold.

Code#

The pool, in Go, with the same operations and the same ordering rules. Block 0 is the null block. A * marks a free block that still carries a hash.

package main

import (
	"fmt"
	"strings"
)

const blockSize = 4

type block struct {
	id         int
	refCnt     int
	hash       string // "" until the block is full and cached
	prev, next *block // links in the free queue; nil while the block is in use
}

type pool struct {
	blocks     []*block
	head, tail *block // sentinels of the free queue
	numFree    int
	cached     map[string]*block // hash -> block
}

func newPool(n int) *pool {
	p := &pool{head: &block{id: -1}, tail: &block{id: -1}, cached: map[string]*block{}}
	p.head.next, p.tail.prev = p.tail, p.head
	for i := 0; i < n; i++ {
		b := &block{id: i}
		p.blocks = append(p.blocks, b)
		p.pushBack(b)
	}
	p.popFront() // block 0 is the null block: never handed out, never freed
	return p
}

func (p *pool) link(b, after *block) {
	b.prev, b.next = after, after.next
	after.next.prev = b
	after.next = b
	p.numFree++
}
func (p *pool) pushBack(b *block)  { p.link(b, p.tail.prev) }
func (p *pool) pushFront(b *block) { p.link(b, p.head) }

// unlink removes a block from anywhere in the queue in O(1).
func (p *pool) unlink(b *block) {
	b.prev.next, b.next.prev = b.next, b.prev
	b.prev, b.next = nil, nil
	p.numFree--
}
func (p *pool) popFront() *block { b := p.head.next; p.unlink(b); return b }

// getNewBlocks takes blocks from the FRONT. A block that still carries a hash
// is evicted from the prefix cache at this moment, not before.
func (p *pool) getNewBlocks(n int) []*block {
	var out []*block
	for i := 0; i < n; i++ {
		b := p.popFront()
		if b.hash != "" {
			fmt.Printf("    evict: block %d loses its hash\n", b.id)
			delete(p.cached, b.hash)
			b.hash = ""
		}
		b.refCnt = 1
		out = append(out, b)
	}
	return out
}

// touch is a cache hit: one more owner, and out of the free queue if it was there.
func (p *pool) touch(bs []*block) {
	for _, b := range bs {
		if b.refCnt == 0 {
			p.unlink(b)
		}
		b.refCnt++
	}
}

// free releases a request's blocks. The caller passes them last-block-first.
func (p *pool) free(ordered []*block) {
	var noHash, hashed []*block
	for _, b := range ordered {
		b.refCnt--
		if b.refCnt > 0 {
			continue // another request still uses it
		}
		if b.hash == "" {
			noHash = append(noHash, b)
		} else {
			hashed = append(hashed, b)
		}
	}
	for i := len(noHash) - 1; i >= 0; i-- {
		p.pushFront(noHash[i]) // nothing worth keeping: reuse these first
	}
	for _, b := range hashed {
		p.pushBack(b) // still useful as cache: reuse these last
	}
}

func (p *pool) queue() string {
	var s []string
	for b := p.head.next; b != p.tail; b = b.next {
		if b.hash != "" {
			s = append(s, fmt.Sprintf("%d*", b.id))
		} else {
			s = append(s, fmt.Sprint(b.id))
		}
	}
	return strings.Join(s, " ")
}

// --- a request: tokens plus an append-only block table ---

type request struct {
	name   string
	tokens string // one letter per token
	table  []*block
}

func hashOf(prefix string) string { return prefix } // lesson 2 does this properly

// admit looks up cached full blocks, touches them, and allocates the rest.
func (p *pool) admit(name, tokens string) *request {
	r := &request{name: name, tokens: tokens}
	var hits []*block
	for end := blockSize; end <= len(tokens); end += blockSize {
		b, ok := p.cached[hashOf(tokens[:end])]
		if !ok {
			break
		}
		hits = append(hits, b)
	}
	p.touch(hits)
	r.table = append(r.table, hits...)
	need := (len(tokens)+blockSize-1)/blockSize - len(hits)
	fmt.Printf("  %s: %d tokens, %d block(s) from cache, %d new\n", name, len(tokens), len(hits), need)
	r.table = append(r.table, p.getNewBlocks(need)...)
	p.cacheFull(r)
	return r
}

// cacheFull gives a hash to every full block that does not have one yet.
func (p *pool) cacheFull(r *request) {
	for i := 0; i < len(r.tokens)/blockSize; i++ {
		b := r.table[i]
		if b.hash == "" {
			b.hash = hashOf(r.tokens[:(i+1)*blockSize])
			if _, dup := p.cached[b.hash]; !dup {
				p.cached[b.hash] = b
			}
		}
	}
}

func (p *pool) release(r *request) {
	rev := make([]*block, len(r.table))
	for i, b := range r.table {
		rev[len(r.table)-1-i] = b
	}
	p.free(rev)
}

func (r *request) ids() string {
	var s []string
	for _, b := range r.table {
		s = append(s, fmt.Sprint(b.id))
	}
	return "[" + strings.Join(s, " ") + "]"
}

func main() {
	p := newPool(11) // block 0 is null, so 10 usable blocks
	show := func() { fmt.Printf("    free queue (front first, * = cached): %s\n\n", p.queue()) }
	fmt.Println("start")
	show()

	fmt.Println("request 0 arrives")
	r0 := p.admit("r0", "ABCDEFGHIJKLMNO") // 15 tokens: 3 full blocks + 1 partial
	fmt.Printf("    block table %s\n", r0.ids())
	show()

	fmt.Println("request 1 arrives; its first 10 tokens match request 0")
	r1 := p.admit("r1", "ABCDEFGHIJxxxx")
	fmt.Printf("    block table %s\n", r1.ids())
	show()

	fmt.Println("request 0 finishes")
	p.release(r0)
	show()

	fmt.Println("request 1 finishes")
	p.release(r1)
	show()

	fmt.Println("request 2 arrives; its first 12 tokens match request 0")
	r2 := p.admit("r2", "ABCDEFGHIJKLyyyyyyyyyyyyyyyyy") // 29 tokens: 8 blocks
	fmt.Printf("    block table %s\n", r2.ids())
	show()

	fmt.Println("request 3 arrives; nothing in common with the others")
	r3 := p.admit("r3", "zzzzzzzz") // 8 tokens: 2 blocks
	fmt.Printf("    block table %s\n", r3.ids())
	show()
}

Follow the free queue through the output:

After request 0 finishes, its unhashed partial block (4) is at the very front and its hashed block (3) at the very back. Blocks 1 and 2 are not in the queue at all: request 1 still holds them.
After request 1 finishes, blocks 5, 2, 1 join the back in that order — deepest first.
Request 2 hits blocks 1, 2 and 3. They are plucked from the middle of the queue; nothing is evicted, because enough unhashed blocks were ahead of them.
Request 3 is the first to need a block that carries a hash. Only then does the cache lose an entry.

Remember this#

All KV memory is allocated at startup and divided into blocks of 16 tokens.
The engine core manages block numbers; the worker owns the memory.
Block 0 is the null block and is never allocated.
The free queue is a doubly linked list threaded through the blocks; its order is the eviction policy.
Freed blocks without a hash go to the front; with a hash, to the back, deepest first.
A freed block keeps its data and hash until it is handed to a new owner. Eviction is lazy.
ref_cnt counts owners; shared blocks are read-only.
Block tables only grow, so identical blocks created at the same time are not merged.

Try it#

Make every freed block go to the back (the older design). Rerun. Which cached block is evicted first when request 2 arrives, and why is that worse?
Free a request’s blocks in forward order instead of reversed. Which block of a shared system prompt is now evicted first?
Add a usage() method that returns 1 − free/(total − 1) and print it after each event. Note that it stays below 1.0 even when no unhashed block is free. What does that mean for reading vllm:kv_cache_usage_perc on a server with prefix caching on?

Check yourself#

Why is the free queue a linked list threaded through the blocks rather than a deque?
At what moment does a cached block actually lose its hash?
Why is a request’s last block evicted before its first?

Sources#

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

vllm/v1/core/block_pool.py
vllm/v1/core/kv_cache_utils.py — KVCacheBlock, FreeKVCacheBlockQueue
vllm/v1/core/kv_cache_manager.py
Automatic prefix caching (design)

The idea in one minute#

A picture#

How it really works#

What a block is#

The pool#

The free queue#

Reference counts#

Allocate: get_new_blocks#

Hit: touch#

Free: where a block goes back to#

Block tables are append-only#

When a block gets its hash#

When prefix caching is off#

Clearing the cache#

Code#

Remember this#

Try it#

Check yourself#

Sources#

Allocate: `get_new_blocks`#

Hit: `touch`#