Pure recency-based KV-cache eviction fails past the cache size — StreamingLLM shows keeping initial tokens ('attention sinks') is required, breaking a clean locality analogy to OS working sets

Denning's working-set model manages OS memory pressure by locality: keep whatever was recently used. StreamingLLM (Xiao et al. 2023, arXiv 2309.17453) tests whether the same principle — evict-by-recency — works for the LLM KV cache, and finds it does not, on its own.

Plain window attention (keep only the most recently seen tokens, evict everything older) "fails when the text length surpasses the cache size": once the very first tokens fall out of the window, generation quality collapses, even though those tokens are the ones least likely to be "needed" by a naive recency heuristic. The fix is not more locality but a fixed exception to it: "keeping the KV of initial tokens will largely recover the performance." The paper terms these retained early positions attention sinks — the model reliably allocates disproportionate attention weight to the first few tokens regardless of their content, so evicting them destabilizes attention over everything downstream.

This is the point where the OS-virtual-memory analogy (see claim-pagedattention-borrows-os-virtual-memory-paging, claim-llm-serving-vllm-reimports-os-preemption-and-thrashing) breaks cleanly: a working set is defined by recent locality, but a KV cache's working set apparently needs a non-local, fixed anchor with no obvious OS-paging equivalent.