Skip to content

Back to the catalog

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

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

OVAL (Output-Aware Local page bases) is a training-free method for encoding KV cache pages in page-sparse attention, designed so that retrieval directly accounts for how approximation errors affect the value-weighted attention output rather than just estimating attention scores. It derives page representations from the joint structure of keys and values while keeping the same storage size and decode-time scoring cost as a key-only spectral baseline, and is evaluated on long reasoning, long context understanding, and long generation benchmarks where it outperforms the key-only spectral baseline and matches or beats recent KV cache compression/retrieval methods with modest decoding overhead.

TL;DR A training-free, output-aware KV cache page encoding that improves page-sparse attention retrieval for long-context LLM inference at no extra storage cost.
Open original ↗
Document

What it claims

OVAL is a training-free page summary for page-sparse KV retrieval. It is a drop-in change to the basis of a page-local spectral summary (LOCKS-style key PCA). The basis weights key directions by how much they move the attention output, which depends on the values, not only by key variance. With the best tuning value η from a grid, it gets the highest avg@k among compressed methods in all nine long-reasoning model/benchmark settings, +3.7 to 3.9 points averaged over FreeKV. It also gets the best LongBench v2 Overall score on two of three models, exceeding FullKV on both.

How it works

Per head, per completed page of m tokens:

  1. Center the page. Compute the key mean µ (kept exactly) and value mean, then centered keys X and centered values Y.
  2. Build two risk matrices. - The key-fidelity matrix is XᵀX, which is plain key PCA. - The output-sensitivity matrix is M_out = XᵀY G YᵀX, with G = W_Oᵀ W_O, the head's output projection. - M_out comes from linearizing the within-page attention output at uniform attention. It ranks key directions by their coupling to value differences. An error that only shuffles attention among similar values costs nothing.
  3. Mix them. Normalize each matrix by its trace, then blend: M_η = (1−η)·c_key·XᵀX + η·c_out·M_out. - η = 0 recovers key PCA. - η = 1 is purely output-driven. - The blend is motivated by the paper's analysis: output error is first-order in discarded logit directions, while page log-mass (retrieval) error is second-order.
  4. Take the leading r eigenvectors as the basis B_η. - When m < d, this is solved as an m×m eigenproblem. - If the rank is below r, the remaining columns are filled from the key residual's singular directions.
  5. Store (µ, B_η, R_η = X·B_η). Pages are scored by an approximate log-sum-exp of the logits. The per-page scoring cost is O(d + dr + mr + m), identical to key-only spectral summaries.

Values are read once, at summary construction, and never during scoring. No value statistics are stored.

Evidence

Unless noted otherwise, results use rank r = 8, G = W_OᵀW_O, and the per-setting best η (η*).

Long reasoning: MATH500, AIME24 and GPQA, with k = 8 generations per problem.

ModelFreeKV avg@kOVAL avg@k
DeepSeek R1 Llama 8B51.8355.69
DeepSeek R1 Qwen 7B54.1457.83
DeepSeek R1 Qwen 14B62.5666.42
  • The largest gains are on AIME24, at 5.8 to 7.1 points.
  • OVAL ties FreeKV on Qwen 14B GPQA.
  • Pass@k is mixed: OVAL is slightly below FreeKV on Llama 8B and Qwen 7B, and above it on Qwen 14B.

LongBench v2: inputs truncated to 64K tokens, KV budget 2048, run on Llama 3.1 8B Instruct and Qwen 2.5 7B/14B Instruct.

  • Overall score is 29.82 on Llama 8B and 28.03 on Qwen 7B. Both are the best among compressed methods and above FullKV.

LongGenBench: 16K-token generations, scored by completion rate (CR) and CR×Acc. The fetched text cuts off before these results.

How to use it

Code is at https://github.com/Ashkan13776/oval-kv. The page gives no install commands or licence.

To adopt it in a system that already uses page-local key PCA summaries:

  • Swap in the M_η basis construction. Scoring and storage are unchanged.
  • You need W_O at summary-build time for G.
  • You need to choose η and r. The paper's default rank is r = 8.

Limits

  • Headline numbers use oracle η. η* is the best value per setting at a fixed budget. The paper separately studies picking η on a disjoint calibration set and how well one value transfers across tasks, but those results are not in the fetched text. Expect smaller gains with a single fixed η.
  • Overhead is not quantified here. The page says "modest decoding overhead", but the efficiency section is not in the fetched text. Ablations over rank and page budget are in the appendix and also not shown.
  • Gains are uneven by metric. They concentrate in avg@k; pass@k does not consistently beat FreeKV.
  • The derivation simplifies. It assumes isotropic queries (E[qqᵀ] = I), linearizes at uniform within-page attention, and drops the page's global attention weight so the basis depends only on (K, V). The paper says extensions are in its appendix.
  • Summaries cover completed pages only. The basis is built when a page completes.

Organisations named here

  • Ashkan Shahbazi

Techniques named here

  • OVAL

Related in inference