KV-Cache Eviction as an Online Caching Problem: Competitive Analysis and a New Policy

1. Introduction

A transformer that generates text keeps a running memory of everything it has read. For each past token it stores a key vector and a value vector at every layer, and at each new decoding step it attends over all of those stored pairs to decide what to write next ^[19]. This store, the key-value cache, is what lets generation stay linear in sequence length rather than quadratic, and it is also the single largest consumer of memory in a modern serving deployment. Its size grows with the product of sequence length and batch size, and at long context it dwarfs the model weights themselves. The vLLM authors measured that before careful memory management, production serving stacks wasted sixty to eighty percent of their key-value memory to fragmentation and over-reservation, and that virtual-memory-style paging cut that waste below four percent ^[1], a number confirmed in the system's public write-up ^[2]. Paging packs the cache more tightly. It does not make the cache smaller. When the context is long enough that even a perfectly packed cache exceeds the memory you have, or when you want to raise the batch size to serve more users on the same hardware, the only remaining lever is to store fewer tokens: to evict.

Eviction is now a crowded field. Heavy-Hitter Oracle keeps the roughly twenty percent of tokens that accumulate the most attention and reports up to a twenty-nine times throughput improvement over contemporary inference systems at that budget ^[5]. StreamingLLM keeps a small window of recent tokens plus a handful of initial attention-sink tokens and streams over four million tokens on a fixed budget, up to twenty-two times faster than sliding-window recomputation ^[6]. Scissorhands keeps the tokens that a persistence-of-importance hypothesis marks as durably pivotal and cuts key-value memory by up to five times ^[7]. FastGen profiles each attention head and assigns it one of several eviction strategies ^[8]; SnapKV clusters the positions a prompt will need and reports a 3.6 times generation speedup and 8.2 times better memory efficiency at sixteen-thousand-token inputs ^[9]; TOVA drops tokens by attention and reports up to eighty-eight percent memory reduction with a 4.8 times throughput gain ^[10]; and PyramidKV allocates more budget to lower layers than upper ones, matching full-cache quality at twelve percent of the cache ^[11]. These are real systems with real gains, and they share a structure the papers rarely name: each decides, online, under a budget, which items to keep in a small fast memory and which to drop.

That structure is the oldest studied problem in online algorithms. Belady defined the optimal offline cache replacement rule, evict the item whose next use is furthest in the future, in 1966 ^[4]. Sleator and Tarjan introduced competitive analysis in 1985, proving that least-recently-used and first-in-first-out are k-competitive for paging, where k is the number of slots in fast memory, and that no deterministic online policy can do better ^[3]. The randomized side was settled soon after: a simple marking algorithm is 2H_k-competitive ^[12] and the optimal randomized ratio is the harmonic number H_k, which is about the natural logarithm of k ^[13]. When items carry unequal costs, the problem becomes weighted caching, and Young's Landlord algorithm, a generalization of Greedy-Dual that itself generalizes least-recently-used, is k over k minus h plus one competitive, the best any deterministic policy can be ^[14]. None of this theory appears in the key-value eviction literature. The eviction papers were written by a different community, and they reinvented recency, importance, and hybrid policies from first principles, arriving at designs that the caching literature could have told them were, and were not, safe.

The stakes of getting eviction right are not academic. The key-value cache is the resource that decides how many users a serving cluster can hold at once and how long a context each can have, so the eviction policy sits directly on the cost and the capability of a deployment. An eviction policy that quietly discards a token the model needs does not crash; it returns a slightly worse answer, and the degradation is invisible until it is not, which is exactly the profile of a failure that ships to production and surfaces only under a distribution the benchmark did not contain. A policy with a worst-case guarantee cannot be driven into that failure; a policy without one can, and the difference is not visible on the average case the benchmarks measure. The reason competitive analysis was invented in the first place was to certify exactly this kind of robustness for exactly this kind of online decision, and its absence from the eviction literature means the field has been choosing among policies on the average case while blind to the tail, in a setting where the tail is where the expensive, hard-to-reproduce failures live.

This paper connects the two. Our thesis is that key-value eviction is a caching problem in the precise technical sense, that the classical guarantees and impossibility results transfer once the cost model is stated carefully, and that doing so both explains why the deployed heuristics work and exposes a latent failure mode in the most cited of them. We make five contributions.

First, a reduction with a caveat (Section 3). We show that under a recompute cost model, where an evicted key-value pair can be reconstructed on demand at a cost that grows with its position, key-value eviction is exactly an instance of weighted caching. We are equally precise about why the reduction is not free: classical caching forces a missed item into the cache, whereas attention merely renormalizes over what remains, so we also define a no-refetch model in which eviction is permanent and a step's cost is the attention mass on absent tokens.

Second, transferred bounds (Section 4). Under the recompute model, every current eviction policy inherits the deterministic lower bound of k, and recency-based and Greedy-Dual policies meet it. We carry out the lower-bound argument in the attention setting and give the Landlord potential argument for the upper bound.

Third, a non-competitiveness theorem (Section 5). We prove that the pure accumulated-attention rule, heavy-hitter selection with no recency and no decay, has an unbounded competitive ratio. An adversary makes decoy tokens hoard early attention and a sleeper token collect it later; the undecayed rule keeps the decoys forever and pays without bound. This isolates recency as the load-bearing ingredient and explains why H2O and StreamingLLM both keep a recent-token window.

Fourth, a new policy (Section 6). We propose Greedy-Dual-Attention, an attention-weighted specialization of Landlord that is k-competitive by construction and that collapses to least-recently-used, to StreamingLLM's sink-plus-window, and to a decayed heavy-hitter rule at three settings of one knob. It gives the deployed family a worst-case guarantee it currently lacks, at no change in asymptotic per-step cost.

Fifth, a persistence-regret bound (Section 7). For the realistic no-refetch model we prove that under a formal persistence-of-importance assumption, a recency-plus-heavy-hitter policy has per-step attention-mass regret bounded by the light-tail mass of the attention distribution. This is the bridge from the pessimistic worst case to the optimistic practice: real attention is sparse, so the tail is small, so the same policy family that can fail arbitrarily on adversarial inputs is near-optimal on the inputs language actually produces.

A word on method, because it determines how the claims should be read. This is a theory and synthesis paper. The competitive bounds and the regret bound are proofs we carry out; the throughput and quality figures are analytical models generated from stated formulas, labeled as such in their captions, or replots of published measurements attributed to the studies that made them. We run no experiments and report no measurements of our own, so every empirical number in the paper is cited to a published source and cross-confirmed across independent searches, and the one policy we propose is analyzed rather than benchmarked. Where a claim is conditional on an assumption, as the regret bound is on persistence, we state the assumption and the regime where it fails. This discipline is not incidental to the contribution; the whole point of bringing competitive analysis to eviction is to replace unproven intuitions with proven statements, and it would defeat that purpose to smuggle in unproven empirical claims of our own alongside the proofs.

Section 2 gives the background on both sides. Section 8 discusses what the analysis says that disagrees with common practice. Section 9 states the threats to validity in full, the most important of which is that we run no experiments and that the tightest bounds assume a recompute model most systems do not implement. Section 10 gives the practical implications and Section 11 the open problems. Figure 1 is the map of the reduction.

flowchart TD
  A["Decoding under a<br/>KV memory budget k"] --> B{"Cost model"}
  B -->|"evicted KV can be<br/>recomputed (cost w_i)"| C["Weighted caching"]
  B -->|"eviction is<br/>permanent"| D["Attention-mass<br/>regret minimization"]
  C --> C1["Lower bound: k<br/>(deterministic)"]
  C --> C2["Landlord / Greedy-Dual:<br/>k-competitive"]
  C --> C3["Marking: 2H_k<br/>optimal H_k (rand.)"]
  D --> D1["Belady analog:<br/>keep max future mass"]
  D --> D2["Persistence bound:<br/>regret <= tail mass"]
  C2 --> E["Greedy-Dual-Attention<br/>(this paper)"]
  D2 --> E
  E --> F["Recovers LRU, StreamingLLM,<br/>H2O as special cases"]

2. Background and Related Work

2.1 The key-value cache and why decode is memory-bound

At decoding step $t$, a single-head attention layer forms a query $q_t$ and attends over the cached keys $k_1,\dots ,k_t$ and values $v_1,\dots ,v_t$ stored for all previous positions ^[19]:

The vector $a_{t,\cdot }$ is a probability distribution over the cached positions, the attention distribution, and the output is its expectation of the value vectors. Two facts about Equation 1 drive everything that follows. First, the sum runs over every cached token, so the memory footprint of the cache is what bounds how long a context and how large a batch a device can hold. Second, computing $o_t$ for one new token reads all of $k_i,v_i$ from memory but does only a small amount of arithmetic per byte read. Autoregressive decoding at modest batch size is therefore memory-bandwidth bound: the hardware spends its time streaming cached vectors and model weights, not computing ^[20]. FlashAttention removes the intermediate materialization of the attention matrix but does not change this bandwidth accounting for the cache itself ^[21]. The practical consequence is that shrinking the cache buys throughput almost linearly in the memory-bound regime, which is why eviction is worth so much.

The size of the cache is exact. For a model with $L$ layers, $n_{\mathrm{kv}}$ key-value heads of dimension $d_h$ each, storing keys and values at $b$ bytes per element, the bytes per token are

