A language model inference service caches previously computed token sequences to avoid redundant computation. The cache uses a compressed prefix tree (radix tree) to store integer token sequences efficiently. Sequences that share a common prefix are merged into shared nodes, reducing memory usage.

Design a data structure called TokenCache to store and query token sequences using this structure. ...