acceptodds
Withdrawn from ICLR 2027

To Predict or Not to Predict: Budget-Aware KV-Cache Compression

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

Abstract

Key-value (KV) caching avoids repeated computation during autoregressive decoding, but its memory cost grows with context length. Same-layer cross-head prediction can improve the low-rank compressibility of KV representations, but retaining anchor heads consumes cache capacity. Under a fixed KV-cache budget, prediction must therefore improve compressibility enough to justify storing the anchors. We propose TPNP (To Predict or Not to Predict), a KV-cache compression method that jointly determines whether to use cross-head prediction and how much of the prediction residual, termed the innovation, to retain. TPNP considers the native representation, prediction-assisted innovation coding, and prediction-free joint low-rank coding in a unified search space. When prediction is selected, TPNP retains same-layer anchors and jointly represents the target innovations in a low-rank subspace. TPNP ranks innovation basis directions using Fisher-Rao sensitivity and jointly selects anchor-target partitions and retained innovation ranks for each layer-wise K/V component to minimize the estimated Fisher-Rao compression cost under a global KV-cache budget. Our analyses reveal a key-value asymmetry: prediction generally improves compressibility in the value partitions selected by TPNP for cross-head prediction, while TPNP predominantly selects prediction-free joint low-rank coding for keys. We evaluate TPNP across four backbones and multiple calibrations. Across four KV saving ratios from 10% to 70%, comparisons with six methods show that TPNP ranks first or second in 14 of 16 backbone-ratio combinations for average perplexity and in 14 of 16 for average accuracy. On Qwen2.5-7B and Yi-1.5-6B, it also achieves the highest average LongBench score in six of eight combinations, ranking second in the remaining two.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV-Cache Compression, Low-Rank Approximation, Cross-Head Prediction

Reviews

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

This paper proposes to-predict-or-not-to-predict (TPNP), which chooses per-layer key and value compression schemes under a global KV-cache budget. It combines optional cross-head prediction with low-rank innovation coding. To choose the optimal strategy the method uses a callibration data and saves additional weights P_i, W_z, b_z, as well as compressed residuals which are used during online inference to both store a compressed KV Cache and to extract it.
The method performs well on several quality benchmarks, particularly at high cache-saving ratios.

Critical strengths

The decision to account for the storage cost of predictor anchors is well motivated. The mathematical analysis is sound and well presented. The comparison with prediction-free coding helps isolate when prediction is useful, and the experiments cover multiple models, budgets, and calibration sets. The analysis Section is interesting. I especially appreciate Figure 2 and the distribution of layer compression as well as the KV-assymetry.

Critical weaknesses

W1. The inference trade-off is unmeasured. The paper reports theoretical token-dependent cache size, but not decode latency, throughput, or peak inference memory. Reconstructing cached heads adds work at every decoding step. The useful comparison is generated tokens per second at a fixed GPU memory budget, including any batch-size increase enabled by compression. This remains the main systems concern. See more in the Questions section below.

W2. The benefit of prediction over a strong prediction-free variant is concentrated only at high compression as can be seen in the table in Appendix C. At 10–50% saving, results are often nearly tied or mixed. For example, at 50% on Yi, the prediction-free variant has higher average accuracy (59.87 versus 59.02). The clearest prediction-specific gains occur at 70%, where absolute quality also degrades substantially relative to the original models. The paper should more clearly separate the benefit of cross-head prediction from that of adaptive low-rank compression and allocation, and characterize when the added prediction machinery is worthwhile.

W3. The main architectural analysis covers a narrow KV-head regime. Qwen2.5-7B and Yi-1.5-6B both have four KV heads of width 128 per layer. Thus, the main experiments and key–value asymmetry analysis use the same size of per-layer anchor-partition search space. The additional backbones provide useful quality results, but do not show how partition choices, gains, and preprocessing cost evolve with the number of KV heads. This matters because candidate enumeration grows exponentially in that number.

Questions for authors

Q1. The evaluation does not establish whether the method improves practical decoding throughput. A newly generated token can be encoded directly into the compact representation, but attending to cached tokens requires reconstructing their K/V representations. As Appendix H.2 shows, this adds work proportional to context length for each decoding step, including target prediction and low-rank decoding. Appendix H.3 states that the implementation lacks dedicated fused kernels and does not report end-to-end latency or throughput. This omission matters because the proposed benefit is memory capacity during inference. Saving cache space may permit a larger batch, but reconstruction could reduce tokens per second enough to erase that gain. The theoretical cache-footprint comparison cannot resolve this trade-off.

Here's a short back-of-the-envolpe calculation I did for the additional calculation during decode:

