arXiv 2026Machine Learning

GraceKV

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

* Equal contribution † Corresponding author

Tsinghua University, Beijing, China

Read paper arXiv HTML

Global One budget across layers, heads, and slots

128× Useful behavior in a 128× stress test

Zero Additional training or model passes

GPU Compression and inference stay on device

Core idea

One budget. Two ways to spend it.

Under a fixed physical cache budget, the next K/V entry can cover a region that is currently absent, or refine a region that is already represented. GraceKV makes those two choices directly comparable.

Buy coverage

Add a new region

One root prototype makes an entire context slot visible to a particular layer and KV head.

Buy resolution

Refine what is already covered

A Split replaces one coarse prototype with its preselected child set, spending extra entries only where detail is worth it.

1 stored K/V pair = 1 physical budget unit

Prompt Exact, outside budget

Compressible long context Shared Add / Split auction

Recent window Exact, counts toward budget

Question + suffix Exact, outside budget

Compression happens after one standard prefill pass. GraceKV reuses the Q/K/V tensors, sampled hidden states, question-region outputs, and token surprisal already collected in that pass. There is no extra model forward, no additional training, and no mask pretending that removed entries still exist.

No preset local quota

Layers, KV heads, and slots do not receive fixed slices of the budget before the input is understood.

Input-conditioned allocation

The same passage may deserve different coverage and resolution in different layer-head pairs.

Global competition, greedy solution

“Global” describes the scope of the auction. It does not claim exact combinatorial global optimality.

A concrete case

Follow one answer through 16.9K tokens.

The question asks for a member of the group that performed “Good Little Girls.” The answer is not in the first matching passage: the model must follow a two-hop evidence chain from the song to Blue Country, then to Aaron Benward.

Question Who performed “Good Little Girls”?

Evidence hop 1 “Good Little Girls” → Blue Country

Evidence hop 2 Blue Country → Aaron Benward

Exact

Original token-level K/V for names, numbers, labels, or other sharp evidence.

Merged

One prototype preserves a span coarsely when broad context matters more than every local detail.

Dropped

No physical cache entry is written for that slot in that particular layer-head pair.

Method

Structure flows down. Value flows up. Budget follows utility.

GraceKV first builds a common structural vocabulary for coverage and resolution. It then estimates what the current input needs and lets every feasible Add or Split compete in the same physical units.

01PartitionFind coherent slots
02RepresentBuild prototype trees
03ValueTrace direct and indirect evidence
04AllocateRank Add and Split globally
05PackWrite a physical ragged cache

01 · Curvature-guided partition

Cut where the representation changes direction.

GraceKV views normalized hidden states as a trajectory along token positions. Smooth stretches can share a longer coarse representation. Stable turns across layers and window scales are better structural boundaries.

Token surprisal provides a smaller auxiliary signal, while a dynamic program also considers within-slot dispersion and reasonable slot lengths. Curvature decides where a merge is structurally safe; it does not decide which content is important to the current question.

Structure decides where to split. Relevance decides where to spend.

Default target: about 64 tokens per slot, adaptively constrained between 16 and 128.

02 · Progressively refinable representation

One tree contains dropping, merging, and exact retention.

The slot boundaries are shared, but every (layer, KV head, slot) tuple receives its own prototype tree. A frontier is a non-overlapping set of nodes that states exactly how this atomic unit is stored.

0 entries: empty frontier, so the slot is physically absent.
1 entry: the root coarsely covers all eight tokens.
3 entries: selected subregions receive more local detail.
8 entries: every leaf stores its original token K/V.

Frontier explorer Coverage: one coarse prototype

1 entry

One stored prototype keeps the whole slot addressable, but local token detail is merged.

Inside one cache entry

A prototype must preserve attention behavior, not merely average vectors.

A coarse node represents a contiguous interval with one packed entry. GraceKV makes the packed representation consistent with the decoder that will actually consume it.

Key

Unrotate, average, rerotate

Post-RoPE keys live in different rotated coordinates. GraceKV inverse-rotates them, averages in one shared frame, then applies RoPE at a representative position.

Value

Let relevant tokens speak louder

