PaperlayerView exact revision on arXiv

Source-linked AI summary

Beyond Sparse Weights: When Is Attention Compressible?

Chiwun Yang, Xiaoyu Li

arXiv:2608.21541v1cs.LGcs.CL

TL;DR

The paper asks when sparse-looking attention actually licenses KV-cache compression, separating mass coverage, output fidelity, and task utility. It analyzes score gaps, omitted weighted values, and retrieval–aggregation behavior, then proposes CertKV. CertKV is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype.

  • Problem

    Sparse attention can mean threshold sparsity, fixed-mass support, output compression, or task preservation, and these properties are not equivalent.

  • Method

    The paper analyzes score-gap coverage, exact omitted weighted-value corrections, and task-dependent retrieval–aggregation behavior to design training-free CertKV.

  • Results

    CertKV has a top-two compressed point estimate in seven of nine LongBench-v2 settings, forms a leading compressed tier on 128K RULER, and realizes a nominal 10× persistent-KV budget in a packed Llama prototype.

  • Takeaways & Limitations

    Attention compressibility is a contract among retained mass, omitted values, future queries, and task rather than a property of sparse-looking weights alone.

  • Takeaways & Limitations

    The fixed-row minimality result does not provide a lower bound for one output, nonlinear compression, or an unseen future-query KV cache.

Abstract

from arXiv · show

KV-cache compression is often justified by attention maps with a few large weights. This is incomplete: large weights may not contain most of the mass, omitted values can cancel, and preserving the attention output may not preserve the task. We separate these questions. Global score gaps -- not threshold counts -- determine how many tokens are needed to retain a target mass. For a realized row, the weighted sum of omitted values is the exact missing statistic. A controlled retrieval--aggregation model explains when truncation helps and when it hurts. These results motivate CertKV, a training-free compressor that reserves one tail-summary slot per head and allocates the rest by value dispersion. Under matched budgets, CertKV is top-two in seven of nine LongBench-v2 settings, remains in the leading compressed tier on 128K RULER, and realizes a ten-fold cache budget in a packed Llama prototype. Compressibility depends on the mass, values, future queries, and task -- not on a sparse-looking map alone.

1 Introduction

The paper argues that sparse-looking attention does not by itself justify KV-cache compression. It separates mass coverage, attention-output fidelity, and task utility, then uses these distinctions to motivate CertKV.

  • 1 Introduction: KV-cache compression must account for future-query state and downstream computation, not merely bright entries in an attention map.The cache stores key–value state rather than a heat map.
  • 1 Introduction: Large-weight counts, target-mass support, output-preserving state, and task-preserving state are distinct objects.The paper identifies these as four separate questions.
  • 1 Introduction: Global score-gap geometry determines target-mass coverage: Gaussian initialization-scale scores may require an asymptotic 0.61 fraction for 90% coverage.A logarithmic lower gap envelope above unit slope permits a length-independent budget, while a sub-unit upper envelope forces growth.
  • 1 Introduction: The exact fixed-row correction for omitted tokens is their weighted value sum, which may cancel or reinforce the retained contribution.Under a stronger all-sub-budget linear-sketch requirement, kept values plus one tail aggregate attain the matching (|S| + 1)d dimension bound.
  • 1 Introduction: Task utility can favor renormalized top-k for retrieval-like targets while exact attention remains preferable for aggregation.A planted-token model explains this transition and shows that output fidelity is not sufficient to determine task utility.
  • 1 Introduction: CertKV reserves one tail-summary slot per KV head and allocates remaining slots using value dispersion within a matched physical budget.It ranks tokens from SnapKV’s observation window and stores a weighted key–value tail summary.

2 Related Work

