Prefix Eviction: Why LRU Is Already Nearly Optimal For LLM Prefix Caching

A September 2026 paper delivers one of the healthiest negative results systems research produces: four decades of cache-replacement sophistication, evaluated honestly on production LLM serving traces, barely moves the needle over Least Recently Used¹. When Fancy Eviction Fails: Rethinking Cache Replacement For LLM Prefix Reuse (Liu, Yu and Yang, Harvard University, arXiv:2609.28870, cs.DC, submitted September 24, 2026) studies production traces from two public LLM inference services — one dominated by agentic traffic, one a broader mix — and evaluates 14 eviction algorithms across both HBM-constrained (24–120 GiB per accelerator) and large memory-pool (0.25–12 TiB) settings. The finding: despite a large remaining gap to Belady's offline optimum, none of the state-of-the-art algorithms improves over LRU at any measured capacity, and frequency-based policies don't just fail to help — they collapse¹. The offline ceiling that defines "headroom" here is Belady's 1966 optimum, reachable only by an algorithm that has already seen the future².

The explanation is structural, not accidental. Prefix-cache reuse is dominated by the regular pacing of active sessions: a conversation or agent loop re-sends its accumulated context turn after turn, at a steady per-session cadence. That makes recency unusually predictive — precisely the signal class the modern algorithm zoo (frequency sketches, fitted analytic models, learned rankers) was built to move beyond. The workload class those sophisticated recency-agnostic policies were designed against — long-lived objects drawn from persistent global pools with popularity-correlated inter-arrival — essentially does not exist in prefix serving¹.

But the paper is not an advertisement for complacency. Prefix caching introduces genuinely new hard parts that hit ratio cannot see: miss costs that grow with token depth (because attention against a long cached context costs real FLOPs), and session footprints so heavy-tailed that the top 10% of sessions hoard 76.2% of all KV bytes¹. For those, the authors construct a compute-savings ratio, two offline oracles (an exact ILP optimum and an efficient approximation they call BeladyCompute), and four surgical fixes layered on top of recency rather than replacing it¹.

This guide reproduces the core finding in a runnable session-paced simulation, works the compute-savings arithmetic where misses stop being uniform, demonstrates why oracle headroom can be large and unrealizable at the same time, and then prices the honest limits — because a negative result this clean invites exactly the over-generalization it argues against.

1. The setup: two organizations, fourteen algorithms, one boring winner

The production data¹:

• FreeInference Trace — heavily agentic, 327.5 K requests over 7.0 days, 34.3% of them in multi-turn sessions, 10.5 B tokens processed, 0.63 B unique, average request 32.0 K tokens.
• Chutes Trace — a broader mix of human multi-turn conversations, agentic sessions and single-shot API calls, 515.8 K requests over 130.9 days, 26.1% multi-turn, 9.7 B tokens processed, 2.23 B unique, average request 18.7 K tokens.

All evaluation uses a 16-token block granularity and the Qwen3-Coder-30B tokenizer, capped at its 256K-token context window (4.3% of requests skipped in FreeInference Trace, 0.03% in Chutes Trace). Replay runs on a custom C++ simulator built on libCacheSim that models the request-level residency constraints real engines impose — an incoming request's prefix is admitted only when space exists for it — and matches native vLLM hit ratios closely at up to 160x the evaluation speed¹.

The paper studies both deployment shapes of modern prefix caching³ — per-replica HBM and the disaggregated memory pool. The fourteen online algorithms, grouped by design principle¹:

• Recency (baseline): LRU.
• Quick demotion: ARC, Sieve, S3-FIFO, S4-FIFO, LIRS.
• Analytic modeling: LHD.
• Frequency: LFU, W-TinyLFU.
• Learned: LeCaR, LRB, 3LCache.
• Prefix-specific: Workload-aware, AsymCache.

Plus Belady's optimum as the offline ceiling. The result is three behavioral groups. First, the large majority — ARC, LHD, LeCaR, 3LCache, LRB, Workload-aware, AsymCache — perform very similar to or slightly worse than LRU: sophisticated designs that merely reproduce the baseline. Second, the quick-demotion family (S3-FIFO, S4-FIFO, Sieve, LIRS) is highly trace-dependent: marginal gains on some workloads, regressions of several points on others. Third, LFU and W-TinyLFU collapse outright, trailing far behind¹. Meanwhile Belady's oracle sits far above the best online algorithm: there is real headroom, and no current "fancy" mechanism reaches it.

