acceptodds
Under review as a conference paper at ICLR 2027

Every Cache Entry Earns Its Place: Global Allocation of Resolution and Coverage for KV Cache Compression

Abstract

As large language models (LLMs) process increasingly long contexts, KV cache storage and repeated access have become a major bottleneck. Existing KV cache compression methods rely on predefined, fixed compression rules and are typically developed around either token eviction or merging. As a result, cache resources can neither flow freely across layers, heads, and context slots, nor be jointly allocated to balance local resolution and information coverage. Therefore, we propose GraceKV, a global approach for the allocation of resolution and coverage in KV cache compression, and formulate the compression process as a global resource allocation problem under a fixed cache budget. GraceKV treats each layer–KV-head–slot combination as an atomic unit and builds a prototype tree. Leaf nodes correspond to token-level KV entries, while each internal node uses a single prototype to compress the KV space covered by its children. A set of non-overlapping nodes in the tree forms the representation of an atomic unit. Adding the root of a new tree expands information coverage, whereas splitting a selected node improves local resolution. All candidate actions compete globally for a shared cache budget. Finally, the nodes retained across all trees form the compressed KV cache. This process adaptively determines the allocation of cache resources among atomic units globally and the balance between resolution and coverage. GraceKV requires no additional training, and the entire compression and inference process is performed on the GPU. Systematic experiments across diverse long-context tasks and compression ratios show that GraceKV ranks first in 25 of 32 settings and remains robust up to 128× compression. These results validate the effectiveness of global budget allocation in coordinating information coverage and local resolution.

Primary area:
foundation or frontier models, including LLMs
Keywords:
KV Cache Compression, Large Language Models, Efficient LLM Inference

Reviews

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

This paper proposes GraceKV, a training-free KV-cache compression method that jointly allocates cache resources across layers, KV heads, and context regions. The method builds multi-resolution prototype trees and uses global utility-based allocation to balance information coverage and local resolution. It also introduces curvature-guided segmentation, multi-hop relevance estimation, and a singleton-preservation mechanism.

Experiments on LongBench and RULER with multiple language models show strong performance across different compression ratios, especially for question answering and retrieval tasks.

Critical strengths
  1. The paper considers KV-cache compression as a global resource allocation problem instead of using fixed eviction or merging rules. The multi-resolution representation provides a flexible way to balance information coverage and local resolution.

  2. The method is evaluated on several models and long-context tasks with different compression ratios. It achieves competitive or superior performance in many settings, and the ablation studies support the importance of multi-resolution representation and global allocation.

Critical weaknesses
  1. GraceKV combines curvature-based segmentation, multi-hop relevance, head sensitivity, prototype distortion, and a singleton floor. Although the ablations show their effectiveness, it is still unclear whether the full complexity is necessary or whether a simpler global allocation method could achieve similar results.
Questions for authors

Can the authors compare GraceKV with a simpler global allocation method using only token importance or fixed-size merging? This would help clarify whether the multi-resolution prototype trees are necessary.

3 comments
AuthorsOpenReview ↗

We sincerely thank you for your constructive comments — Experiments on global token selection and fixed-granularity merging.

(Weakness 1 + Question 1) Can simpler global token selection or fixed-granularity merging achieve similar results?

Simple global token selection or fixed-granularity merging cannot match GraceKV’s performance.

We added two types of controls: global token selection and fixed-granularity merging. All methods use Qwen2.5-7B-Instruct with identical inputs and decoding configurations. We evaluate 200 samples each from the LongBench single-document QA and multi-document QA subsets, matching the actual context-cache budget for every sample.

Table 1. Comparison of GraceKV with simplified global allocation methods. All metrics are F1. The fixed block length is set to rr tokens, where rr is the numerical value of the compression ratio: 8 tokens at 8× and 64 tokens at 64×.

