LRU vs GDSF vs Recency-Weighted Eviction for Long-Context KV Cache

KV cache eviction decides which tokens a large language model forgets while it's still generating an answer, and that single decision now shapes serving performance more than almost any other setting in long-context work. The math forces the issue: KV cache grows in a straight line with sequence length, and once a request runs 32K or 128K tokens, the cache can outweigh the model's own parameters. A single Llama 3.1 70B request at 128K context needs roughly 42.9 GB of KV cache at BF16 precision. Running LLaMA-2-7B at batch size 8 and 32K context pushes that number to 128 GB. Quantization helps some: FP8 cuts the 42.9 GB figure roughly in half, and NVFP4 on Blackwell hardware brings it down near 10.7 GB. But quantization only shrinks the footprint per request. It does nothing to answer the harder question of what to keep and what to throw away once thousands of sessions are fighting over the same pool of memory.

Before eviction policy even enters the picture, there's a more basic question of how memory gets handed out. Systems before PagedAttention wasted 60 to 80% of allocated KV memory to fragmentation, the same failure that plagued early operating system memory managers decades ago. PagedAttention borrowed the fixed-size page idea straight from OS design: fixed-size blocks, per-sequence block tables, waste down under 4%, throughput up 2 to 4x. No more holding a giant contiguous chunk of memory aside for a sequence that might grow or shrink unpredictably. That's the substrate almost every serving system runs on now, and it deserves credit for solving allocation cleanly. But PagedAttention is a prerequisite for sound eviction, not a stand-in for one. Once memory sits in blocks, something still has to decide which block goes when the cache fills up, and the unit of that decision is typically the block rather than the whole request.

The decision also splits into two phases that behave nothing alike. During prefill, a batch of tokens gets evicted up front to fit a cache budget before generation even starts. During decode, eviction happens one block at a time, triggered the moment the newest block fills. A policy tuned for one phase can be exactly wrong for the other, which goes a long way toward explaining why no single eviction algorithm has won out across the board. Memory usage itself is well understood and well measured at this point. What's still contested, and what the rest of this piece works through, is which assumption about token utility actually survives contact with real traffic.

What LRU assumes and where those assumptions break under long-context workloads

Least Recently Used caching runs on one assumption: recency predicts future need. Touch a block, and that block becomes the one most likely to get touched again soon. That held up fine for decades of web caching and database buffer pools, where requests arrived short, stateless, and clustered naturally in time. Nothing about a webpage request cares whether the bytes came from the start or the end of a file.

Long-context LLM serving breaks that assumption in ways that compound on each other, and the compounding is the whole story. Take concurrency first: when unrelated workloads share a cache, a burst of short requests from unrelated workloads can flush the KV blocks belonging to a long-running session, purely because the short requests generate more recent touches. Worse, long shared prefixes, things like system prompts or a document loaded once for repeated questioning, get hammered during prefill and then sit completely idle through the entire decode phase. LRU reads that idle stretch as proof of low value and evicts the prefix, which forces an expensive re-prefill the instant the session needs it again.

Then there's the problem of attention sinks, and this one exposes LRU as fundamentally the wrong tool rather than a merely imperfect one. Research on streaming attention found that the earliest tokens in a sequence, not the most recent ones, absorb a disproportionate share of attention through the entire generation. LRU has no way to see this. It sees old tokens, and it evicts them, throwing away exactly the tokens the model leans on hardest.

LRU assumes that which tokens matter stays fixed over time, and all three failure modes trace back to that single assumption. Recent work on mean-aggregation-based importance scoring shows the assumption is fragile, and the fragility is most visible in the extreme cases: long sequences, skewed attention, adversarial-leaning prompts (arXiv 2510.13334). Once the assumption breaks, any scoring built on top of it breaks with it.

None of this makes eviction a minor inconvenience to shrug off. Re-prefilling a long context costs real, measurable time. In a document QA scenario with a 65K-token document, Llama-3.1-405B has to pull 33 GB back over PCIe to recover from a miss, costing around 500 milliseconds. That's a stall the user feels, not some rounding error buried in a latency budget.

None of this makes LRU a bad algorithm across the board, though, and reading it that way misses the point. For short-context, uniform traffic with no shared prefixes worth protecting, LRU's O(1) simplicity is a real advantage, and reaching for anything heavier wastes engineering effort for no measurable gain. The failure is specific to workload shape: long contexts, shared prefixes, mixed session priorities, attention sinks. Without those conditions, LRU does exactly the job it was built for.

That leaves two paths forward. Bolt a frequency signal onto recency, the GDSF and LFU and ARC route, or reweight recency by something closer to actual cost or learned utility, the attention-signal and RL route. The second path, as the rest of this piece argues, is where the real gains sit.

How GDSF incorporates cost and frequency in practice

Greedy Dual-Size Frequency goes back to 1998, designed by Cherkasova for web proxy caching, long before anyone thought seriously about transformer attention. GDSF gives each cached object a priority score built from three things: how often it gets accessed, how expensive it was to fetch, and how big it is. Whatever scores lowest gets evicted first.

