acceptodds
Under review as a conference paper at ICLR 2027

KV Cache Compression as State Substitution: When Does KV Compression Yield a Reliable Replacement for the Full Cache?

Abstract

Long-context autoregressive inference is increasingly constrained by KV caches, whose memory footprint grows with sequence length, motivating compression for memory-efficient inference. However, when compression replaces the full cache with a smaller one that continued decoding must use and update, matching the current attention output is insufficient in general: two cache states can agree now yet diverge after the same append because softmax hides normalization mass. We characterize when current-output error can nevertheless control cache-extension error. For unchanged-row selection, this control depends on omitted attention mass and the separation between retained and omitted value means. Cancellation is the failure boundary: substantial omitted mass can remain nearly invisible in the current output. Away from it, current error controls the hidden mass exposed by an append, yielding a sharp, attainable one-append guarantee. The same control extends perturbatively to more general compressed caches that remain close, in response and normalization mass, to an unchanged-row selection on the same support. Fresh Qwen and Mistral evaluations support this mechanism: transition-aware scoring improves pairwise post-extension concordance over current-output scoring by .320 and .211, respectively, with 95% confidence intervals excluding zero in both model families. CaM and KeepKV test perturbative transfer at different scales. Finally, we characterize exactly when these headwise guarantees survive fixed output projection. Together, the results show how the geometry of compressed caches can make current-output error informative for reliable KV-cache replacement despite its global insufficiency.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache compression, long-context LLM inference, attention, transformer inference, theoretical analysis, cache replacement, efficient inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_R8M4OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Let S be the softmax normalization mass, N the unnormalized weighted-value sum, and attention output A = N/S. This paper gives several theoretical analyses of the effect of KV cache reduction on A. And they try to analyze under what condition this reduction has less effect on A.

Critical strengths
  • The proposed problem is meaningful.
Critical weaknesses
  • As a theoretical paper, it is very hard to follow. I have the feeling that the formalization is more than the real conceptual content.
  • There is a gap between the theoretical analysis and the experimental analysis. I don't think the experiment is strong enough to show the discussion of the theory part.
Questions for authors

How does the proposed transition-aware criterion correlate with end-to-end downstream degradation, such as LongBench accuracy, long-context perplexity, or generation divergence, rather than local attention-state error alone?

3 comments
AuthorsOpenReview ↗

Response to the Review

We thank the reviewer for recognizing the importance of the problem. We agree that the conceptual contribution and its connection to model behavior should be easier to identify. The central question is whether a compressed cache is a reliable persistent replacement, rather than merely whether it matches one current attention output.

1. Why does state substitution require a different analysis?

Decoding continues to read and extend a compressed KV cache. Attention reveals a normalized output, but hides normalization mass that can change the influence of the next common append. Thus, two states with similar current outputs need not remain similar after extension. Proposition 1 formalizes this obstruction. Theorem 1 establishes a sharp, attainable recovery bound for unchanged-row selection away from cancellation; Theorem 2 transfers that bound to support-anchored constructed states under explicit response and normalization-mass defects. This is a quantitative transition-reliability result, not simply a reformulation of current attention error.

2. What does the constructor-level analysis contribute?

Pure selection preserves the original keys and values. Many practical compressors instead modify their retained representations, so a sharp selection bound alone does not certify them. Theorem 2 provides a concrete bridge: for a constructor with a declared support, we compare it to unchanged-row selection on that same support and separately bound response distortion (ξ\xi) and log normalization-mass distortion (η\eta). This gives a sufficient condition for transferring common-append reliability to support-anchored constructed states, without assuming that arbitrary synthesis inherits selection guarantees.

CaM and KeepKV test different parts of this theory. CaM modifies retained values but preserves normalization mass; its fresh all-head audit retains 91.19%/96.42% of support-only certificate coverage on Qwen/Mistral. KeepKV also changes keys and effective multiplicities: removing its mass-defect term produces a maximum 0.01397 bound violation on fresh Qwen, while the complete bound has no observed violation. The empirical contrast shows why the two defects must be distinguished.

3. How does the criterion relate to downstream model behavior?

We distinguish controlled transition discrimination from native generation. In fresh 256-token, Read-matched attention-state tests (64 prompts/model), the transition-aware score improves post-append endpoint concordance over current-output error by 0.3205 on Qwen (95% CI [0.2364, 0.4114]) and 0.2112 on Mistral ([0.0405, 0.3824]). This is a retrospective test using realized transition information.