The paper also extends the comparison to six external workloads — four Qwen Bailian traces plus AgentX — and the recency conclusion is stable; only the capacity at which LRU pulls even is workload-dependent. On Qwen To-B, for instance, S3-FIFO and ARC reach 0.491 at 24 GiB against LRU's 0.403, but LRU catches up by 1 TiB, on every trace, within 0.4 points of the best online algorithm¹.

2. Why recency wins: session pacing

The paper's workload characterization is the intellectual core. Prefix blocks are not objects drawn from a persistent pool; they accumulate dynamically through conversations and tool executions, and that changes everything. Five measured properties on FreeInference Trace¹:

• Lifetime is short and session-bounded. One-hit objects make up 53.0%–55.7% of blocks across all three compared workloads (prefix cache, web, block). Multi-turn sessions are short-lived — median 55 s, 90th percentile 14 minutes, 99th percentile roughly 4 hours. The cache has no persistent core: adjacent time windows share over 30% of their objects, but overlap decays to near zero past a two-hour gap.
• Reuse intervals are short with low variance. The median intra-session gap is 8.2 s, and 99.7% of gaps fall under a 22-minute reuse window. The tails exist (99th percentile 1,000 s for system prompts, 562 s for multi-turn history, days in the extreme) but the overwhelming mass of reuse is immediate.
• Frequency tracks session progress, not popularity. Multi-turn blocks make up 37.6% of distinct blocks but generate 70.2% of all accesses; single-turn prompts are 57.8% of unique blocks yet only 11.4% of accesses, with 84.9% never touched again. Crucially, the reuse interval is flat across frequency bins — accesses arrive at the stable, sequential pace of their session, so accumulated frequency says almost nothing about when a block will be needed next.
• Miss costs are position-dependent. Two requests both computing 8K tokens: the second must also attend to 64K cached tokens in front of them; measured TTFT goes from 166 ms to 966 ms and compute from 71.1 to 493.3 TFLOP.
• Session footprints are heavy-tailed. The top 10% of sessions hold 76.2% of all KV bytes; the top 1% alone hold 20.3%.

Recency wins not because LRU is clever but because the workload hands it the answer: within a session, the next access to a block comes right after the last one; across sessions, dead sessions release their blocks and stop defending them. Frequency carries a seductive signal — high counts mark active sessions — but that activity is already visible in recency, which is why frequency-based ranking fails while frequency-as-admission-filter can still help (Section 6)¹.

3. Cell 1: the finding in sixty lines

The simulation below builds the structural situation from scratch: 150 sessions, each re-sending its growing prefix at a regular per-session pace, plus shared system-prompt blocks. It replays the same access stream through LRU, pure LFU (the quintessential recency-agnostic policy), and Belady's optimum. Because the workload's reuse is concentrated by session pacing, LRU wins where the frequency oracle cannot, at every measured capacity (standard library only, seed fixed):

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Session-paced prefix-reuse workload:
#   * a small set of shared system-prompt blocks (hit by every request)
#   * N sessions whose turns arrive at a REGULAR per-session pace
#   * each turn re-touches the whole accumulated prefix and appends new blocks
S_SYS = 30                            # shared system-prompt blocks
accesses = []                         # (time, block_id)
 
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)          # regular turn gap (seconds)
    onehit = random.random() < 0.45             # single-turn session
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 30)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])           # new blocks per turn
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth = S_SYS + turn * grow             # prefix length at this turn
        for b in range(depth):
            accesses.append((t, b if b < S_SYS else sess * 100000 + (b - S_SYS)))
accesses.sort(key=lambda a: a[0])
print("accesses:", len(accesses))
 
def replay_lru(cap):
    cache = OrderedDict(); hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cache:
            hits += 1; cache.move_to_end(b)
        else:
            if len(cache) >= cap:
                cache.popitem(last=False)       # evict least recently used
            cache[b] = t
    return hits / total
 
