1 Introduction↩︎

Large language models (LLMs) [1]–[5] with extended context lengths rely on the KV cache to support attention over prior tokens. However, maintaining the KV cache incurs substantial memory overhead, motivating a growing body of work on KV-cache compression [6]–[10]. KV-cache eviction methods reduce memory usage by retaining only the most salient tokens—typically those with the highest attention scores—under a fixed cache budget. This inevitably discards some tokens that, while not top-ranked, still carry useful contextual information [11]. KV-cache merging methods have been proposed to recover information from these lower-ranked evicted tokens by incorporating their representations into the retained tokens, without increasing the cache budget.

Early eviction methods selected tokens according to cumulative attention scores [12], [13], which often fragmented contiguous semantic spans and weakened the integrity of the retained text. SnapKV [14] mitigates this issue by pooling attention scores over segments and then selecting the top-\(k\) segments, thereby allowing retained tokens to form contiguous spans that better preserve context. Consequently, SnapKV was among the first methods to adopt span-based retention rather than token-based retention. Many subsequent eviction methods have adopted this span-based strategy [15]–[18].

In contrast, most prior KV-cache merging methods were designed primarily for earlier token-based retention strategies [11], [19]–[21]. Broadly, these methods can be grouped into two classes: (i) local, adjacency-based matching and (ii) key-similarity-based matching. Adjacency-based matching methods (e.g., CaM [11], AsymKV [21]) leverage the high similarity between neighboring tokens to merge adjacent tokens using carefully weighted averaging, yielding more compact representations. Key-similarity-based methods (e.g., KVMerger [19], D2O [20]) merge tokens when their keys are highly similar, based on the observation that keys largely determine attention weights, so similar keys imply similar importance patterns. Prior work, together with our observations in Fig. 1, indicates that adjacent tokens often have highly similar keys [19]. Thus, key-similarity-based matching can be seen as a generalization of adjacency-based matching over a broader candidate neighborhood.

As eviction methods have increasingly shifted from token-based retention [12], [13], [22]–[24] to span-based retention [14]–[18], the merge assignments produced by prior KV-cache merging methods have become markedly more concentrated. In particular, because most merging methods rely on local heuristics, they often funnel many evicted tokens into a small set of span-boundary tokens. These boundary tokens therefore become the main information carriers, overloading their representations and making them prone to over-merging: excessive aggregation can blur or even erase their original semantics, thereby degrading overall performance. A mathematical analysis is provided in Appendix 6. Fig. 1 provides a concrete example on NarrativeQA [25]: we use the same key-similarity-based matching strategy as in D2O/KVMerger to merge evicted tokens into the KV cache retained by SnapKV, and observe that merge assignments concentrate near span boundaries. Additional visualizations in Appendix 7 further confirm this concentration pattern.

To address the challenges introduced by span-based retention and illustrated in Fig. 2, we propose GRKV (Global Regression for KV Cache), a global KV-cache merging method that aligns the compressed cache with the full cache by directly minimizing the discrepancy in attention outputs. We achieve this alignment with ridge-regression-based merge steps that use the full cache as the information source and distribute information from evicted tokens across retained tokens, while regularizing the updates to prevent over-smoothing and carrier-token blurring. In contrast to prior local heuristics that concentrate merges onto a small set of span-boundary tokens, GRKV treats all retained tokens as merge carriers, mitigating over-merging by expanding the effective carrier capacity.

Our contributions can be summarized as follows:

1. We propose GRKV, a training-free KV-cache merging method that explicitly models the discrepancy between the compressed-cache and full-cache attention outputs. By minimizing this discrepancy, GRKV provides a principled objective for optimizing the merging process.

2. GRKV is the first global KV-cache merging method designed specifically for modern span-based retention. By enlarging the pool of carrier tokens, GRKV increases the capacity to incorporate information from evicted tokens, thereby better preserving otherwise discarded context. Moreover, GRKV mitigates over-merging through ridge-regression regularization, which curbs carrier-token blurring and reduces information loss.

3. Across 16 LongBench and 13 RULER tasks, GRKV is the only KV-cache merging method that improves overall performance when combined with modern span-based KV-cache eviction methods, while remaining a plug-and-play module with minimal added overhead.

2 Related Work↩︎

For token-level KV-cache compression, in which the compressed units are individual KV-cache entries, existing methods can be categorized into eviction-based and merging-based methods.

Eviction-based compression. Training-free eviction methods typically rely on attention-derived importance scores. H2O [12] maintains heavy-hitter tokens using accumulated attention scores. SnapKV [14] identifies important tokens using attention scores computed from a query window. PyramidKV [15] allocates more KV-cache capacity to lower layers while assigning a smaller budget to higher layers. CriticalKV [17] identifies and retains critical tokens under a perturbation constraint. Ada-KV [18] allocates more budget to heads that model long-range dependencies. Training-based eviction methods learn specialized retention or attention patterns. DuoAttention [26] splits attention heads to reduce memory through a specialized training procedure. HeadKV [16] performs compression through learned dropping and abstraction.

Merging-based compression. KV-cache merging methods reduce information loss by merging evicted tokens into retained ones instead of simply discarding them. CaM [11] merges evicted tokens into retained tokens using attention-weighted sampling. KVMerger [19] clusters tokens and replaces each cluster with a pseudo-token constructed by weighted averaging. D2O [20] dynamically chooses between eviction and merging at different token positions. AsymKV [21] applies different local merging strategies for homogeneous keys and heterogeneous values.

Comparison to prior work. Inspired by merge-focused work such as CaM, we study the design of a general merging method for modern span-based KV-cache eviction methods. While GRKV is closely related to prior merging methods, it differs by explicitly optimizing a global reconstruction objective rather than relying on local heuristics. By distributing recovered information across a larger set of retained tokens, GRKV reduces the burden on boundary carrier tokens and more faithfully preserves the attention outputs of the full cache.

3 Methods↩︎

3.1 Preliminary↩︎

Standard attention computation. Autoregressive inference in an LLM typically consists of two phases: prefilling and decoding. For simplicity, we describe a single attention head. In the prefilling phase, the model computes and stores the KV cache for all input tokens, so that the corresponding KV states need not be recomputed during subsequent decoding steps [27], [28]. Concretely, \(K = H W^K\) and \(V = H W^V\), where \(H \in \mathbb{R}^{n \times d}\) denotes the hidden-state matrix for \(n\) input tokens, \(d\) is the head dimension, and \(W^K, W^V \in \mathbb{R}^{d \times d}\) are the key and value projection matrices. In the decoding phase, at the \(i\)-th decoding step, the model forms a query vector \(q_i = H_i W^Q\) with query projection \(W^Q \in \mathbb{R}^{d \times d}\). This query is matched against all cached keys to obtain attention weights, which are then used to aggregate the values and produce the output representation: \(o_i = A_i V W^O\), where \(A_i = \operatorname{softmax}(q_i K^\top / \sqrt{d})\). Here \(W^O \in \mathbb{R}^{d\times d}\) denotes the output projection matrix, and \(A_i\) is the attention-weight vector over all cached tokens.