To assess whether the local phenomenon remains relevant when the compressed state generates its own queries and writes, we also evaluate native continuation after one compression, using prefixes up to 8192 tokens and 32 greedy steps. In the independent HotpotQA/MuSiQue replication (32 prompts/model), common-write/native error rankings have Spearman correlations of 0.9377/0.9384, with both 95% confidence intervals strictly positive. This supports a controlled-to-native correspondence in relative error difficulty.

Direct answer: We have not established a correlation between the transition-aware score and end-to-end LongBench accuracy or long-context perplexity, nor validated the certificate as a generation-lifetime predictor. The native result correlates common-write error with native error; it should not be confused with direct score-to-task prediction. It nevertheless provides evidence that the local transition geometry captures behavior relevant beyond the controlled attention endpoint.

The contribution is therefore a connected account of state-substitution obstruction → sharp recovery → constructor-level transfer, supported by controlled and native behavioral evidence at their respective scopes.

I appreciate the author's reply. It addressed some of my concern. My remaining concern is mainly the presentation. I have a lot of experience on this topic; however, it makes it hard to understand the content. I think this paper could be a good paper if it had much clearer writing. So I encourage the author to keep refining it. I'll keep my original score. Thanks.

AuthorsOpenReview ↗

Response to the Review

We thank the reviewer for the follow-up and appreciate your acknowledgment that our response addressed some of your concerns. We take the remaining presentation concern seriously.

To make the conceptual contribution clearer, the paper's argument can be summarized in three steps:

1. State-substitution obstruction. Matching the current attention output does not ensure reliable cache replacement: two states may agree at the current read yet diverge after the same append.

2. Sharp recovery. Theorem 1 identifies conditions under which current-output error does control the complete post-append discrepancy, with a sharp, attainable guarantee for unchanged-row selection.

3. Constructor-relative transfer. Theorem 2 extends this guarantee beyond pure selection by comparing constructed representations with a same-support selection reference and separately controlling response and normalization-mass defects.

The experiments investigate these mechanisms rather than claiming a new eviction policy or an unconditional long-horizon guarantee.

We recognize that the manuscript could communicate this progression more directly, with the central conceptual results distinguished more clearly from the technical derivations and experimental protocol. We appreciate your constructive feedback on this issue.

Reviewer_ojwhOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper develops theoretical conditions under which a compressed KV cache remains reliable after additional tokens are appended. It derives sharp error bounds for row selection, extends them to other compression methods, and evaluates transition-aware error estimates on Qwen and Mistral models.

Critical strengths

Identifies a fundamental limitation of current attention-output error: it can hide omitted attention mass that becomes visible after appending tokens. Provides rigorous, sharp theoretical guarantees under clearly specified assumptions. Uses preregistered experiments and fresh-prompt evaluations to support its theoretical predictions. Shows that transition-aware scoring improves unsafe-state discrimination over current-output error alone.

Critical weaknesses

The guarantees are local to a common append and depend on restrictive geometric conditions; they do not establish general reliability during long, autoregressive generation. Experiments primarily measure attention-state fidelity rather than downstream task quality or actual inference efficiency. Some findings remain inconclusive, including cross-family failure localization and native-continuation lifetime guarantees. The analysis is technically elaborate, and the practical implications for choosing compression methods could be clearer.

Questions for authors
  1. How well do the proposed bounds predict downstream generation quality over long sequences?
  2. Can the method guide compression decisions without relying on information derived from the full cache?
  3. Do the theoretical advantages translate into measurable memory and inference-speed improvements?
1 comment
AuthorsOpenReview ↗

Response to the review

We thank the reviewer for recognizing the significance of the problem and the rigor of the analysis. We address the three questions directly.

1. How well does the one-append guarantee relate to long-sequence generation quality?

The common-append contract tests a basic requirement of persistent-state substitution: can a compressed cache remain reliable when both states receive the same extension? Theorem 1 gives a sharp recovery bound for unchanged-row selection; Theorem 2 transfers it to support-anchored constructed states under explicit response and normalization-mass defect conditions.

We also evaluate native continuation, in which the compressed state generates its own queries, keys, values, and tokens. After one post-prefill compression, using prefixes up to 8192 tokens and 32 greedy steps, an independent 32-prompt/model HotpotQA/MuSiQue replication finds strong common-write/native error-ranking correlations (ρs=0.9377/0.9384\rho_s=0.9377/0.9384; both 95% CIs strictly positive). This supports the behavioral relevance of relative local error difficulty. It is not, however, a demonstrated long-horizon quality or certificate-to-lifetime prediction.

2. Can the framework guide compression without FullKV-derived information?