MethodSingle-document QA 8×Single-document QA 64×Multi-document QA 8×Multi-document QA 64×
GraceKV42.0531.4629.7726.97
Global token selection (direct attention)36.7128.7129.5925.06
Global token selection (reusing GraceKV’s token importance signal, i.e., w/o MR)39.7329.4529.3325.53
Fixed-block merging (block length rr: 8/64)39.8429.9828.7725.66
Fixed-block merging (block length r/2r/2: 4/32)40.3729.8328.925.66

As shown in Table 1, GraceKV outperforms these controls across all the above settings, supporting the necessity of multi-resolution prototype trees.

Thank you for your rebuttal. I have no further questions.

Thank you for your time and effort!

We sincerely appreciate your careful review and constructive feedback on our work.

Reviewer_ubPEOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

GraceKV compresses the KV cache using prototype trees over layer–head–slot units. Add and Split operations jointly allocate coverage and resolution under a shared budget, supplemented by exact-token protection. Experiments across five backbones report improvements, particularly on QA, and reduced cache memory, with a one-time construction overhead.

Critical strengths

The prototype-tree representation provides a concrete mechanism for jointly choosing coarse coverage and fine-grained retention under one physical cache budget.

The reported QA improvements extend across budgets and backbones.

Critical weaknesses

The empirical evidence is difficult to audit. Appendix D does not clearly specify benchmark subsets, sample counts, aggregation rules, or baseline configurations. Ablation results also differ: Table 3 implies 41.01 F1 without multi-hop relevance at 8× compression, whereas Table 8 reports 41.39 with its weight set to zero. These may reflect configuration differences, but the discrepancy needs explanation.

The contribution of joint allocation needs clearer isolation. Relevant methods such as LAVa and LU-KV already address adaptive or global budget allocation, yet direct comparisons are absent and “w/o Multi-Resolution” is insufficiently defined. Methodologically, Eqs. (8)/(31) leave the normalization domain unclear, while interval-dependent probe sets may affect the comparability of parent–child distortion differences in Eq. (12). Additionally, the singleton floor’s realized budget use and influence on tree construction are unclear. These issues limit attribution of the gains, rather than demonstrate that the heuristic is incorrect.

Questions for authors

Could you provide the exact datasets, sample counts, length settings, metrics, aggregation rules, and baseline configurations, and reconcile the Table 3/8 discrepancy?

What precisely replaces multi-resolution representation in “w/o MR”? Does this provide a matched global eviction-only control, or is there evidence against a close allocation baseline such as LAVa?

Do parent and child distortions use the same probes and normalization? How are Add and Split utilities made comparable across atomic units?

How much budget does the singleton floor actually consume? Does removing it preserve the same trees or rebuild them without forced extraction?

4 comments
AuthorsOpenReview ↗

We sincerely thank you for your constructive comments — Experiments and analyses on evaluation settings, baseline comparisons, utility normalization, and the singleton floor. (Part 1/2)

(Weakness 1 + Question 1) What are the evaluation datasets, sample counts, lengths, metrics, and baseline configurations? Why are Tables 3 and 8 in the original paper inconsistent?

Datasets and length settings. The datasets, sample counts, context lengths, and generation limits are shown in Table 1.

Table 1. Dataset settings. Context lengths and generation limits are measured in tokens.

CategoryDatasetSample countContext length rangeMaximum generation lengthMetric
Single-document QAQASPER2001,909–21,87932F1
Multi-document QAMuSiQue2006,732–17,82432F1
SummarizationMultiNews200132–14,278512ROUGE-L
Few-shot generationSAMSum2001,339–17,987128ROUGE-L
AggregationRULER-style FWE10015,50048Target-string recall
Multi-target retrievalRULER-style MQ-NIAH10015,663–15,67648Target-string recall

Model and generation settings. The main experiments in the original paper use Qwen2.5-7B-Instruct, BF16, and greedy decoding, without sampling or beam search. All methods within the same comparison use identical model weights, tokenizer, inputs, and generation settings.

Metrics and aggregation rules. QA uses token-level F1; summarization and few-shot generation use ROUGE-L; aggregation and retrieval measure the proportion of target strings recalled in the response. When a sample has multiple reference answers, we take the highest score, then compute the arithmetic mean over all samples in the dataset and multiply the result by 100. Different task categories are reported separately and are not combined into an overall score.

