🤖 machine learning

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

This paper reveals that evaluating KV-cache compression methods under a realistic, query-agnostic protocol—where compression occurs before seeing the question—significantly alters performance rankings compared to standard query-aware evaluations, often causing advanced methods like SnapKV to underperform simple baselines while highlighting KeyDiff as the most robust solution.

Original authors: Daming Luo, Christy Liang, Junyu Xuan

Published 2026-07-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daming Luo, Christy Liang, Junyu Xuan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library of books (the "context") and you want to build a super-smart assistant that can answer questions about them. But here's the catch: your assistant's brain (the "KV cache") is tiny. It can't hold every single page of every book at once. So, you need a librarian to throw away the boring pages and keep only the important ones before the assistant starts reading.

For a long time, researchers tested these librarians with a sneaky trick: they let the librarian peek at the question before they started throwing pages away. It's like asking the librarian, "Hey, we're going to ask about the dragon, so please keep the dragon pages!" Of course, the librarian does a great job. They keep the dragon pages and toss the rest. Everyone cheers and says, "This librarian is a genius!"

But in the real world, that's not how it works. In a real app, you compress the library once to save space, and then later, hundreds of people might ask different questions. The librarian has to throw away pages without knowing what the question will be. This is the "query-agnostic" reality.

This paper is a massive, fair audit that asked: What happens when we stop letting the librarian peek at the question?

The Big Surprise: The "Genius" Librarians Fail

The authors ran a huge experiment with 144,300 test cases using three different AI models. They tested six popular "librarian" methods against three super-simple, boring strategies (like "keep the first page and the last few pages" or "keep random pages").

Here is the twist: When the librarian couldn't see the question, almost all the "fancy" methods crashed.

SnapKV, the most popular method in the industry, actually performed worse than the simple "keep the start and the end" strategy. On average, it lost by a small but clear margin.
Out of the five methods they could fairly compare, only one kept winning even when blind to the question: KeyDiff.

The paper suggests that the reason the other methods failed is that they were secretly cheating. They weren't actually measuring "what is important in the book"; they were measuring "what is relevant to the specific question sitting right in front of me." When you take the question away, their scoring system goes haywire.

The "Blind" Librarian Who Won

KeyDiff is the only method that didn't need to peek. Instead of looking at attention (which is like looking at what the AI is focusing on), it looks at the "shape" of the information. It keeps pages that are weird or unique and throws away pages that are repetitive and boring. Because it doesn't care about the question at all, it works perfectly whether the question is there or not.

The paper measured this "cheating" effect precisely. For SnapKV, the performance jumped by +0.198 just because it got to see the question. For KeyDiff, the jump was almost zero (+0.011). The authors propose a hypothesis: the more a method's scoring system relies on the question being visible, the bigger the drop in performance when the question is hidden.

The "Gotchas" the Authors Caught

The paper didn't just test the librarians; it also found two massive traps that could ruin any future test:

The "Engine" Trap: One method, H2O, requires a specific type of computer engine (called "eager") to run, while the others use a different one ("sdpa"). The authors found that just switching engines changes the results by -0.221—a huge difference that is bigger than the gap between the best and worst librarians! Because of this, they had to withdraw any ranking for H2O. You can't compare apples to oranges, and you can't compare librarians running on different engines.
The "Ruler" Trap: The test they used (RULER) claims to test up to 8192 tokens. But for one specific model (gemma-2), the way it counts words is different. The "8192" limit actually overflowed by 30%, causing the model to fail silently on 7 out of 13 tasks. It wasn't that the librarian was bad; it was that the ruler was broken for that specific model.

What This Means for the Future

The authors are very careful not to say they have found the "perfect" solution. They found that KeyDiff is the only one that works well when you don't know the question, but on natural text (like real stories), other methods catch up to it.

The main takeaway is a warning to the whole AI community: Don't trust test results where the AI gets to peek at the answer before it starts working. If a method only works when it sees the question, it's not a good compression tool for real-world reuse. The paper proves that for a method to be truly useful, it must be able to compress the library blindly, and right now, most of the "fancy" methods aren't ready for that job.

Technical Summary: How Query Visibility Changes KV-Cache Compression Rankings

1. Problem Statement

The prevailing literature on KV-cache compression evaluates methods under a query-aware protocol, where the benchmark question is appended to the context before the compression algorithm runs. In this setting, the compressor's scoring mechanism can "see" the question, allowing it to prioritize tokens relevant to that specific query.

However, the primary economic motivation for KV-cache compression is reuse: compressing a document once to answer many future questions. In this deployment scenario, compression must be query-agnostic (occurring before any question is seen). The paper identifies a critical gap: existing evaluations do not quantify how much of a method's reported performance gain is an artifact of seeing the question versus genuine information retention. The authors ask: 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?

2. Methodology: A Matched-Budget Audit

The authors conducted a rigorous, controlled audit rather than proposing a new compression method. The experimental design isolates the "protocol" variable while holding all other factors constant.