Full vs.retained KV cache. Let the uncompressed KV cache be denoted by \(K_{\text{full}}, V_{\text{full}} \in \mathbb{R}^{n \times d}\). To lower memory consumption, an eviction method retains only \(c\) KV-cache entries, producing a reduced cache \(K_{\text{Ret}}, V_{\text{Ret}} \in \mathbb{R}^{c \times d}\) with \(c < n\). For a query \(q_i\), the full-cache attention output is \(o_i^{(\text{full})} = A_i^{(\text{full})} V_{\text{full}} W^O\), where \(A_i^{(\text{full})} = \operatorname{softmax}(q_i K_{\text{full}}^\top / \sqrt{d})\). Using the retained cache, the output becomes \(o_i^{(\text{Ret})} = A_i^{(\text{Ret})} V_{\text{Ret}} W^O\), where \(A_i^{(\text{Ret})} = \operatorname{softmax}(q_i K_{\text{Ret}}^\top / \sqrt{d})\). The difference between \(o_i^{(\text{full})}\) and \(o_i^{(\text{Ret})}\) quantifies the information lost due to compression: a larger gap indicates greater deviation from the full-cache result. This motivates the following per-query discrepancy loss: \[\min_{K_{\text{Ret}}, V_{\text{Ret}}} \mathcal{L}_i = \,\|\,o_i^{(\text{full})} - o_i^{(\text{Ret})}\,\|_2^2 = \,\|\,\Delta_i W^O\,\|_2^2~,\] where we define \(\Delta_i = A_i^{(\text{full})} V_{\text{full}} - A_i^{(\text{Ret})} V_{\text{Ret}}\) as the difference between the full-cache and retained-cache pre-projection attention outputs for query \(i\). Intuitively, \(\mathcal{L}_i\) measures how much the compressed cache changes the model’s output for that query.

Objective decomposition. To simplify the optimization, we derive an upper bound on \(\mathcal{L}_i\) by separating out the output projection \(W^O\), which is fixed for a given model. By submultiplicativity of matrix norms, \(\|\Delta_i W^O\|_2^2 \,\le\, \|\Delta_i\|_2^2\,\|W^O\|_2^2\). Since \(\|W^O\|_2^2\) is constant for a given model, we instead minimize the surrogate objective: \[\min_{K_{\text{Ret}}, V_{\text{Ret}}} \widetilde{\mathcal{L}}_i = \|\Delta_i\|_2^2~.\] Minimizing \(\widetilde{\mathcal{L}}_i\) avoids the additional overhead of explicitly applying \(W^O\), while still promoting consistency with the full-cache attention output.

Notably, this objective naturally leverages all retained tokens as a carrier set for absorbing and consolidating information from evicted tokens. In contrast to local merging heuristics that funnel many evicted tokens into a small set of span-boundary carriers—overloading those tokens and increasing information loss—the GRKV objective promotes a broader set of retained tokens as merge targets. This more uniform distribution across retained tokens mitigates over-merging by reducing the imbalance among carrier tokens.

3.2 Estimating and Optimizing with a Surrogate Query Window↩︎

Surrogate query window. During generation, future queries are unknown, so the compressed cache cannot be optimized for each future query individually. GRKV instead uses a short prompt-derived query window as a surrogate. We find that attention outputs computed from different query windows within the same long context are highly consistent, indicating that a late-prompt query window provides a stable proxy for unseen future queries. Specifically, we conduct this analysis on HotpotQA [29]. For each sequence, we treat the first \(90\%\) of tokens as the prompt and the remaining \(10\%\) as future-query tokens, and further partition the future-query segment into windows of length \(m{=}32\). For each window \(W\), we compute the mean full-cache attention output: \[s_W = \frac{1}{m} \sum_{i \in W} A_i^{(\text{full})} V_{\text{full}}.\] We then measure cross-window consistency using the cosine similarity between summary vectors \(s_W\) from different windows within the same sequence. As shown in Fig. 3, these window-level summaries remain highly similar across the sequence. Additional visualizations are provided in Appendix 8.

Notably, optimizing with respect to a single query can overfit to its attention pattern, which is undesirable since the query distribution may shift during generation. A multi-query window provides a more stable optimization target. Following [14], GRKV uses the final query window of the prompt as its surrogate query window.

Window-level objective. Given a query window \(W\) containing \(m\) queries, we aggregate the discrepancy over all queries in the window: \[\min_{K_{\text{Ret}}, V_{\text{Ret}}} \widetilde{\mathcal{L}}_{\text{win}} = \big\|A_{\text{win}}^{(\text{full})} V_{\text{full}} - A_{\text{win}}^{(\text{Ret})} V_{\text{Ret}}\big\|_F^2~,\] where \(A_{\text{win}}^{(\text{full})}\) and \(A_{\text{win}}^{(\text{Ret})}\) are the attention-weight matrices for \(m\) queries in the window. Specifically, \(A_{\text{win}}^{(\text{full})} = \operatorname{softmax}(Q_{\text{win}} K_{\text{full}}^\top / \sqrt{d})\) and \(A_{\text{win}}^{(\text{Ret})} = \operatorname{softmax}(Q_{\text{win}} K_{\text{Ret}}^\top / \sqrt{d})\), where \(Q_{\text{win}} \in \mathbb{R}^{m \times d}\) contains the \(m\) queries in the window.

3.3 Ridge-Regularized KV Reconstruction↩︎

Directly optimizing the window-level objective can cause the retained KV cache to deviate too far from the initial post-eviction cache, leading to unstable changes in attention weights or overly smoothed values. We therefore regularize both \(K_{\text{Ret}}\) and \(V_{\text{Ret}}\) toward their initial post-eviction cache, \(K_{\text{Ret}}^0\) and \(V_{\text{Ret}}^0\). The resulting ridge-regularized objective is: \[\begin{align} \min_{K_{\text{Ret}}, V_{\text{Ret}}} \widetilde{\mathcal{L}}_{\text{KV}} = &\widetilde{\mathcal{L}}_{\text{win}} + \lambda_k\left\|K_{\text{Ret}}-K_{\text{Ret}}^0\right\|_F^2 \\ &+ \lambda_v\left\|V_{\text{Ret}}-V_{\text{Ret}}^0\right\|_F^2~. \end{align} \label{eq:eq5}\tag{1}\] The coefficients \(\lambda_k>0\) and \(\lambda_v>0\) control the strength of regularization for keys and values, respectively. Larger coefficients keep the compressed cache closer to its initial post-eviction cache, while smaller coefficients allow more aggressive reconstruction of the full-cache attention outputs.

3.4 Alternating KV-Cache Optimization↩︎

GRKV alternates between two updates: with the current keys fixed, it solves a ridge-regression problem for \(V_{\text{Ret}}\); with the current values fixed, it applies a local linearized ridge update to \(K_{\text{Ret}}\).

