1
00:00:01,000 --> 00:00:34,625
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon.
So today we're digging into a paper called "Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective." That's Jiaming Yang et al., four co-authors total, out of Sichuan University and the Institute of High Performance Computing at A*STAR in Singapore. It's a preprint dated April 30th, 2026. Ada, you sent me this one with more enthusiasm than usual.

2
00:00:34,625 --> 00:00:56,775
[Dr. Ada Shannon] Guilty. Most eviction papers I read are a new heuristic bolted onto an old heuristic, with a benchmark table as the only justification. This one actually tries to derive, from first principles, what an optimal KV cache should look like. That's rare. Whether CAPKV, their method, lives up to the theory is a separate question — but having a real mathematical target to aim at, instead of just vibes and ablations, is what made me stop and read it twice.

3
00:00:56,775 --> 00:01:34,150
[Hal Turing] Okay, let's set the stage — some listeners hear "KV cache" and their eyes glaze over. When a transformer generates text token by token, it stores the key and value vectors for every token it's already processed, so it doesn't have to recompute them at every step. That's the KV cache. The problem is it grows linearly with sequence length, and at long context — tens or hundreds of thousands of tokens — that cache can dwarf the model weights themselves in memory footprint. So eviction, deciding which entries to throw away under a fixed budget, becomes the whole ballgame for making long-context inference deployable.

4
00:01:34,150 --> 00:01:58,975
[Dr. Ada Shannon] Right, and the field's split into two camps. One is attention-pattern-based — SnapKV, H2O — which look at which tokens historically got a lot of attention weight and keep those, on the theory that past importance predicts future importance. The other is structure-aware — KeyDiff, Knorm — which score tokens by properties of the key vectors themselves, like their norm or how distinct they are from each other, without even looking at attention weights. Both camps work reasonably well empirically. Neither has a real theory for why.

5
00:01:58,975 --> 00:02:21,350
[Hal Turing] And that's the gap this paper's aiming at. The actual research question is: can you unify these heuristics under one objective, and if you build a method that directly optimizes it instead of approximating it sideways, does it win? To get there they lean on the Information Bottleneck principle, which — Ada, I half-remember this from grad school and half don't.

6
00:02:21,350 --> 00:02:56,600
[Dr. Ada Shannon] Oh, I can save you the half — the Information Bottleneck, from Tishby, Pereira, and Bialek back in 1999, is compression with a purpose. You've got an input X, a target Y you care about, and you want a compressed T of X that throws away as much of X as possible while keeping as much information about Y as possible. Here X is the full KV history, T is whatever survives eviction, Y is the future query the model hasn't asked yet. A regular neural net trained with SGD never explicitly accounts for how much information a layer keeps or discards — it just minimizes a loss. IB puts that trade-off on the table directly.

7
00:02:56,600 --> 00:03:14,250
[Hal Turing] That mapping actually makes it click — keep what survives eviction maximally informative about a query you haven't seen yet. But mutual information over messy, nonlinear attention outputs sounds like a nightmare to compute. How do they get to an actual formula?

8
00:03:14,250 --> 00:03:48,100
[Dr. Ada Shannon] They cheat, in the good sense. Real softmax attention is nonlinear and input-dependent, so exact mutual information has no closed form. So they swap in a linear-Gaussian surrogate — treat the mapping from stored KV pairs to outputs as roughly linear, with Gaussian noise absorbing whatever the approximation misses. That turns the cache into a set of classical Gaussian communication channels, the same math Shannon used for channel capacity. It's the same trick behind Kalman filters — assume linearity and Gaussian noise, and exact inference becomes tractable where the true nonlinear system would be hopeless.

9
00:03:48,100 --> 00:03:56,350
[Hal Turing] And that closed form still involves some matrix that's expensive to search over, which is where leverage scores come in?

10
00:03:56,350 --> 00:04:32,150
[Dr. Ada Shannon] Exactly. Statistical leverage scores are a classical numerical linear algebra idea — no training, no gradients, just a deterministic score from a matrix's singular vectors telling you how much a given row is an irreplaceable pivot versus redundant with the rest. They come out of older work like Drineas and Mahoney's CUR decomposition research. Here they're repurposed as a cheap per-token proxy for how much a KV pair contributes to the cache's information capacity, without brute-forcing every possible subset. That's the toolkit — next is how it actually becomes an algorithm.

11
00:04:32,150 --> 00:05:10,625
[Dr. Ada Shannon] Drineas and Mahoney — their randomized numerical linear algebra work, the CUR decomposition papers from the mid-2000s, is where leverage scores really got formalized as a way to pick the most informative rows of a matrix without touching the rest. This paper folds that into the older D-optimal experimental design line — Mitchell's 1974 Technometrics paper on computer-constructed D-optimal designs, and a 1997 chemical engineering application by Lanouette and colleagues that used the same trick to pick which experiments to actually run. Same math, wildly different domains. Here it's repurposed to decide which KV pairs earn a spot in a shrinking cache.