Related work spans cache selection, attention approximation, score scaling, and theories of concentration. The paper distinguishes its coverage, output-fidelity, and task-utility analyses from these neighboring approaches.

  • KV-cache compression: Prior KV-cache methods select tokens using cumulative scores, observation windows, query-aware selection, summaries, sinks, values, or head-specific budgets.The cited methods include H2O, Scissorhands, TOVA, SnapKV, Quest, InfLLM, StreamingLLM, VATP, Ada-KV, and related systems.
  • Threshold counts and attention approximation: Threshold-count analyses approximate attention under idealized assumptions but do not determine selected probability mass, value-dependent output error, or task utility.This paper makes those three quantities explicit.
  • Softmax dispersion and logit scaling: Logit scaling and softmax-dispersion work alter the score scale, whereas this paper’s criterion uses global log-rank gap slope for mass coverage.A lower envelope steeper than log j supports fixed-length coverage budgets, while an upper envelope below unit slope forces growth.
  • Theory of attention concentration: The planted-token analysis complements concentration theories by characterizing when renormalized selection suppresses a noisy bulk before the signal dominates full softmax.This connects the paper’s task-dependent utility analysis to retrieval-oriented attention theory.

3 From Sparse Weights to Attention Compressibility: Three Separations

“Sparse attention” separates threshold counts, fixed-mass coverage, output fidelity, and task utility. The paper shows that score gaps govern coverage, omitted values govern output correction, and task targets determine whether truncation helps.

  • Four distinct properties—threshold count, fixed-mass support, output representation, and task preservation—are not interchangeable.The paper frames compressibility as requiring an explicitly specified metric and contract.
  • Coverage: Fixed B, W, κ, and d prevent logit scale from growing with context length, but do not imply a favorable gap profile.The relevant coverage object is the ranked-logit gap profile, not merely the scale or count of large weights.
  • Coverage: A global gap slope above one permits a length-independent target-mass budget, whereas a sub-unit slope requires a growing budget.At slope zero, the required budget is Θ(n); the all-rank condition and lower-order terms matter at the unit-slope boundary.
  • Coverage: At σ = 1 and η = 0.1, logarithmic large-weight count coexists with about 0.61 kept fraction, yielding only 1.6× coverage compression.A 4K-fitted profile can miss the measured 128K coverage budget by more than 1.5×, so cross-length stability must be checked.
  • Output fidelity: For a realized row, the omitted weighted value sum is the exact additive correction, and omitted values may cancel or reinforce.The stronger linear-sketch result uses kept values plus one tail aggregate, but does not establish a lower bound for nonlinear compression or future-query caches.
  • Task utility: In the planted-token regime, renormalized top-k can outperform exact attention for retrieval-like targets, while exact attention remains preferable for aggregation.This requires retained-bulk diffuseness; downstream measurements show that one mixture coordinate does not adequately describe real tasks.
  • Design implications: Cache compression should estimate coverage, summarize omitted values, model future-query reweighting, and evaluate the resulting state on the target task.These principles motivate a workflow that treats compressibility as a contract among score geometry, value geometry, future queries, and task.

4 CertKV: Value-Aware Compression under Exact Budgets

CertKV implements value-aware cache compression by reserving one tail-summary slot per head, allocating remaining slots by omitted-value dispersion, and enforcing the physical budget exactly. Under matched budgets, it is competitive across LongBench-v2 and RULER while realizing a ten-fold persistent-KV reduction in a packed Llama prototype.

  • Design: CertKV combines observation-window score selection, value-dispersion allocation, and one synthetic KV pair per head.The synthetic pair approximates the future conditional tail from the eviction-time observation window.
  • Tail summary: The conditional importance distribution within each evicted tail supplies key and value centroids for its synthetic pair.The tail distribution is formed from normalized importance weights over evicted tokens.
  • Allocation: CertKV allocates more slots to heads whose omitted tails carry more mass or are harder to summarize by one value.The allocation uses a tight envelope within the declared mass–centroid–second-moment summary class.
  • Exact budgets: CertKV charges one aggregate per head and uses deterministic best-marginal repair to satisfy the global slot budget exactly.The construction also imposes a minimum real-token allocation per head.
  • Evaluation: CertKV has a top-two compressed point estimate in seven of nine LongBench-v2 settings under matched budgets.The grid is interpreted as evidence for a competitive operating point, not a universal method ranking.
  • Evaluation: At 128K RULER, CertKV and Ada-KV form the leading compressed tier, with CertKV scoring 73.6±17.9 on Llama and 61.5±21.0 on Qwen.The task-bootstrap uncertainty is wide, and the 128K evaluation uses 3% subsets with Qwen using YaRN.
  • Systems result: The packed Llama prototype realizes a nominal 10× persistent-KV budget, reducing 64K storage from 8.59 to 0.86 GB.Decode peak memory falls from 23.11 to 16.34 GiB relative to the full cache; latency gains are not established.