where $B$ is the batch size and $S$ the sequence length. For a seven-billion-parameter model with thirty-two layers, thirty-two heads, head dimension one hundred twenty-eight, in sixteen-bit precision, Equation 2 gives about half a megabyte per token, so a thirty-two-thousand-token context costs roughly sixteen gigabytes for the cache alone at batch one. Grouped-query attention shrinks $n_{\mathrm{kv}}$, which is why the seventy-billion configuration in Figure 2 is cheaper per token than the thirteen-billion one despite being larger. Figure 2 plots Equation 2 across sequence length for three standard configurations.

The trend of Equation 2 is why eviction has moved from a curiosity to a necessity. Two forces push the cache up: context windows have grown from thousands of tokens to hundreds of thousands, and batch sizes must grow to keep expensive accelerators busy, and the cache scales with the product. The architectural responses so far attack the per-token coefficient $P_{\mathrm{kv}}$ rather than the token count. Grouped-query and multi-query attention cut $n_{\mathrm{kv}}$ by sharing key-value heads across query heads ^[20], and low-bit quantization cuts $b$ ^[23], but both leave the linear-in-$S$ growth intact, so at long enough context the cache dominates again. Eviction is the only lever that attacks the token count $S$ itself, replacing it with a budget $k$ that does not grow with context. That is a qualitatively different kind of saving: the others lower the slope of the line in Figure 2, while eviction caps it at a constant. This is why the caching question, which tokens to keep, is the durable one, and why it deserves the analysis the caching community already built.

2.2 Online caching and competitive analysis

The paging problem is the following. A fast memory holds $k$ pages. Requests for pages arrive one at a time; if the requested page is in fast memory it is served for free, and if it is not, a fault occurs and the page must be brought in, evicting some resident page to make room. The goal is to minimize faults. Belady showed that the offline optimum evicts the page whose next request is furthest in the future ^[4], a rule whose optimality has a short exchange-argument proof ^[18]. Since the future is unknown online, the question Sleator and Tarjan asked was how close an online policy can come to this optimum in the worst case ^[3]. Their answers are the foundation we build on. Least-recently-used, first-in-first-out, and flush-when-full are all $k$-competitive, and no deterministic online policy has a competitive ratio below $k$, the number of cache slots.

Randomization helps, but only logarithmically. The marking algorithm, which marks a page on access and evicts an unmarked page at random when it must fault, is $2H_k$-competitive, where $H_k={\sum }_{i=1}^{k}1/i\approx \ln k$ is the $k$-th harmonic number ^[12], and a more careful randomized policy achieves the optimal ratio $H_k$ ^[13]. Weighted caching generalizes paging by giving each page a cost to fetch. Chrobak, Karloff, Payne, and Vishwanathan showed the deterministic Balance algorithm is $k$-competitive for weighted caching ^[16], and Young's Landlord algorithm achieves the same bound while generalizing least-recently-used and admitting resource augmentation ^[14]. The randomized weighted case is $O(\log k)$ by a primal-dual argument ^[17]. Caching is a special case of the k-server problem, whose competitive theory Manasse, McGeoch, and Sleator launched ^[27]; we will return to the k-server view when we discuss per-head budgets. A compact survey of the paging and caching bounds is Young's encyclopedia entry ^[15], and the standard textbook treatment is Borodin and El-Yaniv ^[28].

It is worth seeing why least-recently-used achieves the ratio $k$, because the proof technique, phase partitioning, is the same tool we use for the persistence bound in Section 7. Partition the request sequence into maximal phases, each a maximal run containing requests to at most $k$ distinct pages. Within a phase, least-recently-used faults at most $k$ times, once per distinct page, because a page it has evicted during the phase was less recently used than $k$ others that have been touched, which cannot happen twice in a window of $k$ distinct pages. Meanwhile the offline optimum must fault at least once per phase boundary, because each new phase introduces a page that, together with the $k$ distinct pages of the previous phase, forms $k+1$ distinct pages that cannot all fit. The ratio of at most $k$ online faults to at least one offline fault per phase is the bound. The lesson that carries over is that locality, few distinct items per phase, is exactly what makes the online cost small, and that a policy is competitive when its per-phase fault count is bounded by the phase's distinct-item count.

The contrast that matters most for this paper is least-frequently-used. Least-frequently-used evicts the item with the smallest access count, and it is the direct classical ancestor of accumulated-attention eviction: both keep whatever has been touched most in the past. It is a textbook result that least-frequently-used is not competitive at all; its competitive ratio is unbounded ^[28]. The adversary loads a few items with a huge early count, then cycles forever through fresh items that never accumulate enough count to be kept, so least-frequently-used clings to the stale heavy items and faults on every request while the optimum faults rarely. This is the same construction we give in Section 5 for accumulated-attention eviction, because it is the same policy in a different vocabulary, and the same fix applies: introduce recency or decay, as the competitive least-recently-or-frequently hybrids do. That paging drew the line between competitive least-recently-used and non-competitive least-frequently-used decades ago is the single most useful fact the eviction literature has been missing.

The single most important structural fact for our purposes is the defining constraint of paging: after a request for page $p$, page $p$ is resident. A miss is not optional. You must fetch the requested page, which is what makes the fault the unit of cost. Whether that constraint holds for attention is the crux of Section 3, and getting it right is what separates an honest reduction from a false one.

2.3 Models of locality: working sets and access graphs

Worst-case competitive analysis is pessimistic by design, and the paging community spent twenty years building refinements that formalize the locality real inputs exhibit, so that the bounds predict what practice sees rather than what an adversary could contrive. Two of those refinements are the direct ancestors of the persistence assumption we use in Section 7, and naming them now lets us place our contribution precisely. Denning's working-set model, from 1968, is the oldest and most influential ^[29]. It defines the working set $W(t,\theta )$ as the set of distinct items referenced in the last $\theta$ steps, and it formalizes the principle of locality: programs concentrate their references on a small, slowly-changing working set rather than spreading them uniformly. A policy that keeps the working set resident thrashes rarely, and the working-set size is the natural budget. This is precisely the shape of the persistence-of-importance hypothesis in the eviction literature, a token that matters now mattered recently, restated for attention, and Section 7 makes that correspondence a theorem.

The access-graph model of Borodin, Irani, Raghavan, and Schieber sharpens locality further ^[28]. It replaces the assumption that any item can follow any other with a graph whose edges encode which references can follow which, so that the adversary is restricted to walks on the graph rather than arbitrary sequences. On a graph with strong locality, a path or a low-bandwidth structure, the achievable competitive ratio falls well below $k$, and the optimal policy can be characterized from the graph. The access-graph program is the template for what a full average-case theory of attention-guided eviction would look like: identify the structure that real attention sequences obey, restrict the adversary to it, and re-derive a smaller ratio. We do not build the full access-graph theory for attention here, and we flag it as the central open problem in Section 11, but our persistence bound is a first result in its spirit: it is a competitive-style guarantee that holds on the structured inputs the model actually produces, not on all inputs.

A third refinement points the other way, toward using predictions rather than restricting inputs. Learning-augmented caching, introduced by Lykouris and Vassilvitskii, gives the online policy a prediction of each item's next request time and asks for a policy that is near-optimal when the prediction is accurate (consistency) and no worse than the classical bound when it is arbitrary (robustness) ^[30]. This is the exact shape of attention-guided eviction, because the attention score is a prediction of future importance, and it is the framework we argue in Section 11 the eviction literature should adopt to make its heuristics safe. The three refinements, working sets, access graphs, and learned advice, are the classical answers to the objection that a competitive ratio of $k$ is too pessimistic to be useful, and each has a direct counterpart in the eviction problem that the eviction literature has approached without the theory.

2.4 Key-value eviction methods

The eviction literature can be organized by what signal it uses to decide importance, and once organized it maps cleanly onto caching primitives. Recency-based methods keep the most recent tokens. StreamingLLM is the clearest example: it keeps a sliding window of recent tokens and, crucially, a few initial tokens it calls attention sinks, which absorb a large and largely content-independent share of attention mass; keeping them stabilizes the distribution and lets the model stream indefinitely ^[6]. In caching terms this is least-recently-used with a small pinned set. Importance-based methods keep the tokens that have received the most attention. H2O accumulates attention scores and keeps the heavy hitters, formulating eviction as a dynamic submodular problem and reporting large throughput gains at a twenty percent budget ^[5]. Scissorhands rests on a persistence of importance hypothesis, that a token pivotal at one step stays pivotal, and keeps a fixed budget of persistently important tokens ^[7]. Keyformer selects key tokens with a score robust to the removal of others ^[22], and Q-Hitter refines the heavy-hitter oracle for joint sparsity and quantization ^[25].

Hybrid and structured methods combine signals or vary the budget across the model. FastGen profiles each attention head during prompt encoding and assigns it one of five strategies, local, special-token, punctuation, frequency, or full, then evicts accordingly, and reports that at fifty percent budget a thirty-billion model beats non-adaptive methods at fifteen percent ^[8]. PyramidKV observes that information funnels from broad lower-layer attention to focused upper-layer attention and allocates more cache to lower layers, matching full quality at twelve percent ^[11]. SnapKV clusters the prompt positions an observation window predicts will matter and compresses to them ^[9]. TOVA frames the decoder as a bounded multi-state recurrent network and drops the lowest-attention state each step ^[10], and NACL combines proxy-token importance with a diversity-preserving random eviction ^[24]. A recent survey catalogs the space and its system integration ^[26]. Two neighboring levers are worth separating from eviction because they are orthogonal to it: paging, which relayouts the cache without dropping tokens ^[1], and quantization, which stores every token in fewer bits, as in KIVI's two-bit keys and values with a reported 2.6 times memory reduction and 3.47 times throughput ^[23]. Figure 3 collects the reported operating points, and the decode-and-evict loop is drawn in Figure 4.

