KV Cache Management

1. Why KV Cache Management Is Hard

LLM serving lives and dies by KV cache management.

Big picture: the four layers

Sections 2–4 dissect each layer bottom up.

2. Core Data Structures

Four classes form the foundation.

2.1 KVCacheBlock

The atom.

@dataclass(slots=True)
class KVCacheBlock:
    block_id: int                                  # 0 .. num_gpu_blocks-1 (null_block = 0)
    ref_cnt: int = 0                              # >0 means "someone is using me, don't evict"
    _block_hash: BlockHashWithGroupId | None = None  # hash key when block is full and cached

    # Doubly-linked-list pointers (manipulated only by FreeKVCacheBlockQueue)
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None

    is_null: bool = False                         # placeholder block; never cached, never freed

Lifecycle of a block:

1. Born at pool init
2. Allocated via get_new_blocks()
3. Cached once full
4. Released
5. Re-hit or evicted

2.2 FreeKVCacheBlockQueue

A custom doubly-linked list.

2.3 BlockHashToBlockMap

The prefix cache's hash index.

class BlockHashToBlockMap:
    # Stored on BlockPool as .cached_block_hash_to_block
    _cache: dict[BlockHashWithGroupId, KVCacheBlock | dict[int, KVCacheBlock]]

    def get_one_block(self, key) -> KVCacheBlock | None: ...  # lookup
    def insert(self, key, block): ...                       # cache_full_blocks
    def pop(self, key, block_id) -> KVCacheBlock | None: ... # _maybe_evict_cached_block
    def __len__(self) -> int: return len(self._cache)         # ← true "how much content does CPU have?"

2.4 BlockPool (the container)

Defined in block_pool.py:129.

class BlockPool:
    def __init__(self, num_gpu_blocks, enable_caching, hash_block_size, ...):
        self.num_gpu_blocks = num_gpu_blocks
        self.blocks: list[KVCacheBlock] = [KVCacheBlock(i) for i in range(num_gpu_blocks)]
        self.free_block_queue = FreeKVCacheBlockQueue(self.blocks)
        self.cached_block_hash_to_block = BlockHashToBlockMap()

        # null_block (block_id=0) is a sentinel; never cached, never freed
        self.null_block = self.free_block_queue.popleft()
        self.null_block.is_null = True
        self.enable_caching = enable_caching
        self.kv_event_queue: list[KVCacheEvent] = []  # for distributed KV event broadcast

2.5 Visualizing the three states of a block

3. BlockPool’s Public API

Eight methods cover the entire scheduler surface.

3.1 Annotated: get_new_blocks()

The primary allocation path.

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

    ret = self.free_block_queue.popleft_n(num_blocks)  # head of LRU → oldest

    if self.enable_caching:
        for block in ret:
            self._maybe_evict_cached_block(block)  # drop hash if it had one
            assert block.ref_cnt == 0
            block.ref_cnt += 1                        # take ownership
    return ret

Eviction happens inline at allocation time.

3.2 Annotated: touch()

def touch(self, blocks: Sequence[KVCacheBlock]) -> None:
    for block in blocks:
        # ref_cnt=0 means sitting in free queue as eviction candidate
        if block.ref_cnt == 0 and not block.is_null:
            self.free_block_queue.remove(block)  # O(1) mid-queue removal
        block.ref_cnt += 1

This is where the doubly-linked list pays off.

4. The Three Layers Above BlockPool

Each layer adds one concern.

4.1 SingleTypeKVCacheManager

Manages KV blocks for one cache group.

4.2 KVCacheCoordinator

Coordinates multiple groups (full + sliding + mamba).

class KVCacheCoordinator:
    managers: list[SingleTypeKVCacheManager]   # one per group
    block_pool: BlockPool                        # shortcut to group 0 (or shared)

    def allocate_slots(self, request, num_new_tokens) -> list[list[KVCacheBlock]] | None:
        # Fans out across all groups; returns None if any group runs out

    def find_longest_cache_hit(self, hashes, max_len) -> tuple[list[list[KVCacheBlock]], int]:
        # Used by both GPU-side lookup and CPU-offload connector

4.3 KVCacheManager