def replay_lfu(cap):
    # pure LFU with lazy min-heap: evict the least frequently used block
    cnt = {}; heap = []; seq = 0; hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cnt:
            hits += 1; cnt[b] += 1; seq += 1
            heapq.heappush(heap, (cnt[b], seq, b))
        else:
            if len(cnt) >= cap:
                while heap:                      # skip stale heap entries
                    c, _, v = heapq.heappop(heap)
                    if v in cnt and cnt[v] == c:
                        del cnt[v]; break
            cnt[b] = 1; seq += 1
            heapq.heappush(heap, (1, seq, b))
    return hits / total
 
def replay_belady(cap):
    # offline optimum: evict the block whose NEXT access is farthest away
    fut = defaultdict(list)
    for i, (t, b) in enumerate(accesses):
        fut[b].append(i)
    ptr = defaultdict(int)                       # accesses seen per block
    cache = set(); heap = []; hits = total = 0
    INF = 10**9
    for i, (t, b) in enumerate(accesses):
        total += 1
        if b in cache:
            hits += 1
        else:
            if len(cache) >= cap:
                while heap:                      # max-heap (negated key)
                    nkey, pid, v = heapq.heappop(heap)
                    if v in cache and pid == ptr[v]:
                        cache.remove(v); break
            cache.add(b)
        ptr[b] += 1
        na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
        heapq.heappush(heap, (-na, ptr[b], b))
    return hits / total
 
print()
print("capacity |   LRU     LFU   BELADY")
for cap in (600, 1500, 6000):
    print(f"{cap:8d} | {replay_lru(cap):.3f}  {replay_lfu(cap):.3f}  {replay_belady(cap):.3f}")

Output from a real run (Python 3, seed 20260925):

accesses: 129708
 
capacity |   LRU     LFU   BELADY
     600 | 0.576  0.164  0.754
    1500 | 0.827  0.195  0.844
    6000 | 0.845  0.369  0.845

Every signature of the paper's Figure 2 reproduces. LFU — the policy family the traditional-cache literature treats as the honest alternative to LRU — is not merely beaten, it collapses (0.164–0.369 against LRU's 0.576–0.845), because it keeps one-hit-heavy and dead-frequency blocks resident while evicting precisely the recently-touched blocks of pacing sessions that are about to return. LRU tracks the offline ceiling closely, and at 6,000 blocks capacity the gap to Belady has closed to 0.000 — the paper measures the same convergence, with LRU within 0.4 points of the best online algorithm by 1 TiB on every trace. Note also that the shape of the LRU–Belady gap matches the traces: widest where capacity is tight, structurally shrinking as capacity grows and the working set fits.

This toy deliberately omits real complications — sequence length caps, engine admission constraints, cross-session sharing of block content — which is why the LRU/LFU contrast here is sharper than the production traces'. The direction is the point, not the magnitudes.

4. Hit ratio is the wrong currency: the compute-savings ratio

The paper's first constructive contribution fixes a metric problem. Two policies with the same hit ratio can incur wildly different prefill cost, because recomputing a block deep in a prompt is more expensive than recomputing one near the start — every uncached token attends to all cached tokens before it, so a block's recompute cost grows with its depth in full-attention layers¹.

The fix: the compute-savings ratio, which weights each cache hit by the computational cost it avoids. Under this framing, the traditional hit ratio is exactly the special case of a constant cost model in which every block has the same cost. The paper instantiates the cost model two ways: a measured profile of FLOPs per block on Qwen3-Coder-30B, and an idealized linear model (Appendix C) in which a block's recompute cost is proportional to its depth — the limit where full attention strictly dominates. Every conclusion holds under both, with slightly wider margins under the linear one because its per-block cost spread is larger¹.

The consequence of depth-dependent cost is straightforward arithmetic. Under the linear model a block at depth d costs roughly proportional to (d + constant). Blocks near the prompt start are cheap to recompute; blocks at depth 4,096 cost on the order of 250x more. A cache policy that evicts a shallow block to protect a deep one buys the same hit count with far more saved compute. The two offline oracles make this precise¹:

• Oracle 1 (ILP optimum): the caching process as an Integer Linear Program, reuse intervals as variables, capacity as the constraint — an exact but computationally expensive offline bound on the compute-savings ratio.
• Oracle 2 (BeladyCompute): the efficient approximation, inspired by BeladySize. For each block i it scores Score(i) = ComputeIntensity(i) × TimeUntilNextAccess(i) and evicts the highest-scoring block. It tracks the ILP optimum closely on the FreeInference Trace — 1.03 points below it at 24 GiB, 0.41 points at 48 GiB, 0.08 points at 96 GiB.

The online counterpart the paper builds on this insight is RandomCompute: randomly sample a subset of cached blocks and evict the one with the lowest ComputeIntensity divided by TimeSinceLastAccess — cheap, shallow, long-idle blocks go first. On the FreeInference Trace at a constrained 24 GiB under the measured Qwen3-Coder-30B cost model, RandomCompute achieves a 0.638 compute-savings ratio, 10.4 points above LRU and 2.9 points above the hit-optimal Belady oracle — it deliberately sacrifices hit count to save more expensive compute¹. Under the linear model the margins widen to 12.2 points over LRU, and the two offline oracles separate the same way: BeladyCompute reaches 0.745 against standard Belady's 0.599¹.

The next cell reproduces the metric mechanics on the session-paced workload from Section 3, with depths attached and the linear cost model, ending with the per-block cost asymmetry table:

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Same session-paced workload as cell 1, but each block carries its depth
# (position in the prompt), which sets its recompute cost.
S_SYS = 30
requests = []                                   # (t, [(block, depth), ...])
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)
    onehit = random.random() < 0.45
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 40)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth_total = S_SYS + turn * grow
        requests.append((t, [(b if b < S_SYS else sess * 100000 + (b - S_SYS), b)
                              for b in range(depth_total)]))
requests.sort(key=lambda r: r[0])
 
# Linear miss-cost model (paper Appendix C): recomputing a block costs
# compute proportional to its depth -- every uncached token attends to all
# cached tokens before it. Hit ratio is the special case cost == const.
def cost(depth):
    return depth + 16                           # abstract FLOP units per block
 
flat = [(t, b) for t, bl in requests for b, d in bl]
fut = defaultdict(list)
for i, (t, b) in enumerate(flat):
    fut[b].append(i)
INF = 10**9
 
def replay(cap, policy):
    cache = set(); heap = []
    lru_l = OrderedDict()                       # block -> (depth, last time)
    ptr = defaultdict(int)
    hits = total = 0; recompute = 0.0; nocache = 0.0
    for t, bl in requests:
        for b, d in bl:                         # account + admit
            total += 1
            nocache += cost(d)
            if b in cache:
                hits += 1
            else:
                recompute += cost(d)
                if len(cache) >= cap:
                    if policy == "lru":
                        victim = next(iter(lru_l)); del lru_l[victim]
                    elif policy == "randomcompute":
                        # RandomCompute (paper Sec. 5.2): sample, evict the
                        # block with the LOWEST ComputeIntensity/TimeSinceAccess
                        sample = random.sample(list(lru_l), min(16, len(lru_l)))
                        scored = [(cost(lru_l[v][0]) / max(t - lru_l[v][1], 1e-9), v)
                                  for v in sample]
                        victim = min(scored)[1]; del lru_l[victim]
                    else:                       # offline oracles (lazy max-heap)
                        victim = None
                        while heap:
                            key, pid, v = heapq.heappop(heap)
                            if v in cache and pid == ptr[v]:
                                victim = v; break
                        if victim is None:
                            victim = next(iter(lru_l))
                        del lru_l[victim]
                    cache.remove(victim)
                cache.add(b)
            lru_l[b] = (d, t); lru_l.move_to_end(b)
        for b, d in bl:                         # refresh oracle bookkeeping
            ptr[b] += 1
            na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
            if policy == "belady":              # evict max TimeUntilNextAccess
                heapq.heappush(heap, (-na, ptr[b], b))
            elif policy == "beladycompute":     # evict max Cost x TimeUntilNext
                heapq.heappush(heap, (-cost(d) * na, ptr[b], b))
    return hits, total, recompute, nocache
 
def run(cap, policy):
    h, tot, rc, nc = replay(cap, policy)
    return h / tot, 1 - rc / nc
 