Organized by the caching primitive each rediscovers, the field collapses to a short list. The recency methods are least-recently-used with pinned pages: StreamingLLM's window and sinks ^[6], and the recency component that every hybrid keeps. The importance methods are least-frequently-used with attention mass as the count: H2O ^[5], Scissorhands ^[7], Keyformer ^[22], Q-Hitter ^[25], and TOVA's lowest-attention drop ^[10]. The hybrids are the least-recently-or- frequently-used family that paging built to make importance competitive: H2O's recent-plus-heavy design, NACL's importance-plus-diversity ^[24], and SnapKV's prompt-window-guided selection ^[9]. The structured methods are multi-cache allocation across heads or layers: FastGen's per-head strategies ^[8] and PyramidKV's per-layer budgets ^[11]. Seen this way, the taxonomy is not a list of independent inventions but a rediscovery of the paging design space, with one systematic omission: the competitive analysis that told the paging community which of these designs carry guarantees and which do not. The importance-only methods sit on the non-competitive least-frequently-used branch, the recency and hybrid methods on the competitive least-recently-used branch, and the structured methods raise an allocation question the single-cache theory does not answer. The rest of this paper works out the consequences of that mapping.

flowchart LR
  Q["new query q_t"] --> ATT["attend over cache<br/>(Eq. 1)"]
  CACHE["KV cache<br/>(<= k slots)"] --> ATT
  ATT --> OUT["output token"]
  OUT --> NEWKV["append new K,V"]
  NEWKV --> FULL{"budget<br/>exceeded?"}
  FULL -->|no| CACHE
  FULL -->|yes| EVICT["eviction policy<br/>drops one pair"]
  EVICT --> CACHE

3. The Reduction and Two Cost Models

We now state the correspondence between decoding under a budget and online caching precisely, and we are careful about the one place where the correspondence needs a modeling decision. The items are tokens. Storing token $i$ means holding its key-value pair $(k_i,v_i)$ at every layer; the cache holds at most $k$ tokens, the budget in Equation 2 divided by the per-token size. The request sequence is generated by attention: at decode step $t$ the model places mass $a_{t,i}$ on each token $i\le t$. This is the first divergence from classical paging, where each request names one page. Attention requests all resident tokens at once, with weights. We handle this by letting the cost of a step be determined by the mass on tokens that are not resident, which we define below, and which reduces to the classical fault count in the worst case where all mass sits on a single evicted token.

The second and deeper divergence is the fetch-on-miss constraint. In paging, a requested page that is absent must be fetched, so it becomes resident and you pay a fault. In attention, an absent token is simply excluded from the sum in Equation 1 and the softmax renormalizes over the survivors. Nothing forces the token back. Eviction is a soft, graceful degradation, not a hard fault, which is exactly why H2O and StreamingLLM can drop most of the cache and still produce fluent text. To reason rigorously we split into two cost models, and we keep them separate for the rest of the paper.

The recompute weight $w_i$ is not uniform. Reconstructing token $i$'s key and value requires a forward pass over its prefix, so its cost grows roughly linearly in the position $i$. This is precisely why the RM reduction lands in weighted caching rather than plain paging: later tokens are more expensive to bring back, and a policy that is oblivious to this, evicting a costly late token as readily as a cheap early one, will do worse. Landlord is built for exactly this asymmetry.

A word on why the attention-mass regret of Equation 4 is the right surrogate, and where it is only a surrogate. The output of the attention layer, Equation 1, is linear in the attention weights, so to first order the error introduced by evicting a set of tokens is the displaced mass times the difference between the evicted tokens' values and the renormalized average of the retained ones. When the evicted tokens' values are typical, the first-order error is proportional to the displaced mass, which is exactly Equation 4, and this is the regime the surrogate is built for. The surrogate can understate the cost when an evicted token carries an outlier value the retained tokens cannot reconstruct, and it can overstate the cost when the evicted token's value happens to align with the retained average, in which case the softmax renormalization absorbs the loss almost perfectly. We adopt the mass surrogate because it is the quantity the caching theory can bound and because it is correct to first order, and we flag its two failure directions in Section 9. The alternative, defining cost as the true output perturbation, would be exact but would not reduce to a caching problem, because the cost of an eviction would depend on the values of the other resident tokens, coupling the items in a way weighted caching does not allow. The mass surrogate is the linearization that makes the problem a caching problem, and its accuracy is the accuracy of that linearization.

The renormalization also explains why eviction degrades gracefully where paging faults hard. When a page is missing in a computer, the computation cannot proceed until it is fetched, so the fault is a hard event with a fixed cost. When a token is missing in attention, the softmax simply redistributes its mass over the survivors and the computation proceeds with a slightly wrong answer. This is why an eviction policy can be aggressive in a way a pager cannot: the penalty for a wrong eviction is a small, bounded quality change rather than a stall, and the policy can trade a little accuracy for a large memory saving. It is also why the no-refetch model is the honest default for KV eviction and the recompute model is the exception. Most systems never pay to bring a token back because they never need to; they accept the renormalized answer. The recompute model matters only where a system chooses to reconstruct evicted state, and its value in this paper is that it is the setting where the sharp competitive ratios hold, which is why we prove the competitive theorems there and the regret theorem in the no-refetch model that practice actually runs.

For the no-refetch model we define the objective directly. Let $R_t\subseteq \{1,\dots ,t\}$ be the resident set the policy holds at step $t$, with $|R_t|\le k$. The attention-mass regret of the policy on a decoding run of length $T$ is

Regret is zero when the resident set carries all the mass the model wanted at every step, and it rises as the policy evicts tokens the model then tries to attend to. It is the natural NM analog of the fault count, and Belady's rule has an NM analog too: the offline optimum keeps, at each step, the $k$ tokens that will receive the most future attention mass, the direct translation of furthest-in-future to a weighted setting. We will use Equation 4 as the target of the persistence bound in Section 7. Table in Figure 5 lays out the full dictionary between the two problems, and Figure 6 plots the throughput consequence of shrinking $k$.

The throughput model deserves its own equation because it is what makes the budget worth optimizing. In the memory-bound regime the number of concurrent sequences a device can hold is set by how much cache each consumes, so with free memory $M$ above the weights the maximum batch and the throughput gain from evicting to budget $k$ are

Equation 3 says that halving the retained budget roughly doubles the batch, hence roughly doubles throughput, until batch grows enough to leave the memory-bound regime, a caveat we make quantitative in Section 10. This is the mechanism behind the throughput numbers in Figure 3, and it is why a factor-of-five budget cut (H2O's twenty percent) and a factor-of-eight cut (TOVA's one-eighth) translate into the large gains those papers report ^{[5] [10]}.

4. Competitive Analysis of KV Eviction

With the recompute model in hand, the transfer of the classical bounds is a short argument, and we give it carefully because the conclusion, that every deployed eviction policy is at best $k$-competitive and no cleverness escapes that, is the reason the negative result in Section 5 and the policy in Section 6 matter.

Proof of the lower bound (a). Fix any deterministic online policy $\mathrm{ALG}$ and a universe of $k+1$ tokens, one more than the budget, so at every step exactly one token is absent. Construct the request sequence adversarially: at each step, place all attention mass on the single token $\mathrm{ALG}$ does not currently hold. Because attention can concentrate its mass wherever the input dictates, this is a legal attention pattern, and it forces $\mathrm{ALG}$ to fault, recompute, and evict at every one of the $T$ steps, paying total cost at least $T{w}_{\min }$. Now bound the optimum. On the same sequence, an offline policy applies Belady's rule: on a fault it evicts the token whose next request is furthest in the future. Over any window of $k$ consecutive requests to distinct tokens, Belady faults at most once, because after one eviction the remaining $k$ tokens cover the next $k-1$ requests. Hence $\mathrm{OPT}$ faults at most $T/k$ times, paying at most $(T/k)w_{\max }$. Taking uniform weights $w_{\min }=w_{\max }$ for the cleanest statement, the ratio is at least $k$, which is Equation 6:

This is the attention-setting version of the Sleator-Tarjan bound ^[3]. The only new ingredient is the observation that a softmax can put essentially all its mass on one position, so the adversary of the classical proof is realizable as an attention pattern. Every heavy-hitter, recency, or hybrid policy in Figure 3 is a deterministic online policy, so every one of them is subject to Equation 6. No importance signal repeals it.

The bound is worth reading carefully for what it does and does not say. It does not say that every policy is equally bad; it says that no deterministic policy can guarantee better than a factor of $k$ against an adversary, so the worst-case ratio cannot distinguish among the reasonable policies, which all sit at $k$. It also does not say that the factor $k$ is what you pay on real inputs; the adversary that achieves it is contrived, concentrating all mass on the one absent token at every step, which no real attention pattern does. What the bound does say is decisive at the boundary: a policy that is worse than $k$-competitive, or not competitive at all, has been driven to a regime the reasonable policies escape, and that is the line Theorem 2 shows accumulated-attention eviction crosses. The lower bound is therefore not a ranking tool among good policies but a disqualifier for bad ones, and its role in this paper is exactly that: it certifies the recency-based family as the safe side of a line and sets up the demonstration that pure importance is on the unsafe side.

