Prompt Prefix Cache Hits

Most requests to a model API start the same way: the same system prompt, the same long document, the same first turns of a conversation. Inference servers save that work with a prefix cache: the computed state for the beginning of a prompt is kept, in fixed-size blocks of tokens, so the next prompt that starts the same way can skip it. You are simulating that cache to measure how many tokens it saves.

Prompts are arrays of token ids, processed in order. With block size B, a prompt's first B tokens form its block 1, the next B its block 2, and so on; a final group of fewer than B tokens is not a block and is never cached.

A block is identified by the whole prompt up to the end of that block: block 2 of [1,2,3,4] is the same cached block as block 2 of [1,2,3,4,9,9], but not as block 2 of [0,0,3,4], even though both end in 3, 4.

For each prompt:

1. Lookup. Count the leading blocks that are all in the cache: block 1, block 2, ... up to the first one that is missing. The prompt's cache hit is that count times B tokens.
2. Store. Every block of the prompt is then stored, or refreshed if already there, as the most recently used, deepest block first and block 1 last.
3. Evict. While the cache holds more than capacity blocks, remove the least recently used block.

Return the cache hit, in tokens, of every prompt.

Example

B = 2, capacity = 4. The first prompt [1,2,3,4,5] finds nothing and stores [1,2] and [1,2,3,4] (the lone 5 is not a block). The second, [1,2,3,4,9,9], finds both and misses its third block: a hit of 4 tokens. The third, [1,2,7,7], finds only [1,2]: 2 tokens. The fourth, [5,5,6,6], misses, and storing its two blocks pushes the cache to 6 blocks, so the two least recently used, [1,2,3,4,9,9] and [1,2,3,4], are evicted. The fifth, [1,2,3,4], now finds only [1,2] (2 tokens), and the sixth, [5,5,6,6,1], finds both of its blocks (4 tokens).

The answer is [0, 4, 2, 0, 2, 4].