Values are weighted by task relevance, with a 10% uniform base so lower-value background information never loses all influence.

Multiplicity

Discount incoherent merges

Key coherence determines how many original tokens the prototype should effectively count for, preventing an averaged “ghost key” from receiving exaggerated attention mass.

03 · Bottom-up value flow

Ask what the current question needs.

Direct attention from question and sequence-tail probes identifies explicit evidence. Two rounds of token-to-token propagation then recover indirect dependencies, such as a bridge entity that the question does not attend to strongly on its own.

Token values sum upward through the prototype tree. A layer-KV-head sensitivity multiplier captures how strongly that component affects the model output. Curvature and surprisal are not multiplied into relevance: they shape the tree, while attention evidence values its nodes.

Question probes Direct attention Two-hop evidence

input-conditioned relevance × representation fidelity gain × head sensitivity

node value tokentokentokentoken

Children conserve their value when aggregated into a parent, so the same signal can price both coverage at the root and refinement deeper in the tree.

Exact-information safeguard

The singleton floor protects facts that greedy steps may undervalue.

Names, numbers, labels, and few-shot output formats can have a non-smooth payoff: the exact leaf is very useful, while the intermediate splits needed to reach it may look less attractive one step at a time.

GraceKV therefore isolates a small, budget-capped set of high-value (layer, KV head, token) leaves before the main auction. The protection is neither free nor duplicated outside the tree.

Root Addevidence slot

Split / Extractname-bearing span

Exact leafAaron Benward

The complete path cost is charged to the same hard physical budget. Shared ancestors are paid only once.

04 · Top-down budget flow

Put every feasible Add and Split in one queue.

Add compares complete dropping with one-root coverage. Split compares a parent prototype with its finer child set. Both are scored per newly created cache entry, so an operation in an early layer can compete directly with a different head, slot, or resolution elsewhere.

utility per entry = relevance × fidelity gain × head sensitivity ÷ new physical entries

Illustrative six-entry auction Highest affordable marginal utility wins next

1
Floor path · exact tokenLayer 18 · Head 2 · Slot B · cost 3
2
Split · expiry phraseLayer 18 · Head 2 · Slot B · cost 1
3
Add · troubleshooting notesLayer 9 · Head 0 · Slot C · cost 1
4
Add · meeting backgroundLayer 4 · Head 1 · Slot A · cost 1

A coarse B context ZX-41 Friday B detail C coarse

Toy values are illustrative. The real queue spans every layer, KV head, slot, and currently exposed tree operation.

05 · Physical cache packing

Write only the frontier nodes that won.

Each layer-head pair receives an independently sized ragged cache. An unselected root produces no entry; an internal node stores a packed prototype; a singleton stores the original K/V. Newly generated tokens are appended with multiplicity one.

When the budget returns to FullKV scale, every tree can expand to token leaves and recover the original contextual entries exactly.

L4 H0161641

L9 H13284114

L18 H281112416

L23 H332164

coarse prototype refined prototype exact token

Technical details and default settings

Slot construction. Multi-layer, multi-scale curvature is stabilized across sampled depths and windows; surprisal is a smaller auxiliary boundary signal. Default slot length is 16–128 tokens with a target of 64.

Value flow. Question and sequence-tail probes seed direct relevance; two graph hops with default weight 0.3 recover indirect evidence. Parent values equal the sum of child values.

Prototype fidelity. Probe-based distortion weighs attention-partition error and value-aggregate error at 0.25:0.75. Tree construction considers high-curvature split candidates plus the midpoint, and may isolate a salient token with a three-way child set.

Singleton floor. Its default cap is 0.6 of the allocatable base budget, but this is a hard maximum rather than a guaranteed 60% spend. Every realized singleton pays its complete tree path cost.

Complete GraceKV method overview with curvature-guided prototype trees, global budget flow, and a value flow combining attention, multi-hop relevance, distortion, and head sensitivity. — Complete technical overview. The web diagrams above unpack the same pipeline step by step; open Figure 2 for the full-resolution paper view.

Effects and practical meaning

A flexible cache stays useful as the budget tightens.

