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

1 Introduction

• Attention costs grow with sequence length, and each decoding step must access the growing KV cache, making long-context inference increasingly expensive.Pages are the retrieval unit: systems summarize each page, select a subset, then compute exact attention over its tokens.Source: §1 · p. 1
• Key-based summaries preserve logits or key geometry, but attention propagates a value-weighted output whose sensitivity depends on which values receive probability.A small logit error can substantially change the output when probability shifts between tokens with very different values; key-only criteria cannot distinguish such cases.Source: §1 · p. 2
• OVAL builds each page basis jointly from keys and values, combining output sensitivity with key covariance in a page-local eigenproblem.The basis interpolates from ordinary page-local key PCA toward value-informed directions according to their effect on the attention output.Source: §1 · p. 2
• OVAL uses values only when constructing summaries; its stored representation and decode-time scoring cost match a key-only spectral summary.The introduction reports consistent improvement over the key PCA endpoint on long reasoning and strong performance against contemporary KV compression and retrieval methods.Source: §1 · p. 2
• OVAL’s output-aware component achieves the highest avg@k among compressed methods in all long-reasoning settings, by +3.7–3.9 points.The introduction also reports the best LongBench v2 Overall score on two of three models.Source: §1 · p. 2

2 Related Work

• Cache-compression approaches include shared KV heads, quantization, low-rank projection, and eviction, but evicted information cannot be recovered if its relevance changes later.CriticalKV grounds eviction in attention-output perturbation and finds value states matter beyond attention weights.Source: §2 · p. 2
• Sparse retrieval estimates query-relevant cache regions, using page-level geometric or key statistics, reduced-space token scoring, vector search, and learned or structured selection methods.The surveyed methods include Quest, ArkVale, UNIQUE, SparQ, Loki, ShadowKV, InfiniGen, PQCache, RaBitQCache, ParisKV, and MagicPIG.Source: §2 · pp. 2–3
• Key-only page summaries can leave an output-important page such as p3 below the top-2 retrieval cutoff, while OVAL’s basis uses keys and values to preserve output-sensitive directions.The figure contrasts key-only summaries and approximations with OVAL’s output-aware basis.Source: Figure 1 · p. 3
• LOCKS is the closest page-level spectral approach: it builds a page-local key basis, whereas OVAL uses paired key–value geometry to prioritize directions relevant to the attention output.The passage notes consistency with evidence that value states help identify critical entries [22].Source: §2 · p. 3

3.1 Setup and objectives

• The method retains each page’s mean key and projects its centered keys onto a rank-r subspace, using the resulting residual for retrieval and output objectives.Ranking pages by their log attention mass ranks their total attention probability for a fixed query.Source: §3.1 · p. 4
• The output risk weights key directions by their coupling to value differences, unlike key PCA, which retains directions with the most key energy.The query second-moment analysis assumes E[qq⊤] = I_d.Source: §3.1 · p. 4

3.2 Hybrid objective

• The hybrid objective combines normalized key and output risks; its leading rank-r eigenspace defines the basis, with η=0 recovering key PCA and η=1 minimizing the conditional-output surrogate.Intermediate η values combine the two scaled risks, and the basis is constructed from page keys and values alone because the full-cache page-probability weight is omitted.Source: §3.2 · p. 5

3.3 Computation and summary

• For short pages, the eigenproblem and normalizers use m×m matrices, and the stored summary is scored without values at decode time.Per-page decoding score cost is O(d + dr + mr + m) operations; values are used only during summary construction.Source: §3.3 · p. 5

4 Experiments

• The evaluation uses rank r = 8 by default and reports η⋆, the best value in the evaluated grid at a fixed sparse KV budget, unless stated otherwise.The experiments also include held-out calibration, η sensitivity, end-to-end efficiency, and additional rank and page-budget ablations.Source: §4 · p. 5

4.1 Long reasoning Tasks

• OVAL is the best compressed method across all nine long-reasoning model–benchmark settings, tying FreeKV only on Qwen 14B GPQA; average avg@k rises from 51.83 to 55.69 on Llama 8B, 54.14 to 57.83 on Qwen 7B, and 62.56 to 66.42 on Qwen 14B.Pass@k is more mixed: OVAL is slightly below FreeKV on Llama 8B and Qwen 7B, but above it on Qwen 14B.Source: §4.1 · p. 5, Table 1 · p. 7

4.2 Long context understanding and generation

• On LongBench v2, OVAL leads compressed methods on Llama 8B and Qwen 7B but ranks below the strongest compressed baseline on Qwen 14B; its LongGenBench results are more model-dependent.Across all three models, OVAL has the best or second-best Long-context score; it has the highest completion rate on Qwen 7B, while Llama 8B favors other retrieval methods.Source: §4.2 · p. 6

4.3 Selecting η in practice

