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.
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
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.
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.
Illustrative only. In the real engine this runs per layer and per attention head over thousands of slots.
Setup
- Hardware: one RTX 2080 Ti (11 GB), fp16. An RTX A6000 in the same box was used to check the speed result.
- Models: deepseek-coder-1.3b for the main results; TinyLlama for early experiments.
- Data: real coding-agent sessions from
nebius/SWE-rebench-openhands-trajectories, plus WikiText as a control with almost no repetition. - Metric: perplexity on the part of each sequence where the cache is actually over budget, with all policies run on the same sequences (paired comparison, 95% bootstrap intervals).
- Other baselines: sliding window, random, an R-KV-style importance-minus-redundancy score, and several PRISM objectives.
Result 1: eviction is worth it, mostly because of memory
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
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
I measured how repetitive each dataset is: how often a run of 16 tokens has already appeared earlier in the same sequence.
| Data | Repetition | Weight 0.25 | Weight 1 |
|---|---|---|---|
| WikiText | 0.2% | No | Mixed |
| Start of an agent session | 8% | No | Worse |
| First 16k tokens of an agent session | 16% | No | Worse |
| 24k tokens into an agent session | 26% | Yes, at every budget | Yes, 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
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% | |
|---|---|---|---|---|
| Window | 51.6 | 31.7 | 18.7 | 8.7 |
| H2O | 59.7 | 26.4 | 11.7 | 4.9 |
| R-KV-style | 90.8 | 93.6 | 91.6 | 91.1 |
| WFL | 59.3 | 38.7 | 14.9 | 4.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% | |
|---|---|---|---|---|
| Window | 43.2 | 40.1 | 37.0 | 33.4 |
| H2O | 51.0 | 46.9 | 44.8 | 41.0 |
| R-KV-style | 51.8 | 50.2 | 49.1 | 44.4 |
| WFL | 51.2 | 48.0 | 46.4 | 41.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.
| 2048 | 1024 | 512 | 256 | |
|---|---|---|---|---|
| Window | 60 | 60 | 25 | 15 |
| H2O | 55 | 60 | 65 | 45 |
| R-KV-style | 70 | 45 | 45 | 40 |
| WFL | 60 | 65 | 70 | 50 |
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
- Because the machine was CPU bound, the true effect of a smaller cache on step speed is hard to know: decode speed was identical at every cache size.
- The perplexity results use small models (1.3B and 1.1B parameters), and perplexity isn't the same as an agent actually finishing its task.
- The task benchmarks use bigger models but small subsets: 10 to 20 examples per task, LongBench prompts cut to 16k tokens, only the easiest MATH levels, a 4,096-token generation cap and one sample per problem. Many of their intervals are ±10 points or wider.
- The RULER-style tasks are my own reimplementation with a WikiText haystack. To keep selection fast on long prompts, WFL only chose among the older tokens that H2O ranks highest, twice as many as it had slots to fill. None of the task numbers should be compared with published tables, and I didn't report their timings because the GPU was shared with other jobs.
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
- H2O: Zhang et al., 2023
- PRISM: Kothawade et al., AAAI 2022
- R-KV: Cai et al., NeurIPS 2025
- Agent trajectories:
nebius/SWE-rebench-openhands-trajectories(CC-BY-4.0) - LongBench: Bai et al., ACL 2024
- RULER: Hsieh et al., COLM 2024
- MATH: Hendrycks et al., NeurIPS 2021 (MATH-500 subset from Lightman et al., 2023)