Inference optimization × submodular selection

SubCache

When an LLM's KV cache gets too big and you have to throw tokens away, can a submodular function pick what to keep better than the usual heuristic?

My research is in subset selection for ML, where I use submodular functions (functions with diminishing returns) to pick the most useful subset out of a bigger set. Recently I've gotten interested in inference optimization and how the hardware behind a model affects how fast it runs, and I saw a chance to combine the two.

The short answer: a little, and not in a way that's worth it. H2O turned out to be very hard to beat. My method did win, but only on repetitive text, only by a little, and it was much slower.

2.8×
throughput from keeping 25% of the cache, for ~5% worse perplexity
−2.5%
best perplexity gain over H2O, on repetitive agent sessions
71%
of decode time spent choosing what to evict with my method
21 ms
per decode step at every batch and cache size (CPU bound)

What I built

A small inference engine with its own KV cache instead of Hugging Face's, so cached tokens can be masked out or physically removed. Text goes in 64 tokens at a time, and after each chunk the cache is cut back down to its budget.

How the cache budget is split

Every policy keeps the first 4 tokens (attention sinks) and the newest half of the budget.

So policies differ only in which older tokens survive. That keeps the comparison fair: any difference in quality comes from the selection rule alone.

The baseline: H2O

H2O (“heavy hitters”) keeps the tokens that have received the most attention so far. Choosing is basically a sort, so it's nearly free.

My version: H2O plus a redundancy term

The weakness of H2O is that if the same content shows up twice, both copies tend to get a lot of attention, so both get kept. Coding agents do this constantly: they re-read the same file, re-run the same command, and see the same log again. I added a weighted facility-location term (wfl in the code) so that if two cached tokens are basically duplicates, only one of them needs to stay.

f(A) = (1 − λ) · Σi∈A wi  +  λ · Σi∈V wi · maxj∈A sim(i, j)

V is every cached token, A is the set kept, w is H2O's attention score, and sim compares the cached keys and values. The first term is H2O. The second rewards keeping a representative for every important token, which is where the diminishing returns come in: a second copy of something already covered adds almost nothing. With λ = 0 it is exactly H2O.

Toy example: room for 4 tokens

Two read-outs of the same file (read a.py and its repeat) both draw heavy attention.

H2O keeps the 4 highest-attention tokens
read a.pyread a.py ′test failstest fails ′edit b.pyls src/
With the redundancy term, one copy covers both
read a.pyread a.py ′test failstest fails ′edit b.pyls src/

Illustrative only. In the real engine this runs per layer and per attention head over thousands of slots.

Setup

Result 1: eviction is worth it, mostly because of memory

Bar chart: decode throughput rises from 190 tokens per second with the full cache to about 1,400 at a 6.25% budget

With 8,192-token contexts, the full cache only fits 4 sequences on the card. Keeping a quarter of it fits 12, which is 2.8× the throughput for about 5% worse perplexity.

Something I didn't expect: a smaller cache doesn't make each step faster. A decode step takes about 21 ms no matter the batch size or cache size. On this machine decoding is limited by the CPU launching GPU kernels, not by the GPU. Running the same thing on an RTX A6000 gave the same 21 ms. So all of the speedup comes from fitting more sequences in memory.

Result 2: the submodular part helps, a little

Line chart: on agent tokens the redundancy objective is 0.2 to 0.5 percent better than H2O with weight 0.25 and 1.1 to 2.5 percent better with weight 1.0, more so at smaller budgets

On late agent sessions it beat H2O at every budget I tried, and the gap grew as the budget shrank. With the redundancy weight I picked in advance (λ = 0.25) we're talking 0.2% to 0.5% lower perplexity on the agent's own tokens.

A smaller sweep suggested going all the way to λ = 1, so I reran that on the full 8,192-token setup. It holds up there: 1.1% to 2.5% better than H2O, which is about a fifth of the gap between H2O and the full cache at a 25% budget and a tenth at 12.5%. At those two budgets it ties the R-KV-style baseline, and below them it beats it by a lot. But that's the only dataset where λ = 1 helps (next section).

Result 3: it only helps where there's repetition

Bar chart: the redundancy objective improves on H2O only on late agent sessions, not on session starts or WikiText

I measured how repetitive each dataset is: how often a run of 16 tokens has already appeared earlier in the same sequence.

DataRepetitionWeight 0.25Weight 1
WikiText0.2%NoMixed
Start of an agent session8%NoWorse
First 16k tokens of an agent session16%NoWorse
24k tokens into an agent session26%Yes, at every budgetYes, at every budget

