Long-context language models keep a cache of past keys and values, the "KV cache," so they do not recompute attention inputs at every generated token. To save memory and time, recent systems throw most of this cache away or move it to slower memory. The catch is that a token judged useless now can become important later. Bringing it back means copying it over the host-to-GPU link or recomputing it, and that cost lands in a single decoding step. Today's methods choose how much cache to keep with fixed budgets or per-step rules. None of them accounts for the fact that growing the cache costs real time while shrinking it is nearly free. None offers any guarantee about total latency over a long generation.
We propose to treat the per-step cache budget as an online decision with a switching cost and to control it with the potential-function algorithms of online convex optimization. A potential function is a scalar "bank balance" over the algorithm's state that turns a guarantee about a whole sequence into a check on each step. The specific claim is this. Under a hardware cost model measured on the target GPU, each step's cost (attention latency plus a weighted estimate of attention distortion) is provably convex in the budget. Revival traffic is an asymmetric movement cost. Together these let a cheap, memoryless controller from A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs guarantee total cost within a factor of 3 of the best budget schedule chosen in hindsight. The test that matters is whether this controller beats fixed budgets and simple smoothing on wall-clock latency at equal quality, especially when token relevance spikes.
Why this intersection, and why this particular idea
The two directions meet in a narrow place. Potential-function work proves bounds over abstract costs. Online Scheduling on Identical Machines using SRPT bounds remaining processing work but treats moving a job between machines as free. The automated analyzers in Bounded Expectations: Resource Analysis for Probabilistic Programs and Differential Cost Analysis with Simultaneous Potentials and Anti-potentials count abstract cost ticks; the latter fails on 5 of its 19 benchmarks because its polynomial templates cannot express piecewise costs such as max(x, y).
The FLOPs-latency literature shows that arithmetic counts mislead. ShuffleNet V2 shows that memory traffic and element-wise operations dominate runtime. Compute-Optimal Is Not Cluster-Optimal shows that FLOP-optimal sparse models can be the slowest on real clusters. But its fixes are empirical: lookup tables, rooflines, and fitted performance models.
The closest point of contact is EfficientRollout, which switches speculative decoding on and off with an instantaneous roofline check. A roofline is the rule that a kernel's time is the larger of its compute time and its memory-transfer time. We considered applying switching-cost theory to that toggle and rejected it. Turning a drafter on or off costs little more than a kernel launch, so a hysteresis threshold would almost surely match any theory-derived policy.
KV budgets differ in two ways. First, the switching cost is large and physical: revived tokens must cross the host link or be recomputed, which is the auxiliary-cache pressure LazyLLM reports. Second, Taming the Fragility of KV Cache Eviction shows that token importance is unstable, with abrupt relevance spikes. Unstable demand combined with expensive upward moves is exactly the regime where memoryless greedy control thrashes and amortized analysis pays off.
Core Claim
Let $x_t$ be the number of KV entries kept on the GPU at decode step $t$, with the kept set chosen as the top-$x_t$ tokens by an importance score. Define the per-step cost
$$f_t(x) = \max\Big(\frac{F_t(x)}{P}, \frac{B_t(x)}{W}\Big) + \lambda\, D_t(x),$$
where $F_t(x)$ and $B_t(x)$ are the attention FLOPs and bytes at budget $x$, $P$ and $W$ are the profiled peak compute and bandwidth of the GPU, $D_t(x)$ is the attention mass of tokens outside the kept set, and $\lambda$ sets the exchange rate between quality and time.
The first term is a maximum of affine functions of $x$ and is therefore convex. The second term is a tail sum of sorted scores. Each added token contributes no more than the previous one, so $D_t$ is also convex. The total cost over a generation is
$$\sum_t f_t(x_t) + c \sum_t \max(0, x_t - x_{t-1}),$$
where $c$ is the measured per-token revival time (transfer or recompute). Upward moves are bounded by half the total movement plus the budget range, so the asymmetric cost reduces to Bansal et al.'s symmetric setting up to an additive constant. Their memoryless Algorithm M then gives a 3-competitive bound. It needs only the current budget and the current cost function, which we can compute from scores the eviction method already produces, so the controller adds negligible overhead inside the decode loop.
There is one honest gap. At a fixed budget, the identity of the top tokens can churn, and that churn causes revivals not captured by $|x_t - x_{t-1}|$. The guarantee covers the scalar budget decision only. We will measure churn separately and report how much of the real revival traffic the bound actually covers.
Research Program
The work has three parts.
The first is calibration. On one data-center GPU we profile decode-attention time as a function of budget and batch size, and host-to-GPU transfer and recompute time per revived token. We then fit $P$, $W$ and $c$, and check how far measured step latency departs from the piecewise-linear model.
The second is the controller. It plugs into DefensiveKV's scoring, replacing the fixed budget with Algorithm M driven by $f_t$. Evicted entries are offloaded to host memory so they can be revived, in the spirit of LazyLLM's auxiliary cache.
The third is analysis. Because the problem is one-dimensional and convex, the offline optimal schedule can be computed exactly by dynamic programming over a discretized budget grid for each recorded trace. This gives an empirical competitive ratio for every policy, alongside the worst-case factor of 3.
Baselines
The naive reference is the full KV cache with no eviction. It defines zero quality loss and the latency ceiling.
The strongest existing method is DefensiveKV and Layer-DefensiveKV Taming the Fragility of KV Cache Eviction at fixed budgets of 20% and 40%. The paper reports 2.3x and 4.3x lower generation-quality loss than CriticalKV at a 20% budget. It also reports near-lossless performance at 40% on Llama-3.1-8B. We run it with identical scoring, models, prompts and offload path, so the only difference is how the budget moves. Beating it means either lower mean and p99 per-token latency at matched LongBench/RULER scores, or higher scores at matched latency.
For dynamic token pruning we also run LazyLLM LazyLLM, which reports a 2.34x prefill speedup on Llama 2 7B for multi-document QA. Its gains are in prefill, so we compare it on end-to-end time, prefill plus decode, rather than decode alone.
Two adaptive baselines get the same tuning budget as our $\lambda$: a grid search on a held-out LongBench split. The myopic policy minimizes $f_t$ at each step, which is the KV analogue of EfficientRollout's instantaneous roofline decision. A hysteresis/exponential-smoothing policy damps changes in the budget.
The key ablation sets $c = 0$ inside our controller while still charging real revival costs at evaluation. That isolates whether the switching-cost term is doing the work.
Why not just…?
Why not just use a fixed budget, as DefensiveKV does? A fixed budget never pays revival cost from budget changes. But it must be sized for the hardest moments of the hardest prompts, so it overpays on easy stretches. At 10% budget it is DefensiveKV that survives 32k RULER while other baselines fail completely, which shows the budget choice matters. If the best fixed budget lands within a few percent of our controller on latency at equal quality, we will report that adaptivity is not worth it on these workloads.
Why not just smooth the budget with hysteresis? This is the real threat. Smoothing with a well-tuned constant may match Algorithm M on average traces. What the competitive analysis adds is a principled setting tied to the measured revival cost $c$, plus a worst-case bound that smoothing lacks. Bansal et al. prove that no deterministic memoryless rule beats a ratio of 3. So the test is empirical. We compare against the offline optimum on natural traces and on spike-heavy RULER multi-key retrieval traces. If tuned hysteresis matches our controller on both, the honest contribution narrows to a way of choosing the smoothing constant from $c$.
Why not just profile with a lookup table, like NetAdapt? NetAdapt sums latencies measured per layer for a static network. We do use profiling, to calibrate $f_t$ and $c$. But a table says what one step costs. It does not say when to pay for a revival, which is a decision about the sequence.
Proposed Experiments
We use Llama-3.1-8B and Mistral-7B-v0.3 on LongBench (16 datasets) and RULER up to 32k context, matching DefensiveKV's setup. For this scheme and this offload configuration, we found no reported latency result on Lacuna for KV eviction with host offload, so all latency numbers are measured fresh under the same harness.
We report six metrics: per-token decode latency (mean and p99), revived tokens per step, churn-induced revivals, task scores, and the empirical cost ratio to the dynamic-programming optimum.
Three checks are decisive. First, the switching-aware controller should cut p99 step latency relative to the myopic policy on RULER multi-key retrieval, where relevance spikes, with no loss in score. Second, the ablation with $c = 0$ should lose that advantage. Third, measured empirical ratios should stay well below 3. If they do not, the convexity or cost model is wrong, and the measured departure between real step latency and the profiled roofline model will tell us where.
A negative outcome would also be informative. Two results would show that the bottleneck in revivable eviction is which tokens are kept, not how many: tuned hysteresis matching the controller everywhere, or churn dominating revival traffic.
References
- A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
- Online Scheduling on Identical Machines using SRPT
- Bounded expectations: resource analysis for probabilistic programs
- Differential cost analysis with simultaneous potentials and anti-potentials
- ShuffleNet V2: Practical Guidelines for Efficient CNN Architecture Design
- Compute-Optimal Is Not Cluster-Optimal: Systems-Aware Scaling for Sparse Mixture-of-Experts
- EfficientRollout: System-Aware Self-Speculative Decoding for RL Rollouts
- LazyLLM: DYNAMIC TOKEN PRUNING FOR EFFICIENT LONG CONTEXT LLM INFERENCE
- DefensiveKV: Taming the Fragility of KV Cache Eviction in LLM Inference
- NetAdapt: Platform-Aware Neural Network Adaptation for Mobile Applications