Few-Round Page-Level Coverage Selection for Bounded-Memory Prefill

Long prompts make language models expensive mainly because of the key-value (KV) cache, the stored attention keys and values for every past token. This cache grows linearly with prompt length and can exceed GPU memory before generation even starts. Methods that shrink the cache by keeping only "useful" tokens have so far had to choose between two options. Cheap methods rank tokens by attention score and keep the top ones. More principled methods choose a subset that covers the prompt's content without duplicates, but they pick tokens one at a time, which is slow and sequential. We propose to make coverage-based selection as cheap and as hardware-friendly as top-k ranking. The selector would choose whole memory pages instead of single tokens, add a fixed-size batch of pages per round instead of one item per step, and run inside chunked prefill, so the cache never grows past its budget.

The opportunity comes from two literatures that have not met. Subset selection research has long studied how to take a greedy procedure that adds one best item at a time and parallelize it into a few rounds of batched decisions. Separately, KV-cache compression research has found that attention-only ranking fails in exactly the settings where coverage matters. These are prompts cached before the user's question arrives, and long reasoning traces full of repeated content. If coverage selection can be made to cost roughly what top-k costs, it becomes usable during prefill and inside paged serving engines. Today's submodular cache methods cannot reach either place.

Core Claim

The objective we optimize is a submodular function, meaning one with diminishing returns: adding an item helps less the more similar items you already hold. Our claim is that a submodular coverage objective over the prompt's own keys can be maximized at page granularity in a small, fixed number of parallel rounds. Each round adds a fixed-size batch of pages whose marginal gain exceeds a falling threshold. When this is run after every prefill chunk, three things should follow. The cache stays at a hard budget throughout prefill. Accuracy in the question-agnostic setting should beat attention-ranked eviction with adaptive head budgets. And selection time should stay a small fraction of prefill time. The new contribution is the combination of few rounds, page-sized elements, and per-chunk use during prefill, not the use of submodularity for KV caches, which has already been done.

Relation to Prior Work

The closest work is BumbleBee. It already frames KV reduction as maximizing a mix of facility location (how well chosen keys represent all keys) and attention coverage. It runs an offline greedy pass at prefill and a streaming variant during decoding. We keep its style of objective but change three things. First, BumbleBee selects single tokens with standard greedy or streaming passes, so the number of sequential steps grows with the budget. We select pages in a bounded number of rounds. Second, BumbleBee uses one mixing weight and one budget for every head. We let heads compete for pages through a single shared threshold. Third, BumbleBee does not address paged memory layouts. Our elements are the serving engine's memory blocks by construction.

Two methods motivate why coverage is needed at all. R-KV shows that in reasoning traces, repeated restatements attract attention to each other. This fools attention-only eviction into keeping duplicates. R-KV fixes the problem with a cosine-similarity penalty, which has no approximation guarantee, and its authors note that it does not fit paged attention. Ada-KV shows that heads differ: some focus sharply and others spread broadly, so a uniform budget per head is suboptimal. Ada-KV also documents that SnapKV degrades badly when the prompt is cached before the question. SnapKV votes on token importance using an attention window at the end of the prompt. Without a question in that window, its votes lose their signal. A coverage objective computed only from the prompt's keys needs no question, which is why we target this setting.

The method itself comes from the selection literature. GreeDi and its journal version Distributed Submodular Maximization work in two stages: pick local summaries on separate data partitions, then run a global greedy pass over the union. DISCOVER extends this to cover problems. Low-adaptivity algorithms such as Breaking Barriers, Practical Parallel Algorithms for Non-Monotone Submodular Maximization, and Improved Parallel Algorithm … under Knapsack Constraint replace one-at-a-time greedy with threshold rounds that add many qualifying elements at once.