The central result is not one isolated benchmark win. GraceKV remains competitive across tasks that demand opposite behaviors: broad coverage for summarization and aggregation, but sharp local addressability for question answering and retrieval.

20 / 24 LongBench settings ranked first; GraceKV ranks second in the other four

24 / 32 LongBench + RULER task-budget settings ranked first on Qwen2.5-7B

128× Highest evaluated LongBench compression ratio, used as a stress test rather than a lossless claim

Summarization Keep the whole document in view

Broad, lower-resolution coverage prevents entire topics or sections from disappearing.

QA and retrieval Resolve a few locations precisely

Names, values, and evidence hops need exact or finely split entries amid long distractor context.

Few-shot generation Preserve patterns and exact formats

Demonstration structure benefits from coverage, while labels and answer formats benefit from singletons.

LongBench across all reported compression ratios

Qwen2.5-7B-Instruct. F1 for QA; Rouge-L for summarization and few-shot, all ×100.

Task	FullKV	4×	8×	16×	32×	64×	128×
Single-document QA	43.95	42.97	41.58	38.45	35.57	31.49	25.81
Multi-document QA	29.86	30.18	29.90	28.78	28.18	27.09	25.19
Summarization	15.97	15.03	14.51	14.04	13.48	12.58	11.88
Few-shot	36.23	35.82	34.77	33.92	33.80	33.18	32.83

How to read the quality curve

Compression is a range of operating points, not one yes-or-no result.

At 4×, every LongBench category retains at least 94% of its FullKV row score. At 16×, the four categories retain roughly 87–96%. The 128× setting is a deliberate stress test: useful behavior remains, but the loss becomes strongly task-dependent.

4×Near-FullKV regime≥94% retained in every row

16×Practical high-compression regime87–96% retained across rows

128×Extreme-budget regimeQuality depends on what the task must preserve

Share of each FullKV row score retained at 128×

Few-shot 90.6%

Multi-doc QA 84.4%

Summarization 74.4%

Single-doc QA 58.7%

Descriptive ratios computed within each published table row; they are not a universal quality guarantee.

Precise retrieval under a shrinking budget

GraceKV remains above 76 at the tightest evaluated 32× budget.

RULER set recall checks whether every distant target is recovered, making it a strict test of local addressability rather than approximate semantic similarity. In this Qwen2.5-7B-Instruct Retrieval setting, moving from 4× to 16× costs 1.00 point, while moving from 16× to 32× costs 9.75 points.

87.254× · nominal 4K 86.758× · nominal 2K 86.2516× · nominal 1K 76.5032× · nominal 512

Plots of KV cache memory and per-token decode latency against context length for FullKV and GraceKV at 4x, 8x, and 16x compression. — Physical KV cache memory and per-token decode latency as context grows. Figure 3 from the paper.

Efficiency at 30K context

Memory headroom is the immediate deployment benefit.

FullKV: 1.77 GB
GraceKV 4×: 463 MB
GraceKV 8×: 246 MB
GraceKV 16×: 137 MB

That is roughly 74%, 86%, and 92% less KV-cache memory at 4×, 8×, and 16×. In practice, this headroom can make longer contexts or larger batches feasible, depending on the model weights, activations, serving stack, and available GPU memory.

Within the same 1.77 GB KV-only envelope

FullKV1.0 cache

GraceKV 4×≈3.8 caches

GraceKV 8×≈7.2 caches

GraceKV 16×≈12.9 caches

This is cache-footprint arithmetic, not an end-to-end concurrency claim; weights, activations, fragmentation, and the serving stack also consume memory.

Steady-state decoding Fewer entries reduce cache traffic, but not every latency

Under the unified fixed-cache greedy decoder, GraceKV and FullKV are typically in the same 23–25 ms/token range. The measured difference changes sign across datasets, so memory reduction is the robust conclusion; speedup remains kernel- and workload-dependent.

One-time construction Flexibility has an upfront cost

The default path used for the main quality results takes 3.00–21.53 seconds across the five detailed workloads below. This is paid once after prefill, making tree construction the main systems optimization target.

Where it matters most Long or reusable contexts

