# How Query Visibility Changes KV-Cache Compression Rankings: A Matched-Budget Audit

> Under a deployment-realistic query-agnostic protocol, only KeyDif beats trivial baselines (31/36 cells), while SnapKV loses to them, with per-method drops ordered by how much the question is visible in each scoring signal.

- **Source:** [arXiv](https://arxiv.org/abs/2607.11942)
- **Published:** 2026-08-17
- **Permalink:** https://picx.dev/p/RxY43P
- **Whiteboard:** https://picx.dev/p/RxY43P/image

## Summary

## Summary (Overview)

- **Core finding**: Query visibility fundamentally changes which KV-cache compression methods win. Under the deployment-realistic query-agnostic protocol (compress once, query many times), only KeyDif consistently beats trivial baselines (31/36 cells), while SnapKV—the most widely deployed method—loses to "keep the start and recent window" on average (−0.066).
- **Mechanistic hypothesis**: The per-method drop from query-aware to query-agnostic protocols (Δ) is ordered consistently with how visible the question is in each method's scoring signal, ranging from Δ=+0.198 for SnapKV (question fills its 64-token observation window) to Δ=+0.011 for KeyDif (no query term in its score).
- **Methodological hazards discovered**: An attention-backend confound (eager vs. sdpa shifts pooled accuracy by −0.221, larger than most method-vs-baseline gaps) forced withdrawal of H2O's ranking claim; a tokenizer-dependent benchmark length issue silently zeroed 7 of 13 RULER subtasks for gemma-2.
- **Scale**: 144,300 paired evaluations on RULER-8192 and 40,800 on LongBench across three 7–9B open models, with 50,000-resample paired bootstrap throughout.

## Introduction and Theoretical Foundation

The paper addresses a critical mismatch between how KV-cache compression methods are evaluated and how they are deployed:

- **The evaluation protocol problem**: Most KV-cache compression research evaluates with the query appended to the context *before* compression runs (query-aware protocol). This matches a deployment where every question re-reads and re-compresses the document—a setting where the KV cache buys almost nothing, because the dominant cost (prefill) is paid again per question.
- **The economic case for compression**: The economically interesting deployment is *compress once, query many times*—a contract interrogated by dozens of questions. Here compression is necessarily query-agnostic: the question does not exist yet when eviction happens.
- **Prior work**: SCBench (Li et al., 2025) documented qualitatively that query-dependent methods degrade when the query is unavailable. A recent line of methods (KVzip, Compactor, ExpectedAttention) is explicitly designed query-agnostic. What the literature lacked is a *controlled, per-method quantification* of query dependence.

**The research question**: Under a matched budget, how much of each published method's reported gain survives the move from query-aware to query-agnostic compression—and does the size of the drop track how the method's scoring signal uses the question?

## Methodology

### Design Principle: One Variable

A cell of the audit fixes (model, benchmark axis, compression ratio, protocol arm) and varies only the compression method (called "press"). Within a cell, every press answers the same 650 instances with the same decoding (greedy, fixed max_new_tokens) at the same cache budget (uniform compression ratio $r \in \{0.25, 0.5, 0.75, 0.9\}$). A Full-Cache anchor ($r=0$) calibrates each cell's headroom.

### Methods Audited

**Six real presses** (from NVIDIA kvpress 0.5.4):
- **SnapKV**: scores tokens by attention from the last 64 positions ("observation window")
- **H2O**: keeps "heavy hitters" by accumulated attention mass
- **TOVA**: uses the final token's attention
- **ExpectedAttention**: scores by an analytic estimate of future query attention
- **AdaKV**: reallocates a SnapKV-style budget per-head
- **KeyDif**: keeps tokens whose key vectors are angular outliers from the mean key direction

**Three trivial baselines**: Random eviction, Knorm (keep lowest-norm keys), StreamingLLM (keep first $n_{\text{sink}}$ + recent window). The comparison target is best-of-3 trivial—the max of the three trivial scores per cell.

### Protocol Arms

- **Query-aware**: the question is visible to the press's scoring pass
- **Query-agnostic**: the context is compressed first; the question is appended after eviction

### Benchmarks and Models

- **RULER-8192**: 13 subtasks, 650 instances, grouped into three axes—retrieval, aggregation, multi-hop
- **LongBench**: 16 English tasks × 50 instances (natural-text robustness check)
- **Models**: Llama-3.1-8B-Instruct, Qwen2.5-7B-Instruct, DeepSeek-R1-Distill-Qwen-7B (a fourth lineage, gemma-2-9b, was disqualified by a tokenizer-length issue)

### Statistical Approach

All contrasts are paired per instance with B=50,000 bootstrap resamples. Cross-model "rank flip" probabilities use joint instance-aligned resampling.

## Empirical Validation / Results

### Anchors (Full-Cache Scores)

| Model | Retrieval | Aggregation | Multi-hop |
|-------|-----------|-------------|-----------|
| Llama-3.1-8B | 1.000 | 0.964 | 0.825 |
| Qwen2.5-7B | 0.993 | 0.948 | 0.753 |
| R1-Distill-Qwen-7B | 0.667 | 0.624 | 0.285 |

R1-Distill's low anchors (it spends its budget reasoning, not retrieving) produce floor effects.

### Headline: The Protocol Decides Who Wins

**Per-press verdict vs best-of-3 trivial baseline over 36 cells:**

| Press | Query-agnostic (wins) | Query-agnostic (mean gap) | Query-aware (wins) | Query-aware (mean gap) | Δ |
|-------|----------------------|---------------------------|--------------------|------------------------|---|
| KeyDiff | 31/36 | +0.171 | 33/36 | +0.183 | +0.011 |
| TOVA | 21/36 | +0.095 | 33/36 | +0.198 | +0.103 |
| AdaKV | 16/36 | −0.018 | 28/36 | +0.154 | +0.172 |
| ExpectedAttention | 14/36 | −0.051 | 15/36 | −0.027 | +0.024 |
| SnapKV | 13/36 | −0.066 | 25/36 | +0.132 | +0.198 |
| H2O† | 4/36 | −0.133 | 9/36 | −0.112 | +0.021 |

†H2O runs on the eager backend while every other row runs on sdpa; the backend confound makes its ranking unresolvable.

Under the aware protocol, four of five backend-comparable methods beat trivial baselines (reproducing the literature's picture, SnapKV +0.132). Under the agnostic protocol, only KeyDif survives.

### KeyDif's Advantage Concentrates Where Compression Is Hardest

Per-axis mean gap vs best-of-3 trivial (agnostic arm, 12 cells per entry):

| Press | Retrieval | Aggregation | Multi-hop |
|-------|-----------|-------------|-----------|
| KeyDiff | +0.249 (12/12) | +0.201 (11/12) | +0.064 (8/12) |
| TOVA | +0.115 (7/12) | +0.124 (8/12) | +0.047 (6/12) |
| AdaKV | −0.021 (4/12) | −0.042 (5/12) | +0.009 (7/12) |
| ExpectedAttention | −0.067 (4/12) | −0.116 (2/12) | +0.030 (8/12) |
| SnapKV | −0.092 (3/12) | −0.088 (3/12) | −0.018 (7/12) |
| H2O† | −0.232 (0/12) | −0.129 (2/12) | −0.037 (2/12) |

The single sharpest cell (Qwen2.5-7B, retrieval, r=0.9, anchor 0.993): KeyDif 0.663, TOVA 0.260, StreamingLLM 0.100, AdaKV 0.093, ExpectedAttention 0.090, SnapKV 0.077, Knorm 0.003, H2O 0.003, Random 0.000. Under the aware protocol, SnapKV recovers to 0.230 and TOVA to 0.500—seeing the question is worth 3× to SnapKV.

### Leave-One-Out and Selection Debias

- Best-of-6-real vs best-of-3-trivial: real wins 34/36 (agnostic), but removing KeyDif collapses the verdict to 25/36—the agnostic-arm "real methods win" story is a one-method story.
- Debiasing by expectation over all $\binom{6}{3} = 20$ matched best-of-3 subsets: agnostic 34→29/36; aware 34→34/36.

### Natural Text: KeyDif Keeps Validity, Loses Monopoly

On LongBench (agnostic), KeyDif's mean gap vs best-of-3 trivial:

| Model | r = 0.5 | r = 0.75 |
|-------|---------|----------|
| Llama-3.1-8B | +0.019 | +0.055 |
| Qwen2.5-7B | +0.072 | +0.088 |
| R1-Distill | −0.011 | −0.017 |

Validity survives on healthy-anchor models, but exclusivity does not: on natural text other real presses catch up (Qwen r=0.75: TOVA +0.105 > KeyDiff +0.088; Qwen r=0.5: ExpectedAttention +0.084 > KeyDiff +0.072).

### The Attention-Backend Confound

Re-running FullCache, KeyDif and StreamingLLM under eager on Qwen2.5-7B (agnostic) with exact instance pairing:

$$\text{pooled score}(\text{eager}) - \text{score}(\text{sdpa}) = -0.221, \quad 95\% \text{CI} [-0.255, -0.188]$$

The uncompressed FullCache row falls 0.897 → 0.611 (−0.286) on a model where the two backends are mathematically equivalent. The divergence is numerical (fp16 accumulation-order differences flip an early greedy argmax), not semantic.

### The Tokenizer-Length Trap

RULER's nominal "8192" is counted in a reference tokenizer; gemma-2's tokenizer renders the same contexts as up to ~10,600 tokens, overrunning its positional budget on 7 of 13 subtasks. On those subtasks, gemma's uncompressed FullCache scores 0.000 while scoring 0.907–0.925 on the six that fit.

## Theoretical and Practical Implications

### The Mechanistic Hypothesis

The measured deltas are ordered consistently with how visible the question is to each scoring signal:

| Press | Scoring signal (source) | Question's visibility | Δ |
|-------|------------------------|----------------------|---|
| SnapKV | attention from last 64 tokens (pooled) | fills the window | +0.198 |
| AdaKV | SnapKV's scorer, head-adaptive | same window | +0.172 |
| TOVA | attention from the last token | 1 noisy query token | +0.103 |
| ExpectedAttention | analytic future-query estimate | not directly observed | +0.024 |
| H2O | attention summed over all ~8,200 positions | ≈0.4% of the sum | +0.021 |
| KeyDiff | $-\cos(k_i, \bar{k})$; no query term | zero | +0.011 |

**The hypothesis**: Δ grows with the fraction of the scoring signal contributed by the question. Methods whose observation window is "the end of the context" are not measuring which tokens are *important*; they are measuring which tokens are *relevant to whatever happens to sit at the end*—in query-aware evaluation, the answer key itself.

### Practical Implications

- **Deployment decisions**: Under query-agnostic compression (the economically relevant setting), most published methods' advantages evaporate. Practitioners should benchmark against the trivial "keep start + recent window" baseline.
- **Evaluation practice**: Any audit mixing attention backends across arms carries a hidden ~0.2 confound; benchmark nominal lengths are tokenizer-dependent and can silently invalidate results.
- **Design guidance**: Query-agnostic design does not by itself guarantee agnostic-protocol wins (ExpectedAttention still loses to trivial baselines); the scoring signal's independence from the query is what matters.

## Conclusion

Under a matched budget, a substantial part of what the audited methods' query-aware scores measure is access to the question—an input that cache reuse, the very deployment that motivates compression, cannot provide. The dependence is ordered by the question's visibility in each scoring signal, legible in source code, and the one method with no query term is the one whose performance the protocol cannot touch—an ordering advanced as a mechanistic hypothesis awaiting direct manipulation.

The audit was built to be adversarial to its own conclusions—trivial baselines, paired statistics, leave-one-out, selection debias, backend controls—and it overturned its author's first headline, withdrew a ranking (H2O), and disqualified a model (gemma-2). What survived is correspondingly harder to explain away.

**Future directions**: Extending the audit to purpose-built query-agnostic methods (KVzip, Compactor); testing at 32k–128k context lengths where the "recent window" fraction shrinks; head- or layer-adaptive budget allocation under an agnostic protocol; and establishing the visibility hypothesis quantitatively via continuous query-sensitivity measures (e.g., counterfactual query selection overlap, graded query exposure at compression time).

---

_Markdown view of https://picx.dev/p/RxY43P, served by PicX — AI-generated visual whiteboard summaries of research papers._