Baseline configurations. Each method constructs its decoding cache after the complete prefill pass. The prefix and question are retained in full, and the recent window is counted toward the context-cache budget.

The discrepancy between Tables 3 and 8. The w/o MH setting in Table 3 and λ=0\lambda = 0 in Table 8 represent the same ablation configuration, but their results were obtained in two independent runs. The Full row in the ablation table denotes complete GraceKV and reuses its previously obtained result. To provide a consistent comparison, we evaluated this shared ablation configuration under a unified protocol again. Using Qwen2.5-7B-Instruct on the LongBench single-document QA subset at 8× compression, complete GraceKV achieves 42.05 F1, compared with 41.47 F1 for the ablation.

(Weakness 2 + Question 2) Does w/o MR provide a budget-matched global eviction control? How does GraceKV differ from LAVa and LU-KV?

Yes, w/o MR is a global token-eviction control with a matched actual budget. It retains the same importance scores, singleton candidates, and priority rules, removes the prototype trees and ADD/SPLIT operations, and uses the same actual valid-entry budget.

GraceKV’s contribution lies in jointly allocating budgets across layers, heads, and regions based on “how much adding one more cache entry better trade off coverage and resolution” for the current input. Table 2 compares the mechanisms of GraceKV and existing adaptive budget allocation methods.

Table 2. Mechanism comparison with other methods. ✓ indicates support.

MethodNo model trainingInput-adaptive budget allocationCross-layer budget allocationLayer-head marginal utility to compete for budgetMulti-resolution cache representationJoint coverage–resolution allocation
Ada-KV✓✓
LAVa✓✓✓
LU-KV✓✓✓
GraceKV✓✓✓✓✓✓

As shown in Table 2, GraceKV jointly determines where to allocate cache entries and how finely to represent each region, based on the current input. Coverage and refinement compete through the same layer-head utility criterion, jointly determining global budget allocation and multi-resolution representation.

We also added comparisons on 200 questions from each of the two QA tasks at five context compression ratios, as shown in Table 3.

Table 3. Performance comparison of GraceKV, LAVa, and LU-KV. The metric is F1 (↑). Each task subset contains 200 samples, and the FullKV scores are 44.42 and 29.46, respectively.

(a) Single-document QA

Compression ratioGraceKVLAVaLU-KV
4×43.943.0443.21
8×42.054141.38
16×38.2837.6538.37
32×35.7533.9134.81
64×31.4630.2731.3

(b) Multi-document QA

Compression ratioGraceKVLAVaLU-KV
4×29.8429.2129.38
8×29.7729.1428.52
16×27.6627.9327.68
32×27.1626.1826.26
64×26.9726.2926.03
AuthorsOpenReview ↗

We sincerely thank you for your constructive comments — Experiments and analyses on evaluation settings, baseline comparisons, utility normalization, and the singleton floor. (Part 2/2)

(Weakness 2 + Question 3) Do parent and child distortions use the same probes and normalization? How are ADD and SPLIT utilities compared across different atomic units?

Probes and normalization for parent and child nodes. Parent and child distortions use the same probes and normalization.

Cross-unit comparison of ADD and SPLIT. Both types of operations are ranked by the following marginal utility per entry:

Utility=Head sensitivity×Region relevance×Non-negative distortion reductionNumber of additional cache entries\text{Utility} = \frac{\text{Head sensitivity} \times \text{Region relevance} \times \text{Non-negative distortion reduction}}{\text{Number of additional cache entries}}

head sensitivity measures how strongly a layer–KV-head pair influences model output, while region relevance aggregates token importance within the interval (Eqs. (10)–(11)). To align scales across units, token relevance is normalized to sum to one within each layer–KV-head pair’s compressible context, and head sensitivity is normalized to have mean one across all layers and KV heads. Distortion reduction measures the improvement in the attention approximation defined in Eq. (8). ADD compares dropping an interval with representing it by a root prototype. SPLIT compares the parent’s distortion with the summed distortion of its children. Number of additional cache entries is one for ADD and the number of children minus one for SPLIT (Eq. (12)). Dividing each gain by its entry cost gives both operations a common comparison criterion. All feasible operations then compete in the same global priority queue under the shared cache budget (Eq. (13)).

