How does a serving stack find the longest cached KV prefix for a request?

## The lookup problem A cache entry is only valid for a span that begins at token zero and matches exactly (causal attention and position binding force this). So the server's job on each request is: walk the incoming token id sequence and find the longest stored prefix identical to it. It must do this in roughly constant or logarithmic time, across thousands of stored prefixes and dozens of concurrent requests, without copying tensors. ## Design one: a radix (prefix) tree SGLang popularised **RadixAttention**: a radix tree whose edges are labelled with token spans and whose nodes point at the KV blocks for that span. Inserting a request's tokens creates or extends a path; a new request walks the tree from the root, following matching tokens until it diverges, and adopts the KV of everything it walked. The structure is a natural fit because shared prefixes are exactly what a prefix tree compresses: a system preamble used by two hundred concurrent sessions is one path in the tree, held once in memory, with two hundred divergent branches hanging off it. Nodes in use by live requests are reference-counted and cannot be evicted; cold leaves are dropped under memory pressure, usually by least-recently-used order. ## Design two: chained block hashes vLLM's automatic prefix caching takes a different route. The token sequence is divided into fixed-size blocks — 16 tokens is a common default — and each block gets a hash computed over *its own tokens plus the hash of the preceding block*. That chaining is what encodes history: two blocks with identical contents but different predecessors hash differently and cannot be confused, which is precisely the causal-dependency requirement expressed as a hash. Lookup then becomes a sequence of hash-table probes: probe block 1, probe block 2, stop at the first miss. Blocks are the allocation unit as well as the matching unit, so pages of KV memory can be shared and reference-counted directly. ## Granularity and the rounding-down effect Block-based matching has a visible consequence: the reported match rounds **down** to the last fully identical block. Two prompts that share exactly 100 tokens before diverging, with a block size of 16, share six full blocks — 96 tokens — and the remaining four tokens of real overlap are recomputed. This is harmless at scale but confuses people comparing an expected match length against a reported one. Tree-based designs can split nodes at the divergence point and match to the exact token, though they still allocate KV in pages. ## Why matching is on token ids The stored tensors were derived from specific token ids at specific positions, so ids are the only sound key. This has a practical edge: identical-looking text can produce different ids. Byte-pair merges span visual boundaries, so a trailing space, a different Unicode normalization, a swapped quote glyph, or a re-serialized structure can shift the id stream at some point, and the server sees a plain divergence at that token. There is no fuzzy fallback and no similarity threshold — a near-miss and a total mismatch are handled identically from the divergence point onward. ## Sharing across concurrent requests The same stored prefix serves many in-flight requests at once, which is the property that makes this economically interesting on a self-hosted server: one copy of a 30,000-token preamble in GPU memory, read by every session that starts with it, instead of one copy per session. Sharing is safe because the state is a pure function of the shared tokens — nothing user-specific has been mixed in yet, since the divergent per-user content comes later in the sequence by construction. ## Eviction and lifetime Entries under an active request are pinned. Everything else is a candidate: LRU is the common policy, sometimes weighted by how expensive a prefix was to build or how frequently it is hit. A prefix that falls out of the cache simply means the next matching request pays a normal prefill. Hosted APIs express lifetime as a time-based policy rather than a memory-pressure policy, but the underlying object being evicted is the same. ## What to say in an interview Name the two mechanisms — prefix tree over token spans, or chained hashes over fixed token blocks — and then the three properties that follow from either: exact token-level matching from position zero, longest-prefix semantics with a possible round-down to block granularity, and cross-request sharing with reference-counted eviction. That is the complete mental model, and it explains a class of confusing observations without reference to any one vendor's documentation.