The framework identifies the information needed for a reliable replacement judgment: omitted attention mass, retained–omitted response separation, append scale, and constructor-specific response and log-mass defects. Theorem 2 makes the constructor-level contribution explicit: rather than treating a constructed cache as unchanged-row selection, it compares the constructor against a same-support selection reference and accounts separately for its response and log-mass defects. The fresh CaM/KeepKV audits exercise both cases: CaM preserves normalization mass, while KeepKV requires the mass-defect term to avoid observed bound violations.

Our current evaluations measure these coordinates on realized states using FullKV information. They therefore establish a reliability criterion for evaluating compressed states, rather than a verified FullKV-free online estimator or certificate-guided eviction policy.

3. Do these advantages improve memory usage or inference speed?

Our results characterize the reliability of already compressed representations. The memory reduction comes from the underlying compression constructors; the present analysis does not introduce a new compression kernel or show additional measured throughput or latency gains. Its practical contribution is complementary: it identifies conditions under which a memory-efficient compressed state is a reliable substitute for the original under a specified transition contract. This distinction lets reliability be evaluated alongside, rather than conflated with, memory and speed objectives.

Reviewer_nKbrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper asks when matching the current attention output keeps a compressed KV cache close to the full cache after a common append. Building on the identity δ=pζ\delta = p\zeta from prior work, it derives a sharp one-append bound under a margin ζ≥γ\zeta \ge \gamma, extends it to constructors such as CaM and KeepKV, and studies composition through the output projection. Audits on Gemma, Qwen, and Mistral show that a transition-aware score improves post-append concordance by .320 and .211.

Critical strengths
  1. The derivations are correct, and I verified Eq. (4), the maximizer of Eq. (5), and the numerical example Φ(.025)=.07861\Phi(.025) = .07861.

  2. The empirical protocol is rigorous, with outcome-blind prompt selection, prompt-level bootstrap intervals, and honest reporting of unresolved cells.

Critical weaknesses
  1. The identity δ=pζ\delta = p\zeta and the tanh envelope come from Yang and Li (2026), and the role of hidden normalization mass is known from Haverbeck et al. (2026) and log-sum-exp merging, so the new theory seems incremental.
  2. Experiments use 256-token states, two query heads per layer, and appends from the full model, without any downstream task. Unsafe endpoints occur on only 0.1% to 2.6% of points, which makes the obstruction look rare in practice.
  3. The transition-aware score needs future append mass from the full cache and is derived from the same expression as the endpoint error, so the concordance gain partly holds by construction.
  4. Heavy protocol terms such as registered natural budget and frozen gates make the main text hard to follow.
Questions for authors
  1. Which results go beyond Yang and Li (2026), theorem by theorem?
  2. Can pp or xx be estimated online without the full cache, and would the estimate improve an eviction policy?
  3. Does the score predict degradation on an end-to-end LongBench task at realistic lengths?
  4. How do the bounds behave under repeated recompression?
2 comments
AuthorsOpenReview ↗

Response to the Review

We thank the reviewer for checking our analysis. Yang & Li (2026) establish δ=pζ\delta=p\zeta, the hidden-mass envelope, and future-query mismatch (Theorem C.1). Our contribution is sharp common-append recovery and its transfer beyond selection.

1. Which results are new, theorem by theorem?

ResultClosest prior resultAdditional contribution
Proposition 1Hidden mass and future-query mismatch are known.Shows that current-output equivalence is not preserved under a common append.
Proposition 2Yang & Li's fixed-row factorization and future-query mismatch analysis.Derives the sharp, attainable fixed-mass envelope Ψ(u,p)\Psi(u,p) for the complete post-append discrepancy.
Theorem 1The identity δ=pζ\delta=p\zeta and hidden-mass envelope h(p)h(p).Establishes the sharp, attainable uniform modulus Φγ(u)\Phi_\gamma(u) under ζ≥γ\zeta\geq\gamma, optimizing omitted and append mass.
Theorem 2Yang & Li's synthetic-tail mass and distribution mismatch analysis.Transfers the common-append recovery guarantee to support-anchored constructed states with separate response and log-mass defects (ξ,η)(\xi,\eta).
Appendix Proposition 4Headwise error propagation through WOW_O is known.Characterizes necessary and sufficient conditions for universal finite-scale nonexpansion under fixed output projection.

Crucially, we optimize the complete transition coefficient,

Bcoeff(p,u,x)=(1−p)u+px(1+x)(1−p+x),B_{\mathrm{coeff}}(p,u,x)=\frac{(1-p)u+px}{(1+x)(1-p+x)},

which retains propagated current error as well as the exposed hidden-mass contribution. The attaining construction establishes optimality under the stated conditions. Theorem 2 then gives

eC+≤Φγ(δC+ξ)+ξ+tanh⁡(∣η∣/4).e_C^+\leq\Phi_\gamma(\delta_C+\xi)+\xi+\tanh(|\eta|/4).