Proof sketch of the upper bound (b). Young's Landlord algorithm maintains for each resident token a credit $c_i$, initialized to its weight $w_i$ when it is fetched. When space is needed, Landlord computes $\delta ={\min }_{i\in R}{c}_i/{\mathrm{size}}_i$ (with unit sizes, $\delta ={\min }_i{c}_i$), decrements every resident credit by $\delta$, and evicts any token whose credit has reached zero; on a subsequent request to a resident token its credit is reset up to $w_i$. The credit update is Equation 7:

Young's potential-function analysis shows that Landlord is $k/(k-h+1)$-competitive when compared against an offline optimum restricted to a cache of size $h\le k$, and that this is optimal for deterministic online file caching ^[14]. Setting $h=k$ gives the $k$-competitive guarantee, Equation 8:

Because Landlord specializes to least-recently-used when all weights are equal and credits track recency ^[15], part (b) covers both the recency policies (StreamingLLM's window) and the Greedy-Dual policies as instances of one $k$-competitive family. Figure 7 plots the resource-augmentation curve of Equation 8: giving the online policy only a little more budget than the offline comparator collapses the ratio toward one, which is the theoretical statement behind the practical observation that a modest budget increase buys disproportionate quality.

The randomized bound (c). The marking algorithm evicts a uniformly random unmarked token under pressure and is $2H_k$-competitive on the unweighted instance ^[12], with the optimal randomized ratio $H_k$ achievable ^[13]; the weighted randomized case is $O(\log k)$ ^[17]. Equation 9 records the tight unweighted statement,

and the gap between $k$ and $\ln k$ in Figure 8 is the value of randomization: for a budget of two hundred slots the deterministic worst case is two hundred but the randomized worst case is about six. This is a real lever for KV eviction that the literature has not used. A policy that breaks ties among equally-recent tokens at random, rather than by a fixed rule, moves from the deterministic curve toward the randomized one against adversarial or distribution-shifted inputs, at no quality cost on benign ones. We return to this in Section 11.

The marking argument, in the attention setting. The randomized bound is worth unpacking because it is the one place the classical theory offers KV eviction a strictly better worst case than any deployed policy achieves, and the improvement is nearly free. Partition the run into phases as in the least-recently-used proof, each a maximal window touching $k$ distinct tokens. The marking policy marks a token when it is attended above threshold, and when it must evict it chooses uniformly among the unmarked tokens; at a phase boundary all marks reset. Within a phase, the $i$-th newly-attended token that was not resident at the phase start faults, but because the choice of which unmarked token to evict is random, the probability that any particular earlier token has been evicted by the time it is re-attended is only about $1/(k-i+1)$, and summing that harmonic series over the phase gives the $H_k$ factor rather than the deterministic $k$. The randomness denies the adversary the ability to predict which token the policy will drop, and that unpredictability is the whole improvement. For KV eviction the practical translation is exact: when several tokens tie on recency or on decayed importance, do not break the tie by a fixed deterministic rule such as lowest position or oldest index, which an adversary can learn and exploit, but break it at random. The tokens the policy is uncertain about are precisely the ones near the eviction margin, and randomizing there costs nothing on benign traffic while moving the worst case from linear to logarithmic in the budget ^{[12] [13]}.

Why KV eviction is weighted, not plain, caching. It would be tidier if KV eviction reduced to plain paging, where every item costs the same, because then the unweighted bounds would apply directly. It does not, and the reason is the recompute weight. Bringing back token $i$'s key-value pair requires a forward pass over the prefix up to position $i$, so its cost grows with $i$, and a late token can cost an order of magnitude more to reconstruct than an early one. A policy that treats all tokens as equally cheap to lose will evict expensive late tokens too readily and pay for it on the refetch. This is exactly the setting Chrobak, Karloff, Payne, and Vishwanathan built the Balance algorithm for, and that Young's Landlord generalizes: both are $k$-competitive for weighted caching and both reduce to least-recently-used when weights are uniform ^{[16] [14]}. The weighting is not a technicality; it changes which policy is right. A recency-only policy is optimal for plain paging but suboptimal once weights vary, and the correction, credit tokens by their weight and charge rent uniformly, is what Greedy-Dual-Attention in Section 6 inherits. The eviction literature has largely ignored recompute cost because most systems run the no-refetch model where there is no refetch to pay for, but any system that does recompute, and prefix-caching systems do, is in the weighted regime and should use a weighted policy.

What the offline optimum is, for attention. Belady's rule translates cleanly. In the recompute model the offline optimum on a fault evicts the resident token whose next attention above threshold is furthest in the future, exactly furthest-in-future with the request stream defined by the attention pattern. In the no-refetch model the optimum is the weighted analog: at each step keep the $k$ tokens that will receive the most future attention mass, since those are the tokens whose eviction would cost the most regret in Equation 4. Both are offline, both need the future attention pattern, and both are what the competitive ratio and the regret bound measure against. The value of naming them is that they give a concrete target for evaluation: an eviction policy's quality is how close its resident set stays to the future-mass-maximizing set, and that gap, not raw quality on a benchmark, is the quantity the theory predicts and a practitioner can measure with a replay that has the full attention trace in hand.

A worked example. Take a budget of $k=2000$ tokens on a model that produces half a megabyte of cache per token (Section 2.1), serving a context of $S=16000$ tokens. Equation 3 says evicting to the budget lets batch grow by about eightfold in the memory-bound regime, matching the order of the memory-efficiency gains SnapKV reports at sixteen-thousand-token inputs ^[9]. The deterministic competitive ratio for this cache is $k=2000$, a number so large it certifies only that the policy cannot be driven to unbounded cost, not that it is within any small factor of optimal on real traffic. The randomized ratio is $H_{2000}\approx 8.1$, a reminder that randomizing the tie-break tightens the worst case from two thousand to about eight. And the resource-augmentation curve of Equation 8 says that if the online policy is given the full budget while the offline comparator is restricted to half of it, the ratio is about two, so the online policy at budget $k$ is within a small factor of the best any policy could do at budget $k/2$. These three numbers, $k$, $\ln k$, and the augmentation ratio, are the honest summary of what worst-case theory promises for a real KV budget: not a tight bound, but a clear ranking of which structural choices, recency, randomization, a little extra budget, buy how much.

5. Why Attention-Only Eviction Is Not Competitive

The theorems of Section 4 are about policies that use recency or explicit weights. The most cited KV-eviction idea, keep the tokens with the highest accumulated attention, uses neither in its pure form, and we now show that in its pure form it is not competitive at all. We state the result in the no-refetch model, because that is the model deployed systems actually run and because it makes the failure vivid: the policy's regret grows without bound while the optimum's stays at zero.

Construction. Fix budget $k$. Use $k-1$ decoy tokens $d_1,\dots ,d_{k-1}$, one sleeper token $s$, and later a single filler token $x$. The run has two phases. In the priming phase, steps $1$ through $P$, the decoys and the sleeper are all resident (that is $k$ tokens, within budget, so no eviction occurs) and the attention distribution places large mass on the decoys and tiny mass on the sleeper: say each decoy receives mass close to $0.9$ spread across the priming steps and the sleeper receives cumulative mass $\epsilon$. After priming, each decoy has accumulated a large score and the sleeper has accumulated $\epsilon$.

At step $P+1$ the filler token $x$ is produced. The cache is now full at $k+1$ tokens and ACC must evict. It evicts the smallest accumulated score, which is the sleeper $s$ at $\epsilon$. From step $P+2$ onward, for $T$ steps, the adversary places essentially all attention mass on the sleeper: $a_{t,s}\approx 1$. But $s$ has been evicted and, in the no-refetch model, contributes nothing; the softmax renormalizes over the resident decoys and filler, which the model did not want. Each such step incurs regret close to one, so after $T$ steps $\mathcal{R}(\mathrm{ACC})\gtrsim T$. Crucially, because ACC has no decay, the decoys' large accumulated scores never fall, so ACC never reconsiders them: on every future step it would still rather evict the low-scoring sleeper than a decoy, and the sleeper never re-enters. Choosing $T\ge M$ gives Equation 10:

The optimum is trivial: at step $P+1$ it evicts a decoy, which is never attended again, and keeps the sleeper, so it places full mass on the sleeper at every later step and pays zero regret. Figure 9 draws the two attention profiles that drive the construction. The mechanism is entirely the absence of decay: an accumulated score is a statement about the past, the eviction decision is a bet on the future, and without decay the past never stops voting.

Why the deployed systems survive this. The theorem is about pure accumulation, and no shipped system is pure. H2O keeps a component of recent tokens alongside the heavy hitters precisely so that a newly-important token is protected by recency until its accumulated score catches up ^[5]. StreamingLLM is recency-first, keeping a fixed window plus attention sinks, which is why it streams stably over millions of tokens ^[6]. Scissorhands' persistence hypothesis is, read through this lens, an assumption that the adversarial input does not occur: that importance is temporally coherent, so recent importance predicts current importance ^[7]. Theorem 2 does not contradict any of these results. It explains them. It says that the recency component is not a heuristic garnish on top of the heavy-hitter idea; it is the ingredient that carries whatever worst-case safety the policy has, and the heavy-hitter component is a refinement that operates inside the budget recency protects. Remove recency and decay, and the refinement is defenseless.

The recompute-model version. The same construction gives an unbounded competitive ratio in the recompute model with a small change: instead of one sleeper, use a stream of sleeper tokens that are each attended, evicted by ACC, and then re-attended, forcing a recompute each time, while OPT keeps the active sleeper resident by evicting a spent decoy. The undecayed decoy scores again pin ACC to the wrong tokens. We omit the bookkeeping; the no-refetch statement is the one that matches practice and makes the point.

The adversary is not only adversarial. It is tempting to dismiss Theorem 2 because its construction is deliberate, but the construction is a caricature of an event that happens naturally: a topic change. In a long conversation, or a document that shifts subject, the tokens that mattered for the first topic accumulate large scores and then stop being relevant, while the tokens of the new topic start from zero accumulated score. An undecayed accumulation policy is, at exactly that moment, holding the stale high-score tokens of the finished topic and starving the fresh tokens of the current one, which is the decoy-and-sleeper configuration arising without any adversary. The severity is milder than the worst case because real topic changes are not maximally hostile, but the direction is the same, and it predicts a specific, observable failure: accumulation-heavy eviction should degrade most right after a topic boundary, and decay should help most there. That the failure mode has a natural trigger, not only a contrived one, is why the theorem is a practical warning and not only a theoretical curiosity.

This is the least-frequently-used result in disguise. Section 2.2 recalled the textbook fact that least-frequently-used has an unbounded competitive ratio ^[28], proved by exactly the decoy construction: a few items with a huge early count, then a cycle of fresh items that never catch up. Accumulated-attention eviction is least-frequently-used with attention mass in place of an integer count, so Theorem 2 is not a new phenomenon but the transfer of a known one, which is precisely the point of the reduction. The eviction literature reinvented least-frequently-used under the name heavy-hitter selection and inherited its defect without inheriting the forty-year-old knowledge of how to fix it. The fix is also known, and we state it as a lemma because it is what the deployed systems already do and what Greedy-Dual-Attention formalizes.

Proof. The contribution of the attention at step $s$ to the score at step $t$ is ${\gamma }^{t-s}{a}_{s,i}\le {\gamma }^{t-s}$, which is below $ϵ$ once $t-s>{\log }_{\gamma }ϵ=\ln (1/ϵ)/\ln (1/\gamma )$. A decoy last attended at step $P$ therefore has decayed score at most ${\gamma }^{t-P}/(1-\gamma )$ at step $t$, which falls below the sleeper's score, refreshed to at least $a_{t,s}\approx 1$ whenever the sleeper is attended, once $t-P$ exceeds $W_{\gamma }$. From that step on the decayed policy prefers to evict the decoy, so the sleeper is retained and the regret stops accruing after a bounded prefix. The decayed score is exactly the credit of a Greedy-Dual policy with geometric aging, which is why Lemma 1 is the bridge to Section 6: decay does not merely patch the failure, it converts the heavy-hitter score into a quantity that carries the Landlord guarantee. The half-life $\ln 2/\ln (1/\gamma )$ should be set on the order of the persistence window of Section 7, long enough to see genuine heavy hitters, short enough that a topic change flushes the stale ones.

6. Greedy-Dual-Attention: A Competitive Attention-Aware Policy

The negative result and the positive results point at the same design. We want a policy that keeps the attention-awareness that makes heavy-hitter selection useful, while carrying the worst-case guarantee that only recency-and-weight policies have. Landlord is the natural host, because it already unifies recency and weight, and because its guarantee survives any tie-breaking rule. We add attention as the tie-break and as the credit refresh, and get a policy that is $k$-competitive by inheritance and attention-aware by design.

The credit update is Equation 11, written to make the inheritance explicit:

Proof. GD-A is Landlord with two modifications, and we check that neither affects the competitive bound. First, the eviction choice among zero-credit tokens is made by smallest recent attention rather than arbitrarily. Young's analysis holds for any rule that evicts a token whose credit has reached zero ^[14]; the potential-function argument bounds cost using only the credit dynamics and never uses which zero-credit token is chosen, so any tie-break, including the attention-based one, preserves the bound. Second, the refresh sets the credit to $\max (c_i,w_i)$ rather than exactly $w_i$; since a token is refreshed only when attended, and its credit is at most $w_i$ before the first refresh and remains within the range Landlord permits, this is a valid Landlord reset. Therefore GD-A inherits Landlord's guarantee, Equation 8, giving Equation 12:

The point of the construction is not that GD-A beats Landlord in the worst case; it cannot, and Theorem 1 says nothing can. The point is that it matches Landlord in the worst case while using the attention signal to do better on the typical case, and that it unifies the deployed heuristics as its own limiting behaviors. Consider three settings. When all recompute weights are equal and the attention tie-break is replaced by recency, GD-A is exactly least-recently-used, the classical $k$-competitive policy. When the credit is a recency window and a fixed pinned set of initial tokens is given infinite credit, GD-A is StreamingLLM's sink-plus-window ^[6]. When the credit decays geometrically and is refreshed by attention mass, so that the credit is a decayed accumulated attention, GD-A is a heavy-hitter policy of the H2O family, but with the decay that Theorem 2 shows is mandatory ^[5]. GD-A is thus a single policy with a single proof that contains the deployed designs as points, and that repairs the one, pure undecayed accumulation, that the proof rules out. Figure 10 draws the state and Figure 11 shows the typical-case regret of the three families under a stylized persistence model.

We choose Landlord as the host, rather than the Balance algorithm or a randomized weighted-paging scheme, for three reasons. It generalizes least-recently-used, so the recency floor the deployed systems already keep is a native special case rather than a bolt-on. It admits resource augmentation cleanly, so Equation 8 quantifies the value of a little extra budget, which is the lever a serving team actually controls. And its credit-and-rent mechanism has a direct operational reading as decayed importance, so the attention signal enters naturally as the credit rather than as a foreign object ^[14]. Balance would deliver the same worst-case ratio, but without the clean reduction to a recency-plus-decay policy that maps onto what systems already run, and the randomized weighted schemes buy a better ratio at the cost of a more complex state that is harder to justify when the deterministic bound is already the target. The design goal here is not the tightest possible ratio; it is the smallest change to deployed practice that carries a guarantee, and Landlord is the host that meets that goal.

Implementation and per-head instantiation. Greedy-Dual-Attention runs one credit accounting per attention head, because each head has its own attention distribution and its own notion of which tokens matter, which is the same reason FastGen assigns strategies per head ^[8]. The state per head is a priority queue keyed by credit, plus a decayed attention average per resident token, so the memory overhead is a constant per cached token and the time overhead is a logarithmic-cost queue operation per eviction, matching the asymptotics of the heavy-hitter heap in H2O. The rent step, subtracting the minimum credit from all resident tokens, is implemented lazily with an offset counter rather than by touching every token, so it is constant time, a standard Landlord implementation detail ^[14]. In a paged serving system the eviction granularity is a block of tokens rather than a single token, which does not change the analysis: a block is an item of larger size, and Landlord's file-caching form already handles non-unit sizes with the same competitive bound ^[14]. The policy therefore drops into a modern serving stack at the block level without special accommodation, and its per-head instantiation is the natural place to let the structured, per-head budget allocation of Section 8 eventually plug in.

flowchart TD
  A["token i attended<br/>(mass above threshold)"] --> B["refresh credit<br/>c_i = max(c_i, w_i)"]
  C["memory pressure"] --> D["delta = min_j c_j"]
  D --> E["c_j -= delta for all j"]
  E --> F{"any c_i = 0?"}
  F -->|yes| G["evict argmin recent<br/>attention among c_i=0"]
  F -->|no| D
  G --> H["k-competitive<br/>(Landlord, Thm 3)"]
  B --> H

The per-operation cost of GD-A is the cost of Landlord, which with a suitable priority queue is $O(\log k)$ per eviction, the same asymptotic order as maintaining a heap of accumulated scores in H2O or a recency structure in StreamingLLM. The attention tie-break needs a decayed running average per token, one multiply-add per attended token per step, negligible against the attention computation itself. There is no throughput tax for the guarantee.

A trace of the policy. It helps to run Greedy-Dual-Attention by hand on the adversarial input of Section 5, to see why it does not fail there. During priming, the decoys are attended and their credits are refreshed to their weights; the sleeper is attended lightly, so its credit is low. When the filler token forces an eviction, Landlord subtracts the minimum credit from all tokens and evicts a zero-credit token. Because the decoys were attended in the recent past, their credits are still high, so the token whose credit reaches zero first is a decoy that has aged out, not the sleeper, provided the sleeper has been attended within the credit's effective horizon. From then on, every step the sleeper is attended refreshes its credit back up, so it is never the minimum and never evicted, and the decoys, no longer attended, decay to zero and leave. The policy converges to keeping the sleeper, which is what the optimum does, and the adversary's leverage is gone. The mechanism is the rent step: it charges every resident token for the passage of time and lets only continued attention pay the rent, which is precisely recency and importance combined into one accounting.

The unification, stated as a table. Greedy-Dual-Attention is worth stating as one policy with parameters because it makes the deployed systems comparable rather than incommensurable. Figure 12 lists the settings. The point is not that any one row is novel; each row is an existing system. The point is that they are the same policy at different parameter settings, that one proof (Theorem 3) covers all of them, and that the one setting the proof excludes, undecayed accumulation with no recency, is exactly the one Theorem 2 shows is non-competitive and that no shipped system actually uses. The family is coherent, the guarantee is uniform, and the boundary of the guarantee coincides with the boundary of good practice.

7. Persistence and the No-Refetch Regret Bound

Competitive ratios are worst-case, and the worst case, Theorem 2, is adversarial. Practice is not adversarial, and the eviction papers report near-lossless quality at aggressive budgets because real attention has structure the adversary is forbidden to use. Scissorhands names that structure the persistence of importance ^[7]. We formalize a version of it and prove that under it, a recency-plus-heavy-hitter policy, the GD-A family, has regret bounded by a quantity that real attention makes small. This is the bridge between the pessimism of Section 5 and the optimism of Figure 3.

Define the per-step heavy set $H_t(\tau )=\{i:a_{t,i}\ge \tau \}$ and the light-tail mass $M_t^{\mathrm{tail}}(\tau )={\sum }_{i:a_{t,i}<\tau }{a}_{t,i}$, the attention the model places on tokens below the threshold. Consider the policy R-LRU-H: always retain the union, over the recent window $W$, of the heavy sets $H_s(\rho \tau )$, filling any remaining budget with the most-recently-attended tokens. This is the recency-plus-heavy behavior of GD-A with credits keyed to recent attention.

Proof. Take any token $i$ with $a_{t,i}\ge \tau$ at step $t$. By $(\rho ,W)$-persistence, $i$ received mass at least $\rho \tau$ at some step $s\in [t-W,t-1]$, so $i\in H_s(\rho \tau )\subseteq {\bigcup }_{s^{\prime }\in [t-W,t]}{H}_{s^{\prime }}(\rho \tau )$. The policy retains that entire union, and by the budget assumption the union fits in $k$ slots, so $i\in R_t$: the token is resident. Therefore every token the policy has evicted has $a_{t,i}<\tau$, and the regret at step $t$ is at most the sum of attention over sub-threshold tokens, which is $M_t^{\mathrm{tail}}(\tau )$. Summing over $t$ gives Equation 13:

The bound is only as good as the tail is small, and this is exactly where the empirical record enters. The whole premise of KV eviction is that attention is sparse: a small set of tokens carries most of the mass, so $M_t^{\mathrm{tail}}(\tau )$ is small for a modest threshold. H2O's finding that twenty percent of tokens suffice ^[5], TOVA's one-eighth ^[10], and PyramidKV's twelve percent ^[11] are all statements that the heavy set is small and the tail is light. Theorem 4 turns those observations into a guarantee: to the extent attention concentrates and persists, a recency-plus-heavy policy loses only the light tail, and the light tail is what the softmax was going to smear thinly anyway. Figure 13 shows how the tail mass shrinks as attention gets sparser (larger Zipf exponent), for three budgets, and Figure 14 replots the published quality-versus-budget operating points that this bound predicts.

This is the working-set model, recovered. Theorem 4 is the working-set bound of Denning ^[29] in attention's vocabulary. Denning's working set is the set of distinct items referenced in a recent window, and his thesis was that keeping the working set resident is enough because programs revisit a small, slowly-changing set. Our persistent heavy set ${\bigcup }_s{H}_s(\rho \tau )$ is precisely a soft, weighted working set: the tokens attended above a threshold in the recent window $W$. The budget condition $k\ge |{\bigcup }_s{H}_s(\rho \tau )|$ is Denning's condition that the cache hold the working set, and the conclusion, regret bounded by the light tail, is his conclusion that a working-set-resident policy thrashes only on the transient tail. The eviction literature's persistence-of-importance hypothesis ^[7] is the same hypothesis under a different name. Recognizing this matters because it imports fifty years of working-set engineering: the working-set size is measurable and adaptive, and the classical guidance, size the budget to the observed working set rather than to a fixed constant, is the adaptive-budget recommendation we make in Section 8.

Choosing the threshold. The bound has one free parameter, the threshold $\tau$ that separates the heavy set from the tail, and its choice is a genuine tradeoff the theorem makes explicit. A high $\tau$ makes the heavy set small, so the budget condition is easy to satisfy, but it makes the tail mass $M_t^{\mathrm{tail}}(\tau )$ large, so the regret bound is loose. A low $\tau$ tightens the regret bound but grows the heavy set until it no longer fits the budget, at which point the theorem's premise fails and no bound holds. The optimal threshold is the one where the heavy set just fills the budget, ${\tau }^{\star }$ such that $|{\bigcup }_s{H}_s(\rho {\tau }^{\star })|=k$, and at that setting the regret bound is the tail mass beyond the top-$k$ persistent tokens, which is the smallest the theorem can promise at that budget. This gives an operational recipe: measure the attention distribution on representative traffic, find the threshold whose recent heavy set matches your budget, and read the expected regret off the tail. It also predicts the shape of the quality-versus-budget curve, near-lossless while the budget exceeds the persistent heavy set, then a steepening decline as the budget drops below it, which is the shape every eviction paper reports and Figure 14 replots.

Two honest qualifications belong here rather than only in Section 9, because they bound the theorem's reach directly. First, the budget assumption $k\ge |{\bigcup }_s{H}_s(\rho \tau )|$ can fail: if the recent heavy set is larger than the budget, some heavy token must be evicted and the bound does not hold. This is the regime where quality degrades, and it is why aggressive budgets eventually break, consistent with every eviction paper reporting a budget floor below which quality falls. Second, persistence is an assumption about the input, not a theorem about transformers; it is well-supported for the slowly-varying attention of ordinary generation but can be violated at topic boundaries, by retrieval-heavy prompts, or by adversarial inputs, which is the same door Theorem 2 walks through. The two theorems are the two sides of one coin: persistence is precisely the assumption that rules out the adversary.

The bound is measurable, which makes it actionable. Unlike the competitive ratio, which is a worst-case abstraction, every quantity in Theorem 4 can be measured on a trace. The persistent heavy-set size $|{\bigcup }_s{H}_s(\rho \tau )|$ is a count over the recent attention distribution; the tail mass $M_t^{\mathrm{tail}}(\tau )$ is a sum over the same distribution; the persistence parameters $(\rho ,W,\tau )$ can be estimated by checking, over a corpus, how far back a currently-heavy token was last heavy. This means the bound is not only an explanation but an instrument: a serving team can compute, for its own traffic, the budget at which the persistent heavy set stops fitting, and read off the regret it should expect above and below that budget. The prediction that quality is near-lossless until the budget crosses the working-set size, then declines, is directly checkable against a team's own quality-versus-budget sweep, and a divergence from it is a signal that the traffic violates persistence, which is itself useful diagnostic information about the workload. A bound whose terms are all measurable is worth more to a practitioner than a tighter bound whose terms are not, and this is the sense in which the working-set framing earns its place over the raw competitive ratio for day-to-day budget setting.

8. Discussion: Where the Theory Disagrees with Practice

Casting eviction as caching does more than re-derive known results in new notation. It changes three judgments a practitioner would otherwise make from intuition, and in each case the theory disagrees with a common instinct.

Accumulated importance is a liability, not an asset, unless decayed. The intuitive reading of H2O is that accumulating attention is the good idea and recency is a safety net. Theorem 2 inverts this. The accumulated score, undecayed, is the mechanism of unbounded failure, and recency is the source of the only guarantee the policy has. The correct mental model is that recency provides the competitive backbone and a decayed importance term refines the choice within it. A team that reaches for a longer accumulation horizon to improve quality is strengthening exactly the quantity that makes the policy fragile to distribution shift. The theory says to shorten the effective horizon with decay and to lean on recency, which is the opposite of the instinct to remember more.

Per-head and per-layer budgets are a multi-cache allocation problem, not independent tuning. FastGen assigns strategies per head ^[8] and PyramidKV assigns budgets per layer ^[11], both by profiling and heuristics. Through the caching lens these are instances of allocating a shared memory across several caches that compete for it, which is close to the k-server problem on a structured metric ^[27]. The consequence is that the right per-head budget is not the one that minimizes each head's local regret independently; it is the one that equalizes the marginal regret reduction per slot across heads, a global condition that local profiling approximates but does not solve. That there is a clean optimization statement here, rather than a bag of heuristics, is something the caching view makes visible and the eviction literature has not stated. The k-server view sharpens it: with per-head budgets, the servers are the budget slots and the metric space is the structure of which tokens each head attends to, so the optimal joint policy moves budget between heads the way a k-server policy moves servers toward demand, spending more slots on the heads whose attention is currently broad and fewer on the heads that have collapsed onto a few tokens ^[27]. FastGen's fixed per-head strategy assignment ^[8] and PyramidKV's fixed per-layer schedule ^[11] are static approximations of a decision the k-server framing says should be dynamic and coupled across heads, and quantifying the gap between the static schedules and the coupled optimum is a concrete question the framing makes precise.

Quality floors are budget assumptions, not model limitations. Every eviction paper reports a budget below which quality collapses, and it is tempting to read this as a property of the model, that below some fraction the model simply cannot function. Theorem 4 says otherwise: the collapse happens exactly when the budget drops below the size of the persistent heavy set, so the floor is a property of the input's attention concentration, not of the model. A prompt whose attention is broad (many tokens matter at once) has a high floor, and a prompt whose attention is sharp has a low one. This predicts that adaptive per-prompt budgets, sized to the measured heavy-set size, should outperform a fixed global budget, and that the gain from adaptivity should be largest on heterogeneous workloads that mix broad and sharp prompts, which is a testable and, to our knowledge, largely untested prediction.

The lens also clarifies what eviction is not. Paging ^[1] and quantization ^[23] are orthogonal levers: paging changes layout without dropping tokens, quantization changes precision without choosing among tokens, and eviction chooses which tokens to drop. Only eviction has the online-decision structure competitive analysis was built for. This is why the guarantees and the impossibility results attach to eviction specifically, and it is why a serving stack should treat the three as a composable stack, page a quantized, evicted cache, rather than as competing options. The savings multiply, and only one of the three layers carries a caching-theoretic guarantee.

The right benchmark is closeness to the future-mass set, not end-task quality.The eviction literature evaluates a policy by running it end to end and measuring task quality, which conflates two things: how well the policy tracks the tokens the model wants, and how tolerant the task is of losing some of them. The caching view separates them. The policy's job is to keep its resident set close to the offline optimum's future-mass-maximizing set (Section 4), and that closeness can be measured directly on a replay that has the full attention trace, before any task metric is applied. A policy could score well on an easy benchmark while tracking the optimum poorly, and it would then fail on a harder distribution; measuring the tracking gap catches this where end-task quality hides it. This is the eviction analog of measuring cache hit rate rather than application latency, and it is the more diagnostic number. That the field reports the downstream metric almost exclusively is, we suspect, why policies that look equivalent on one benchmark diverge on another: they have different tracking gaps that only a harder distribution reveals.

The average case, not the worst case, is where the real ranking lives. Every reasonable eviction policy is $k$-competitive, so the worst-case ratio does not rank them, and the access-graph program (Section 2.3) is the classical tool for the ranking that matters. Restrict the adversary to the structure real attention obeys, low branching from token to token, strong recency, a few high-degree sink tokens, and the achievable ratio drops below $k$ in a way that depends on the structure, so different policies separate ^[28]. We do not carry out that analysis here, and its absence is the honest gap between our worst-case theorems and the average-case reality the benchmarks probe. What we can say is that the persistence bound of Section 7 is a first step into that program, and that the access graph of attention, whose edges are which token can be attended after which, is a concrete, measurable object that a full average-case theory would characterize. The disagreement with common practice here is methodological: the field tunes policies against benchmarks without a model of what structure the benchmarks reward, and the access-graph view says that structure is exactly what determines the ranking.

H2O's submodular guarantee and ours measure different things. H2O is not without theory: it formulates eviction as a dynamic submodular maximization and proves a guarantee for its greedy rule ^[5]. It is worth being precise about how that guarantee relates to ours, because they are complementary, not competing. The submodular guarantee is a statement about a single step: given the accumulated scores as the objective, the greedy choice is within a constant factor of the best subset for that objective. It says nothing about the future, because the objective it optimizes, accumulated past attention, is backward looking, which is exactly why it cannot prevent the failure of Theorem 2, where the past is a bad predictor of the future. The competitive ratio is a statement about the whole sequence measured against the offline optimum that sees the future, so it is the property that catches the drift the submodular bound misses. The two are answers to different questions: the submodular bound certifies that the greedy selection is good for the chosen objective, and the competitive ratio asks whether the objective itself leads anywhere good over time. A policy can be greedy-optimal for a backward objective at every step and still be non-competitive over the sequence, which is precisely the situation the two theorems together describe. Our contribution is not to refute H2O's analysis but to supply the sequential guarantee its single-step analysis does not, and Greedy-Dual-Attention keeps a per-step selection rule while adding the recency and decay that make the sequential guarantee hold.

Reasoning models stress the assumption that recency is enough. The persistence bound and the recency-floor recommendation rest on the premise that importance is temporally coherent, that a token needed now was needed recently. Long-chain reasoning is the workload most likely to violate it: a model that thinks for thousands of tokens may need to revisit a fact stated far in the past, at a distance that a recency window has long since evicted and a decayed score has long since forgotten. This is the access-graph observation that some workloads have long-range edges, and it predicts that the same eviction policy that is near-lossless on ordinary generation will degrade on long reasoning traces precisely because the persistent heavy set is larger and more spread out in time. The caching-theoretic reading is that reasoning workloads have a larger working set, so they need a larger budget or a policy with genuine long-range retention, not just recency and decay. This is a concrete, falsifiable prediction of the framework: measure the persistent heavy-set size on reasoning traces versus ordinary generation, and the budget floor should be higher for the former by the ratio of their working-set sizes. It also cautions against carrying a recency-tuned budget from a chat workload to a reasoning workload unchanged, which the theory says will silently lose the long-range facts the reasoning depends on.

Sink tokens are the high-degree vertices of the access graph. StreamingLLM's finding that a few initial tokens absorb a large, content-independent share of attention ^[6] has a clean reading in the access-graph model: attention sinks are high-degree vertices that nearly every step references, so the optimal policy pins them regardless of any importance score. This is why a pure importance rule that does not special-case sinks can underperform: it spends importance budget re-learning each step that the sinks matter, when the graph structure says to pin them once. The practical rule, pin a small sink set outside the importance mechanism, is the access-graph-optimal treatment of high-degree vertices, and it is another instance of the field arriving at the caching-optimal design empirically without the model that explains why it is optimal.

9. Threats to Validity and Limitations

This is a theory and synthesis paper, and its conclusions are only as strong as its assumptions and its honesty about them. We list the threats in order of how much they should temper the claims.

We run no experiments. Every empirical number in this paper is cited to a published source and cross-confirmed across at least two independent search results; none is our own measurement. In particular, Greedy-Dual-Attention is not benchmarked here. Its$k$-competitiveness is a proof (Theorem 3), and its typical-case behavior in Figure 11 is an analytical model under a stated persistence assumption, not a measured curve. The claim we make for GD-A is precisely that it carries a worst-case guarantee the deployed policies lack while reducing to them as special cases; the claim we do not make is that it beats them on any particular benchmark, which would require the experiments we did not run.

The tightest bounds assume a recompute model most systems do not implement. The$k$-competitive results (Theorems 1 and 3) live in the recompute model, where an evicted pair can be brought back. Most serving stacks do not recompute; they run the no-refetch model, for which we prove a regret bound (Theorem 4) rather than a competitive ratio. The recompute model is not a fiction, some systems do recompute evicted state, and prefix-caching systems recompute on cache miss, but it is not universal, and a reader should attach the competitive-ratio claims to the recompute setting and the regret claims to the no-refetch setting, not blur them.

The softmax renormalization breaks the strict fault model. Classical caching costs a fault when a requested item is absent. Attention does not fault; it renormalizes, and the true quality impact of an eviction is not exactly the evicted mass but a nonlinear function of it, mediated by how the renormalized distribution changes the output. Our attention-mass regret (Equation 4) is a tractable surrogate for that impact, well-motivated because the output is linear in the attention weights (Equation 1) so first-order the error is the displaced mass, but it is a surrogate. A large evicted mass on a token whose value vector happens to align with the retained tokens' average costs less than the surrogate says, and a small mass on an outlier value costs more. The surrogate is the right first-order object; it is not the exact quality loss.

Competitive ratios are worst-case and loose. A ratio of $k$ is a guarantee against an adversary, and $k$, the budget in slots, can be in the thousands, so the bound is far from a typical-case speedup. Its value is structural, it certifies bounded-versus-unbounded, and comparative among policy families, not a promise about any workload. All reasonable recency policies share the same $k$, so the competitive ratio does not rank them; that ranking needs the persistence bound and, ultimately, measurement.

The recompute weights and the persistence parameters are estimates. The weight $w_i$ is modeled as growing with position, which is right in order but not exact (attention and layer structure make the true recompute cost input-dependent). The persistence parameters $(\rho ,W,\tau )$ are properties of the input that we assume rather than measure; the theorem is conditional on them, and a workload that violates persistence, retrieval-augmented prompts with many equally-relevant passages, long-horizon reasoning that revisits distant tokens, or adversarial inputs, is outside the bound. We flagged these two failure regimes in Section 7 and repeat them here because they are the most likely real-world violations.

Scope. We analyze token-level eviction. We do not analyze quantization, low-rank compression, or learned eviction predictors except to place them; a learned predictor that forecasts future attention would change the analysis toward learning-augmented caching, which we flag as future work rather than resolve. We also assume a single model and a static budget; dynamic budgets that respond to memory pressure across concurrent requests are a scheduling problem on top of the caching problem, which we do not treat.

The reduction's fidelity depends on the request-model choice. We modeled a decode step as placing weighted requests on all resident tokens and reduced the worst case to a single hard token by letting the adversary concentrate the mass. A reader could object that real attention never concentrates all mass on one token, so the worst-case adversary is unphysical. The objection is correct and is exactly why the worst-case ratio is loose and the average-case analysis of Section 8 is where the real ranking lives. The competitive results are worst-case statements about what cannot happen (unbounded cost) rather than typical-case predictions, and we have tried to be consistent about labeling them so. The persistence bound of Section 7 is the statement that does make a typical-case prediction, and it is conditional on an assumption we do not verify. Neither is a measured claim about any model, and a reader should treat both as what they are: a worst-case guarantee and a conditional typical-case bound, joined by the observation that the condition of the second is the negation of the adversary of the first.

The empirical numbers we cite are from heterogeneous settings. The operating points in Figure 3 and the quality points in Figure 14 come from different papers using different models, benchmarks, and hardware, so they are not directly comparable to each other and we do not treat them as a single controlled sweep. We use them only to establish the qualitative facts the theory needs, that attention is sparse enough for small budgets to retain most quality, and that the throughput gain is roughly the budget-reduction factor, and we cross-confirmed each headline number across at least two independent sources. Any apparent trend across the points in Figure 14 is a synthesis across studies, not a measurement, and the connecting curve is explicitly an eye-guide. We would not draw a quantitative conclusion, such as a precise quality-versus-budget exponent, from a cross-study synthesis, and we do not.

10. Practical Implications

For a team running an inference stack, the analysis reduces to a short list of decisions with reasons attached.

Keep a recency floor and a small pinned sink set, always. This is the cheapest way to buy the competitive backbone Theorem 2 says you need. A fixed window of the most recent tokens plus a handful of initial attention-sink tokens ^[6] is a provably non-pathological base on top of which any importance refinement is safe. The recency floor is not where you save memory; it is where you buy safety.

Decay every accumulated importance score. If you keep heavy-hitter statistics, apply geometric decay, which turns the accumulated score into the credit of a Greedy-Dual policy (Section 6) and removes the undecayed-past failure of Theorem 2. The decay half-life is the one real tuning knob, and it should be on the order of the persistence window $W$, not the whole context.

Size the budget from the roofline, not by feel. In the memory-bound regime, Equation 3 says throughput gain is about $S/k$, so the budget follows directly from the batch you want and the memory you have. But the gain saturates when batch grows enough to leave the memory-bound regime and enter the compute-bound one, where the decode step is no longer waiting on memory ^[20]. Past that crossover, further eviction buys latency headroom, not throughput. Figure 15 sketches the crossover; its position is a property of your hardware's roofline and your sequence length, and it is computable in advance. The practical rule is to evict aggressively up to the crossover batch and to stop expecting throughput gains beyond it.

Compose the three levers. Eviction, quantization ^[23], and paging ^[1] multiply. A quantized, evicted, paged cache captures all three savings, and only the eviction layer needs the guarantee this paper supplies; the other two are orthogonal and do not interact with the competitive analysis.

Randomize the tie-break if you face distribution shift. The gap between $k$ and $\ln k$ in Figure 8 is free robustness. Breaking ties among equally-eligible eviction candidates at random, rather than by a fixed deterministic rule, moves the worst case from linear to logarithmic in the budget at no cost on benign inputs ^[12]. For a serving stack exposed to adversarial or rapidly shifting traffic, this is a cheap hedge the current systems do not take.

A concrete default policy. Assembling the rules gives a specific recommendation a team can implement without adopting anything exotic. Reserve a fixed floor of the most recent tokens, a few hundred, and pin the first handful of tokens as attention sinks; these are never evicted and cost a fixed slice of the budget. Fill the remaining budget by decayed attention: maintain a geometrically decayed attention score per token with a half-life on the order of the recent-token floor, and when the budget is exceeded evict the token of lowest decayed score, breaking ties at random. This is Greedy-Dual-Attention with a recency floor, it is within a small constant factor of the memory and compute of any current policy, and it is the smallest change to a heavy-hitter system that removes the Theorem 2 failure: the recency floor supplies the competitive backbone, the decay bounds the score horizon (Lemma 1), and the random tie-break buys the logarithmic worst case. Every ingredient is already present in one deployed system or another; the contribution is knowing which ones are load-bearing and assembling exactly those. A team that ships this default is provably safe against the adversarial and distribution-shift failures, and gives up nothing measurable on benign traffic.

Instrument the working set, not just the hit rate. The budget that the theory says to use is the working-set size, and the working-set size is a property of live traffic that drifts with the workload, so it should be measured continuously rather than set once. The telemetry to collect is the recent-window heavy-set size per request and its distribution across traffic, because that distribution is what determines the budget floor and its dispersion is what determines how much an adaptive per-request budget would save over a fixed one. A serving stack that logs only the coarse memory usage and the end-task quality is blind to the quantity the theory identifies as controlling, and it will discover a quality regression only after it ships, when a shift in traffic pushes the working set past a fixed budget. Logging the heavy-set-size distribution turns that latent failure into a leading indicator: when the tail of the distribution approaches the budget, quality is about to degrade, and the budget should rise or the policy should adapt before it does. This is the eviction-specific case of the general point that the right telemetry follows from the right model, and the caching model says the working set is the thing to watch.

For readers building on this, the TMLS engineering notes on platform engineering cover the serving-system side of these levers, the LLMOps and observability material covers the telemetry needed to measure the persistence and heavy-set sizes the budget should track, and the deep-tech research practice covers the theory-to-systems path this paper walks. The companion research note on speculative cascades analyzes the orthogonal latency lever of draft-verify decoding, which shares the memory-bound-regime premise used here in Equation 3.

11. Open Problems and Future Work

The caching framing opens four problems with clean statements.

Learning-augmented eviction. The attention score is a prediction of future importance, and learning-augmented caching studies exactly how to use a possibly-wrong prediction: to be near-optimal when it is accurate (consistency) and robust when it is not (robustness). Importing that framework would give attention-guided eviction a formal safety net, a policy that is close to Belady when attention predicts the future well and no worse than$k$-competitive when it does not. The open question is the exact consistency-robustness tradeoff achievable when the prediction is the attention distribution itself, whose error structure is specific and not arbitrary. The generic learning-augmented bound treats the prediction as a black box that can be wrong in any way; attention is a structured predictor whose errors correlate with position, with topic boundaries, and with head identity, and a bound that exploits that structure should beat the generic one. Concretely, the open question is to give a policy and a bound of the form: regret at most the optimum plus a term that grows with the measured attention-prediction error and is capped at the$k$-competitive worst case, with the error term specialized to the way attention mispredicts. This would turn the attention score from an unproven heuristic into a predictor with a guarantee that degrades gracefully as the prediction degrades, which is exactly the safety property the deployed systems lack and Theorem 2 punishes.

Optimal per-head and per-layer allocation. Section 8 argued that per-head budgets are a multi-cache allocation problem close to k-server on a structured metric ^[27]. The open problem is to state and solve the allocation that equalizes marginal regret across heads and layers, and to characterize how far the heuristic allocations of FastGen ^[8] and PyramidKV ^[11] are from it. A competitive analysis of the joint allocation, rather than of a single cache, is open.

Refetch-aware policies. Our two cost models are endpoints: recompute always, or never. A real policy could recompute selectively, trading compute for memory when a wrongly evicted token is attended again, which sits between the models and matches prefix-caching systems that recompute on miss. The competitive analysis of a policy that chooses per token whether to drop-and-recompute or keep is open and would unify the two models we kept separate.

Joint eviction and quantization. Deciding per token whether to keep at full precision, keep at low precision, or drop is a caching problem with three service levels rather than the two of weighted caching. This generalizes the problem the classical theory solves, and the right competitive ratio for multi-level caching of this specific shape, one full-cost level, one reduced-cost level, one drop level, is not known to us. It is the theory that a combined eviction-and-quantization system ^[25] would need to carry a guarantee.

Underlying all four is a single question the framing makes askable: what is the average-case, not worst-case, competitive ratio of attention-guided eviction on the input distribution real language produces? Theorem 4 is a first answer under a persistence assumption; a distributional theory that predicts the measured quality-versus-budget curves of Figure 14 from properties of the attention distribution would close the loop between the caching theory and the eviction practice.

Empirical validation of Greedy-Dual-Attention. The most immediate follow-up is the experiment this paper does not run. Greedy-Dual-Attention should be implemented in a serving stack and measured against H2O, StreamingLLM, and TOVA on the standard long-context benchmarks, at matched budgets, with two quantities reported that the current literature omits: the tracking gap against the offline future-mass optimum (Section 4), and the behavior on a distribution-shifted or adversarially-constructed suffix that the persistence assumption violates. The theory predicts a specific pattern, that Greedy-Dual-Attention matches the heavy-hitter policies on benign long-context tasks, where all policies track well, and separates from them on the shifted suffix, where the undecayed policies exhibit the Theorem 2 degradation and the decayed, recency-floored policy does not. Confirming or refuting that pattern is the cleanest test of whether the worst-case distinction the theory draws has practical bite, and it is the experiment a team with a serving stack could run in days. We state the prediction explicitly so that it can be falsified.

Working-set-adaptive budgets. Section 8 argued that the quality floor is the working-set size, not a model constant, which suggests a budget that tracks the measured persistent heavy set per request rather than a fixed global constant. The open problem is to design and analyze an online budget controller that estimates the working-set size from the recent attention distribution and sizes the cache to it, trading a little more memory on broad-attention prompts for a lot less on sharp ones, and to bound its regret against the best fixed per-request budget. This is the eviction analog of working-set-based memory management, which the operating-systems literature solved for pages decades ago ^[29] and the LLM-serving literature has not yet posed for tokens.

Frequently Asked Questions

Glossary

Closing synthesis. The key-value cache is a cache, and the decision of which tokens to keep under a budget is the online caching decision that Belady, Sleator, Tarjan, Young, and their successors characterized completely for pages decades ago. The eviction literature rebuilt the paging design space, recency, importance, hybrids, and per-cache allocation, without the analysis that tells which points in that space carry guarantees, and it landed, by careful empirical work, mostly on the safe points, while treating the one unsafe point, undecayed importance, as a respectable idea rather than the non-competitive least-frequently-used rule it is. Reading eviction as caching supplies three things the literature was missing: a reason the recency component is load-bearing rather than incidental, given by the reduction and the non-competitiveness theorem; a single policy, Greedy-Dual-Attention, that carries a worst-case guarantee while reducing to the deployed heuristics as special cases; and a bridge, the persistence bound, between the pessimistic worst case and the sparse, coherent attention that makes eviction work in practice. None of it required an experiment, because none of it is an empirical claim; it is the transfer of proven statements from one problem to another that turned out to be the same problem. The eviction question is not going away, because it is the one lever that caps rather than merely lowers the memory a long context costs, and it deserves to be reasoned about with the theory built for exactly it.

Byline: Agon Avdimetaj, TMLS AI Research. This is a theory and synthesis paper; it reports no experiments of its own, and every empirical figure it cites is attributed to a named, verifiable source.