Consider one layer, one newly decoded token, and NN earlier tokens in the KV cache. Let HqH_q be the number of query heads and dhd_h the head dimension. For each component c∈{K,V}c\in\{K,V\}, let AcA_c be the number of cached anchor heads, TcT_c the number of reconstructed target heads, and rcr_c the number of cached innovation coordinates. Thus Ac+Tc=HkvA_c+T_c=H_{\mathrm{kv}}.

Without compression, computing attention scores and the weighted value sum takes approximately Fattention=4NHqdhF_{\mathrm{attention}}=4NH_qd_h FLOPs, counting a multiply-add as two FLOPs.

TPNP performs this attention computation after reconstructing the target heads. For each cached token, it forms a prediction from the anchors and decodes the innovation: xTc=PcxAc+μc+Brczc.x_{T_c}=P_c x_{A_c}+\mu_c+B_{r_c}z_c. Using dense matrix products, this adds approximately

=2N\sum_{c\in\{K,V\}} \left(A_cT_cd_h^2+T_cd_hr_c\right)$$ FLOPs per decoding step, plus additions and positional rotations. The first term is target prediction; the second is innovation decoding. The key predictor has a RoPE-constrained structure, so its prediction term can be cheaper than this dense estimate. For Qwen2.5-7B we have $H_q=28$ query heads, $H_{\mathrm{kv}}=4$ KV heads, and head dimension $d_h=128$. Assume, for illustration, that both K and V use prediction-free low-rank coding: $A_K=A_V=0$, $T_K=T_V=4$, and $r_K=r_V=154$. Counting a multiply-add as two FLOPs, ordinary attention costs $$F_{\mathrm{attention}} =4NH_qd_h =4N(28)(128) =14{,}336N.$$ Reconstructing both cached K and V components adds $$\Delta F_{\mathrm{TPNP}} =2N\sum_{c\in\{K,V\}}T_cd_hr_c =2N\bigl[2(4)(128)(154)\bigr] =315{,}392N.$$ about $23$ times as much arithmetic. I might be wrong in my calculation, but I would like to at least see/read such a theoretical discussion. A much better demonstration would be to see the actual decode latency and throughput across context lengths and batch sizes, peak inference memory, and the maximum sustainable batch size at a fixed GPU memory budget. A comparison of total generated tokens per second at equal memory use would be particularly informative. If optimized reconstruction is required for the method to be competitive, the paper should quantify that requirement in the paper body rather than in the appendix. Q2. Could the authors extend the TPNP-versus-prediction-free comparison to long-context tasks and report the gain at each saving ratio? This would show whether prediction improves the outcomes most relevant to the proposed cache use case, beyond the perplexity and accuracy averages in Appendix C. Q3: Could the authors report partition counts or distributions, preprocessing time, and peak preprocessing memory for backbones with more KV heads? If a broader scaling study is infeasible, please qualify the scalability and key–value asymmetry claims accordingly. Q4. TPNP is generally strong in the main evaluations (Tables 1 and 2), but its relative advantage is less consistent elsewhere. On Qwen2.5-7B at 70% cache saving, it ranks third on RULER (Table 6), despite strong results on the other reported benchmarks. On the additional backbones in Table 8, it remains competitive but is not consistently best across metrics and saving ratios. I appreciate the inclusion of these results, and would welcome a discussion of why its relative ranking changes across long-context benchmarks and model architectures. Q5. In the second paragraph of Appendix D -- please refer to table 1.
Reviewer_xeNVOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes TPNP (To Predict or Not to Predict), a training-free KV-cache compression method that jointly considers cross-head prediction and low-rank compression. For each layer's key and value representations, TPNP selects among retaining the original representation, predicting target heads from anchor heads and compressing the prediction residuals, or applying prediction-free joint low-rank compression. The method uses Fisher–Rao sensitivity to rank basis directions and global budget allocation to determine the compression configuration and retained rank. Experiments cover four LLM backbones, multiple compression ratios, and evaluations on perplexity, zero-shot accuracy, and LongBench.

Critical strengths

The paper addresses a meaningful trade-off between the improved compressibility obtained through cross-head prediction and the additional storage required for anchor heads. The unified formulation allows the method to select prediction only when it is estimated to be beneficial. The empirical evaluation is reasonably extensive, covering four backbones, four compression ratios, and six low-rank compression baselines. TPNP achieves competitive results across most settings, particularly at higher compression ratios. The ablation studies and reconstruction analysis are also useful, especially the observation that cross-head prediction appears more beneficial for values than for keys.