Value step. With the current keys \(K_{\text{Ret}}\) fixed, we update \(V_{\text{Ret}}\) by minimizing: \[\min_{V_{\text{Ret}}} \widetilde{\mathcal{L}}_{\text{V}} = \widetilde{\mathcal{L}}_{\text{win}} + \lambda_v\left\|V_{\text{Ret}}-V_{\text{Ret}}^0\right\|_F^2~.\]

Closed-form solution. This is a linear least-squares problem with Tikhonov regularization. Define \(X = A_{\text{win}}^{(\text{Ret})}\), \(Y = A_{\text{win}}^{(\text{full})} V_{\text{full}}\) and the \(c \times c\) identity matrix \(I_c\). Setting the gradient with respect to \(V_{\text{Ret}}\) to zero yields the closed-form solution: \[V_{\text{Ret}}^* = \big(X^\top X + \lambda_v I_c\big)^{-1} \big(X^\top Y + \lambda_v V_{\text{Ret}}^0\big)~. \label{eq:eq7}\tag{2}\] Here, \(V_{\text{Ret}}^*\) corresponds to the merged value cache.

Dual solution via Woodbury. When the cache budget \(c\) is large, directly inverting the \(c \times c\) matrix in Eq. 2 can be computationally expensive. However, since the query window size \(m\) is typically much smaller than \(c\), we use the Woodbury identity to solve an \(m \times m\) system instead: \[V_{\text{Ret}}^* = V_{\text{Ret}}^0 + X^\top Z,\] where \(Z = (X X^\top + \lambda_v I_m)^{-1}(Y - X V_{\text{Ret}}^0)\). In implementation, we adopt the corresponding dual formulation to improve efficiency. Since \(m\) (e.g., 32) is typically far smaller than \(c\) (e.g., 10% of the context length), this dual formulation substantially reduces both compute and memory overhead.

Key step. With the current values \(V_{\text{Ret}}\) fixed, we update \(K_{\text{Ret}}\) by minimizing: \[\min_{K_{\text{Ret}}} \widetilde{\mathcal{L}}_{\text{K}} = \widetilde{\mathcal{L}}_{\text{win}} + \lambda_k\left\|K_{\text{Ret}}-K_{\text{Ret}}^0\right\|_F^2~.\]

Linearized dual solution. Unlike the value step, the key-step objective is nonlinear because \(K_{\text{Ret}}\) appears inside the softmax. GRKV linearizes the attention output \(f(K_{\text{Ret}})=A_{\text{win}}^{(\text{Ret})}V_{\text{Ret}}\) around the current \(K_{\text{Ret}}\) and solves the resulting ridge problem in dual form. Let \(E=Y-f(K_{\text{Ret}})\), \(G=K_{\text{Ret}}-K_{\text{Ret}}^0\), and \(J=\left.\frac{\partial f}{\partial K}\right|_{K=K_{\text{Ret}}}\), where the matrices are vectorized when applying \(J\). Define \(e=\operatorname{vec}(E)\) and \(g=\operatorname{vec}(G)\). The key update is: \[\operatorname{vec}(K_{\text{Ret}}^*)=\operatorname{vec}(K_{\text{Ret}}^0)+J^\top\alpha, \label{eq:key95dual95update}\tag{3}\] where \(\alpha = (JJ^\top+\lambda_k I_{\mathcal{Y}})^{-1}(e+Jg)\). Here, \(I_{\mathcal{Y}}\) is the \(md \times md\) identity matrix and \(K_{\text{Ret}}^*\) corresponds to the merged key cache. Although the dual system has dimension \(md\), it is smaller than the primal key space of dimension \(cd\) when \(m \ll c\).

Fixed tokens during optimization. GRKV treats the retained cache as a global set of carriers, but some retained tokens should not be modified. In particular, we keep sink tokens, surrogate-window query tokens, and the \(\beta=10\%\) retained tokens with the highest attention scores unchanged. These tokens often anchor attention or carry local query semantics, so modifying their KV cache can harm generation fidelity. In Sec. 4.3, we analyze this design choice and its effect on performance.

Fig. 2 (c) presents an overview of the GRKV pipeline, and Algorithm 7 provides detailed pseudocode. The full derivations for the key and value steps are provided in Appendix 9.

2.4pt max width=

3.0pt max width=

5pt

4 Experiments↩︎

4.1 Experimental Settings↩︎

Models and Benchmarks. We evaluate GRKV on three open-source LLMs: Mistral-7B-Instruct-v0.3 [30], supporting up to 32K tokens; Llama-3.1-8B-Instruct [31] and Qwen3-14B [32], both supporting up to 128K tokens. The evaluation uses two long-context benchmarks: LongBench [33] and RULER [34]. Detailed benchmark information is provided in Appendix 10.

Baselines. For span-based eviction methods, we consider SnapKV [14], PyramidKV [15], CriticalKV [17], and Ada-KV [18]. For token-based eviction methods, we consider H2O [12]. For KV-cache merging methods, we evaluate CaM [11], D2O [20], and AsymKV [21].

Protocol and hyperparameters. We follow the protocols of [17], [18] and [35]: for tasks with a prompt and a final query, we compress the prompt independently of the final query, which yields a more challenging and realistic setting. Consistent with [11], each merging method is paired with a base eviction method to test whether merging can recover discarded information. For GRKV, we use one alternating KV update step (\(S=1\)), set the surrogate window size to \(m=32\), as in prior KV-cache eviction methods [14], [17], [18], and keep sink tokens, surrogate-window query tokens, and the top \(\beta=10\%\) retained tokens by attention score fixed. We set \(\lambda_k=\lambda_v=10^{-2}\) for Llama and \(\lambda_k=\lambda_v=10^{-1}\) for Mistral and Qwen. We use FlashAttention-2 [36], [37] for all methods except AsymKV, which cannot leverage FlashAttention-2.

4.2 Experimental Results↩︎

LongBench. LongBench [33] contains 16 long-context tasks spanning six categories: single-/multi-document QA, summarization, few-shot learning, synthetic tasks, and code. We evaluate under a 10% cache budget and report per-task scores in Table [tab:longbench95detailed9510]. GRKV consistently improves both base eviction methods across both model backbones. On Llama-3.1-8B-Instruct, it raises the average score from 33.96 to 34.58 with SnapKV and from 36.00 to 36.58 with CriticalKV, improving 14/16 tasks in both cases. On Mistral-7B-Instruct-v0.3, it improves SnapKV from 33.12 to 33.75 and CriticalKV from 33.69 to 34.30, with gains on 12/16 and 14/16 tasks. Other merging baselines are less reliable. CaM yields occasional gains but often reduces the average score, while D2O and AsymKV frequently degrade under span-based retention. In contrast, GRKV consistently improves the average score in all settings, demonstrating the benefit of global, ridge-regularized reconstruction.