CAP = 700
print("capacity", CAP, "blocks | linear cost model (block cost = depth + 16 units)")
print("policy            |  hit ratio   compute-savings ratio")
for name, pol in (("LRU", "lru"),
                  ("RandomCompute", "randomcompute"),
                  ("Belady (hit-opt)", "belady"),
                  ("BeladyCompute", "beladycompute")):
    hr, csr = run(CAP, pol)
    print(f"{name:17s} |   {hr:.3f}          {csr:.3f}")
 
print()
print("block recompute cost vs depth (linear model):")
for d in (0, 256, 1024, 4096):
    print(f"  depth {d:5d}: {cost(d):6.0f} units  ({cost(d) / cost(0):4.0f}x depth-0 block)")

Output from a real run (Python 3, seed 20260925):

capacity 700 blocks | linear cost model (block cost = depth + 16 units)
policy            |  hit ratio   compute-savings ratio
LRU               |   0.566          0.312
RandomCompute     |   0.586          0.343
Belady (hit-opt)  |   0.652          0.388
BeladyCompute     |   0.644          0.375
 
block recompute cost vs depth (linear model):
  depth     0:     16 units  (   1x depth-0 block)
  depth   256:    272 units  (  17x depth-0 block)
  depth  1024:   1040 units  (  65x depth-0 block)
  depth  4096:   4112 units  ( 257x depth-0 block)