Critical weaknesses
  1. Limited contribution of cross-head prediction. Table 5 shows that cross-head prediction provides little improvement over prediction-free joint low-rank coding at 10%–50% KV-cache savings. This raises questions about whether the reported gains primarily come from prediction or from global budget allocation and joint low-rank compression.

  2. Missing practical efficiency evaluation. The paper reports theoretical memory savings but lacks actual GPU memory, latency, and throughput measurements. The computational overhead of KV reconstruction may offset the benefits of compression.

  3. Incomplete baseline comparisons. The evaluation omits closely related methods exploiting cross-head or cross-layer redundancy, such as xKV and AQUA-KV, making it difficult to assess the incremental contribution of TPNP.

  4. Limited justification of methodological choices. Fisher–Rao ranking provides relatively modest improvements in Table 3. Moreover, the observed key–value asymmetry may be influenced by the RoPE-compatible constraints imposed on key prediction.

Questions for authors

Please refer to the Critical Weaknesses section for my main concerns and suggested additional experiments.

Reviewer_yop5OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes TPNP (To Predict or Not to Predict), a training-free KV-cache compression framework that unifies native retention, cross-head linear prediction with low-rank residual (innovation) coding, and prediction-free joint SVD within a single search space. Using empirical Fisher–Rao sensitivity and dynamic programming, TPNP globally selects the optimal anchor–target head partition and truncation rank for each layer under a target memory budget. Empirical evaluations across four GQA models demonstrate competitive accuracy while revealing a structural asymmetry: cross-head prediction improves compressibility for Values, whereas Keys strongly favor prediction-free joint SVD.

Critical strengths

(S1) The paper formulates a clear budget-aware trade-off between anchor storage overhead and residual compressibility, empirically uncovering a distinct structural asymmetry where cross-head prediction benefits Values while Keys favor prediction-free joint SVD (Table 4, Figure 2). Furthermore, the proposed framework is thoroughly evaluated across four GQA backbones, multiple calibration datasets, and orthogonal quantization methods, consistently achieving competitive accuracy and perplexity.

Critical weaknesses

(W1) Incremental Methodological Novelty and Narrow Regime of Effectiveness

The core technical components in Sections 3.1 through 3.3 largely synthesize existing mechanisms already cited in the paper rather than introducing fundamentally new compression primitives: same-layer cross-head linear regression follows Shaikh et al. (2026), compressing prediction residuals builds upon the predict-then-compress paradigm of AQUA-KV (Shutova et al., 2025), and joint low-rank SVD with weight folding as well as Fisher-information-guided rank allocation were already established in Palu (Chang et al., 2025). Consequently, TPNP's unique contribution is narrowed down to dynamically selecting between cross-head prediction and prediction-free SVD via global budget allocation. However, Appendix C (Table 5) reveals that at 10%, 30%, and 50% saving ratios, TPNP yields virtually no improvement—and occasionally slightly lower accuracy—compared to its prediction-free joint low-rank (0A4T) variant. Thus, the proposed cross-head prediction mechanism provides meaningful benefits only at the extreme 70% compression regime, where it still consistently trails behind ReCalKV and Palu on the long-context RULER benchmark (Appendix D, Table 6).

(W1) Lack of Empirical Inference Memory Verification and Disproportionate Preprocessing Overhead

While Table 9 reports theoretical per-token KV-cache sizes based on scalar counts, the paper omits actual end-to-end peak GPU memory measurements during inference. Because TPNP lacks a custom fused kernel, reconstructing and materializing the full target KV representations (X~T\widetilde{\mathbf{X}}_{\mathcal{T}}) right before attention computation at each decoding step risks inducing runtime memory spikes that could undermine the theoretical compression gains. Furthermore, while TPNP aims to reduce memory, Appendix G.2 (Table 10) shows that its offline preprocessing—which requires enumerating all candidate partitions and evaluating Fisher–Rao sensitivities—consumes the highest peak GPU memory among all evaluated methods across all compression ratios.

Questions for authors

(Q1) Does the runtime overhead of reconstructing the full KV representations (X~T\widetilde{\mathbf{X}}_{\mathcal{T}}) at each step cause peak GPU memory spikes that negate your theoretical savings, and how do you justify TPNP having the highest offline preprocessing memory overhead (Table 10) in resource-constrained setups?

(Q2) What is the core conceptual breakthrough of TPNP beyond framing existing primitives as a DP search, especially since it shows marginal gains over the simpler prediction-free (0A4T) baseline at 10%–50% ratios and still lags behind ReCalKV/Palu on the long-context RULER benchmark at 70%?

(Q3) Reconstructing target heads introduces a non-trivial computational overhead per layer—what are the actual wall-clock TTFT, TPOT, and decoding throughput (tokens/sec) evaluations of TPNP compared to uncompressed and existing compressed baselines?

(Q4) How does TPNP handle practical GPU batching and parallel execution given its highly heterogeneous, layer-wise partitions and ranks, and is there a concrete path to hardware-efficient deployment without custom CUDA or Triton kernels like Palu or KIVI?

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

Related papers

Discussion (0)

Sign in to comment.