5 Evidence for the Three Separations

The evidence separates count sparsity from mass coverage, fixed-row output fidelity, and task utility. Across experiments, short-context count trends do not provide transferable coverage budgets, exact tail aggregates outperform generic controls for realized rows, and controlled task behavior does not fully predict real-task ordering.

  • Count sparsity: 99.87±0.22% of eligible gpt-oss heads show sublinear large-weight-count growth, versus 98.93±0.66% for Llama-8B and 96.05±0.53% for Llama-70B.The result establishes finite-range count sparsity, not cheap probability-mass coverage.
  • Coverage: A 4K gap-profile fit misses the measured 128K coverage budget by more than 1.5× despite beating its within-head shuffle on five of six anchors.A(1), and therefore concentration, changes with length even when normalized count remains small.
  • Output fidelity: The true weighted tail aggregate exactly reconstructs the realized attention output at 4K with k = 64, while tested controls are worse than keeping no extra statistic.This is a fixed-row diagnostic, not evidence for unseen future queries.
  • Task utility: The controlled task recovers a transition where top-k helps retrieval after retaining the planted signal, while exact attention remains preferable for aggregation.The analogous real-task coordinate does not predict method ordering, and trained entmax improves at 4× and 8× while 16× and 32× intervals include zero.
  • Evidence synthesis: The experiments rule out using count as a transferable coverage budget, generic tail moments as fixed-row summaries, or one controlled coordinate as a real-task predictor.The mechanisms instantiate cleanly only where additional structure supports them.

6 Discussion

The paper treats attention compressibility as a contract involving coverage, omitted values, future queries, and task targets rather than as a heat-map property. It therefore separates descriptive sparsity from guarantees and identifies unresolved theoretical boundaries.

  • 6 Discussion: Attention sparsity comprises distinct questions about threshold counts, mass coverage, omitted values, and task-read value directions.The paper states that none of the transitions between these objects follows without additional assumptions.
  • 6 Discussion: Count curves are not memory budgets, and coverage predictors require validation under length transfer.A fixed-length profile can fail to predict behavior at a longer context.
  • 6 Discussion: A fixed-row tail aggregate does not automatically provide a future-query cache guarantee.Future-query guarantees require statistics available before eviction, including tail normalization and conditional-value information.
  • 6 Discussion: Multi-layer error propagation, pre-eviction future-query bounds, and theory for crossing the γ = 1 coverage boundary remain open problems.These are identified as mathematical gaps rather than results already resolved by the experiments.

7 Conclusion

The conclusion frames compressibility as a contract among retained mass, omitted values, future queries, and task requirements. It summarizes the paper’s coverage, fixed-row, and task-conditional results while limiting the claims about future queries and multilayer behavior.

  • 7 Conclusion: Attention compressibility depends on retained mass, omitted values, future queries, and task targets, not on sparse-looking maps alone.The paper presents this decomposition as the central conclusion.
  • 7 Conclusion: Theorem 3.6 separates threshold counts from mass coverage through global score-gap conditions.Above unit log-rank slope, fixed-mass budgets can be length-independent; below it, budgets grow.
  • 7 Conclusion: Theorem 3.7 identifies the omitted weighted value sum as the exact missing statistic for a realized attention row.Under the stronger linear-sketch requirement, retained values plus one tail aggregate meet the matching dimension bound.
  • 7 Conclusion: Theorem 3.8 shows that task structure can reverse the ordering of exact and top-k attention in a controlled model.Retrieval-like targets can favor denoising, whereas aggregation targets can favor exact attention.
  • 7 Conclusion: The appendix scopes the proofs to one realized row and an explicit planted model, without asserting an unconditional future-query guarantee.The appendix also documents CertKV’s construction, allocation rule, experiments, cache measurements, and reproducibility procedures.