RULER. RULER [34] evaluates long-context understanding across extraction (CWE/FWE), retrieval (NIAH), question answering, and variable tracking (VT) tasks. Under a 10% cache budget, Table [tab:ruler95detailed9510] shows that GRKV consistently improves both base eviction methods across both model backbones. Because AsymKV incurs high overhead at 16K and increases latency by \(\sim\)​15×, we exclude it. On Llama-3.1-8B-Instruct, GRKV raises the average score from 27.44 to 29.09 with SnapKV and from 40.83 to 41.51 with CriticalKV, improving 8/13 tasks in both cases. On Mistral-7B-Instruct-v0.3, it improves SnapKV from 21.18 to 21.67 and CriticalKV from 22.57 to 23.10, with gains on 10/13 tasks in both cases. In contrast, CaM and D2O often degrade performance, especially on retrieval tasks, due to over-merging.

Additional results on LongBench and RULER under a 20% cache budget are given in Appendix 11.

4.3 Ablations, Compatibility, and Efficiency↩︎

All ablations use SnapKV with GRKV under a 10% cache budget and report LongBench averages.

Regularization strength. As shown in Table 1, a mild ridge penalty is important: \(\lambda_k=\lambda_v=10^{-2}\) performs best (34.58), while removing regularization drops the score to 32.06. This indicates that regularization prevents overly aggressive KV updates while still allowing useful reconstruction.

Fixed retained-token ratio. Table 1 shows that fixing a small fraction of high-attention retained tokens is beneficial. The default \(\beta=10\%\) performs best (34.58), while fixing no retained tokens is weaker (34.34) and larger ratios slightly reduce performance by constraining too many carriers.

Update steps. Table 1 shows that one alternating KV update step is sufficient. Increasing \(S\) from 1 to 2 or 3 lowers the average score, suggesting that repeated updates can overfit the surrogate window.

Surrogate window size. Table 1 shows that the default \(m=32\) achieves the best score in this sweep (34.58), while increasing the window size to \(m=48\) and \(m=64\) lowers the average to 33.86 and 33.49, respectively. This supports using \(m=32\), which is also consistent with prior eviction baselines [14], [17], [18].

Fixed sink and window tokens. Table 1 validates keeping sink and surrogate-window query tokens fixed: allowing them to be updated reduces performance from 34.58 to 34.19. Preserving these special tokens improves optimization stability.

Optimized cache components. Table 1 compares updating only keys (GRK), only values (GRV), and both (GRKV). Updating both components performs best (34.58), indicating that key and value corrections provide complementary benefits.

Compatibility. Table [tab:compatibility95longbench] shows that GRKV improves diverse eviction backbones under a 10% cache budget on LongBench. On Llama-3.1-8B-Instruct, it improves PyramidKV, which dynamically allocates KV-cache budgets across layers, from 34.40 to 35.21, and Ada-KV, which dynamically allocates KV-cache budgets across heads, from 34.72 to 35.28. It also benefits the token-based retention baseline H2O, improving it from 29.65 to 31.68. On the larger Qwen3-14B model, GRKV improves span-based SnapKV from 38.29 to 38.98 and CriticalKV from 41.68 to 42.20.

Efficiency. We profile Llama-3.1-8B-Instruct on an A6000 with 16K–96K contexts at a 10% cache budget. As shown in Fig. 4, compression methods substantially reduce peak memory and avoid the full-cache out-of-memory failure at 96K. SnapKV with GRKV closely follows SnapKV in memory usage and retains efficient decoding: at 64K, it reduces latency from 64.84 to 37.75 ms/token compared with Full Cache, while remaining close to SnapKV. Its prefill overhead is moderate compared with heavier merging methods; at 96K, SnapKV with GRKV takes 49.71 s, close to D2O (48.20 s) and below CaM (53.87 s), whereas AsymKV reaches 788.49 s and also has higher decoding latency because it cannot use FlashAttention-2.

Additional RULER ablations, compatibility results, and efficiency tests across GPUs, batch sizes, and context lengths are provided in Appendix 12.

5pt

5 Conclusion↩︎

We proposed GRKV, a general training-free KV-cache merging method for modern span-based KV-cache eviction methods. GRKV formulates merging as a global regression objective to minimize the attention-output discrepancy between a compressed cache and the full cache. By treating all retained tokens as carriers and solving a ridge-regression problem, GRKV more effectively recovers information from evicted tokens and mitigates over-merging caused by local heuristics. Across 16 LongBench and 13 RULER tasks, GRKV is the only KV-cache merging method that improves overall performance with minimal overhead, suggesting that aligning compression objectives with model outputs can yield practical inference gains.

Limitations↩︎

Our empirical evaluation covers three open-source models: Llama-3.1-8B-Instruct, Mistral-7B-Instruct-v0.3, and Qwen3-14B, and evaluates them on LongBench and RULER. These benchmarks mainly evaluate English long-context understanding, code-oriented tasks, and synthetic retrieval tasks. We therefore do not claim that the same gains will necessarily generalize to other model families, larger proprietary systems, or multilingual/multimodal settings.

6 Why Span-Based Retention Amplifies Over-Merging↩︎

This appendix provides a first-order analysis of why span-based retention amplifies over-merging in local KV-cache merging methods. We show that span-based retention does not merely change which tokens are retained; under local matching rules, it reduces the number of active carrier tokens. This simultaneously increases the load on each carrier and shrinks the first-order feasible space for reconstructing the full-cache attention output.

6.1 Setup and Notation↩︎

Consider a single attention head. Let the full cache be denoted by \(K_{\text{full}},V_{\text{full}}\in\mathbb{R}^{n\times d}\). After eviction, the retained cache is \(K_{\text{Ret}}^0,V_{\text{Ret}}^0\in\mathbb{R}^{c\times d}\), and the evicted cache is represented by \(K_{\text{evict}},V_{\text{evict}}\in\mathbb{R}^{e\times d}\), where \(e=n-c\). For the surrogate query window \(Q_{\text{win}}\in\mathbb{R}^{m\times d}\), define the full-cache target \(Y = A_{\text{win}}^{(\text{full})}V_{\text{full}}\), where \(A_{\text{win}}^{(\text{full})} = \operatorname{softmax}(Q_{\text{win}}K_{\text{full}}^\top / \sqrt{d})\). For any retained cache \((K,V)\), define the attention output \(F(K,V) = A(Q_{\text{win}},K)V\), where \(A(Q_{\text{win}},K) = \operatorname{softmax}(Q_{\text{win}}K^\top / \sqrt{d})\). The window-level objective in the main text is: \[\widetilde{\mathcal{L}}_{\text{win}}(K,V) = \left\|Y-F(K,V)\right\|_F^2 .\]

6.2 Local KV Merging and Carrier Support↩︎

Many local KV-cache merging methods can be abstracted to first order as carrier-restricted updates of the retained KV cache: \[\begin{align} K_{\text{Ret}}^* &= K_{\text{Ret}}^0 + B_KK_{\text{evict}}, \\ V_{\text{Ret}}^* &= V_{\text{Ret}}^0 + B_VV_{\text{evict}}, \end{align} \label{eq:appendixA95local95kv95merge}\tag{4}\] where \(B_K,B_V\in\mathbb{R}^{c\times e}\) are merge-assignment matrices and \(K_{\text{Ret}}^*\), \(V_{\text{Ret}}^*\) correspond to the merged key cache and merged value cache, respectively. Local adjacency-based or key-similarity-based matching rules usually assign each evicted token to one or a small number of candidate carriers. In the one-carrier case, if \(\pi(j)\) is the retained carrier selected for the evicted token \(j\), then: \[(B_K)_{ij}=(B_V)_{ij}=0 \quad\text{whenever}\quad i\neq \pi(j). \label{eq:appendixA95one95carrier}\tag{5}\] More generally, local KV-cache matching rules restrict the nonzero rows of \(B_K\) and \(B_V\) to an active carrier set \(\mathcal{C}\subseteq\{1,\ldots,c\}\).

