Find the longest reusable KV-cache prefix for each requested token sequence. The root has node ID zero. Cached sequences are inserted in input order, with tokens processed from left to right. Each previously unseen token edge receives the next node ID, starting at one; duplicate sequences and shared prefixes reuse existing nodes.
A request matches consecutive edges from the root until its first missing token, even if the matched prefix ends inside a longer cached sequence. With no match, the cache node is zero and the entire request is uncached. An empty cached sequence adds no nodes; an empty request matches zero tokens at the root.
Return a Python dictionary with matches, a list in request order. Each match is a dictionary containing matched_length and cache_node as Python integers, plus uncached_suffix as a list of the remaining token integers.
Input: cached_sequences = [[1,2],[1,2,3],[4]], requests = [[1,2,9],[4,5],[5]]
Output: {"matches":[{"matched_length":2,"cache_node":2,"uncached_suffix":[9]},{"matched_length":1,"cache_node":4,"uncached_suffix":[5]},{"matched_length":0,"cache_node":0,"uncached_suffix":[5]}]}
Explanation: Insertion creates nodes 1 and 2 on the first branch, node 3 below it, and node 4 for token 4.
Input: cached_sequences = [[7],[7]], requests = [[7,8]]
Output: {"matches":[{"matched_length":1,"cache_node":1,"uncached_suffix":[8]}]}
Input: cached_sequences = [[9]], requests = [[2,2,2]]
Output: {"matches":[{"matched_length":0,"cache_node":0,"uncached_suffix":[2,2,2]}]}
A dictionary can map a token to a child node ID.
List length can supply the next sequential node ID.
List slicing extracts the unmatched suffix.
Accepts: array
Accepts: array
Find the longest reusable KV-cache prefix for each requested token sequence. The root has node ID zero. Cached sequences are inserted in input order, with tokens processed from left to right. Each previously unseen token edge receives the next node ID, starting at one; duplicate sequences and shared prefixes reuse existing nodes.
A request matches consecutive edges from the root until its first missing token, even if the matched prefix ends inside a longer cached sequence. With no match, the cache node is zero and the entire request is uncached. An empty cached sequence adds no nodes; an empty request matches zero tokens at the root.
Return a Python dictionary with matches, a list in request order. Each match is a dictionary containing matched_length and cache_node as Python integers, plus uncached_suffix as a list of the remaining token integers.
Input: cached_sequences = [[1,2],[1,2,3],[4]], requests = [[1,2,9],[4,5],[5]]
Output: {"matches":[{"matched_length":2,"cache_node":2,"uncached_suffix":[9]},{"matched_length":1,"cache_node":4,"uncached_suffix":[5]},{"matched_length":0,"cache_node":0,"uncached_suffix":[5]}]}
Explanation: Insertion creates nodes 1 and 2 on the first branch, node 3 below it, and node 4 for token 4.
Input: cached_sequences = [[7],[7]], requests = [[7,8]]
Output: {"matches":[{"matched_length":1,"cache_node":1,"uncached_suffix":[8]}]}
Input: cached_sequences = [[9]], requests = [[2,2,2]]
Output: {"matches":[{"matched_length":0,"cache_node":0,"uncached_suffix":[2,2,2]}]}
A dictionary can map a token to a child node ID.
List length can supply the next sequential node ID.
List slicing extracts the unmatched suffix.
Accepts: array
Accepts: array