• With η frozen from a disjoint 40-problem calibration pool, OVAL averages 53.69 versus FreeKV’s 50.42 on Llama 8B, but 54.28 versus 54.72 on Qwen 7B.Calibration transfers well on Llama 8B, while on Qwen 7B the pool does not identify the best setting; task-specific sweeping leaves gaps of 2.05 and 3.50 points, respectively.Source: §4.3 · p. 6

4.4 Sensitivity to η

• No η setting is universally optimal: long reasoning generally benefits from nonzero η, LongBench v2 is relatively stable across interior values, and LongGenBench is more model-dependent.η = 0 recovers page-local key PCA, while larger values increase output sensitivity.Source: §4.4 · p. 6

4.5 Efficiency

• On LongBench v2, OVAL incurs about 10% decode overhead over FreeKV while improving accuracy most on long inputs.On InfiniteBench LongQA, it achieves higher accuracy at modest latency and is substantially faster than ArkVale.Source: §4.5 · p. 7

5 Conclusion

• OVAL combines key fidelity with value-dependent output sensitivity while retaining the summary format and decode-time scoring complexity of key-only spectral retrieval.The conclusion reports held-out η calibration transfer on Llama 8B, with substantial headroom remaining on Qwen 7B.Source: §5 · p. 7
• Across long reasoning, long-context understanding, and long generation, OVAL improves over the key-only endpoint and performs strongly against recent sparse KV baselines with modest decoding overhead.The paper’s evaluation also includes LongBench v2 accuracy by context length and LongGenBench generation metrics.Source: §5 · p. 7, Table 2 · p. 8
• The results support incorporating output sensitivity into compact retrieval representations and designing sparse-attention summaries around downstream approximation error rather than key geometry alone.The evaluation includes calibration-based η selection for long reasoning, with scores compared on the same held-out examples.Source: §5 · p. 7, Table 3 · p. 8

A Proofs and extensions

• The appendix organizes proofs of output sensitivity and first-order output expansion, derives a page-mass surrogate, and extends results beyond isotropic-query and uniform-attention assumptions.It also collects the softmax and spectral facts used throughout the paper.Source: A Proofs and extensions · p. 15

A.1 Preliminaries

• The preliminaries define softmax-based output and sensitivity notation, and center the page keys and values as X = HK and Y = HV.For a probability vector b, S(b) is defined as Diag(b) − bb⊤.Source: §A.1 · p. 15
• The spectral residual minimization is equivalent to maximizing tr(B⊤MB), with equality at leading invariant subspaces; positive eigenvectors of C⊤C are right singular vectors of C.The retained subspace is unique when λr > λr+1.Source: §A.1 · p. 15

A.2 Output sensitivity

• The appendix gives an exact path identity for output changes along a logit perturbation and a deterministic bound based on the convex hull of the page values.The path identity integrates along the segment between the two logit vectors.Source: §A.2 · pp. 16–17
• For centered perturbations at uniform attention, page-mass derivatives vanish and the output derivative is proportional to the centered value response Y⊤h/m.The global sensitivity result fixes the query, page values, and background cache.Source: §A.2 · p. 17

A.3 Output aware page basis

• The output surrogate is positive semidefinite, so its leading rank-r eigenspace minimizes the surrogate risk.When its rank is below r, the remaining basis directions can be chosen orthonormally in its nullspace.Source: §A.3 · p. 18
• The surrogate is the leading coefficient of expected squared conditional error in the local limit, not a claim of optimality for finite-logit nonlinear error.No higher query moment is needed for this local statement.Source: §A.3 · p. 19
• A value permutation can preserve key and marginal value covariances yet change output sensitivity; the example’s sensitivity scalar changes from 4 to 1.The page’s key matrix is unchanged in the example.Source: §A.3 · p. 19
• For rank 1, key PCA selects the first direction while the output-aware basis selects the second, whose leading output risk is zero.The leading output risk for key PCA is σ2^2/(m^2d).Source: §A.3 · p. 19

A.4 Page mass fidelity and the hybrid basis

• The key-fidelity bound needs only a finite second query moment, not a restriction on logit magnitudes.The expected signed log-mass error has a local expansion whose leading term is identified under query scaling.Source: §A.4 · p. 21
• The hybrid risk is minimized by the leading rank-r invariant subspaces of Mη, combining scaled key and output components.When the output-aware subspace has lower rank than r, the completion preserves minimum hybrid risk while minimizing key risk among completions.Source: §A.4 · pp. 21–22

A.5.1 Nonisotropic query distributions

• For a positive-definite query second moment, whitening gives a corresponding output-aware basis in whitened query coordinates.The leading rank-r eigenspace minimizes the corresponding normalized risk.Source: §A.5.1 · p. 22

A.5.2 Nonuniform within page attention

• Uniform within-page attention yields a query-free eigensolution; a fixed nonuniform reference gives a frozen local metric, while query sampling loses the single closed-form eigenproblem.The sampled-query construction is more query-dependent.Source: §A.5.2 · p. 22

