acceptodds
Withdrawn from ICLR 2027

Predicting Output Preservation and First Divergence under KV-Cache Compression

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Key-Value (KV) cache compression is usually evaluated by how much cache state is removed or distorted, but cache distortion alone does not determine whether the model output is preserved. Under deterministic greedy decoding, we study when compression preserves the dense-model token and when compressed generation first diverges. Our key observation is that output preservation depends not only on perturbation magnitude, but also on how the compression-induced change acts relative to the decision margin. Based on this observation, we derive an exact per-step characterization of output preservation through output crossing. We then introduce the Output Crossing Predictor (OCP), a first-order framework that predicts whether a candidate compression will cause output crossing before compressed logits are observed. OCP combines the local cache-read perturbation with the local sensitivity of the dense model. Repeated across decoding steps, the same prediction estimates the first divergence time. Experiments across multiple models and compression operators show that OCP predicts output crossing and first divergence, while the compression boundary becomes more conservative as generation length increases. These results shift KV-cache compression from measuring cache distortion to predicting output preservation and first divergence.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV-cache compression, output preservation, first divergence, output crossing, efficient LLM inference

Reviews

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

This paper studies when KV cache compression changes the dense model’s output under greedy decoding. The authors propose the Output Crossing Predictor (OCP), which uses a first-order approximation to predict whether a candidate compression will change the next token, and apply it to estimate the first divergence time and to guide the compression level of existing methods.

Critical strengths
  • The paper clearly characterizes the condition for output preservation under KV cache compression as the ratio of compression pressure to the decision margin.
  • The authors demonstrate that the proposed framework is applicable across multiple models and compression methods.
Critical weaknesses
  • I have concerns about the core premise of this paper. Should a good KV cache compression method necessarily reproduce exactly the same output tokens as the uncompressed model? A compressed model could reach the same correct answer through a different, or even more efficient, reasoning trajectory.
  • The authors control the dense outputs to be deterministic by using a batch size of 1 on a single GPU. However, most practical serving systems use batching, and even under greedy decoding, floating-point results can vary with batch composition and kernel reduction order. In this case, divergence between dense outputs can occur at steps with small margins even without any compression. How can divergence caused by compression be distinguished from divergence caused by such numerical nondeterminism?
  • The paper defines and analyzes output crossing under the assumption of greedy decoding. However, recent models such as Qwen3 discourage greedy decoding in their model cards due to repetition and endless loops, and instead recommend sampling (e.g., T=0.6). Under sampling, one should examine changes in the output distribution rather than whether a single output token matches. Can the proposed framework be extended to this setting?
  • The models used in this paper (Qwen2.5, Llama-3.1, and Mistral) are not reasoning models. An evaluation on long reasoning scenarios, where the demand for KV cache compression is greatest, is needed.
Questions for authors

Please see the weaknesses above.

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

This paper studies KV-cache compression via output preservation and first divergence. It argues cache distortion magnitude alone cannot determine whether compression changes the next token; instead, compression-induced logit changes must be compared with dense decision margins. The authors define output crossing as a competing token overtaking the dense-model token, yielding an exact per-step preservation criterion. They propose the Output Crossing Predictor (OCP), which predicts crossing before compressed logits are evaluated. OCP uses candidate local cache-read perturbations and dense-model local sensitivity, computed as a Jacobian-vector product, to estimate a predicted crossing ratio. The first predicted crossing gives predicted first divergence. They also derive a length-dependent compression boundary scaling with generation length. Experiments use Qwen2.5-7B, Llama-3.1-8B, and Mistral-7B on GSM8K, LongBench, and RULER, covering token eviction, value quantization, low-rank compression, and key perturbation. OCP lowers false-safe rates at fixed false-alarm rates, predicts first divergence with 38.6% exact-hit and 4-step median error on a 73% subset, and delays median first divergence by 23.7–37.7 steps with 6.8–8.6% runtime overhead.

Critical strengths

1.The paper moves beyond measuring internal cache distortion and instead formalizes whether compression crosses the dense model’s decision margin. This leads to the exact output-crossing criterion and the Output Crossing Predictor (OCP), which predicts whether a candidate compression intervention will change the next token before compressed logits are observed. This is consequential because it provides a common, output-level interface for token eviction, value-side quantization, low-rank compression, and key-side perturbation, rather than an operator-specific heuristic.