Our setting is monotone, the easier case, so we expect near-greedy quality. Two complications have no direct theory behind them. Chunked prefill splits the prompt into contiguous pieces, not the random partitions that GreeDi's guarantee assumes. And we fix the batch size per round to avoid uneven GPU workloads, which standard threshold algorithms do not do. Fairly Allocating Goods in Parallel is a warning here: some greedy rules cannot be parallelized without changing what they compute. Part of our work is measuring how far our selections drift from exact greedy.

Research Program

Fix one attention layer. Let $\mathcal{P}$ be the set of candidate pairs $(h, p)$, each pairing a head $h$ with a page $p$ of $P$ consecutive tokens, where $P$ matches the serving engine's block size (we use 16). For a chosen set $S \subseteq \mathcal{P}$, the objective is

$$f(S) = \sum_{h} \sum_{i=1}^{L} w_{h,i} \max_{(h,p) \in S} \max_{j \in p} \mathrm{sim}(k_{h,i}, k_{h,j}).$$

The symbols are as follows. $L$ is the number of prompt tokens seen so far. $k_{h,i}$ is the key of token $i$ in head $h$. $\mathrm{sim}$ is a clipped cosine similarity. $w_{h,i}$ is a weight for token $i$ that does not depend on any question. Our default weight is the attention the token receives from within the prompt itself, passed through a concave function as in BumbleBee. Each term is a facility-location score, so $f$ is monotone and submodular. Because every head sums into one objective, a single budget of $B$ pages per layer is split among heads by whichever pages buy the most coverage. This plays the role of Ada-KV's adaptive head budgets, but here the split comes out of the optimization. A minimum share per head guards against starving any head.

The selector runs in a fixed number of rounds $R$. In each round it computes the marginal gain of every remaining page in parallel. This is one batched similarity-max operation against the current coverage vector. It then adds the $b = B/R$ highest-gain pages that clear the current threshold, updates coverage, and lowers the threshold. With $R$ fixed, the kernel's shapes are static. During prefill, after each chunk of $C$ tokens, the candidate set is the $B$ retained pages plus the new chunk's pages, and the selector cuts it back to $B$. Peak cache memory is therefore bounded by $B$ plus one chunk, regardless of prompt length. The same procedure, applied at a lower frequency, maintains the cache during decoding for reasoning traces.

We will build this as a selection kernel inside a paged serving engine, in the spirit of CentroidKV's vLLM integration. Evicting a page frees one block, so no compaction is needed. On the analysis side, we will report three measurements. First, the objective ratio between $R$-round selection and exact greedy, as a function of $R$ and $b$. Second, the ratio between chunked selection and selection over the full prompt at once, which tests how much contiguous partitioning costs relative to GreeDi's random partitions. Third, how often a fixed batch size forces in pages below threshold.

Baselines

The naive reference points are the full, uncompressed cache, which is an accuracy upper bound wherever it fits in memory, and random page eviction at the same budget, which is a floor. All methods run on Llama-3.1-8B, the model behind Ada-KV's question-agnostic RULER numbers, on the same GPU, at budgets of 20% and 80%. No method's hyperparameters get more than a small fixed grid tuned on a held-out RULER split.

The strongest existing method for our main question is SnapKV combined with Ada-KV's adaptive head budgets, run question-agnostically. In this setting Ada-KV reports RULER averages of 87.59 to 92.67 at an 80% budget and 44.02 to 53.29 at 20%, on Llama-3.1-8B (Ada-KV). We will rerun it under our harness instead of copying those numbers. Beating it means a higher RULER average at the 20% budget, where the gap between methods is largest, with selection overhead comparable to SnapKV's scoring.

For reasoning traces, the strongest competitor is R-KV, run on the same distilled DeepSeek-R1 Llama-8B model on MATH-500 and AIME 2024. R-KV reports near-full-cache accuracy at 10–34% of the cache and up to 40% higher accuracy than SnapKV. The file gives these only as relative figures, not absolute per-benchmark accuracies, so no absolute number is quoted here. Beating R-KV means equal or better accuracy at the same budget while running page-granular inside the paged engine, where R-KV does not run.