(Weakness 2 + Question 4) How much budget does the singleton floor actually consume? When it is removed, is the same tree retained, or is the tree rebuilt without forced extraction?

Actual budget consumption. The floor is charged according to the actual number of valid KV entries, including exactly retained single-token entries and the necessary prototype entries retained to isolate these tokens. All these entries are deducted from the unified cache budget. We report the actual entry counts and budget shares in Table 4.

Table 4. Actual budget consumption of the singleton floor. Experiments use Qwen2.5-7B-Instruct and cover LongBench single-document QA, multi-document QA, and summarization, with 200 samples per subset. Entry counts are summed across all layers and KV heads; both entry counts and percentages are averaged over samples.

Task subsetCompression ratioActual valid floor entriesShare of the post-compression valid KV-entry budget
Single-document QA8×39,829.6056.06%
Single-document QA64×3,045.4029.69%
Multi-document QA8×86,438.5037.95%
Multi-document QA64×8,978.9031.46%
Summarization8×11,968.9029.87%
Summarization64×994.111.44%

When removing the Singleton Floor, we retain the same tree. Only the floor’s forced-retention stage is disabled; token importance, numerical prototype values, distortion estimates, and the subsequent global allocation mechanism remain unchanged.

We additionally include a control that rebuilds the tree without forced extraction: during tree construction, forced single-token extraction for floor candidates is disabled, the prototype trees are rebuilt, and global allocation is then performed without floor protection.

Both controls are matched sample by sample in final valid KV-entry counts to the complete GraceKV. As shown in Table 5, both treatments lead to performance degradation.

Table 5. Performance changes for the two controls without the floor. Experiments use 200 samples from the LongBench single-document QA subset. Values are F1 changes relative to the complete GraceKV on the same batch of samples.

Floor removal methodF1 change at 8×F1 change at 64×
Retain the same tree and disable only forced floor retention−1.22−1.59
Rebuild the tree without forced extraction and remove floor protection−1.90−2.27

Thank you for the additional comparisons and ablations. They substantially address my main concerns, and I am raising my rating from 2 to 3.

Thank you for your thoughtful feedback and encouraging assessment!

We sincerely appreciate the time and care you have devoted to reviewing our work. Your constructive suggestions have helped us strengthen the paper, and we are glad that you found our responses and additional experiments helpful.

Comments on the paper

2 comments
AuthorsOpenReview ↗

We sincerely thank you for your constructive comments — Experiments on end-to-end efficiency and clarifications on pruning, FullKV recovery, and w/o MR. (Part1/2)

(Weakness 1 + Question 1) Please report quality, time to first token, total time, and peak GPU memory for long outputs or repeated generation from exactly the same prompt, including all additional feature collection costs.

We have added end-to-end experiments confirming that both single long outputs and repeated generation from the same prompt can amortize GraceKV’s construction cost and yield actual total-time savings.

In these experiments, we consistently use Qwen2.5-7B-Instruct, a single A800 GPU, and BF16. All methods use identical prompts, paired random seeds, and sampling parameters (temperature=0.7, top-p=0.9).

Timing starts when the loaded model, after service warm-up, receives the input and includes tokenization, prefill, collection of all additional features and per-token logits required by GraceKV, cache construction, feature release, CUDA Graph capture, generation, and output.

(1) Repeated generation from the same prompt

We selected 6 prompts from the LongBench summarization subsets and generated 32 responses for each prompt. Both FullKV and GraceKV perform prefill only once and subsequently reuse their respective prompt caches. The results are shown in Table 1.

Table 1. Quality, end-to-end time, and memory usage for repeated generation from the same prompt. Time and memory usage are averaged over the 6 prompts; ROUGE-L is evaluated over all generated responses.