6.2.0.1 Claim 1: carrier-load amplification.

Let \(b=|\mathcal{C}|\), and let \(\ell_i = \left|\{j:\pi(j)=i\}\right|\) for \(i\in\mathcal{C}\) denote the number of evicted tokens assigned to carrier \(i\). Since \(\sum_{i\in\mathcal{C}}\ell_i=e\), the pigeonhole principle gives: \[\max_{i\in\mathcal{C}}\ell_i \ge \left\lceil\frac{e}{b}\right\rceil~. \label{eq:appendixA95load95bound}\tag{6}\] With token-based retention, retained tokens are typically dispersed, so local neighborhoods can use many carriers. With span-based retention, retained tokens form contiguous spans, and evicted tokens in the gaps between spans are matched mainly to span-boundary tokens. As a result, the effective carrier set has size \(b\ll c\), and the unavoidable maximum load in Eq. 6 increases from the all-carrier scale \(e/c\) to the boundary-carrier scale \(e/b\). Under local matching rules whose active carriers concentrate near span boundaries, span-based retention therefore amplifies carrier load.

This load amplification helps explain over-merging. For a boundary carrier \(i\), Eq. 4 gives: \[\begin{align} \Delta k_i &= \sum_{j=1}^{e}(B_K)_{ij}k_j^{(\text{evict})}, \\ \Delta v_i &= \sum_{j=1}^{e}(B_V)_{ij}v_j^{(\text{evict})}. \end{align} \label{eq:appendixA95row95updates}\tag{7}\] As more evicted tokens are assigned to the same carrier, both \(\Delta k_i\) and \(\Delta v_i\) accumulate more terms. Unless these terms cancel, the carrier can move farther from its post-eviction representation. Large value updates blur the content stored in the carrier, while large key updates perturb the attention logits: \[\Delta s_{ri} = \frac{q_r^\top \Delta k_i}{\sqrt{d}},\] thereby changing how query \(q_r\) attends to that carrier. Thus, span-based retention amplifies over-merging in both key and value spaces.

6.3 First-Order Bottleneck for KV Reconstruction↩︎

The load argument explains why boundary carriers become prone to over-merging. We next show that this concentration also restricts the optimization geometry of the objective used in the main text.

6.3.0.1 Claim 2: first-order carrier bottleneck.

Let \(A_0 = A(Q_{\text{win}},K_{\text{Ret}}^0)\), \(Y_0 = F(K_{\text{Ret}}^0,V_{\text{Ret}}^0) = A_0V_{\text{Ret}}^0\), and \(R=Y-Y_0\) be the residual that merging should reconstruct. For small updates \(\Delta K\) and \(\Delta V\), the first-order expansion of \(F\) around the post-eviction cache is: \[\begin{align} F(K_{\text{Ret}}^0+\Delta K,V_{\text{Ret}}^0+\Delta V) = &Y_0 + \mathcal{J}_K[\Delta K] \\ &+ A_0\Delta V + \mathcal{R}, \end{align} \label{eq:appendixA95linearization}\tag{8}\] where \(\mathcal{J}_K\) is the first-order derivative operator of \(A(Q_{\text{win}},K)V_{\text{Ret}}^0\) with respect to \(K\), evaluated at \(K_{\text{Ret}}^0\), and \(\|\mathcal{R}\|_F=\mathcal{O}(\|\Delta K\|_F\|\Delta V\|_F+\|\Delta K\|_F^2)\). This is the same type of local linearization used by the key step in the main text; at later alternating steps, the same argument applies with the current value cache replacing \(V_{\text{Ret}}^0\). Let \(J_K\in\mathbb{R}^{md\times cd}\) denote the vectorized matrix of \(\mathcal{J}_K\).

Let \(S_{\mathcal{C}}\in\mathbb{R}^{c\times b}\) select the active carrier rows. A local merge that uses only carriers in \(\mathcal{C}\) satisfies: \[\Delta K=S_{\mathcal{C}}U_K, \qquad \Delta V=S_{\mathcal{C}}U_V,\] where \(U_K,U_V\in\mathbb{R}^{b\times d}\). After vectorization, the first-order change in the pre-projection attention output lies in the subspace: \[\mathcal{T}_{\mathcal{C}} = \operatorname{col}\!\left( \left[ J_K(I_d\otimes S_{\mathcal{C}}) \quad I_d\otimes(A_0S_{\mathcal{C}}) \right]\right) \subseteq\mathbb{R}^{md}. \label{eq:appendixA95tangent95space}\tag{9}\] Therefore: \[\dim(\mathcal{T}_{\mathcal{C}}) \le \min(md,2bd) . \label{eq:appendixA95dim95bound}\tag{10}\] The best unregularized first-order reconstruction attainable by any local KV merge using only \(\mathcal{C}\) is the projection of \(\operatorname{vec}(R)\) onto this subspace: \[\begin{align} \min_{U_K,U_V} &\left\| \operatorname{vec}(R) - \operatorname{vec}\!\left(\mathcal{J}_K[S_{\mathcal{C}}U_K]+A_0S_{\mathcal{C}}U_V\right) \right\|_2^2 \\ = &\left\| (I-\Pi_{\mathcal{T}_{\mathcal{C}}})\operatorname{vec}(R) \right\|_2^2 , \end{align} \label{eq:appendixA95projection95error}\tag{11}\] where \(\Pi_{\mathcal{T}_{\mathcal{C}}}\) is the orthogonal projector onto \(\mathcal{T}_{\mathcal{C}}\). Eq. 11 formalizes the bottleneck: any residual component outside \(\mathcal{T}_{\mathcal{C}}\) cannot be recovered by local KV updates restricted to the active carriers.

If all retained tokens are allowed to act as carrier tokens, the corresponding subspace is \(\mathcal{T}_{\text{all}}\) with dimension at most: \[\dim(\mathcal{T}_{\text{all}}) \le \min(md,2cd) .\] Since \(\mathcal{C}\subseteq\{1,\ldots,c\}\) and \(\mathcal{T}_{\mathcal{C}}\subseteq\mathcal{T}_{\text{all}}\), we have: \[\left\| (I-\Pi_{\mathcal{T}_{\mathcal{C}}})\operatorname{vec}(R) \right\|_2^2 \ge \left\| (I-\Pi_{\mathcal{T}_{\text{all}}})\operatorname{vec}(R) \right\|_2^2~. \label{eq:appendixA95monotone95error}\tag{12}\] Thus, even when both keys and values are updated, restricting updates to boundary carrier tokens is at most as expressive as updating all retained tokens. Span-based retention makes this restriction severe because \(b\ll c\), reducing the available first-order degrees of freedom from the all-carrier scale \(2cd\) to the boundary-carrier scale \(2bd\). This shows that carrier concentration cannot improve the best local first-order reconstruction and becomes strictly worse when the residual has components captured by \(\mathcal{T}_{\text{all}}\) but not by \(\mathcal{T}_{\mathcal{C}}\).