B.4 Task-conditional denoising

The controlled planted-token model analyzes when truncation denoises retrieval-like targets and when exact attention remains preferable for aggregation. Its ordering result depends on explicit bulk-diffuseness assumptions and does not transfer directly to downstream performance.

  • B.4 Task-conditional denoising: The exact and top-k planted-token weights determine the crossover through their relative placement in the estimator.The analysis distinguishes the planted-token weight under full softmax from that under top-k renormalization.
  • B.4 Task-conditional denoising: The controlled model predicts an ordering change between exact and top-k attention as task-relevant signal and noisy bulk are weighted.The value-aware oracle is no worse than the score-selected subset under the stated comparison.
  • B.4 Task-conditional denoising: Retrieval-like targets can benefit from suppressing diffuse noisy bulk, while aggregation targets can prefer exact attention.The planted token may enter top-k before dominating the full softmax.
  • B.4 Task-conditional denoising: The retained-bulk diffuseness assumption is load bearing and is not implied by rank inclusion.The proof uses this assumption to control top-k bulk fluctuations.
  • B.4 Task-conditional denoising: The controlled experiment validates the predicted ordering within the planted model, but a one-parameter estimate does not predict downstream accuracy differences.The downstream test covers retrieval and aggregation tasks and exposes the proxy’s limits.

C.1 A posteriori future-query error decomposition

The appendix separates a posteriori future-query error analysis from fixed-row reconstruction and dispersion envelopes. These results clarify what tail summaries can recover, what their guarantees require, and where minimality claims do not extend.

  • C.1 A posteriori future-query error decomposition: The future-query theorem decomposes compressed-output error into tail-summary and logit-normalization mismatches.The bound assumes unchanged retained logits and bounded values, and evaluates quantities using the omitted keys.
  • C.1 A posteriori future-query error decomposition: The future-query bound is a posteriori rather than a pre-eviction guarantee for CertKV.Exact tail log-partition and related quantities are unavailable after eviction unless omitted keys remain accessible.
  • C.1 A posteriori future-query error decomposition: For a fixed realized row, retained values plus one weighted tail aggregate recover the full output and every retained sub-budget.The matching linear-sketch dimension is (k + 1)d.
  • C.1 A posteriori future-query error decomposition: The (k + 1)d lower bound applies only to linear sketches supporting every retained sub-budget, not to one output, nonlinear summaries, or future-query caches.The scope restriction is explicit in the theorem’s discussion.
  • C.1 A posteriori future-query error decomposition: Centered value dispersion supplies a tight observation-weighted envelope for the declared summary classes, but not universal optimality over arbitrary summaries.The same mass and representative value can permit either nonzero or zero deviation, depending on the tail’s centered moment.

D.1 Supplementary diagnostics and scope checks

