Memory during long-context LLM inference is dominated not by model weights but by the key-value (KV) cache, which grows linearly with context length. At 100k+ token contexts, this becomes the primary constraint on serving throughput and batch size. The two dominant training-free approaches to compressing this cache, token selection and uniform low-rank coding, each fail in structurally predictable ways. VarRate proposes a third path: allocate a variable low-rank budget to each token in proportion to its query salience, keeping every token at some nonzero fidelity rather than evicting any of them.
This matters practically because the failure modes of existing methods are not edge cases. Token selection methods like SnapKV and Ada-KV score tokens using a recent observation window that is essentially the current query. When a cache is compressed once and reused across multiple queries, as happens in prefix caching or multi-turn dialogue, that signal goes stale. Because eviction is irreversible, every token the stale signal misjudges is permanently gone, and the paper reports accuracy drops of 11-15 points on LongBench under this regime. Uniform low-rank coding avoids eviction but spends identical rank budget on trivial and critical tokens alike, wasting capacity where it is not needed and starving it where it is.
Key Contributions
The central claim is that both failure modes share a common cure: rank should be allocated, not evicted. The paper makes three concrete contributions:
- A diagnostic framing showing that query-aware selection fails because a stale signal meets an irreversible response, while uniform coding fails because it ignores salience entirely. These are complementary failures, not the same failure.
- VarRate itself: a training-free codec that assigns each token a variable low-rank budget via water-filling over a shared PCA basis derived offline from a handful of unlabeled calibration contexts. No gradients, no fine-tuning, no architecture changes.
- Empirical evidence across two model families (Llama-3.1-8B and Qwen2.5-7B) and 16 LongBench tasks that this approach stays within 0.8 points of the uncompressed model at a 20% KV budget, and degrades by only 3.5-5.5 points under query-agnostic reuse where token selection loses 11-15.
Methodology
The codec operates on a joint per-token vector formed by stacking pre-RoPE keys and values across all GQA heads. Working pre-RoPE is important: the rotary position embedding inflates the numerical rank of the key cache, making low-rank approximation far less effective after it is applied. This is consistent with prior work including Palu and DeepSeek's MLA architecture.
A strided set of anchor tokens is kept exact, and every other token is coded by its residual to a local anchor mean. A shared basis of right singular vectors is computed once offline via SVD on residuals from six unlabeled calibration contexts. The budget allocation problem then reduces to distributing integer ranks across coded tokens subject to a total budget constraint, with a nonzero floor r_min = 16 ensuring no token is dropped entirely. Water-filling over the singular value spectrum of this shared basis gives the per-token rank assignments.
The salience signal itself is borrowed directly from SnapKV: attention mass from a recent observation window. The paper tests a second-order alternative (attention squared, weighted by value-distinctiveness via the output projection) and finds it ties the default signal on both models, which is useful evidence that the allocation mechanism rather than the specific salience heuristic is doing the work.
Results and Comparisons
At a matched 20% KV budget on LongBench, VarRate achieves an average of 45.69 on Llama-3.1-8B and 48.00 on Qwen2.5-7B, against uncompressed baselines of 46.01 and 48.79 respectively. Averaged across both models, it is the strongest matched-memory compressor in the comparison set, ahead of SnapKV (46.02), Ada-KV (45.91), KIVI-2 (45.82), and PyramidKV (45.46). The uniform-rank ablation scores 43.47 on Llama and collapses to 30.50 on Qwen, a gap the paper attributes to Qwen's four-KV-head architecture being far less forgiving of a wrong allocation shape.
The comparison against KVzip deserves attention. KVzip is a purpose-built method for query-agnostic reuse that scores tokens by how well the cache reconstructs the context rather than by query attention, making it inherently robust to cache reuse. It evicts tokens, but based on a signal that does not go stale. VarRate comes within a point of KVzip's accuracy in three of four model-budget settings and is behind by a small margin in the fourth, but achieves this at roughly one-eighth of KVzip's prefill overhead, since KVzip requires re-encoding the entire context with the full model.
Against quantization, VarRate ties KIVI-2 at matched memory on Llama and beats it on Qwen. KIVI-4 uses 31% of the cache rather than 20%, so it is not a matched comparison, though it performs well where it does. The paper confirms that quantization and VarRate compose, which is the sensible practical outcome.
A cross-validation on Mistral-7B-Instruct-v0.2 replicates the main pattern: the uniform-rank codec collapses to 29.1 on passage retrieval at a 15% budget, VarRate recovers to 73.6 against a 75.6 ceiling, and the relative ordering of methods holds.
Limitations and Open Questions
Several limitations are worth flagging. The shared basis is calibrated offline on six unlabeled contexts, which is minimal and presumably sufficient for the tasks tested, but the sensitivity of the basis quality to calibration data distribution is not explored in depth. For highly domain-specific deployments this could matter.
The paper is also honest that VarRate does not beat every baseline in every setting. Against KIVI-4 at its actual memory footprint (31%), quantization wins on summarization tasks across all three models. The authors acknowledge this and frame quantization as orthogonal and composable rather than competing.
The decode-time overhead of reconstructing tokens from their low-rank codes is not discussed in detail. The paper focuses on compression cost relative to KVzip's prefill overhead, but for latency-sensitive serving the decode reconstruction cost matters too.
More broadly, the paper's framing of the problem as a choice between allocation and eviction is clean and useful, but the interaction with speculative decoding, continuous batching, and paged attention systems like vLLM is left as future work. Whether variable-rank storage integrates cleanly with these serving infrastructures is a real engineering question.
The core insight, that making a cheap signal survivable is more efficient than paying to replace it, is well-supported by the evidence and has clear implications for how practitioners should think about cache compression under reuse. The training-free property is genuinely useful: it means VarRate applies to any off-the-shelf model without access to training infrastructure or proprietary data.
Full paper: arxiv.org/abs/2607.15498