B Rank and Page Budget Ablations

• The rank ablation uses DeepSeek R1 Qwen 7B on GPQA, fixes the budget at 2048 tokens, and tests r values of 1, 4, 8, and 16.It measures retrieval-quality sensitivity to page-representation capacity.Source: B Rank and Page Budget Ablations · p. 23
• The budget ablation fixes r = 8 and tests retrieved KV budgets of 512, 1024, 2048, and 4096 tokens.It measures the effect of increasing the number of retrieved KV tokens.Source: B Rank and Page Budget Ablations · p. 23
• Together, the ablations test the robustness of the main-evaluation default, r = 8 with a 2048-token budget.Other settings follow the main experiments.Source: B Rank and Page Budget Ablations · p. 23

C InfiniteBench Results

• On LongQA, OVAL reaches 37.4 accuracy versus FreeKV at 36.0, ArkVale at 35.9, and RaaS at 35.5, recovering 87.2% of FullKV accuracy versus FreeKV’s 83.9%, while remaining 5.5 points below FullKV.Source: C InfiniteBench Results · p. 23
• OVAL adds 1.7 ms per token, a 7.4% decode overhead relative to FreeKV, and is faster than RaaS at 27.4 ms and ArkVale at 76.9 ms.The reported accuracy–latency comparison places OVAL on the evaluated retrieval methods’ Pareto frontier, while a 5.5-point gap to FullKV remains.Source: C InfiniteBench Results · p. 23

D Implementation details and reproducibility

• The artifact includes code, a FreeKV patch, and per-experiment scripts; the implementation patches a specified FreeKV commit rather than vendoring the upstream repository.The patch covers 19 files.Source: D Implementation details and… · p. 23

D.1 Software, hardware, and build

• The implementation lists flash_attn as a hard dependency and requires transformers below 4.54 for the stated vLLM compatibility constraint.It supports cu121 through cu128, while cu130 does not load with the CUDA 12.2 driver.Source: §D.1 · p. 24

D.2 Models

• The listed evaluations use Llama 3.1 8B, Qwen 2.5 7B and 14B, and DeepSeek R1 Distill Llama 8B and Qwen 7B and 14B checkpoints.The shared model configuration sets a 65,536-token context limit.Source: §D.2 · p. 24

D.3 Method configuration

• The core configuration uses page size 32, rank r = 8, and η values from 0 to 1 in increments of 0.25.Summaries are constructed in float32 and cast back to the cache dtype; centering limits a page of size 32 to rank 31.Source: §D.3 · p. 24

• The protocol table specifies benchmark-specific data, budgets, decoding, and metrics; LongGenBench judging uses Qwen3 32B with a 400-record evaluation file.The judge settings include tensor parallelism 2 and a maximum generation length of 50.Source: §D.4 · p. 25
• Every method uses an effective KV budget of 2048, even when harnesses express it through different selectable, sink, and recent-region settings.Baseline arms otherwise differ only in page representation or retrieval method.Source: §D.4 · p. 25
• LongBench v2 uses greedy decoding and truncates inputs over 65,536 tokens to the first and last 32,768, while 6–13% of examples remain unparsable across methods.A valid prediction must produce the specified answer format within 128 tokens.Source: §D.4 · p. 25
• For reasoning evaluation, the study samples k = 8 generations per problem at T = 0.6 and p = 0.95, using separate seeds for independent generations; MATH500 and GPQA use harness-distributed 50-problem subsets.Source: §D.4 · p. 25
• InfiniteBench evaluation samples 50 examples per task with seed 42, uses the reference prompts and scorers, and omits math_calc, leaving 11 tasks.The shared evaluation harness includes OVAL and all baseline arms.Source: §D.4 · p. 25

D.5 Latency Evaluation

• Latency is the mean interval between generated tokens after a complete-generation warmup, with all methods measured at effective KV budget 2048.LongBench v2 timing covers short, medium, and long inputs across 148, 190, and 39 items, respectively.Source: §D.5 · p. 26

D.6 Decoding released output paths

• Output-path fields encode representation, rank, η, retrieval steps, and other settings, allowing released experiment paths to be decoded.For example, oval_r8 denotes the OVAL representation at rank 8.Source: §D.6 · p. 26

D.7 Corrections to the reference harness

• The reference harness corrections align metadata with selected prompt ranges and validate reordered projection width when multi-GPU sharding can duplicate columns.The width issue was observed on Qwen2.5 14B under multi-GPU sharding.Source: §D.7 · p. 26

D.8 Scope and reported quantities

• OVAL changes only the retrieval page representation; reported accuracy experiments retain the full KV cache, and η⋆ may differ across metrics within a table row.Thus, these experiments measure sparse retrieval rather than compressed key attention.Source: §D.8 · pp. 26–27