Prefix-Cache Hit Accounting
Background
LLM serving caches the KV state of shared prompt prefixes (system prompts, instruction templates). A new request whose prefix matches a cached one skips prefill for the matched length — a huge speedup when many requests share boilerplate.
Problem statement
Implement prefix_cache_savings(prompts). Process the list of token-id sequences in order; the first prompt incurs no savings (cache is empty). For each subsequent prompt, find the longest prefix of length that was already cached by any earlier prompt; save tokens of prefill. After processing each prompt, all of its prefixes are added to the cache.
Input
prompts—list[list[int]], token-id sequences in arrival order.
Output
Returns an int >= 0 — the total tokens saved across the whole stream.
Examples
Example 1 — first prompt saves 0
Input: [[1, 2, 3]]
Output: 0
Example 2 — identical repeated prompt saves its length
Input: [[1, 2, 3], [1, 2, 3]]
Output: 3
Example 3 — shared prefix of length 2
Input: [[1, 2, 3, 4], [1, 2, 5, 6]]
Output: 2
Example 4 — no shared prefix
Input: [[1, 2], [3, 4]]
Output: 0
Constraints
- "Prefix" is a strict left-anchored prefix (not a longest common substring).
- All sub-prefixes of every emitted prompt are added to the cache.
- Returns Python
int.
Notes
- Real implementations. Cache by block (vLLM uses 16-token blocks): the matched prefix must align to a block boundary. The kernel here is token-granular for simplicity.
- Eviction. Production caches have an LRU / size limit; this kernel keeps everything.
▶ Run executes the 3 visible sample tests below in your browser. Submit runs the full suite — including hidden tests — on the server for an official verdict.
- •Reference example: empty cache first prompt saves zero
- •Sample stream: identical repeated prompt
- •Reference: shared prefix of length two