KV-Cache Eviction (Sliding Window)

Background

For long-context inference the KV cache grows linearly with sequence length and dominates memory. Sliding-window eviction (the simplest variant) keeps the most recent $W$ tokens' KVs and drops the rest. More sophisticated schemes (Heavy-Hitter / H2O) keep important early tokens; the windowed form is the baseline.

Problem statement

Implement kv_evict_sliding(kv_cache, window_size, n_keep_first=0). Drop entries between position n_keep_first (kept always) and the start of the trailing window. Return the reduced list.

Input

• kv_cache - list of items (one per token position).
• window_size - int >= 1, number of trailing entries to keep.
• n_keep_first - int >= 0, "sink" tokens to keep at the start (default $0$).

Output

• list of length $\le n\_keep\_first + window\_size$.

Examples

Input: kv_cache=list(range(10)), window_size=3, n_keep_first=1
Output: [0, 7, 8, 9]    # sink token 0, then last 3

Constraints

• Returns the cache unchanged when len(kv_cache) <= n_keep_first + window_size.
• window_size >= 1 and n_keep_first >= 0.

Notes

• Why sink tokens. The very first tokens often carry instruction context. Keeping a few "sinks" preserves grounding even with aggressive eviction.