MethodROUGE-L ↑TTFT (s)Total time for one generation (s)Total time for 32 generations (s)Peak GPU memory (GiB)KV cache (MiB)
FullKV25.350.8913409.0915.27312.98
GraceKV 2×24.41415.21364.1816.86192.9
GraceKV 4×23.963.9314.38352.4716.86109.96
GraceKV 8×22.523.4813.67342.4416.870.86
GraceKV 64×18.173.113.35316.0916.8137.34

(2) Single long outputs

We selected four task types from LongGenBench: floor planning, daily diaries, daily menus, and neighborhood planning. For each task, we used one predetermined input draft and asked the model to continue generating the subsequent content, with generation limits of 23,982–24,115 tokens. The results are shown in Table 2.

Table 2. Quality, complete end-to-end time, and peak GPU memory for single long outputs. End-to-end throughput is the number of output tokens divided by the total end-to-end time. Values are averaged over the four task types.

MethodAverage output tokensContent constraint satisfaction rate (%) ↑TTFT (s)Total time (s)End-to-end throughput (tokens/s) ↑Peak GPU memory (GiB)
FullKV14,099.5021.281.09753.418.7117.07
GraceKV 4×21,661.3034.595.021,038.8320.8517.4
GraceKV 8×17,524.0028.754.08822.5421.317.2
GraceKV 16×12,034.5025.973.67559.6421.517.16

As shown in Tables 1 and 2, repeated generation from the same prompt and single long outputs can amortize GraceKV’s construction cost and yield actual time savings.

AuthorsOpenReview ↗

We sincerely thank you for your constructive comments — Experiments on end-to-end efficiency and clarifications on pruning, FullKV recovery, and w/o MR. (Part2/2)

(Weakness 2 + Question 2) Please specify the pruning rules and the w/o MR implementation, report actual cache-entry counts, and explain how pruned branches are handled when recovering FullKV.

Pruning and FullKV recovery. Pruning in Appendix F.3 refers to early termination during prototype-tree construction: further subdivision stops when the interval distortion, , defined in Eq. (8), is sufficiently low or the specified minimum leaf size is reached, thereby controlling the size of the candidate trees. At compression ratios greater than 1×, pruning is an optional means of accelerating construction, rather than a necessary step for cache compression. Exact FullKV recovery requires all single-token branches to be fully preserved. Therefore, at 1×, pruning must be disabled in advance and the minimum leaf size set to 1, allowing all branches to expand fully to single-token leaves. In this case, the budget is sufficient to expand all single-token leaves, and each token directly retains its original K/V, position, and unit effective multiplicity, thereby recovering FullKV. On 3 independent samples, we performed tree construction and allocation with GraceKV under a 1× budget and verified that the cache tensors, associated metadata, and generated token sequences were all exactly identical to FullKV.

The w/o MR implementation. w/o MR replaces the multi-resolution prototype trees with global original-token selection. It retains the same head sensitivity, token relevance, singleton candidates, and preferential retentions. It globally ranks tokens across all layers, KV heads, and context positions according to “head sensitivity × token relevance” and retains the original K/V of the selected tokens within the budget, while removing the prototype trees, aggregated representations, and ADD/SPLIT operations. The rules for handling the prefix, question, recent window, and all other details remain unchanged. This control therefore retains the ability to allocate the budget globally across layers and heads, and the ablation tests the role of multi-resolution representation and its allocation mechanism relative to global token selection.

Actual cache-entry counts. We checked the number of valid KV entries after compression and before decoding on 200 samples from the LongBench single-document QA subset using Qwen2.5-7B-Instruct. As shown in Table 3, the actual entry counts of GraceKV and w/o MR match exactly for every sample at both compression ratios.

Table 3. Actual valid KV cache-entry counts for GraceKV and w/o MR. Values are averaged over 200 samples from the LongBench single-document QA subset and summed across all 28 layers, with 4 KV heads per layer.

Context compression ratioGraceKVw/o MR
8×92,478.5492,478.54
64×30,910.5430,910.54

GraceKV and w/o MR use the same actual entry budget.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.