The cost term is the reason GDSF is worth borrowing for KV caching, full stop. Cost maps directly onto the compute expense of re-prefilling a block: a long shared prefix that took a large number of FLOPs to compute the first time is expensive to lose, and GDSF's score says so out loud, instead of leaving the fact implicit the way LRU does. Frequency patches LRU's biggest blind spot directly, too: a system prompt or a heavily queried document gets touched by many requests over time, building a frequency score that protects it through long stretches where it isn't the most recently touched thing in the cache. Size factors in as well, since a bigger block usually means more tokens and more recompute cost if it gets dropped.

What GDSF doesn't have is any model of what the transformer's attention is about to do next. Cost, in GDSF's world, is a static number stapled to a block. It has zero view into which tokens the model is about to lean on. That gap widens most in workloads that never let GDSF's real strengths show up. High-concurrency serving with a wide mix of context lengths, and traffic with identifiable hot prefixes that repeat often enough to build up frequency, are exactly where GDSF earns its keep. One-shot, non-repeating long documents are at the other end: frequency never accumulates, so cost weighting is the only thing separating GDSF from plain LRU, and on its own, that's thin ground to stand on.

That's the theoretical case for GDSF. Whether it survives a controlled, head-to-head test against the field is a separate question, and one recent benchmark study took it on directly.

What the CLEVER benchmark study found when it put LRU, LFU, ARC, GDSF, and others under one protocol

Kulkarni, Harkare, and Arvind Yogesh Suresh Babu, in "Which Eviction Policy Should an LLM Cache Use?" (arXiv 2608.20280, submitted August 20, 2026, University of Michigan) ran seven policies through one shared protocol called CLEVER, testing FIFO, LRU, LFU, ARC, GDSF, a single-pass streaming version of SISO, and a semantic-redundancy policy. The test covered three query corpora (LMSYS, QQP, MOSS), three cache capacities (10%, 20%, 30%), and two embedding models (MiniLM, gte-base), eighteen settings in total.

The headline number is almost anticlimactic: no policy beat LFU by more than 0.041 percentage points in any of the eighteen settings. That's the entire spread among the strongest contenders, a real margin, not a rounding artifact, but a thin one nonetheless. ARC landed within 0.01 points of LFU. GDSF stayed within 0.62 points. The top tier of eviction policies is, practically speaking, a dead heat, and anyone arguing hard for one sophisticated policy over another at that tier is arguing over noise. Pick LFU and move on; the fight over which top-tier policy wins is not a fight worth having.

The bottom of the ranking tells a sharper story. FIFO trailed LFU by as much as 8.67 points, and the streaming SISO variant trailed by up to 8.55 points, both at tight cache capacity. So policy choice matters, but the real gap is between "reasonable" and "naive," not between one clever policy and another.

The paper offers a mechanism for why the top tier converges so tightly: a conditional packing result showing that, under exact lookup with insert-on-miss, a newly admitted cache entry can't have a resident neighbor within the hit radius. That starves geometry-aware, semantic-scoring policies of the redundancy signal they'd need to differentiate themselves, so their scores collapse back toward plain frequency and recency anyway. Raw hit rates of 51 to 60% on LMSYS and QQP fall to quality-adjusted rates of just 1.1 to 2.2% once an LLM judge checks whether the cached answer actually substitutes for what the query needed. Only 2.1 to 3.9% of sampled hits survived that audit at the tested MiniLM threshold. Thresholds don't transfer across embedding models either: a threshold tuned on MiniLM produced a degenerate 100% hit rate with zero evictions when swapped onto gte-base.

One caveat needs to sit front and center, because skipping it would misread the whole study. CLEVER evaluates semantic caches, response-level reuse based on embedding similarity between queries, not token-level KV eviction inside a single inference run. The packing result and the quality collapse are properties of that semantic layer, not of within-context eviction, where GDSF-style cost weighting works on an entirely different signal. What likely carries over is the shape of the finding: sub-point gaps among strong policies, real underperformance from FIFO-class policies at tight capacity. The exact percentages don't map onto token-level KV eviction, and treating them as if they do would be a mistake.

CLEVER's ranking doesn't stand uncontested, either. Sun et al. (2026) report LRU and LFU losing to FIFO on agent-memory workloads, the reverse of what CLEVER found, where FIFO never beat LRU in any of the eighteen settings. That disagreement is not a flaw in either study so much as a demonstration that eviction rankings depend on workload shape, and any claim of a universal winner deserves suspicion on sight.

Why recency-weighted and attention-signal-based eviction exists as a separate category from simple recency

Within-context eviction asks a different question than semantic caching does: which tokens' key and value vectors to drop while a single long sequence is still being generated.