It only helps on the most repetitive data, which fits the idea of removing redundancy. But the 16k sessions are fairly repetitive too and it didn't help there, so this repetition number alone doesn't predict when it will work. Turning the weight up makes the trade-off sharper: λ = 1 is the best setting on late sessions and up to 4% worse than H2O on the others.

Result 4: why I wouldn't actually use it

Bar chart: selection takes under 1 percent of decode time for H2O, 19 percent for the R-KV-style baseline and 71 percent for the redundancy objective

Picking what to evict isn't free. H2O's choice is basically a sort. Mine has to compare cached tokens against each other in every attention head, and at a 12.5% budget that took 71% of decode time. Throughput dropped to 78 tok/s, which is worse than not evicting at all (190). A 1–2% perplexity gain doesn't pay for that.

Result 5: what happens on real tasks

Perplexity only goes so far, so I also checked whether the policies change actual answers. These ran on the RTX A6000 in bf16 with bigger models, and WFL is the λ = 1 version. Every task is a small subset (details under Limitations), so treat this as a first look, not a leaderboard entry.

For LongBench and the RULER-style tasks the model reads the whole prompt, the cache is cut down to the budget once, and then it answers with nothing else evicted. Budgets are a share of the prompt, and scores are each task's own metric out of 100. Like in SnapKV-style evaluations, the first answer token comes from the full cache, so every method gets it for free. On the RULER-style tasks that token is only punctuation, but on LongBench's short-answer tasks it can be the whole answer (a fifth to over a third of the answers there are one word), which narrows the gaps between methods. Best compressed method per column in blue.

RULER-style retrieval

Llama-3.1-8B-Instruct, 8,192-token prompts, 5 needle and variable-tracking tasks × 10 examples. Full cache: 92.8.

50%25%12.5%6.25%
Window51.631.718.78.7
H2O59.726.411.74.9
R-KV-style90.893.691.691.1
WFL59.338.714.94.1

The R-KV-style baseline scores tokens by how much the question (the last 32 prompt tokens) attends to them, so it keeps the needle at every budget. H2O and WFL use attention summed over the whole prompt and lose it. WFL is built on H2O's scores, so being redundancy-aware can't fix that.

LongBench

Llama-3.1-8B-Instruct, prompts cut to 16k tokens. qasper, multifieldqa_en, hotpotqa and lcc with 20 examples each, gov_report with 10; average over the 5 tasks. Full cache: 51.8.

50%25%12.5%6.25%
Window43.240.137.033.4
H2O51.046.944.841.0
R-KV-style51.850.249.144.4
WFL51.248.046.441.4

WFL lands between H2O and R-KV-style, and on every individual task it was statistically tied with H2O. R-KV-style was clearly better on two of the QA tasks at some budgets, but clearly worse than H2O on summarization (gov_report) at 25% and below, where WFL stayed level with H2O. That fits the idea: a summary needs coverage of the whole document.

MATH-500 with chain-of-thought

DeepSeek-R1-Distill-Qwen-1.5B, 20 problems from levels 1 and 2, one sample each, capped at 4,096 generated tokens. The cache is cut back every 64 generated tokens and the budget is a number of slots. Accuracy in percent; full cache: 55.

20481024512256
Window60602515
H2O55606545
R-KV-style70454540
WFL60657050

This one is too noisy to rank. Half of the full-cache runs hit the 4,096-token cap before answering, so the scores mostly say whether the model finished thinking in time. WFL was 5 points above H2O at every budget, but every interval was about ±20 points. The only clear results: Window falls apart at 512 and 256 slots, and R-KV-style was worse than H2O at 512.

The obvious next step is WFL with question-window weights instead of H2O's, which might keep the retrieval wins and the summary coverage at once. I haven't run that.

Limitations

Run it yourself

pip install torch transformers datasets
python tests/test_policies.py
python tests/test_longctx.py                       # benchmark code, tiny random model on the CPU
python scripts/gate.py                              # needs a GPU
python scripts/run_eviction.py --n-seqs 8           # small sweep on WikiText
python scripts/analyze.py results/batch/core8k_late.jsonl --masked
python scripts/make_figures.py

# task benchmarks (A6000-sized GPU; also needs rouge, fuzzywuzzy, math-verify)
bash scripts/bench_all.sh long                      # RULER-style tasks, then LongBench
bash scripts/bench_all.sh math                      # MATH-500
python scripts/analyze_bench.py results/bench/longbench_llama31.jsonl

The engine is in subcache/engine.py, the eviction policies in subcache/policies.py, and the evaluations in subcache/evals.py; the task benchmarks are in subcache/benchmarks.py and subcache/longctx.py. Every number on this page comes from the raw results in results/.

Credit