6.4 Connection to GRKV↩︎

GRKV is designed to avoid the two failure modes above. First, it treats the retained cache as a global carrier set rather than preselecting only boundary carriers. In the notation above, GRKV uses the all-carrier space \(\mathcal{T}_{\text{all}}\) rather than the boundary-restricted space \(\mathcal{T}_{\mathcal{C}}\), which expands the feasible first-order reconstruction space for both \(K_{\text{Ret}}\) and \(V_{\text{Ret}}\). Second, GRKV directly optimizes the window-level attention-output discrepancy: \[\widetilde{\mathcal{L}}_{\text{win}} = \left\| A_{\text{win}}^{(\text{full})}V_{\text{full}} - A_{\text{win}}^{(\text{Ret})}V_{\text{Ret}} \right\|_F^2,\] instead of relying on local token matching. The value step solves a global ridge-regression problem, and the key step applies a locally linearized ridge update analyzed above. \[\begin{align} &\lambda_k\|K_{\text{Ret}}-K_{\text{Ret}}^0\|_F^2 + \lambda_v\|V_{\text{Ret}}-V_{\text{Ret}}^0\|_F^2 \\ &= \sum_{i=1}^{c} \lambda_k\|\Delta k_i\|_2^2 + \lambda_v\|\Delta v_i\|_2^2~. \end{align}\] The regularizers penalize excessive movement of any carrier in both key and value spaces. Consequently, GRKV enlarges the carrier set and controls update magnitude, mitigating the over-merging that span-based retention induces under local merging.

7 Additional KV Merge Map Visualizations↩︎

To complement the NarrativeQA example in 1, we provide additional KV merge-map visualizations on HotpotQA [29]. We follow the same setup as in the main text: SnapKV performs span-based retention to determine the retained KV cache, and a representative key-similarity matching strategy (as in D2O/KVMerger) assigns each evicted token to the retained token whose key has the highest cosine similarity. The resulting correspondence induces a merge in which evicted values are fused into their matched retained carriers.

7.0.0.1 How to read the merge map.

In each subplot of 5, the x-axis gives the original token index of the retained token, and the y-axis gives the original token index of the evicted token merged into the retained cache. Each point represents one matched pair \((\text{evicted} \rightarrow \text{retained})\), with color encoding the cosine similarity between their keys. The dashed diagonal is a visual reference: assignments near the diagonal correspond to merges onto nearby retained tokens in the original sequence. Finally, the black bars on the x-axis indicate the spans retained by SnapKV, highlighting the span structure imposed by modern eviction methods.

7.0.0.2 Concentration induced by span-based retention.

Across layers (e.g., 24 vs.), heads (e.g., 0 vs.), and two representative context regions corresponding to the left and right columns, 5 exhibits the same qualitative behavior as 1: once retention becomes span-based, merge assignments become strongly concentrated. Rather than being distributed across many carriers, a large number of evicted tokens are funneled into a small subset of retained tokens, appearing as prominent vertical bands (many y-values sharing the same x-value). These bands align closely with span boundaries (i.e., near the first and last retained tokens within each black-bar segment), whereas interior tokens within retained spans receive substantially fewer assignments. This visualization supports our main-text claim that span-based retention reshapes merge assignments into an imbalanced carrier load, in which a few boundary carrier tokens are forced to absorb a disproportionate fraction of evicted information—thereby increasing the risk of over-merging and representation blurring under local matching rules.

8 Additional Cross-Window Consistency Visualizations↩︎

Our method relies on the empirical observation that attention outputs are relatively stable across query windows in long contexts, which motivates using a late-prompt (prefill) query window as a surrogate for unseen future queries (Sec. 3.2; Fig. 3). We provide additional evidence on NarrativeQA.

8.0.0.1 Setup.

For each sequence, we take the first 90% of tokens as the prompt (prefill segment) and the remaining 10% of tokens as the future-query segment. We partition the tokens into non-overlapping windows of length \(m\), using the same \(m\) as in our main analysis. For a fixed layer \(\ell\) and head \(h\), we compute a window summary by averaging the full-cache attention outputs within each window: \[s_W^{(\ell,h)} \;=\; \frac{1}{|W|}\sum_{i\in W} A_{i}^{(\text{full},\ell,h)} V_{\text{full}}^{(\ell,h)} \;\in\; \mathbb{R}^{d_h},\] where \(A_{i}^{(\text{full},\ell,h)}\) denotes the full-cache attention weights for query token \(i\) at head \((\ell,h)\) and \(d_h\) is the head dimension. We then compute cosine similarities between window summaries, forming a cross-window similarity matrix whose \((u,v)\) entry is \(\cos\!\big(s_{W_u}^{(\ell,h)}, s_{W_v}^{(\ell,h)}\big)\). In the main text, Fig. 3 reports this analysis on HotpotQA; here, we visualize analogous results on NarrativeQA.

8.0.0.2 Findings.

Fig. 6 shows that cross-window similarities are typically close to one for most heads, with many matrices appearing almost uniformly bright. This suggests that, across a wide range of layers and heads, the direction of the full-cache attention output varies only mildly across query windows, even when comparing windows from different parts of the sequence. We also observe heterogeneity across heads: a minority of heads exhibit more structured variation (e.g., banded patterns or lower similarity involving early windows), indicating modest window-dependent shifts in attention outputs. Nevertheless, the overall high similarity supports the premise underlying GRKV: optimizing the cache to match full-cache outputs on a surrogate window provides a meaningful proxy for the outputs induced by future queries, while avoiding brittle overfitting to any single query token.

9 Derivations for GRKV Updates↩︎

This appendix derives the two update rules used by GRKV. We follow the notation in the main text. Define the full-cache pre-projection attention-output target for the surrogate query window \(Y \triangleq A_{\text{win}}^{(\text{full})}V_{\text{full}}\in\mathbb{R}^{m\times d}\). The coefficients \(\lambda_k>0\) and \(\lambda_v>0\) control the strength of regularization for keys and values, respectively. GRKV alternates between a value step, where \(K_{\text{Ret}}\) is fixed, and a key step, where \(V_{\text{Ret}}\) is fixed.

9.1 Value-Step Dual Form through the Woodbury Identity↩︎

With the current keys fixed, define \(X \triangleq A_{\text{win}}^{(\text{Ret})} = \operatorname{softmax}\!\left(Q_{\text{win}}K_{\text{Ret}}^\top/\sqrt{d}\right)\in\mathbb{R}^{m\times c}\). The value-step objective in the main text is: \[\min_{V_{\text{Ret}}} \left\|Y-XV_{\text{Ret}}\right\|_F^2 + \lambda_v\left\|V_{\text{Ret}}-V_{\text{Ret}}^0\right\|_F^2~. \label{eq:appendixD95value95objective}\tag{13}\]