The tradeoff is most attractive when memory is the binding constraint, the context will support a long continuation or repeated turns, or severe compression would otherwise erase critical evidence.

Measured system tradeoff at 8×

Large cache savings come with a visible one-time build cost.

Qwen2.5-7B-Instruct; one compression after prefill, then a fixed RaggedCache and the same greedy decoder. LongBench rows average about 200 examples and RULER rows 100. The table reports the default path that produced the main quality results.

Workload	FullKV cache	GraceKV cache	Cache left	Decode, Full → Grace	Build once
Qasper	294.9 MiB	51.7 MiB	17.5%	23.15 → 24.02 ms/token	5.51 s
MultiNews	181.3 MiB	53.9 MiB	29.7%	23.23 → 23.33 ms/token	3.00 s
SAMSum	523.2 MiB	93.7 MiB	17.9%	24.43 → 23.95 ms/token	13.03 s
RULER-FWE	877.0 MiB	130.3 MiB	14.9%	25.63 → 24.06 ms/token	20.41 s
RULER-MQNIAH	887.4 MiB	131.4 MiB	14.8%	25.17 → 23.28 ms/token	21.53 s

“Cache left” is GraceKV cache divided by FullKV cache. These latency numbers describe this unified one-shot protocol; they are not end-to-end service measurements and should not be extrapolated to native step-wise eviction implementations.

What this can change in practice

GraceKV can create headroom under a fixed memory ceiling.

Saved KV-cache bytes may support longer serviceable contexts or larger batches. These are deployment implications, not end-to-end serving measurements; realized gains also depend on model weights, activations, memory fragmentation, and the scheduler.

Document assistants Keep more source material resident

A smaller cache can make it feasible to keep more of a long report, contract, or paper collection resident without forcing every section to receive the same resolution. Repeated generations from the same complete prefill state can amortize construction.

Agents and coding systems Preserve exact identifiers inside long histories

Repository context, tool traces, entity names, numbers, and output formats mix broad background with a few exact facts, matching the method's coverage-versus-resolution design.

Multi-user serving Create possible batch or concurrency headroom

When KV memory limits admission, a smaller physical cache may let a serving system keep more sessions on device or reduce pressure to evict and offload caches. This behavior was not measured end to end in the paper.

Where the tradeoff is weaker Short, one-shot, or compute-bound requests

If generation is brief, the context is small, or attention is not memory-bandwidth limited, the seconds-level construction cost can outweigh the steady-state saving. The paper therefore presents memory capacity as the primary near-term systems benefit.

What the ablations say

The gains come from coordinating the whole pipeline.

Change in Qwen2.5-7B single-document QA versus the full method. Larger drops identify the parts doing the most work.

Without multi-resolution trees −2.53 / −2.37: The cache loses the ability to move continuously from dropping to coarse coverage to exact token retention.
Without global allocation −2.25 / −1.98: Fixed layer-head limits trap unused budget and prevent it from flowing to higher-utility operations elsewhere.
Without the singleton floor −1.14 / −1.45: Greedy marginal steps can blur entities, numbers, labels, and other facts whose exact benefit appears only after a complete refinement path.
Without curvature-guided structure −0.43 / −0.93: Uniform chunks are more likely to merge across representational turns or spend roots on unnecessarily short smooth regions.
Without multi-hop relevance −0.57 / −0.37: Indirect evidence can receive too little value when the question attends mainly to the first hop in a reasoning chain.

Each pair reports the score drop at 8× / 64×; the complete method scores 41.58 / 31.49.

Citation

Every cache entry earns its place.

Tian, Haolin; Liu, Yuzhe; and Wang, Tonghan. 2026. Every Cache Entry Earns Its Place: Global Allocation of Resolution and Coverage for KV Cache Compression. arXiv:2608.07001.

DOI

BibTeX

@article{tian2026every,
  title   = {Every Cache Entry Earns Its Place: Global Allocation of Resolution and Coverage for KV Cache Compression},
  author  = {Tian, Haolin and Liu, Yuzhe and Wang, Tonghan},
  journal = {arXiv preprint arXiv:2608.07001},
  year    = {2026}
}