Early approaches were blunt instruments. FIFO drops the oldest tokens. Sliding window keeps only a fixed number of recent tokens. Neither one looks at attention structure at all, just position in the sequence. Research into streaming attention changed that by pointing at something specific: initial tokens in a sequence draw a disproportionate share of attention for the entire generation, the attention sink effect, while recent tokens carry most of the immediately relevant context. Plain recency misses the sink tokens by definition, since they're the oldest thing sitting in the cache.

Recency-weighted eviction means giving high retention scores to both recent tokens and attention-sink tokens, then evicting whatever falls in the middle: tokens neither recent enough nor structurally important enough to earn a pass. That's a genuinely different mechanism from LRU on cache blocks. LRU only tracks time since last touch. Recency-weighted schemes bake in a model-specific prior about where attention actually flows inside a transformer, and that's a real step up, not a cosmetic one.

These scoring-aggregation frameworks still assume a fixed subset of tokens stays consistently important across the whole generation, and most default to mean aggregation to enforce that assumption, a limitation that carries straight over from the LRU discussion above. That assumption is fragile in exactly the way described earlier, and it fails hardest at the extremes. Recency-weighted eviction is still backward-looking at bottom: it uses past attention patterns to guess at future relevance. That's a better proxy than raw recency, but a proxy is what it stays. It doesn't measure what the model is about to need.

What learned and automated eviction policies reveal about the limits of heuristic scoring

If every heuristic is a proxy, the next question answers itself: can a model learn the real thing directly, instead of guessing at it from position or attention history? Apple's KV Policy framework (KVP, Moschella, Manduchi, Sener, arXiv 2602.10238, accepted ICML 2026) tests exactly that, with lightweight, per-attention-head reinforcement learning agents trained on pre-computed generation traces, using only key and value vectors as input and no changes to the underlying LLM.

KVP reframes eviction as a ranking problem, with a reward signal built from future token utility evaluated across all cache budgets at once. The finding cuts against the heuristics discussed so far: the StreamingLLM sink-and-recency rule deviates substantially from actual future attention importance, while KVP's learned policy recovers the real, non-local structure of that future attention, something no fixed heuristic can capture by construction. Tested on RULER up to 128K tokens, on OASST2-4k multi-turn dialogue, and zero-shot on BoolQ, LongBench passage retrieval, and GovReport, KVP beats strong baselines across the board.

A separate line of work, CacheCraft, used an LLM-guided code-evolution engine to search for eviction policies automatically instead of hand-designing them. The policy it landed on, FRC (Feature-Rich Compression), scores tokens with three fixed-weight signals: local attention received, neighborhood attention density, and KV-head maximum salience, combined with chunk-level top-k selection. Without any per-model retuning, FRC ranked first among evaluated single-pass KVPress baselines in 12 of 20 RULER 4k/8k grid cells at compression ratio ≥ 0.75, across both Llama-3.1-8B-Instruct and another model, with gains of +15.4 points on Llama at 4k and +13.9 points on the other model at 8k, both at 88% compression (arXiv 2608.14555).

A third approach, VaSE (value-aware stochastic eviction), skips training. It combines key-based scoring, value-magnitude upweighting, and a stochastic diversity term across multiple axes. Recent work also frames KV eviction through the Information Bottleneck principle, treating it as a question of how much task-relevant information a compressed cache can hold onto (arXiv 2604.25975).

Taken together, these results say something CLEVER's results didn't: in within-context eviction, the gap between a fixed heuristic and a learned policy runs wide. That cuts the opposite way from what CLEVER found for semantic response caching, where the top policies converged to within fractions of a point of each other. The structure explains the difference. A semantic cache has exactly one signal to work with, embedding similarity between a new query and stored ones. Token-level eviction has a far richer signal on hand: the actual key and value vectors, plus the attention pattern accumulated so far. That richer signal is what gives a learned policy room to pull ahead, and it's the reason a fixed heuristic should be treated as a starting point here, not an endpoint.

How the memory hierarchy interacts with policy choice: eviction destination matters as much as eviction order

Every eviction decision has two parts: what gets dropped, and where it lands. The second part gets less attention than it deserves, and the bandwidth numbers make that neglect hard to defend. HBM moves data at terabytes per second. PCIe 5.0 tops out around 64 GB/s. A 50 GB KV cache transfer takes roughly 15 milliseconds out of HBM, and roughly 800 milliseconds out of CPU DRAM, a 53x gap between two "eviction targets" that a scoring policy might otherwise treat as interchangeable.

That gap is why production systems build a three-tier hierarchy instead of a flat cache. HBM holds active KV data. CPU memory holds idle-session offload, recoverable over PCIe 5.0 at 64 GB/s. NVMe (Gen5) sits underneath for sessions accessed rarely enough that even a PCIe round trip isn't worth reserving DRAM for. An eviction policy can score tokens with perfect precision and still waste most of the available performance if it sends everything to the same tier regardless of how soon it's likely to come back into use. The policy decides the order. The hierarchy sets the price of getting that order wrong, and the two need to be designed together from the start, never bolted on as an afterthought once the scoring logic is already locked in.