5pt

5pt

2.4pt max width=

3.0pt max width=

9.1.0.1 Primal solution.

Define \(\Delta V=V_{\text{Ret}}-V_{\text{Ret}}^0\), \(M=\left(X^\top X+\lambda_v I_c\right)\), \(N=\left(XX^\top+\lambda_v I_m\right)\), and \(E_V=Y-XV_{\text{Ret}}^0\). Substituting \(V_{\text{Ret}}=V_{\text{Ret}}^0+\Delta V\) into Eq. 13 gives the ridge problem: \[\min_{\Delta V} \left\|E_V-X\Delta V\right\|_F^2 + \lambda_v\left\|\Delta V\right\|_F^2~. \label{eq:appendixD95ridge95delta}\tag{14}\] Setting the derivative with respect to \(\Delta V\) to zero yields: \[M\Delta V = X^\top E_V~,\] and therefore: \[\begin{align} V_{\text{Ret}}^* &= V_{\text{Ret}}^0 + M^{-1} X^\top \left(Y-XV_{\text{Ret}}^0\right) \\ &= M^{-1} \left(X^\top Y+\lambda_v V_{\text{Ret}}^0\right), \end{align} \label{eq:appendixD95value95primal}\tag{15}\] which is the closed form in Eq. 2 . Here, \(V_{\text{Ret}}^*\) corresponds to the merged value cache.

9.1.0.2 Dual form.

When \(c\) is large, solving the \(c\times c\) system can be expensive. Using the ridge identity: \[M^{-1} X^\top = X^\top N^{-1}, \label{eq:appendixD95value95identity}\tag{16}\] Eq. 15 becomes: \[V_{\text{Ret}}^* = V_{\text{Ret}}^0 + X^\top N^{-1} \left(Y-XV_{\text{Ret}}^0\right).\] Equivalently, define the window-sized variable \(Z \triangleq N^{-1} \left(Y-XV_{\text{Ret}}^0\right) \in\mathbb{R}^{m\times d}\). Then: \[V_{\text{Ret}}^* = V_{\text{Ret}}^0+X^\top Z~.\] This matches the dual formulation in the main text. The dual form requires solving an \(m\times m\) system rather than a \(c\times c\) system, which is efficient because GRKV uses a small surrogate window (e.g., \(m=32\)) while \(c\) can be much larger.

9.2 Local Dual Key Update↩︎

With the current values \(V_{\text{Ret}}\) fixed, define \(f(K)=\operatorname{softmax}\!\left(Q_{\text{win}}K^\top/\sqrt{d}\right)V_{\text{Ret}}\). At the current key cache \(K_{\text{Ret}}\), let \(E=Y-f(K_{\text{Ret}})\), \(G=K_{\text{Ret}}-K_{\text{Ret}}^0\). The key objective is nonlinear because \(K_{\text{Ret}}\) appears inside the softmax. For an update \(\Delta K\), we use the first-order approximation: \[f(K_{\text{Ret}}+\Delta K) \approx f(K_{\text{Ret}}) + \mathcal{J}[\Delta K],\] where \(\mathcal{J}\) is the derivative operator of \(f\) with respect to \(K\), evaluated at the current \(K_{\text{Ret}}\). Let \(J\in\mathbb{R}^{md\times cd}\) denote the vectorized matrix representation of \(\mathcal{J}\), and let \(e=\operatorname{vec}(E)\), \(\delta=\operatorname{vec}(\Delta K)\), and \(g=\operatorname{vec}(G)\). Substituting the linearization into the key objective gives the local ridge problem: \[\min_{\delta} \left\|e-J\delta\right\|_2^2 + \lambda_k\left\|\delta+g\right\|_2^2~. \label{eq:key95local95ridge}\tag{17}\] Let \(z=\delta+g\). Eq. 17 becomes: \[\min_z \left\|e+Jg-Jz\right\|_2^2 + \lambda_k\left\|z\right\|_2^2~.\] The normal equation is: \[\left(J^\top J+\lambda_k I_{cd}\right)z = J^\top(e+Jg)~.\] Using the standard ridge identity: \[\left(J^\top J+\lambda_k I_{cd}\right)^{-1}J^\top = J^\top\left(JJ^\top+\lambda_k I_{\mathcal{Y}}\right)^{-1},\] where \(I_{\mathcal{Y}}\in\mathbb{R}^{md\times md}\) is the identity matrix over the vectorized output space, we obtain: \[z=J^\top\alpha,\] where \(\alpha=\left(JJ^\top+\lambda_k I_{\mathcal{Y}}\right)^{-1}(e+Jg)\). Let \(K_{\text{Ret}}^*\) denote the merged key cache. Since \(z=\delta+g=\operatorname{vec}(K_{\text{Ret}}+\Delta K-K_{\text{Ret}}^0)\), the updated key cache satisfies the rule: \[\operatorname{vec}(K_{\text{Ret}}^*) = \operatorname{vec}(K_{\text{Ret}}^0) + J^\top\alpha~.\] Equivalently, with vectorization implicit: \[K_{\text{Ret}}^* = K_{\text{Ret}}^0 + \operatorname{unvec}\!\left(J^{\top}\alpha\right).\] This is the form used in Eq. 3 . In implementation, GRKV applies the operator \(JJ^\top+\lambda_k I_{\mathcal{Y}}\) in a matrix-free manner using Jacobian-vector and vector-Jacobian products, and solves the dual system with conjugate gradients. This avoids explicitly constructing \(J\) or \(JJ^\top\).

9.3 Fixed Tokens during Optimization↩︎

For clarity, the derivations above assume that all retained tokens are allowed to be updated. When a subset of tokens is fixed, the same derivations apply after restricting the optimization variables to the free tokens while keeping the fixed tokens unchanged. Let \(\mathcal{F}\) and \(\mathcal{G}\) denote the fixed and free token sets, respectively. For the value step, we first subtract the fixed-token contribution from the target, \(Y_{\mathcal{G}} = Y - X_{\mathcal{F}}(V_{\text{Ret}}^0)_{\mathcal{F}}\), and then apply the ridge solve only to \(X_{\mathcal{G}}\) and \((V_{\text{Ret}})_{\mathcal{G}}\). For the key step, we similarly restrict the Jacobian \(J\) to the columns corresponding to the free key variables.

Algorithm 7 provides detailed pseudocode.

10 Benchmark Details for LongBench and RULER↩︎

We use LongBench (licensed under MIT) and RULER (licensed under the Apache License, Version 2.0) as benchmarks. Our use of these benchmarks is consistent with their intended use. Table 2 provides detailed information about the 16 datasets in LongBench. Table 3 provides detailed information about the 13 tasks in RULER.

11 Additional Results on LongBench and RULER at 20% Cache Budget↩︎

5pt

This appendix reports detailed per-task results under a larger 20% KV-cache budget on LongBench and RULER. All settings follow the main text. Compared with the 10% budget in the main experiments, the 20% budget preserves more tokens after eviction. In this less aggressive compression regime, GRKV remains the most reliable KV-cache merging method across benchmarks, model backbones, and base eviction methods.