2.OCP-guided compression delays median first divergence by 23.7–37.7 decoding steps across four representative compression methods under matched average compressed KV-memory usage, with 6.8–8.6% runtime overhead. This is consequential because it shows that the predictor is not merely diagnostic: it can be used to adjust compression strength online and produce later divergence without replacing the underlying compression operator.

Critical weaknesses

1.The guided evaluation maintains a dense reference cache and defines each step's candidate compression intervention relative to that dense state, yet the dense reference KV memory is not included in the reported matched compressed-cache footprint. In a real deployment, the whole purpose of KV-cache compression is to avoid storing or accessing the dense cache. If the dense reference must be maintained, the claimed memory benefit is largely negated, which directly undermines the practical significance of the main OCP-guided results.

2.The predicted first divergence is computed along the dense reference trajectory, including after the observed divergence when needed, and is reported only on a 73% both-observable subset with a 38.6% exact-hit rate and 4-step median absolute error. This is consequential because the extension from per-step output crossing to generation-level first divergence is a central claimed contribution. Without evidence that OCP works online using only compressed-branch information, the practical value of the first-divergence prediction remains uncertain.

Questions for authors
  1. In OCP-guided compression, is the dense reference KV cache maintained throughout generation? If so, how can the method be used in a real deployment where only the compressed cache is available? If not, please clarify the exact online protocol and report memory usage including the dense reference state.

  2. For first divergence prediction, is the predictor evaluated only using the current dense state at each step, or does it use future dense trajectory information? How are the 27% of generations that are not both-observable handled, and could they systematically change the reported exact-hit rate and median error?

  3. Can the authors provide downstream task accuracy (e.g., GSM8K exact match, LongBench F1, RULER scores) for OCP-guided compression versus baselines under matched memory? Delaying first divergence is only meaningful if it translates into better or equal task performance.

  4. How does OCP compare to existing output-error-based compression criteria, such as attention-output error used in CAOTE or similar methods? A direct comparison would help establish the unique value of OCP's direction- and margin-aware prediction.

  5. What is the runtime overhead of OCP when the dense reference is included? The reported 6.8–8.6% overhead appears to exclude the cost of maintaining and running the dense model. Please provide a full end-to-end accounting.

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

This paper studies the impact of KV cache compression on model outputs. The authors point out that the magnitude of cache distortion does not determine whether the output changes; what matters is the direction and magnitude of the compression-induced logit shift relative to the decision margin. Based on this insight, the paper derives an exact criterion for preserving single-step outputs and proposes the Output Crossing Predictor (OCP). Experiments cover three models and four compression operators.

Critical strengths
  1. The paper argues that we should prioritize the phonetic correctness of generated text instead of relying solely on absolute PPL.
  2. The extensive experimental results strengthen the validity of the arguments.
Critical weaknesses

1.The proposed OCP method primarily relies on first-order Taylor approximation. It leverages perturbations on the KV Cache and local model sensitivity to predict whether the model output will change. Nevertheless, the paper does not derive strict theoretical bounds for the approximation error, nor does it discuss the conditions under which the first-order approximation remains valid. Consequently, the predicted output preservation does not guarantee invariance of the actual output, which somewhat undermines the theoretical rigor and reliability of the method.

2.The paper guides KV Cache compression by predicting output changes, yet it fails to adequately discuss whether retrieval-augmented methods like RAG can achieve comparable practical objectives in a simpler manner. For instance, for long-context question answering or tasks with Yes/No constrained outputs, one can retrieve critical contextual information and adopt a result discrimination mechanism to guarantee answer quality, without resorting to sophisticated gradient sensitivity calculations. Although RAG cannot directly guarantee token-level consistency with the original model’s outputs, if the ultimate task objective is answer accuracy rather than exact output preservation, the paper should further elaborate on the unique advantages of OCP over these alternatives and validate its practical necessity via comparisons on task performance, computational cost and memory overhead.

Questions for authors

see weakness

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

Related papers

Discussion (0)

Sign in to comment.