Scope: The audit covers six published compression methods (SnapKV, H2O, TOVA, ExpectedAttention, AdaKV, KeyDiff) and three trivial baselines (Random eviction, Key-norm, and StreamingLLM's "start + recent window").
Models & Benchmarks: Evaluations were performed on three open 7–9B models (Llama-3.1-8B, Qwen2.5-7B, DeepSeek-R1-Distill-Qwen-7B) across two benchmarks:
- RULER-8192: 13 subtasks (retrieval, aggregation, multi-hop) with 650 instances.
- LongBench: 16 natural English tasks (50 instances each) used as a robustness check.
Protocol Arms:
- Query-Aware: The question is visible during the scoring pass.
- Query-Agnostic: The context is compressed first; the question is appended only after eviction.
Controls:
- Matched Budget: All methods use identical compression ratios ( $r \in \{0.25, 0.5, 0.75, 0.9\}$ ) and decoding settings (greedy).
- Paired Statistics: Every instance is evaluated under both protocols, allowing for paired bootstrap resampling ( $B=50,000$ ) to measure the delta.
- Baseline Anchoring: Methods are compared against a "best-of-3" trivial baseline to ensure gains are not just over trivial heuristics.
Scale: The audit generated 144,300 paired records on RULER and 40,800 on LongBench, with strict coverage checks to prevent OOM-induced data holes.

3. Key Contributions

A. Quantitative Measurement of Query Dependence

The audit reveals that the protocol choice fundamentally alters performance rankings.

The Flip: Under the query-aware protocol, four of the five comparable methods outperform the trivial baselines. Under the query-agnostic protocol, this picture inverts: only KeyDiff consistently beats the best-of-3 trivial baseline (winning 31/36 cells), while the widely deployed SnapKV actually underperforms the "keep start + recent window" baseline (average gap of -0.066).
The Delta: The performance drop between protocols varies by method. SnapKV suffers a massive drop ( $\Delta = +0.198$ ), whereas KeyDiff's performance remains stable ( $\Delta = +0.011$ ).

B. Mechanistic Hypothesis: Visibility Tracks Performance

The authors propose a mechanistic hypothesis: the magnitude of the performance drop ( $\Delta$ ) is ordered consistently with the visibility of the question within the method's scoring signal (as seen in source code).

High Visibility: SnapKV and AdaKV use an observation window (last 64 tokens) that is filled by the question in the aware protocol. They show the largest drops.
Low/No Visibility: KeyDiff scores based on key-vector angular outliers from the mean, containing no query term in its score calculation. It shows the smallest drop.
Evidence: This is presented as ordinal evidence across six methods, not a fitted quantitative law. The hypothesis suggests that query-aware scores often measure "query relevance" rather than the "information importance" required for cache reuse.

C. Identification of Evaluation Hazards

The audit surfaced two reproducible methodological hazards that can silently corrupt evaluations:

Attention-Backend Confound: Swapping the attention backend (e.g., sdpa vs. eager) on an uncompressed model shifted RULER accuracy by -0.29. This shift is larger than most method-vs-baseline gaps. Consequently, the authors withdrew all ranking claims regarding H2O, which requires the eager backend, as its deficit is observationally inseparable from the backend difference.
Tokenizer-Dependent Benchmark Length: RULER's nominal "8192" token limit is counted in a reference tokenizer. For gemma-2, the same context renders as ~10,600 tokens, overflowing its positional budget and causing 7 of 13 subtasks to score 0.000 even without compression. This disqualified gemma-2 from the audit.

4. Results and Findings

RULER Results: In the query-agnostic setting, KeyDiff is the only method that consistently beats the trivial baselines, particularly in high-compression retrieval tasks. Other methods (SnapKV, AdaKV, TOVA) rely heavily on seeing the question to achieve their reported gains.
LongBench Results (Natural Text): On natural prose, KeyDiff remains valid (beating baselines) but loses its exclusivity. Other methods (TOVA, ExpectedAttention) catch up or overtake KeyDiff in specific configurations. This suggests RULER's synthetic "haystack" (repetitive text) disproportionately favored KeyDiff's outlier-detection mechanism, inflating its uniqueness but not necessarily its general effectiveness.
Retraction of Cross-Model Flips: An earlier snapshot of the data suggested models disagreed on whether real methods beat trivial ones (rank flips). After filling OOM holes and completing the roster, these flip probabilities dropped to near zero, indicating the initial finding was an artifact of incomplete data and floor effects in the reasoning-tuned model (R1-Distill).

5. Significance and Claims

The paper positions itself as a controlled, per-method quantification of the query visibility effect, rather than a new compression algorithm or an endorsement of KeyDiff.

Deployment Reality: The authors argue that for the economically interesting use case of "compress once, query many times," the query-aware evaluation protocol is misleading. Methods that rely on seeing the question to prune the cache may fail in production reuse scenarios.
Methodological Rigor: The paper demonstrates that valid audits of KV-cache compression must hold fixed not just the model and budget, but also the attention backend and tokenizer alignment.
Modest Claims: The authors explicitly state they are not claiming KeyDiff is the "best" method overall, but rather the only audited method that is both query-independent and effective across the tested families. They emphasize that the "mechanistic hypothesis" regarding visibility is supported by ordinal evidence and requires further manipulation to be proven as a quantitative law.

In summary, the paper asserts that a substantial portion of the reported gains in KV-cache compression literature is an artifact of the evaluation protocol, and that true deployment-ready methods must demonstrate efficacy without access to the future query.