acceptodds
Withdrawn from ICLR 2027

OVAL: Output-Aware Local Page Bases for KV Cache Retrieval

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

Abstract

Long context inference with large language models becomes increasingly expensive as attention must operate over an ever growing KV cache. Page sparse attention reduces this cost by representing each KV page compactly and retrieving only a subset for each query. Existing retrieval methods are designed to estimate attention scores or page relevance, but their objectives do not directly account for how approximation errors affect the resulting value weighted attention output. We introduce OVAL, an output aware page encoding derived from the joint structure of keys and values while preserving the key information needed for accurate retrieval. OVAL is training free and requires no additional value dependent statistics at inference time. Once constructed, its stored representation has the same size and decode time scoring cost as a key only spectral representation. Across long reasoning, long context understanding, and long generation benchmarks, OVAL consistently improves over the key only spectral baseline and performs competitively with recent KV cache compression and retrieval methods. On long reasoning benchmarks, it achieves strong avg@\(k\) performance across model benchmark pairs, while matching or surpassing leading baselines on several long context understanding and generation settings with modest decoding overhead. Code is available at https://anonymous.4open.science/r/oval-kv-4424/.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV cache compression, LLM Inference, Sparse Attention

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_sUWTOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes a training-free page-level summary for sparse KV retrieval. Standard methods build each page's compact representation from keys only, use it to predict a page's attention mass for top-k ranking, and then run exact attention on the original tokens of the kept pages. The authors argue the selection objective should reflect the attention output, not just the logits, so they construct each page basis from keys and values via one tuning parameter that trades key fidelity against output sensitivity, computed cheaply as a small per-page eigenproblem. Values are used only when building the basis, not at decode, so the stored summary and its scoring cost match a key-only spectral method. Gains are reported on reasoning, long-context-understanding, and long-generation benchmarks.

Critical strengths
  1. The motivating observation is valid: preserving attention logits is genuinely not the same as preserving the attention output, and the worked example showing that the highest-variance key direction can be irrelevant to the output while a lower-variance one is critical is a clean way to make this precise.
  2. Results look strong as reported: OVAL achieves the highest avg@k among compressed methods in all long reasoning settings and the best LongBench v2, and to stay competitive on LongBench and InfiniteBench.
  3. Code is open-sourced via the anonymized repository, which supports reproducibility of the paper.
Critical weaknesses
  1. The gains look like oracle tuning, not a method property. No η is stable across datasets or models, yet every headline cell reports "η⋆ is the best evaluated mixing parameter for each setting," chosen on the test score itself. A per-setting sweep that keeps the winner is effectively parallel trials picking the best, and is not a fair comparison to baselines with no such knob.
  2. Latency is only reported on LongBench v2 and InfiniteBench, not on the long-reasoning benchmarks that carry the headline. Reasoning decodes far more tokens, so per-step scoring over more pages and the extra per-page summary build should cost more than the ~10% overhead shown. Report decode and build overhead on reasoning.
  3. By the paper's own numbers pass@k is below FreeKV on two of three models while avg@k is above. For reasoning, pass@k is often the metric that matters. Please explain the mechanism and state whether this is a real weakness or small-sample noise.
Questions for authors

I think Weakness 1 and Weakness 3 are linked: by sweeping over η (the five grid values, keeping the best per setting), you are running an implicit pass@5, which raises the average (avg@k). This is why I give you rejection. I'm not sure my understanding is correct, but if you can rebut this point, I would be willing to give the paper a higher score.

Reviewer_xNK4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

OVAL constructs compact page summaries for sparse KV retrieval using both keys and values. It combines normalized key covariance with a matrix describing the local sensitivity of the conditional attention output, then retains a leading eigenspace. Values influence summary construction but are unnecessary for subsequent page scoring. Selected pages use their original keys and values for attention. The paper derives this construction, evaluates it across reasoning and long-context tasks, and studies a calibration procedure for the mixing parameter eta and decode latency.

Critical strengths
  1. The method provides a precise, implementable connection between key-value coupling and a spectral page representation. Appendix A carefully distinguishes the conditional surrogate from full-cache sensitivity, states the local nature of the approximation, and handles rank deficiency and eigenspace completion. The stored summary format and scoring complexity match the key-only spectral endpoint.
  2. Table 4 exposes the complete eta sweep, including the key-only endpoint, while Table 3 evaluates a separately calibrated, frozen setting. The latter improves over FreeKV on all three reasoning tasks for Llama 8B, including AIME24, which is absent from calibration. The paper also candidly reports unsuccessful transfer on Qwen 7B.