The Scheduler's only entry point.

5. Important Files

All paths relative to vllm/.

6. GPU & CPU: The Same BlockPool, Twice

vLLM instantiates the same BlockPool class twice.

6.1 Where each pool is constructed

6.2 The code that creates the CPU pool

# vllm/v1/simple_kv_offload/manager.py:110
class SimpleCPUOffloadScheduler:
    def __init__(self, vllm_config, kv_cache_config, cpu_capacity_bytes, lazy_offload=False):
        self.cpu_kv_cache_config = self._derive_cpu_config(kv_cache_config, cpu_capacity_bytes)
        self.num_cpu_blocks = self.cpu_kv_cache_config.num_blocks

        # ← Same factory, different config
        self.cpu_coordinator: KVCacheCoordinator = get_kv_cache_coordinator(
            kv_cache_config=self.cpu_kv_cache_config,
            max_model_len=vllm_config.model_config.max_model_len,
            enable_caching=True,                        # prefix hash stays on
            enable_kv_cache_events=self.enable_kv_cache_events,
            hash_block_size=self.block_size,
        )
        self.cpu_block_pool: BlockPool = self.cpu_coordinator.block_pool

        # GPU side reference, bound by the connector after Scheduler builds kv_cache_manager
        self._gpu_block_pool: BlockPool | None = None

6.3 What differs, what doesn’t

7. The Scheduler’s Role, Step by Step

Every Scheduler.schedule() call follows a predictable KV-touch sequence.

7.1 Interaction points per step

7.2 Example: a prefill step with a CPU offload hit

# Inside Scheduler.schedule() — simplified

def schedule(self):
    self.kv_cache_manager.new_step_starts()                          # 1

    if sched_trace.enabled():                                        # 2 (tracing only)
        free_blocks = self.kv_cache_manager.block_pool.get_num_free_blocks()

    for request in self.waiting:
        computed_blocks = self.kv_cache_manager.get_computed_blocks(request)  # 3 local

        if self.connector is not None:
            n_ext, is_async = self.connector.get_num_new_matched_tokens(       # 4 external (CPU)
                request, num_computed=len(computed_blocks) * block_size
            )

        new_blocks = self.kv_cache_manager.allocate_slots(request, ...)   # 5

        if new_blocks is None:
            victim = self._pick_preempt_victim()
            self.kv_cache_manager.free(victim)                        # 6
            new_blocks = self.kv_cache_manager.allocate_slots(request, ...) # retry

        block_ids = self.kv_cache_manager.get_block_ids(request.request_id)  # 7
        scheduler_output.add(request, block_ids)

    return scheduler_output

7.3 Tracing hooks

The agent-kvcache fork emits a step_snapshot event per schedule() call.

# vllm/v1/core/sched/scheduler.py:484 (simplified)
sched_trace.step_snapshot(
    step=self._sched_step_counter,
    running=self.running, waiting=self.waiting,
    free_blocks=self.kv_cache_manager.block_pool.get_num_free_blocks(),  # ⚠ see §8
    total_blocks=self.cache_config.num_gpu_blocks,
    cpu_free_blocks=cpu_block_pool.get_num_free_blocks() if cbp else None,
    cpu_total_blocks=getattr(sm, "num_cpu_blocks", None),
    num_pinned=len(self.pinned_requests),
    pinned_blocks=pinned_blocks,
    ...
)

8. Pitfall: the Semantics of get_num_free_blocks()

It's a plain counter of blocks in the free queue.

8.1 The right way to count CPU DRAM usage

# The actual "blocks with usable cached content" count:
cpu_cached_blocks = len(cpu_block_pool.cached_block_hash_to_block)

# Three distinct numbers the viewer should show:
empty_blocks  = free_count - cached_count         # truly empty
cached_blocks = len(cached_block_hash_to_block) # has content, evictable
ref_blocks    = total - free_count                # ref_cnt > 0 (in-flight, active)

The trace schema currently emits only free/total. Adding cpu_cached_blocks fixes this.

8.2 Why the API is designed this way

The counter is correct for allocation but wrong for reporting. The word "free" is overloaded.

9. One-Page Recap