Prefix Cache Lookup and Reuse
The problem, from first principles
Many real workloads repeatedly send requests that share a long common prefix — a system prompt, a few-shot template, a long document being asked multiple questions about. Recomputing that shared prefix's KV cache from scratch every request wastes both compute and time-to-first-token. Implement automatic prefix caching: given a store of previously computed KV-cache blocks keyed by the hash of the token sequence they represent, find the longest matching prefix of a new request's tokens already in the store, and report how many tokens (and blocks) of prefill computation can be skipped by reusing it.
From theory to code
hash_i = H(hash_{i-1}, block_i) with hash_{-1} = SEED -- chained hash per block
reused_tokens = block_size * (number of leading blocks whose chained hash is a cache hit)
Constraints
- Tokens are grouped into non-overlapping blocks of
block_size(a trailing partial block never counts as reusable and is not added to the store as a partial hash). - Use a hash chained across blocks so a match at block
irequires every earlier block to also match. - Report the number of tokens/blocks reused from the cache and the exact token ids that still need prefilling.
- After processing, insert the new request's full block hashes into the store for future reuse.
Hints
Hint: Chaining is what makes it a prefix match
Chain the hash across blocks (hash_i depends on hash_{i-1}) so a match at block i can only happen if every earlier block matched too — this is what makes it a genuine PREFIX match rather than a coincidental match of an isolated block deeper in the sequence.
Hint: Stop at the first miss
Stop walking forward at the first block whose chained hash is not already in the store — every block after a miss must be treated as new regardless of its own content, since the chaining means a later "match" would be coincidental, not a genuine shared prefix.
Click "Run Tests" to test your implementation