12
00:05:10,625 --> 00:05:59,450
[Hal Turing] Building on that leverage-score lineage — here's what's nagging me. Section 4.1's whole validation story is 'capacity correlates with performance, Spearman 0.75 to 0.87, therefore the theory holds.' But the K, U, and KU-Capacity proxies they use are simplified, isotropic versions of the exact log-determinant form in Theorem 3.2 — the same structural form CAPKV directly optimizes through leverage scores. So when a method that maximizes log-det performs well, and a proxy built from that same log-det form also tracks performance, how much of that correlation is genuine external validation of the general information-bottleneck claim, versus the method just agreeing with a simplified version of itself?

13
00:05:59,450 --> 00:06:39,050
[Dr. Ada Shannon] It's a real distinction and worth being precise about. The proxies drop ΛQ and Σnoise entirely and assume isotropic everything, so they're not literally CAPKV's objective — but the family resemblance is tight enough that a strong correlation there is weaker evidence for the broad theory than the framing suggests. It's solid support for a restricted, isotropic corollary of their own objective. Whether the full query-covariance-aware, noise-aware version in Theorem 3.2 is what's actually driving Table 1's gains is a separate, untested question. An honest paper would've flagged that gap explicitly instead of presenting 4.1 as clean independent confirmation.

14
00:06:39,050 --> 00:07:06,750
[Hal Turing] Oh — wait, hold on, that's actually connected to something else that bugged me. Appendix B.3 spends real effort showing H2O's attention-averaging approximates the query covariance ΛQ — a legitimate, worked-out unification claim. So why does H2O just vanish from Table 1? EA's there, KeyDiff, SnapKV, Sink, Knorm — five baselines, and the one method they bothered to theoretically analyze in depth is missing from the actual numbers.

15
00:07:06,750 --> 00:07:49,225
[Dr. Ada Shannon] No good technical reason given, either — unlike SnapKV getting dropped from the Section 4.3 decoding experiment, which at least has a stated cause: it needs real-time attention-window construction that doesn't work under online eviction. H2O's absence from Table 1 just reads as a quiet choice, and it's the kind of thing that makes me want the raw numbers before I trust the qualitative story in the appendix. Same caution applies to their scale claims — every experiment, main results and ablations alike, runs on four-to-fourteen-billion-parameter dense models: Qwen3, Llama 3.1-8B, Mistral-7B. Nothing at 70B, nothing MoE with per-expert head dims that would actually stress-test that O(Nd² plus d³) leverage-score cost.

16
00:07:49,225 --> 00:08:15,850
[Hal Turing] And there's a sharper inconsistency buried in the math itself. Theorem 3.2 explicitly says mutual information is invariant to the query mean, μQ — that's the whole point of it dropping out in the derivation. But then the actual eviction weight in Equation 8, w_i, is built entirely on μQ. So the score that decides what gets evicted leans on the one quantity their own theorem says carries zero mutual information. How do you square that?

17
00:08:15,850 --> 00:09:30,800
[Dr. Ada Shannon] They square it by quietly answering a different question than the one the theorem answers. The theorem's about population-level mutual information under the true query distribution — mean-invariant by construction. But at inference time you're conditioning on a finite, structured stream of queries you've already seen, and μQ is a cheap online estimate of where that stream is currently pointed — a relevance prior bolted onto a diversity-driven objective, not derived from Theorem 3.2 itself. Same disconnect shows up with serving systems: CAPKV's eviction is per-request and μq-dependent, never checked against PagedAttention — Kwon and colleagues, UC Berkeley, 2023 — whose whole design relies on block-level KV sharing across requests with an identical prefix. Two users, same prompt, different query history, different retained subset — that breaks block reuse. And they sidestep Alemi, Fischer, Dillon, and Murphy's Deep Variational Information Bottleneck, Google Research, 2017, entirely, opting for a linear-Gaussian surrogate instead of a variational bound. That's a real accuracy-for-tractability trade the paper never quantifies — though to their credit, they flag it themselves and point to richer, controlled-nonlinearity surrogates as the honest next step, not linear-Gaussian as a final word.

18
00:09:30,800 --> 00:10:09,075
[Hal Turing] Practically, though, this is still a genuinely useful score — cheap, model-agnostic, and it degrades more gracefully than the heuristics it's replacing, especially in that irreversible decoding setting. If you're running structural eviction today, swapping in leverage scores instead of raw attention or key-norm heuristics looks like a low-cost upgrade worth testing, with the scale and serving-system caveats we just laid out firmly in mind. That's the paper — a genuinely useful unifying lens, evidenced more strongly for a simplified corollary than for the full theory it claims. Thanks for listening, and take care.