Three readings. First, the currency gap: with depths this small (the toy's prompts top out around 1,200 blocks), the compute-savings ratio already sits substantially below hit ratio everywhere — the misses that survive are disproportionately the deep, expensive ones, because there are so many more shallow blocks competing for the same capacity. On the production traces, with requests averaging 32 K tokens and reaching 256 K, this decorrelation is the paper's motivation for the metric, not a footnote.

Second, RandomCompute beats LRU on both currencies here (+2.0 points hit, +3.1 points compute-savings) — the same direction as the paper's +10.4/+12.2-point production margins, tempered by the toy's shallow depths and short horizons.

Third, an honest observation the production numbers don't show as bluntly: in this toy the two oracles nearly coincide (0.388 vs 0.375). With session pacing making reuse timing so regular, most blocks' TimeUntilNextAccess is already proportional to their next-turn gap, and depth and recency correlate — so multiplying cost into the oracle score buys little extra. The paper's production separation between the two oracles is much wider (12.6 points under the measured model, 14.6 under the linear one at 24 GiB), because real traces mix cheap one-hit traffic with 100-K-token agent contexts in a way this 150-session toy compresses away. The lesson is the same in both: which oracle you measure against changes what "headroom" means, and the compute-aware oracle is the one that prices decisions in the currency that actually buys FLOPs.

5. The Belady gap is real and mostly unusable

The weakest reading of this paper would be "tune harder; Belady shows 18 more points are available." The paper's own data argues the opposite, and the simulation below makes the mechanism explicit: it gives Belady a bounded lookahead window — an offline oracle that knows the future only N accesses ahead, which is the only future any online policy could ever approximate knowing — and measures how much of the full-information headroom survives.

import random
from collections import OrderedDict, defaultdict
import heapq
 
random.seed(20260925)
 
# Same session-paced workload as cell 1 (identical seed -> identical stream).
S_SYS = 30
accesses = []
for s in range(150):
    sess = 1000 + s
    pacing = random.uniform(6.0, 12.0)
    onehit = random.random() < 0.45
    turns = 1 if onehit else min(2 + int(random.expovariate(1/6)), 30)
    t0 = random.uniform(0, 3600)
    grow = random.choice([24, 32, 40])
    for turn in range(1, turns + 1):
        t = t0 + turn * pacing + random.gauss(0, pacing * 0.05)
        depth = S_SYS + turn * grow
        for b in range(depth):
            accesses.append((t, b if b < S_SYS else sess * 100000 + (b - S_SYS)))
accesses.sort(key=lambda a: a[0])
 
fut = defaultdict(list)
for i, (t, b) in enumerate(accesses):
    fut[b].append(i)
INF = 10**9
 
def replay_lru(cap):
    cache = OrderedDict(); hits = total = 0
    for t, b in accesses:
        total += 1
        if b in cache:
            hits += 1; cache.move_to_end(b)
        else:
            if len(cache) >= cap:
                cache.popitem(last=False)
            cache[b] = t
    return hits / total
 
def replay_belady_limited(cap, horizon):
    """Belady restricted to a lookahead window of `horizon` accesses. Blocks
    whose next access lies beyond the window are indistinguishable, so the
    oracle degrades toward FIFO among them."""
    ptr = defaultdict(int)
    cache = set(); heap = []; hits = total = 0
    for i, (t, b) in enumerate(accesses):
        total += 1
        if b in cache:
            hits += 1
        else:
            if len(cache) >= cap:
                while True:
                    key, pid, v = heapq.heappop(heap)
                    if v in cache and pid == ptr[v]:
                        cache.remove(v); break
            cache.add(b)
        ptr[b] += 1
        na = fut[b][ptr[b]] if ptr[b] < len(fut[b]) else INF
        if na - i > horizon and na != INF:      # beyond the window
            na = INF
        heapq.heappush(heap, (-na, ptr[b], b))
    return hits / total
 
CAP = 600
lru = replay_lru(CAP)
print(f"capacity {CAP} blocks -- Belady headroom vs usable lookahead")
print()
print(f"{'policy':28s} hit ratio   gap to LRU (pts)")
print(f"{'LRU':28s}   {lru:.3f}          -")
for h, name in ((INF, "Belady (full future)"), (20000, "Belady, 20k-access window"),
                (5000, "Belady, 5k-access window"), (1000, "Belady, 1k-access window"),
                (250, "Belady, 250-access window")):
    hr = replay_belady_limited(CAP, h)
    print(f"{name:28s}   {hr:.3f}        {(hr - lru) * 100:+5.1f}")

Output from a real run (Python 3, seed 20260925):

capacity 600 blocks -- Belady headroom vs usable lookahead
 
policy                       hit ratio   gap to LRU (pts)
LRU                            0.576          -
Belady (full future)           0.754        +17.9
Belady, 20k-access window      0.754        +17.9
Belady, 5k-access window       0.754        +17.9
Belady, 1k-access window       0.742        +16.7
Belady, 250-access window      0.427        -14.9

The full-information oracle leads LRU by 17.9 points — a large, honest gap that matches the paper's observation that Belady sits far above the best online algorithm. But the headroom is front-loaded into perfect knowledge of the far future: windows of 5,000 and even 20,000 accesses recover all of it, and any oracle that knows enough future to matter needs the entire trace. Real prediction cannot get there — the learned policies in the paper's own evaluation (LeCaR, LRB, 3LCache), which approximate exactly this kind of limited lookahead, land at LRU's level or below. The 250-access window is the instructive failure: told only the near future, the "oracle" does worse than LRU, because within a short window the far-future blocks are indistinguishable and the eviction among them degenerates to FIFO, which is blind to the session-pacing signal LRU exploits for free. The gap is real, algorithmically reachable headroom is essentially zero, and the paper's conclusion is precisely that the exploitable part of the gap has already been harvested — by recency plus a few surgical additions.

6. The four surgical fixes

The paper's design response is deliberately not a new monolithic policy. It keeps recency as the foundation — LRU as "bedrock," robust at minimal metadata cost — and adds four targeted techniques for the failure modes the workload characterization actually exhibits¹:

• Quick demotion, conditionally. When one-hit prompts form an overwhelming volume of traffic, they can flood the admission path before their no-reuse fate is known. An early frequency filter (S3-FIFO-style) fixes the Qwen To-B case: at 24 GiB, S3-FIFO reaches 0.491 against LRU's 0.403⁴. But one-hit prompts are shallow and short, so they occupy little footprint — quick demotion only pays when their traffic volume is extreme, and the paper is explicit that it is a conditional add-on, not a default.
• Compute-aware eviction with partial nodes. Weight victims by recompute cost (RandomCompute's sampled ComputeIntensity over TimeSinceLastAccess) to spend capacity on expensive deep blocks. The catch is fragmentation: evicting scattered blocks leaves "holes" — contiguous runs a request must recompute — averaging 9.21 holes per request, which breaks attention-matrix parallelism and makes plain RandomCompute worse than LRU end-to-end (4.0x higher TTFT, 3.9x lower throughput). The fix is evicting partial nodes/contiguous segments instead of lone blocks: the same recompute volume (258.0 M vs 257.9 M blocks) packed into 8.7 times fewer, 8.7-times-longer holes, restoring the gains — on an H200 at 48 GiB replaying 10,000 requests, average TTFT drops from 1.29 s to 1.04 s and throughput rises from 55 to 66 K tok/s relative to LRU.
• Capacity-dependent eviction granularity. In constrained HBM, block-level management avoids destructive all-or-nothing choices on the heavy-tailed sessions (top 10% hold 76.2% of KV bytes — evicting whole sessions wastes the reusable part). In a large pool, session-level eviction slashes metadata overhead with little efficiency loss once capacity is ample.
• Recency as the base for all of it. None of these replaces LRU; they are admission filters and victim-weighting layers on a recency-ordered cache, precisely because Section 3's negative result shows the ordering signal itself is already right.

7. Anti-hype: what this result does and does not establish

LRU near-optimality is a property of these workloads, not of caches. The finding holds for prefix reuse paced by active sessions. It is not general cache advice: on the paper's own comparison workloads from web CDN and block-storage domains, the classical sophisticated policies exist because popularity and inter-arrival structure there genuinely diverge from recency. If your workload has persistent hot objects and bursty independent requesters, this paper's negative result tells you nothing except that you are not in its regime.

The traces are two specific deployments. "Two organizations" means two public LLM inference services with distinct mixes (agentic-heavy vs conversational-agentic-API), validated against six external workloads — a strong but bounded sample. A trace where reuse is not session-paced (massively shared system prompts across sessions, heavy cross-user template reuse, single-shot document search) would sit outside the characterized regime; the paper measured one such boundary itself (Qwen To-B, where quick demotion beats plain LRU by 8.8 points at 24 GiB). Generalization beyond prefix-cache serving — to KV offload policy, weight caching, anything without session pacing — is not established.

The compute-savings ratio assumes the miss-cost model. Both instantiations (measured Qwen3-Coder-30B FLOPs per block; linear depth-proportional) are cost models, and the paper says so: sliding-window attention caps cost growth with depth, hybrid and GQA/MQA/MLA designs and KV quantization and cross-layer sharing all change the recomputation cost and require recalibrating the model before the compute-aware machinery transfers. In the sliding-window limit, cost approaches constant per block and the compute-savings ratio collapses back toward hit ratio — the sophisticated objective pays exactly in proportion to how full-attention-dominated your model and context lengths are.

Full text over abstract. One abstract-level claim deserves sharpening: "quick demotion for one-hit prefixes" reads like a general recommendation, but the full text wins — the paper shows it pays only under extreme one-hit traffic volume and can regress to 10.1 points below LRU on other workloads (LIRS on Qwen To-C at 724 GB), and the headline design is its conditional, workload-triggered use.

8. Verdict

The durable contribution here is a boundary, drawn with production data: the sophisticated-eviction research program, as applied to session-paced prefix reuse, has no more headroom worth chasing, because the hard part of the workload — predicting when a session's blocks return — is answered by the sessions themselves. What remains hard is different, and the paper names it: misses cost wildly different amounts of compute, sessions consume wildly unequal capacity, and the right granularity depends on how much memory you have. Its constructive program follows — a compute-weighted metric with two offline oracles as diagnostics, and four surgical recency-preserving fixes whose value is demonstrated per-failure-mode rather than as a monolithic winner.

For practitioners the checklist is short. Serve agentic or conversational traffic with session-paced reuse: ship LRU first, measure, and add only what your measurement shows missing — a demotion queue if one-hit traffic floods you, compute-aware victim weighting if your long contexts make deep blocks expensive, block-granular eviction if memory is tight. Serve something else: know that every claim above was verified in a regime you may not be in. And when a vendor claims their learned eviction policy leverages "just like Belady's headroom," ask which part of this paper's oracle decomposition they believe they can reach — the paper's evidence is that the online-reachable part of that gap has already been cashed by a 1966 algorithm.

Footnotes