Critical weaknesses
  1. The main accuracy claims rely heavily on evaluation-dependent parameter selection. Section 4.3 acknowledges this, and Appendix D.8 specifies that eta is maximized separately for each metric, so table entries need not describe one common configuration. The calibration study partially addresses this concern, but its Qwen 7B average is 54.28 versus FreeKV's 54.72, and it does not cover Qwen 14B or the long-context and generation tasks. Consequently, the headline sweep improvements establish potential rather than consistently demonstrated deployment gains. The small reasoning subsets also make uncertainty around these differences relevant.
  2. The claimed longer-context result has an unresolved protocol conflict. Table 6 and Appendix C describe contexts exceeding 100K and a regime beyond the 64K LongBench setup, whereas Appendix D.4 specifies InfiniteBench truncation to 65,536 tokens and D.2 lists that context limit. This directly affects interpretation of the result. The accompanying runtime evidence supports a measured accuracy-latency tradeoff, but its scope should remain clear: Table 6 reports 24.7 versus 23.0 ms/token for OVAL and FreeKV, with no dense timing reference. D.8 also notes that accuracy runs retain full KV plus summaries, so equal attended-token budgets do not establish equal memory usage.
Questions for authors
  1. Can you report the principal comparisons using an eta selected without test labels, together with the key-only endpoint and FreeKV on matched held-out examples, and uncertainty for the reasoning differences?
  2. What were the actual post-truncation context lengths for Table 6? Which description should be corrected if the reported experiments used a different context limit?
  3. For the reported efficiency setting, can you clarify summary memory and construction/prefill costs, and provide a matched key-only spectral comparison to isolate the incremental cost of output awareness?
Reviewer_r32SOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

To address a limitation of existing sparse KV cache retrieval methods, which construct page summaries from keys alone, the authors propose training-free OVAL, an output-aware page encoding derived from both keys and values. OVAL obtains each page basis in closed form that combines key fidelity with value-dependent output sensitivity, balanced by a single parameter eta. Values are used only when the summary is built, so the stored summary and decode-time scoring cost match those of a key-only spectral summary. When using the oracle eta, OVAL achieves the best performance among compressed methods on long reasoning benchmarks and is competitive on LongBench v2 and LongGenBench. Authors also report the results when using the practically available eta which also shows decent performance in some cases.

Critical strengths
  1. I believe the paper's motivation (tackling the limitation of existing retrieval methods that focus only on keys) is sound. The proposed method the final objectives seems reasonable and theoretically grounded. The final objective is reduced to PSD eigenvalue problem and it is practically meaningful since it is training-free.

  2. The paper is generally well-written and easy to follow, even for novice readers.

  3. The results using the oracle (\eta) are very strong, showing the effectiveness of the underlying motivation and proposed method under an idealized setting.

  4. The experiments cover a diverse range of benchmarks and model backbones.

Critical weaknesses
  1. The main weakness is that the performance seems to be highly dependent on the choice of eta. Although the authors evaluate practical settings using a frozen eta selected on a held-out dataset and a sweep over candidate values in Tables 3 and 4, the results suggest that the choice of eta can substantially affect the final performance. More detailed analyses are needed to establish whether the proposed method can consistently outperform the original model (FreeKV) in practical settings.
  • Table 3 evaluates only a limited set of tasks and models. I believe the main results in Tables 1 and 2 should also be reported using practically obtainable values eta.
  • Although the performance gap in Table 3 seems substantial, it is unclear whether this advantage holds more broadly, given the strong sensitivity to eta suggested by the results in Table 4.
  • If identifying a suitable eta is necessary to outperform FreeKV, the additional computational cost and time required for tuning should also be considered in the overall evaluation.
  • A more systematic algorithm for selecting eta would strengthen the practical applicability of the method.
  1. I'm not sure how the underlying assumptions are reasonable like assumption 3.1.

  2. Minors

  • In Figure 1, two left figures seem almost same, which cannot find the main difference.
Questions for authors

Wrote above.

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

Related papers

Discussion (0)

Sign in to comment.