11.0.0.1 LongBench (20% budget).

Table [tab:longbench95detailed9520] reports per-task scores on all 16 LongBench tasks. GRKV consistently improves the average score of both base eviction methods across both model backbones. On Llama-3.1-8B-Instruct, it improves SnapKV from 39.62 to 40.28, with gains on 12/16 tasks, and improves CriticalKV from 42.00 to 42.52, with gains on 14/16 tasks. On Mistral-7B-Instruct-v0.3, it raises SnapKV from 36.46 to 36.99 and CriticalKV from 38.47 to 39.05, improving 13/16 and 15/16 tasks, respectively. These gains are more consistent than those of the local KV-cache merging baselines. CaM, D2O, and AsymKV occasionally improve individual tasks, but they reduce the average score in all four LongBench settings. This pattern is consistent with the main-text results: when the retained cache already contains more tokens, local merging can still over-aggregate information, whereas GRKV’s global, ridge-regularized reconstruction provides a more stable way to recover information from evicted tokens.

11.0.0.2 RULER (16K, 20% budget).

Table [tab:ruler95detailed9520] reports results on all 13 RULER tasks. GRKV again improves both base eviction methods across both model backbones. On Llama-3.1-8B-Instruct, SnapKV with GRKV improves the average score from 43.81 to 45.47, with gains on 10/13 tasks, and CriticalKV with GRKV improves from 58.23 to 58.74, also with gains on 10/13 tasks. On Mistral-7B-Instruct-v0.3, SnapKV with GRKV improves from 25.58 to 26.23, with gains on 9/13 tasks, while CriticalKV with GRKV improves from 32.71 to 33.19, with gains on 8/13 tasks. The improvements are most visible on retrieval-oriented NIAH variants and variable tracking, where useful evidence can be dispersed across the context. In contrast, CaM and D2O often reduce the average score relative to the corresponding base eviction method, especially in retrieval-heavy settings. These 20% budget results reinforce the main conclusion that GRKV is robust across cache budgets and that global reconstruction is more dependable than local KV-cache merging under span-based retention.

12 Additional Results on Ablations, Compatibility, and Efficiency↩︎

Table 4 reports additional ablations on RULER using SnapKV with GRKV on Llama-3.1-8B-Instruct under a 10% cache budget. The trends are consistent with the LongBench ablations in the main text.

Regularization strength. Regularization remains important: the default \(\lambda_k=\lambda_v=10^{-2}\) achieves the best average score (29.09), while removing regularization lowers the score to 27.49. Stronger regularization also weakens performance, with \(\lambda_k=\lambda_v=10^{-1}\) and \(\lambda_k=\lambda_v=1\) obtaining 28.47 and 27.95, respectively. This supports the role of ridge regularization in allowing useful reconstruction while preventing overly aggressive KV-cache updates.

5pt

Fixed retained-token ratio. The fixed retained-token ratio also affects performance. Fixing the top \(\beta=10\%\) of high-attention retained tokens gives the best score (29.09), outperforming both updating all retained tokens (28.48) and fixing larger ratios, such as \(\beta=20\%\) (28.90) or \(\beta=30\%\) (28.94). This suggests that preserving a small set of important anchor tokens improves optimization stability, while fixing too many retained tokens restricts the carrier set available for global reconstruction.

Update steps. The number of alternating update steps follows a similar pattern to the main-text ablation. A single update step performs best (29.09), while increasing the number of steps to \(S=2\) or \(S=3\) lowers the average score to 28.77 and 28.84. This indicates that additional alternating updates do not improve generalization to downstream queries and may overfit the surrogate window.

Surrogate window size. The surrogate window size has the largest effect in this RULER sweep. The default \(m=32\) achieves the highest score (29.09), while increasing the window size to \(m=48\) and \(m=64\) lowers the average to 27.12 and 26.50, respectively. This supports using \(m=32\) in the main experiments, which matches the window size used by the eviction baselines.

Fixed sink and window tokens. Fixing sink and surrogate-window tokens is beneficial: updating them reduces performance from 29.09 to 28.72.

Optimized cache components. Updating both keys and values performs best overall (29.09), but the key-only variant GRK is very close (29.05), while value-only updating is weaker (28.40). These results suggest that key reconstruction is especially important on RULER, while joint key-value optimization still gives the best default configuration.

Compatibility. Table [tab:compatibility95ruler] reports additional compatibility results on RULER under a 10% cache budget. The results show that GRKV remains effective across both span-based and token-based retention methods. On Llama-3.1-8B-Instruct, GRKV improves the span-based budget-allocation methods PyramidKV and Ada-KV, which dynamically allocate KV-cache budgets across layers and heads, respectively. Specifically, PyramidKV improves from 28.55 to 30.49, and Ada-KV improves from 31.50 to 32.17. GRKV also improves the token-based H2O baseline from 19.33 to 22.43, indicating that its global reconstruction objective is not limited to span-based retention. On the larger Qwen3-14B model, GRKV further improves span-based SnapKV from 32.23 to 34.10 and CriticalKV from 52.61 to 53.32. These results complement the LongBench compatibility results in the main text and show that GRKV consistently improves different eviction backbones across retention granularities, model scales, and benchmarks.

Efficiency. We additionally evaluate efficiency on two A6000 GPUs with batch sizes 1, 2, and 3, using context lengths of 16K and 32K. As shown in Fig. 8, SnapKV with GRKV preserves the efficient decoding behavior of SnapKV while adding a moderate prefill cost for the global regression update. At 16K, SnapKV with GRKV increases prefill latency from 3.65 to 5.91 s at batch size 1, from 7.42 to 9.66 s at batch size 2, and from 11.47 to 14.41 s at batch size 3. These costs remain substantially lower than those of AsymKV, which reaches 56.77, 95.93, and 123.82 s, and are also lower than CaM’s costs at larger batch sizes. In decoding, SnapKV with GRKV remains close to SnapKV: at 16K, decoding latency is 41.93, 41.13, and 40.49 ms/token for batch sizes 1, 2, and 3, compared with 40.97, 39.47, and 39.04 ms/token for SnapKV.

The same trend holds at 32K. SnapKV with GRKV has moderate prefill overhead relative to SnapKV, increasing TTFT from 9.19 to 11.28 s at batch size 1, from 20.31 to 22.69 s at batch size 2, and from 31.45 to 36.79 s at batch size 3. This overhead is comparable to D2O and much smaller than CaM and AsymKV, with AsymKV reaching 155.87–353.55 s across batch sizes. During decoding, SnapKV with GRKV again stays near SnapKV and other compression methods: SnapKV with GRKV obtains 42.64, 41.76, and 40.03 ms/token across batch sizes, while Full Cache grows from 48.57 to 81.12 ms/token as the batch size increases. These results support the main-text observation that GRKV preserves the decoding benefits of eviction-based compression, while its additional regression step mainly affects prefill and remains practical compared with heavier merging methods.

References↩︎