Theorem 2 analyzes constructed representations beyond pure selection: it compares a constructor to unchanged-row selection on its declared support and separately quantifies response (ξ\xi) and log-mass (η\eta) defects. This transfers the common-append bound to support-anchored constructors under explicit conditions, without claiming arbitrary synthesis is safe. The novelty is sharp recovery plus constructor-relative transfer, not the discovery of hidden mass.

2. Does the constructor analysis matter for real methods?

In a fresh 32-prompt/model all-head audit, CaM modifies retained values but preserves normalization mass (η=0\eta=0), retaining 91.19%/96.42% of support-only certificate coverage on Qwen/Mistral. KeepKV changes keys and effective multiplicities: omitting its mass-defect term causes a 0.01397 maximum bound violation on Qwen, versus none observed with the complete bound. These results test distinct constructor defects.

Separately, among candidate caches matched for current Read error, the transition-aware score better predicts relative post-append errors, improving pairwise concordance by 0.3205 on Qwen (95% CI [0.2364, 0.4114]) and 0.2112 on Mistral ([0.0405, 0.3824]). These are gains in retrospective transition discrimination, not evidence of an online eviction improvement.

3. Can pp or xx be estimated online, and would that improve eviction?

For a specified query, omitted mass pp is computable when FullKV is available, but is not generally recoverable from a compressed state that no longer stores the omitted keys. The append coordinate xx additionally depends on the realized query and appended keys. Our experiments use these coordinates retrospectively; we have not validated a FullKV-free estimator or demonstrated a better online eviction policy. The theorem instead specifies which information a prospective policy would need to approximate to assess transition reliability.

4. Does the score predict realistic-length LongBench degradation?

Native-continuation audits compress once after prefill, use prefixes up to 8192 tokens (68/64 retained rows), and decode 32 greedy tokens without recompression. An independent 32-prompt/model HotpotQA/MuSiQue replication finds common-write/native error-ranking correlations ρs=0.9377/0.9384\rho_s=0.9377/0.9384 (both 95% CIs exclude zero). This connects local transition difficulty to native behavior, not to validated LongBench accuracy, perplexity, or lifetime prediction.

5. How do the bounds behave under repeated recompression?

Theorem 2 can be applied again after a new compression event if its support-relative margin and defect conditions are re-established. Recompression changes the representation and introduces new defects; native decoding may also change later queries and writes. Hence the present theorem does not imply an unconditional additive or recursive multi-step bound.

Together, these results establish a sharp criterion for reliable common-append state substitution and extend it from pure selection to support-anchored constructed representations.

I thank the authors for the theorem-by-theorem clarification, which helps place the sharp modulus and the constructor transfer, but since the response confirms that pp and xx remain FullKV-derived and that no online estimator or downstream-task validation is available, my concern about practical relevance remains and I will keep my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

Summary of the Author Responses and Main Contributions

We thank the reviewers for their careful assessment and constructive discussion. As the discussion concludes, we would like to summarize the paper's central contribution and clarify the scope of the remaining concerns.

The central contribution is a theory of reliable KV-cache state substitution, rather than a new compression algorithm. The paper establishes three connected results:

First, a state-substitution obstruction: current attention-output agreement does not generally survive a common append.

Second, sharp recovery: under explicit visibility conditions, we derive a sharp and attainable guarantee relating current-output error to the complete post-append discrepancy. This goes beyond the previously established hidden-mass identities and envelopes.

Third, constructor-relative transfer: Theorem 2 extends the recovery guarantee from unchanged-row selection to support-anchored constructed states by separately controlling response and normalization-mass defects. This provides a theoretical treatment of representation-modifying compression rather than assuming that selection guarantees automatically extend to synthesis.

Empirical support. On Qwen and Mistral, transition-aware scoring improves Read-matched post-append concordance by 0.3205 and 0.2112, respectively, with positive 95% confidence intervals. The CaM/KeepKV audits test the distinct constructor defects, while native-continuation experiments establish strong correspondence between controlled and independently evolving cache-error rankings.

We acknowledge the paper's deliberately limited scope: these are local transition guarantees and retrospective reliability diagnostics, not an online eviction algorithm, a multi-step autoregressive certificate, or a demonstration of inference-speed improvement.

The reviews have helped identify where the presentation can better distinguish the central theoretical contribution from the technical machinery. We appreciate Reviewer R8M4's follow-up acknowledgment that our response addressed some concerns, while recognizing that presentation remains their principal concern.

We respectfully hope the paper can be assessed on the novelty and significance of its stated theoretical contribution, with its practical limitations and presentation weaknesses considered separately.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.