KV Cache
Paged, session-aware key/value cache with cross-session prefix sharing. Lets repeated and shared prompts skip the prefill cost entirely.
Why a KV cache exists
The problem: attention re-reads every previous token's K and V matrices on every new token. Recomputing them from scratch each time is wasted work — they're deterministic from the prompt.The fix: store the K/V tensors for every prompt position once, look them up by prefix, and only run the model on the new tail tokens. For repeated or shared prompts (chat templates, system prompts, multi-turn sessions) the savings are huge.
Two-layer lookup
A fast exact match for whole prompts, a flexible radix tree for prefix sharing.
incoming prompt tokens
a list of integers
e.g. [2, 106, 1645, ..., 107]
Layer 1 — Exact-match index
a plain dict from "the whole prompt" to its blocks
key: tuple(token_ids)
value: list of cache blocks
always block-aligned
→ if the exact same prompt has been seen before, full hit
Layer 2 — Radix tree
prefix matching across all sessions
walks the tree along the prompt's tokens
returns the longest cached prefix
enables sharing — many prompts that start the same
(e.g. shared chat template) reuse the same blocks
Why both layers exist (this is the gotcha)
The radix tree only stores nodes at block-aligned boundaries. When two prompts share, say, 47 tokens but the
block size is 64, the radix tree has nothing to insert and silently bails. This happens constantly because the
chat-template prefix is a fixed N tokens that almost never lines up with a block boundary.
Without the exact-match layer, "ask the same question twice" would miss the cache. The dict catches it.
This two-layer pattern matches what SGLang and vLLM ship — same problem, same shape of fix.
Blocks and the block pool
The cache is a fixed pool of equally-sized blocks. Allocations are handles into per-layer tensor pools — no python-level tensors flying around.
BlockManager
owns one big tensor per layer, per K and per V
shape: (num_blocks, n_kv_heads, block_size, head_dim)
allocated once at startup, never grows
allocate(n) → pops n from the free list, ref_count++
free(blocks) → ref_count--, return to free list when 0
tracks: total_blocks, free_blocks, used_blocks, utilization
Block (the handle)
a thin object pointing into the pool
block_id, block_size
token_ids — what's actually stored here
ref_count — how many references hold this block
last_accessed — timestamp for LRU
is_first_block — attention-sink flag, protected from eviction
acquire / release / clear methods
Why pre-allocated tensor pools
no malloc on the hot path · contiguous memory means good cache behavior · capacity is bounded and predictable
Radix tree (compressed prefix trie)
Lets many prompts share the same blocks for the part of the prompt they have in common.
root
[chat template prefix]
[other prompt start]
node A
2 blocks · ref=3
node B
1 block · ref=1
[user A's tokens]
[user B's tokens]
node A1
3 blocks · ref=1
node A2
2 blocks · ref=1
Operations
find_prefix(tokens)
walks edges as long as tokens match. returns longest matched
prefix and the blocks along the way (block-aligned only).
insert(tokens, blocks)
walks existing edges. on a partial match it splits the edge at
the largest block-aligned boundary. bails silently if the
first block of the new entry would straddle the split point —
that's exactly when the exact-match index covers for it.
remove(tokens)
walks to leaf, frees blocks, cleans up empty parent edges.
edges hold variable-length token sequences (compressed trie)
Lookup flow (full path)
backend.prefill_lookup(tokens, sid)
called by scheduler.admit_pending
cache.lookup(tokens, sid)
begin two-layer search
try exact_index first
whole-prompt dict hit?
fallback to radix.find_prefix
longest matching prefix
for each matched block: eviction.on_access(block)
marks the block as recently used (or bumps its score, depending on policy)
so it won't be evicted out from under us
turn matched blocks into a HF DynamicCache
slice the per-layer pools by block_id and stack them
into the format the model.forward() expects as past_key_values
return value
(matched_tokens_count, partial_kv | None)
the scheduler now knows how many prompt tokens it can skip and what KV state to start from.
remaining tokens go through prefill (chunked or whole), then store the suffix back into the cache.
Store flow
After prefill produces new K/V state for the uncached portion of the prompt, store it for next time.
prefill produced new KV
for the suffix the cache didn't have
cache.store(...)
called by the backend or scheduler
need new blocks?
if pool is full → evict
allocate + write into pool
copy K and V slices, layer by layer
eviction loop (if needed)
while not enough free blocks: pick a victim with ref_count == 0 using the eviction policy,
remove it from the radix tree and the exact-match index, clear the block, return it to the free list
attention-sink flag
if this is the first block of the prompt
(skip_tokens == 0), set is_first_block = True
SinkLRU and H2O refuse to evict it
register in both layers
radix.insert(tokens, blocks) — for prefix sharing
exact_index[tuple(tokens)] = blocks — for whole-prompt fast path
caller releases its temporary reference; ref_count drops to 0 only after the row finishes
Eviction policies
Same interface, three implementations. Selected via the EVICTION_POLICY env var.
LRU
"least recently used"
on every access, stamp the block with now()
to evict, pick the block with the oldest stamp
cheap and predictable
downside: oblivious to which tokens
actually carry useful information
good default · the baseline to beat
SinkLRU
LRU but never evict the first block
protects blocks marked is_first_block
picks LRU among everything else
why: the very first tokens of a sequence
are an "attention sink" — most layers
attend back to them no matter how long
the sequence gets (StreamingLLM finding)
good for: long-context streaming
H2O
attention-mass-weighted eviction
on every step, sum the attention weight
paid to each block by every head
to evict, pick the lowest-scoring block
(also protects is_first_block)
⚠ wired but inactive: backend doesn't
extract attention weights yet, so all scores
stay at 0 — currently behaves as LRU
future: needs output_attentions=True path
Method What it must do on_access(block) called when a block is read from. update timestamps or accumulators. select_victim(candidates) given the set of blocks with ref_count == 0, pick one to evict. record_attention(block, score) H2O-only hook. backend would call this with attention mass per block.
Stats & observability
Counter Where hit_count, miss_count, hit_rate /cache/statseviction_count /cache/statstotal / used / free / utilization /cache/statscache_hit_tokens (per request) response body of /generate