Walk through how vLLM's prefix caching identifies a reusable KV block and hands it to a new request, step by step.

TL;DR: Every full 16-token block gets a hash of (parent hash, its token ids, extra keys such as LoRA or image ids), so one hash identifies the whole prefix ending at that block. A new request walks its hashes until the first miss, takes those blocks by bumping their reference counts, and recomputes the rest; the last prompt token always runs, so a fully cached 1,200-token prompt still recomputes one block (1,184 of 1,200 tokens hit).

How to approach it

Name the version, because the internals have moved: this is vLLM v0.31.0 (October 2026), where prefix caching is on by default and lives in the scheduler's KV cache manager, not the workers. Then trace one request through four stages: hash, look up, allocate, free. Ask whether multimodal inputs or LoRA are in play, since both change what a block's identity includes.

A strong answer

1. Hash. When a request arrives, its block hasher walks the prompt in 16-token blocks (the default block size) and hashes only full blocks. Each hash is sha256 (the default prefix_caching_hash_algo) of a tuple: the parent block's hash, the block's token ids, and extra keys. The first block's parent is a fixed NONE_HASH. Extra keys carry what the token ids alone do not: the LoRA adapter name, multimodal content hashes and offsets for any image overlapping the block, prompt-embedding digests, and on the first block only, a per-request cache_salt. Chaining makes position implicit: the same 16 tokens after a different prefix produce a different hash.
2. Look up. The KV cache manager searches for the longest run of hashes present in its hash-to-block map, capped at num_tokens - 1. The cap exists because the model must run at least the last prompt token to produce logits, and since allocation is block-aligned, a fully cached prompt recomputes its whole last block.
3. Take. Each hit block is "touched": its reference count goes up, and if it was sitting in the free queue (ref count 0, still holding valid KV) it is pulled out. The request's computed-token count jumps forward by the hit length, so the scheduler never schedules those tokens. Hit blocks are shared read-only; a request writes only into blocks it owns alone.
4. Free and evict. When a request finishes, its blocks are released in reverse order. Hashed blocks go to the tail of the free queue, unhashed ones to the head. Allocation pops from the head, and only at that moment does a cached block lose its hash. So eviction is LRU over freed blocks, and a request's tail blocks go before its head, which keeps the shared system prompt alive longest.

A runnable model of the lookup:

import hashlib, pickle

BLOCK = 16
NONE_HASH = hashlib.sha256(b"vllm-none-hash").digest()  # fixed seed, sha256

def block_hashes(tokens, extra=None):
    """Chained hashes of every FULL block; a partial tail block gets none."""
    out, parent = [], NONE_HASH
    for i in range(0, len(tokens) - BLOCK + 1, BLOCK):
        key = (parent, tuple(tokens[i:i + BLOCK]), extra)
        parent = hashlib.sha256(pickle.dumps(key)).digest()
        out.append(parent)
    return out

def cache_hit_tokens(cache, tokens, extra=None):
    hashes = block_hashes(tokens, extra)
    max_hit = len(tokens) - 1          # last token must run to produce logits
    hit = 0
    for h in hashes:
        if h not in cache or (hit + 1) * BLOCK > max_hit:
            break
        hit += 1
    return hit * BLOCK

system = list(range(1000))
a = system + [7] * 200
b = system + [9] * 200
cache = set(block_hashes(a))                       # A finished, blocks cached
print("B hits", cache_hit_tokens(cache, b))         # 992: 62 full blocks
print("A again", cache_hit_tokens(cache, a))        # 1184: last block recomputed
print("A, other LoRA", cache_hit_tokens(cache, a, ("lora", "x")))  # 0
print("empty", cache_hit_tokens(cache, []))         # 0

What the hit is worth for Llama 3.1 8B on an H100, at an assumed 50% of the 989 TFLOP/s dense BF16 peak:

prefill per token = 2 x 8.03e9 / (989e12 x 0.50)  = 32.5 us
B's prompt        = 1,200 tokens x 32.5 us        = 39.0 ms without the cache
B's hit           = 992 tokens (62 blocks)        = 32.2 ms saved, 83% of prefill
the 8 system-prompt tokens in block 63 share it with user text, so they recompute

Two details separate a strong answer. First, the seed: for cryptographic hashes v0.31 derives NONE_HASH from a fixed default, so separate vLLM processes compute identical hashes for identical content, which is what lets KV-aware routers and external KV stores key on them. The xxhash options keep a random per-process seed unless PYTHONHASHSEED is set, because a predictable non-cryptographic seed would let an attacker precompute collisions. Second, isolation: two tenants with the same system prompt share blocks unless they send different cache_salt values, and that sharing is a timing side channel worth closing on a multi-tenant API.

The reversal: when prompts share nothing (unique documents, a batch job over distinct inputs), every lookup misses and hashing every block is pure overhead, small but nonzero. That is the one workload where turning prefix caching off is defensible.

What interviewers probe next

"Why hash the parent instead of the block's token positions?" A position-keyed scheme would match the same tokens at the same offset after a different prefix, which would be wrong KV. The parent chain makes a hit at block k imply a match on blocks 0 through k.

"The cache is full of hit blocks and a new request needs space." Only blocks with reference count 0 are in the free queue; blocks used by running requests can't be evicted, so the scheduler preempts instead.

"Now the model uses sliding-window layers." Those groups get their own manager, which only needs the blocks inside the window, so a hit can be valid for full-attention layers and partial for local ones; the coordinator takes the hit length that all groups agree on.

How it's scored

Weak: describes caching whole prompts by string, or says blocks are evicted when the request ends.

Hire: explains chained block hashes, the longest-prefix walk, reference counts and LRU eviction from the free queue, and computes a hit length at block granularity.

Strong Hire: knows the num_tokens - 1 cap and its whole-block consequence, names the extra keys and cache_salt, and explains why the fixed seed matters for cross-node reuse.

Common mistakes

• Forgetting the extra keys, then expecting a LoRA request to hit the base model's cache.
• Saying a cached block is freed when its request finishes; it stays valid until allocation reuses it.
• Counting a partial last block as cached. Only full blocks are hashed.
• Benchmarking the cache with identical prompts and reporting 100% hits, when the last block always recomputes.