Prompt prefix cache

A model server keeps the work it did on prompts it has seen, so a new prompt that starts the same way can skip that part. Prompts are lists of token ids.

Build PrefixCache(capacity=None). capacity is for level 3 and is None until then.

• insert(tokens: list[int]) -> int: cache this prompt. Prompts that share a beginning store it once: think of every cached token as a node in a trie, where a prompt is the path from the root. Return how many tokens were new (nodes created).
• lookup(tokens: list[int]) -> int: the length of the longest cached prefix of tokens: the largest k such that tokens[:k] is the start of some inserted prompt (0 if none).
• cached_tokens() -> int: how many tokens (trie nodes) are stored.

c = PrefixCache()
c.insert([1, 2, 3, 4])    # 4
c.insert([1, 2, 9])       # 1   (1, 2 are already stored)
c.lookup([1, 2, 3, 7])    # 3
c.lookup([1, 2])          # 2
c.lookup([2, 1])          # 0
c.insert([1, 2])          # 0
c.cached_tokens()         # 5

Every prompt has 1..1000 tokens, ids in 0..10^9; up to 10^6 tokens over all calls.