Supplementary diagnostics probe the scope and stability of the paper’s claims across modalities, resampled real books, trained hidden states, controlled architectures, and evaluation protocols.

  • Cross-modal scope: Neither vision nor audio passes the pre-specified clean two-mode gate for the fitted phase structure.The gate requires a sufficiently deep trough between fitted modes, not merely a non-unimodal histogram.
  • Real-book stability: 98.9%, 99.1%, and 99.4% of heads show sublinear large-weight-count growth for Llama-3.1-8B, Qwen3-8B, and Mistral-7B, respectively.These are six document/position resampling replicates over eight books, not independent training runs or corpora.
  • Distributional scope: Trained hidden states are anisotropic and heavier-tailed, with effective rank roughly 43–182 and condensed-head fractions ranging from low single digits to about 60%.The distributions vary by architecture and depth, motivating direct use of the deterministic row-wise criterion.
  • Controlled emergence: On real text, next-token accuracy rises while median kept fraction falls; shuffled-token accuracy remains near chance despite changing kept-fraction trajectories.The supported observation is the conjunction of learned task structure and attention concentration, not falling kept fraction alone.
  • Replication: Sparse-head fractions exceed the 15% guide in both controlled architectures, reaching approximately 93% for GPT-NeoX and 75% for Qwen3 on real text.Random-byte controls remain nonzero but low, supporting recurrence across these two controlled architectures without establishing an in-the-wild model-scale trend.
  • Evaluation protocol: The protocol requires at least three distinct lengths, finite document slopes, document bootstrap seed 0 with B = 5000, and BH-FDR q = 0.05.The Gemma surface is a 4K descriptive control and is excluded from growth inference.

D.3 One-factor ablations

One-factor studies separate CertKV’s component effects under matched physical budgets and report fidelity, memory, and evaluation-accounting details without overstating practical gains.

  • Evaluation design: The component study averages errors over ratio–layer–head grids, treats documents as independent units, and uses paired percentile bootstrap intervals with Holm-corrected tests.The practical-effect gate requires a negative upper confidence endpoint, pHolm < 0.05, and at least a 10% relative reduction.
  • Component effects: Adaptive allocation reduces mean relative output error from 0.405364 to 0.395369 versus true-uniform allocation, a 2.466% relative reduction.The difference is ∆= −9.995 × 10−3 with pHolm = 4.000×10−5, but remains below the 10% practical-effect threshold.
  • Component effects: Centering yields a smaller 0.203% relative error reduction over the uncentered statistic, with ∆= −8.044 × 10−4 and pHolm = 1.320 × 10−3.Both adaptive allocation and centering are statistically resolved but below the pre-specified practical-effect threshold.
  • Component effects: The charged tail summary is slightly worse than spending the same slot on one additional real token, with ∆= 1.494 × 10−4.The safeguard does not improve p95 error, although its registered mean-error non-inferiority check passes.
  • Physical memory: At 64K and 10×, packed CertKV stores 0.86 GB of persistent K/V state versus 8.59 GB for the full cache and lowers decode peak memory from 23.11 to 16.34 GiB.The packed prototype uses Llama-3.1-8B and bfloat16 storage.

D.7 Reading the domain tables

Domain-table results show architecture- and ratio-dependent competitiveness, while descriptive domain intervals and point-estimate ranks do not justify universal or domain-wise superiority claims.

  • Aggregate patterns: CertKV’s aggregate compressed scores are 26.8/26.0/24.1 on Llama, 31.0/30.0/29.0 on Qwen, and 28.0/28.2/28.2 on Mistral at 2/4/10×.The method is close to the leading point across the grid and reaches the leading Mistral average at 10×, but is not uniformly largest.
  • Interpretation limits: Domain half-widths are often 6–18 points because each domain contains only a subset of the 503 examples.The estimates localize aggregate differences but do not support separate domain significance claims or domain-wise SOTA labels.
  • Domain heterogeneity: No single domain explains the averages: strongest domains differ across architectures, ratios, and methods.This supports an architecture-dependent operating region rather than a universal method ordering.
  • Compression sensitivity: Llama’s average falls from 26.8 at 2× to 24.1 at 10×, Qwen’s from 31.0 to 29.0, while Mistral remains between 28.0 and 28.2.These are model-specific trajectories with different full-cache references and attention/value geometries.
  • Statistical reading: Point-estimate ranks are not significance decisions; comparative claims rely on paired Holm tests over the complete 503-example evaluation.The full cache is a calibration reference and is excluded from compressed-method ranking.
  • Supported conclusion: The narrower supported conclusion is that exact-budget, value-aware selection is competitive across the declared four-baseline grid.The results do not establish a domain-wise SOTA claim or a universal semantic category where one eviction rule must win.
Loading 2608.21541v1…