The closest method is BumbleBee, reimplemented with exact token-level greedy on its own objective. No numeric LongBench score from BumbleBee is in the file. CentroidKV represents merging instead of selecting. It reports 75% memory reduction and up to 4× serving throughput on vLLM, but the file has no RULER or LongBench score for it.

Three ablations isolate our ingredients. The first is exact greedy on our page-level objective, which isolates the cost of using few rounds. The second runs the same objective with token-level elements, which isolates the cost of page granularity. The third is a one-round score that sorts pages once by attention weight minus maximum similarity to higher-ranked pages, R-KV style, which isolates the value of recomputing marginal gains across rounds.

Why not just…?

Why not just keep SnapKV's top-k with pooling, since it is already a single parallel step? On standard question-at-the-end prompts it is very strong: it reports performance comparable to the full cache at 92% compression on LongBench (SnapKV). Its weaknesses are exactly our target settings. It degrades in the question-agnostic case, where Ada-KV reports a 44.02 RULER average at a 20% budget. It falls into the redundancy trap on reasoning traces documented by R-KV. And it cannot shrink memory during prefill. If our method does not beat SnapKV+Ada-KV on question-agnostic RULER at 20%, the coverage objective is not worth having, and we will report that.

Why not just run exact greedy on the GPU, since budgets are modest? This is the most serious threat to the adaptivity part of the claim. If the exact page-level greedy ablation takes a negligible share of prefill time at 128K tokens, then few rounds buys nothing. In that case the contribution shrinks to page-level coverage during chunked prefill. We will measure selection time against prefill time across lengths from 4K to 128K and budgets, and we will state where, if anywhere, sequential greedy becomes the bottleneck. Per-chunk selection runs hundreds of times per long prompt, so we expect greedy's sequential steps to add up. But this is the hypothesis being tested, not an assumption.

Why not just use a one-shot redundancy-penalized score like R-KV? A single sort with a similarity penalty is the cheapest diversity-aware option. If it matches multi-round selection, the rounds are unnecessary. The one-round ablation tests this directly. Our prediction is that it underperforms when one span is restated many times, because a single fixed penalty cannot tell the second copy of a span from the tenth. Recomputing marginal gains can.

Why not just merge similar keys into centroids, as CentroidKV does? Merging avoids selection entirely and has strong serving numbers. However, it creates synthetic keys, which requires changing the attention kernel, and it follows a manually set compression schedule. Selection keeps real tokens and their positions. We will compare at matched memory, and a CentroidKV win on RULER would mean selection is the wrong tool.

Why not just quantize weights instead? This is orthogonal. TACQ and ASVD shrink the weights, but the cache still grows linearly with context. Ada-KV notes that a cache for 2M tokens on an 8B model reaches 256GB, which dwarfs the weights. The two can be combined.

Decisive Checks

We evaluate on RULER from 4K to 128K in the question-agnostic setting (RULER), on LongBench in both question-aware and prompt-cached orderings (LongBench), and on MATH-500 and AIME 2024. Metrics are task score, peak GPU memory during prefill, time to first token, decoding throughput in the paged engine, and selection time as a fraction of prefill.

Four outcomes decide the proposal. First, the 20% question-agnostic RULER average must beat the rerun SnapKV+Ada-KV. Second, the $R$-round selector must stay within a few percent of exact greedy's objective value with $R$ near 8, and its downstream accuracy must be indistinguishable from greedy's. Third, page-level selection must lose little accuracy relative to token-level selection while remaining compatible with paged serving. Fourth, peak prefill memory must stay flat as prompt length grows, letting the method handle prompts beyond the length at which full-attention prefill runs out of memory on the same GPU. SnapKV reports 380K tokens on one A100-80GB, but under a different setup, so we will compare under our own harness.

Failing the first check kills the objective. Failing the second kills the parallelization. Failing the timing comparison against exact greedy turns this into a paper about prefill-time page coverage alone.