acceptodds
Under review as a conference paper at ICLR 2027

Quantize the Keys, Audit the Values: Retained-State Certificates for KV-Cache Compression

Abstract

KV-cache compression aims to support long-context inference within limited memory while preserving output quality. How that memory is distributed matters because compression in different cache regions can affect the current attention output differently. Aggregate task scores assess overall quality but do not by themselves provide query-specific feedback for allocating memory within a compressed cache. We provide this feedback with a deterministic certificate that bounds attention error for each query, even after the original entries are discarded. It also gives the exact reduction in the bound that each increase in value precision would produce, which enables adaptive allocation while the cache stays compressed. This allocation lowers attention error by 30–67% under the same memory budget and reaches a calibrated value-error target with roughly two-thirds as much refinement memory as uniform allocation. In packed serving of two 7–8B models at 32K, adaptive allocation brings the next-token distribution 2.6–3.4 times closer to dense decoding in KL divergence than uniform allocation with the same memory. The design is also practical to serve. A fused kernel evaluates the certificate alongside attention with little additional arithmetic and reads the selected state directly from a packed cache. Its base representation uses about dense KV storage and serves a 70B model at 128K on one GPU.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
KV-cache compression, attention error bounds, adaptive memory allocation, quantization, long-context inference

Reviews

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

This paper introduces a deterministic retained-state certificate (Theorem 1) that upper-bounds single-head, single-step attention output L2 error ||o - o-hat|| for a quantized KV cache without retaining the original full-precision KV states. At compression time, the cache records compact receipts: per-channel key reconstruction error bounds Delta-g in R^d for each 64- or 128-token key group (which yield score radii |s(i) - s-hat(i)| <= eps(i) = <|q|, Delta-g(i)> / sqrt(d)), per-token value reconstruction residual bounds rho-bar(i) >= ||v(i) - v-hat(i)||, and original value norm bounds nu-bar(i) >= ||v(i)||.

Using a softmax perturbation bound (Lemma 1), Theorem 1 decomposes the error bound into a key weight-perturbation term and a chunk-additive value reconstruction term:

||o - o-hat|| <= E-key(q) + sum over chunks c of sum over i in c of p-hat(i) rho-bar(i),

where E-key(q) = min( [sum over i of p-hat(i) (A + exp(eps(i)) - 1) nu-bar(i)] / (1 - B), 2 max over i of nu-bar(i) ), with A = sum over i of p-hat(i) (exp(eps(i)) - 1) and B = sum over i of p-hat(i) (1 - exp(-eps(i))).

Because refining value precision while holding keys fixed leaves the served attention weights p-hat(i), key score radii eps(i), and value norm bounds nu-bar(i) unchanged, the key term E-key(q) cancels out completely. Installing a 2-bit residual correction page on chunk c therefore reduces the certificate by an exact, local, additive amount:

Delta-E(c, q) = sum over i in c of p-hat(i) (rho-bar-before(i) - rho-bar-after(i)) (Proposition 1).

Guided by this key-value asymmetry, the authors fix keys at 5 bits (in packed serving) or 8 bits (in stream replays) and store values as a 2-bit base with up to three nested 2-bit residual correction pages per chunk, allocated across layers and heads via a closed-form running-minimum nested greedy algorithm (Proposition 4). They validate zero certificate violations across 2.54 billion float64 checks, show 30-67% lower p99 single-step attention error and 2.6x-3.4x lower teacher-forced KL divergence relative to uniform page allocation, and evaluate a custom Triton kernel up to Llama-3.1-70B at 128K context.

Critical strengths
  1. Clear Theoretical Articulation of Key-Value Asymmetry in Attention Error Certification (Theorem 1, Proposition 1, Proposition 3): The paper cleanly formalizes why keys and values behave fundamentally differently under post-compression error certification:

    • Lemma 1 bounds |p(i) - p-hat(i)| <= p-hat(i) (A + exp(eps(i)) - 1) / (1 - B) in proportion to the served attention weight p-hat(i) (which Proposition 2 shows is first-order sharp as p-hat(i) approaches 0) rather than a vacuous global Lipschitz constant.
    • Proposition 1 and Proposition 3 show that while any key refinement perturbs the shared softmax normalization and couples all groups across the head, a value refinement with fixed keys changes the upper bound by an exact, chunk-local linear functional Delta-E(c, q) = sum over i in c of p-hat(i) (rho-bar-before(i) - rho-bar-after(i)).
  2. Exact Running-Minimum Characterization of Nested Greedy Allocation (Proposition 4) and Rigorous Numerical Auditing: Reducing the global multi-unit nested greedy page selection over Q decision queries to a single top-k threshold over running minima g-hat(u, j) = min over j' <= j of g(u, j') (Lemma 4 and Proposition 4) is elegant, and the implementation is backed by outward FP16 rounding guarantees (Corollary 1) and 2.54 billion violation-free float64 audits (Table 6).

Critical weaknesses
  1. Zero Statistically Significant Downstream Task-Score Improvement Over Uniform Allocation or Static KIVI-Style 4-Bit Quantization (Table 4 & Tables 13–15):

    • Despite reducing single-step p99 attention ℓ2\ell_2 error by 30–67% (Table 1) and teacher-forced next-token KL divergence by 2.6–3.4×2.6\text{--}3.4\times (Figure 6, Table 16), adaptive page allocation produces zero statistically significant gain on any downstream task benchmark in Table 4.
    • Across all five benchmark studies in Table 4 (RULER-32K on Qwen2.5-7B and Llama-3.1-8B; LongBench on Qwen2.5-7B, Llama-3.1-8B, and Qwen3-8B), every 95% confidence interval for Adaptive - Uniform (+0.41 [-0.14, +0.96], -0.35 [-1.29, +0.57], +0.11 [-0.25, +0.50], +0.03 [-0.46, +0.49], -0.09 [-0.58, +0.41]) and Adaptive - KIVI-style (+0.17, -0.41, +0.04, -0.03, -0.06) covers zero. Even at half the page budget (0.289x dense KV, Table 13), Adaptive - Uniform on RULER-32K is -0.09 [-1.33, +1.14].
    • This highlights a critical surrogate gap: minimizing unweighted single-head ℓ2\ell_2 attention output error across all heads/layers spends refinement budget on heads with large value norms ∥vi∥2\|v_i\|_2 (Figure 5) rather than the specific retrieval or reasoning heads that affect discrete downstream generation decisions.
  2. The Key Certificate Ekey(q)E_{\mathrm{key}}(q) Is Completely Unused by the Page Allocator, Is 66×–171×66\times\text{--}171\times Loose in Serving, and Dictates an Unfavorable Key-Heavy (k5v2) Bit Allocation:

    • Ekey(q)E_{\mathrm{key}}(q) and νˉi\bar{\nu}_i cancel out of allocation: Because Proposition 1 subtracts Eafter(q)E_{\mathrm{after}}(q) from Ebefore(q)E_{\mathrm{before}}(q) at fixed keys, Ekey(q)E_{\mathrm{key}}(q), the key error bounds Δg\Delta_g, and the value norm bounds νˉi\bar{\nu}_i cancel completely from the page price ΔEc(q)=∑i∈cp~i(ρˉibefore−ρˉiafter)\Delta E_c(q) = \sum_{i \in c} \tilde{p}_i (\bar{\rho}_i^{\mathrm{before}} - \bar{\rho}_i^{\mathrm{after}}). Even the target-driven controller in Figure 3 / Table 10 thresholds only the value-error bound max⁡h∑i∈Tp~i(h)ρˉi\max_h \sum_{i \in T} \tilde{p}_i^{(h)} \bar{\rho}_i, ignoring Ekey(q)E_{\mathrm{key}}(q). Thus, the entire key-side certificate apparatus is unused by the memory allocator.
    • Severe looseness and cap saturation at 5-bit keys: In the actual k5v2 serving configuration (Table 7, 16K and 32K deploy arms), the total certificate exceeds realized error by a median factor of 66×–72×66\times\text{--}72\times (157×–171×157\times\text{--}171\times at p90), and the softmax perturbation factor min⁡(2A/(1−B),2)\min(2A/(1-B), 2) hits its vacuous cap of 22 in 24.0%–30.5% of all instances (and 61.2%–64.1% without sinks). Because εi=⟨∣q∣,Δg(i)⟩/d\varepsilon_i = \langle |q|, \Delta_{g(i)}\rangle/\sqrt{d} assumes worst-case sign alignment across all d=128d = 128 channels, AA and BB grow exponentially unless keys use ≥5–8\ge 5\text{--}8 bits.
    • Inefficient base bit split (k5v2 vs. k4v4): To keep Ekey(q)E_{\mathrm{key}}(q) from saturating everywhere, the packed cache spends 5 bits on keys (80 bytes/token) and only 2 bits on base values (32 bytes/token, Table 5). Without correction pages, k5v2 loses 1.791.79 RULER points relative to a simple static k4v4 KIVI-style baseline (Table 13), and adding pages up to the k4v4 byte budget (0.316x dense) merely recovers parity with k4v4 (Table 4) while incurring substantial metadata and kernel complexity.
  3. Disconnect Between Dynamic Per-Query Framing and Static Pre-Decode Serving, Plus Uncompetitive Serving Latency:

    • While the abstract and Section 3 emphasize query-specific feedback at every decode step, the actual packed serving system (Appendix C, line 1088; Tables 17–18) prices and installs pages once before decoding using the last 32 prompt queries—taking 1.6s to 53.1s of selection time (Sel.) plus up to 214s of packing time (Pack) (Table 18)—and holds the pages static during decoding.
    • Furthermore, Table 17's latency ratios exclude Sel. and Pack overhead, yet Base + selected pages is still slower than dense 16-bit serving in 4 of the 5 measured rows (1.305x on Qwen2.5-7B 16K, 1.198x at 32K, 1.063x on Llama-3.1-8B 32K, and 1.952x on Llama-3.1-70B 64K), and was not measured (n/r) for either 128K row! Meanwhile, keeping all three candidate pages resident in GPU memory for true dynamic per-step switching would inflate the cache from 0.258×0.258\times to 0.504×0.504\times dense FP16 (Table 5, line 1134).
Questions for authors

Clarification Requests

  1. Where Is E-key(q) Used Actionably?: Since E-key(q) and nu-bar(i) drop out of Proposition 1's page price Delta-E(c, q), and Figure 3's dynamic controller also sets its threshold tau on the value-error bound max over h of sum over i in T of p-hat(i, h) rho-bar(i) alone, is E-key(q) ever used by any controller or decision rule in your experiments, or is it purely a passive diagnostic?
  2. Why Does One-Time Page Selection (Sel.) Take Up to 53.1 Seconds, and What Is the Latency of Base + pages at 128K?: By Lemma 4 and Proposition 4, pricing pages from 32 prompt queries and running the nested greedy selector requires only averaging 32 attention vectors per head and finding a 1D quantile over chunk chains. Why does Sel. take 6.8s-13.6s on Llama-3.1-8B (32K-64K) and 53.1s on Llama-3.1-70B (64K) in Table 18 (longer than the entire 200-step decode phase), and why were the Base + selected pages runs omitted (n/r) at 128K in Tables 17-18?
  3. Can Adaptive Allocation Beat Uniform or KIVI-Style Quantization on Task Scores in a Tighter Budget Regime?: In Table 4 (0.316x dense) and Table 13 (0.289x dense), RULER-32K and LongBench scores are saturated near the uncompressed baseline, leaving little headroom. Have you tested a tighter budget (e.g., k3v2 or k4v2 + 0.25-0.5 pages/chunk at roughly 0.22x-0.25x dense KV) where uniform allocation degrades by several points, to see if certificate-guided allocation yields a statistically significant task-score improvement?

Suggestions for Future Work

  1. Incorporating Output-Projection Sensitivity (||W-O(h)||) into Page Pricing: As noted in Appendix A.9, head errors pass through the output projection W-O before entering the residual stream. Weighting each head's marginal page price Delta-E(c, q) by ||W-O(h)|| (or head-specific downstream sensitivity) rather than treating raw pre-projection L2 norms equally across all heads could align page allocation with downstream task accuracy.
  2. Sub-Gaussian / Johnson-Lindenstrauss Key Score Radii: Replacing the worst-case L1/L-infinity inner-product bound eps(i) = <|q|, Delta-g(i)> / sqrt(d) with a high-probability sub-Gaussian concentration bound across the d = 128 quantization residuals would tighten eps(i) by a factor of roughly sqrt(d) (about 11x), preventing E-key(q) from saturating at 4-5 key bits.
5 comments
AuthorsOpenReview ↗

Reviewer FGun (1 of 2: task scores, Q3 and the surrogate)

Thank you for the detailed technical review. We ran the regime you propose in Q3 and implemented both suggestions.

Q3. A tighter budget where uniform allocation degrades. We ran 4-bit keys, the 2-bit value base and pages at the bytes of a KIVI-style 3-bit cache (0.253x dense) on all 2,652 RULER-32K requests per model. The budget was chosen on disjoint requests, and the primary comparison was fixed before the main runs.

RULER-32K points, 95% intervalsQwen2.5-7BLlama-3.1-8BQwen3-8B
Price-blind pages - dense-1.53 [-2.21, -0.85]-1.22 [-1.82, -0.63]-1.19 [-1.74, -0.66]
Certificate - price-blind (primary)+0.65 [+0.02, +1.29]+0.86 [+0.34, +1.39]+1.20 [+0.64, +1.77]
Certificate - KIVI-style 3-bit+0.81 [+0.10, +1.51]-0.06 [-0.62, +0.50]+0.66 [+0.10, +1.21]
Certificate - rate-distortion-0.37 [-0.68, -0.07]-0.02 [-0.28, +0.24]-0.09 [-0.39, +0.20]

The answer to Q3 is yes against uniform allocation on each model, and yes against the KIVI-style cache on the two Qwen models. The gains are modest, since a page rule can recover at most what price-blind pages lose, and certificate pages recover 43%, 71% and all of it. On LongBench price-blind pages lose at most 0.3 points, so no rule can resolve a gain there.

The surrogate gap. The output KL falls 2.2-3.3x and falls in each of the 13 tasks on each model, so the pages reach the output distribution. Weighting each head's price by the spectral norm of its slice of W_O, as you suggested, changes the RULER-32K score by about 0.1 points with intervals that include zero (Appendix D.9). The rate-distortion and saliency rules, which rank pages differently, land within 0.4 points of certificate pages. At these budgets the loss to dense limits the score gain more than the choice of surrogate does, and we agree that a sensitivity-weighted price could matter where the loss is larger.

Rate-distortion pages. The rule that ties the certificate price is the rate-distortion gain of RDKV and RateQuant. Its gain is the exact page price of a mean-square analogue of the value term under independent residuals, the value-side counterpart of your sub-Gaussian radii. That independence model underestimates the 90th-percentile realized error by 1.7-4.9x (Table 28), while the deterministic bound holds on every instance. The paper presents both prices and claims no ranking between them.

AuthorsOpenReview ↗

Reviewer FGun (2 of 2: E_key, the bit split, serving)

Q1. Where is E_key used? No allocation decision uses it. Proposition 1 makes the page price independent of the key term, so its looseness cannot distort the ranking. E_key makes the total a sound bound and adds ranking information. With the key term of Proposition 6 the certificate flags the top decile of realized error with AUROC 0.97-0.98, against 0.94-0.97 for the value term alone (Appendix D.17).

The bit split. Your reading holds at tight budgets. The certificate cannot arbitrate key against value bits, because the key term overstates the realized key error more than 300-fold. A budget sweep gives the lower KL to 4-bit keys with value pages below about 0.28x dense and to 5-bit keys above it, so the 0.25x study uses 4-bit keys. Page prices are the same under either choice.

Looseness and cap saturation. Proposition 6 centers the weight-change term at the served output. With it and Proposition 5 the median certificate falls from 66-72x to 37-40x the realized error, and the cap frequency falls by 28-43% (Table 35).

Sub-Gaussian radii. We implemented them with Hoeffding's inequality at delta = 1e-3 per token. The radius tightens 1.54-1.88x, short of sqrt(d), because the query-weighted channel errors concentrate on 36-54 of the 128 channels. No token exceeds its radius. The key term stays about 280x the realized key error, since most of its slack comes from the sum over tokens.

Q2. Selection time and the 128K row. Your reading of Proposition 4 is right. The slow selection was a per-page Python heap, a poor implementation and an oversight on our part. The closed form selects the same pages in 9-107 ms from 32K to 128K, and the 128K row with pages is now measured. The 70B row was not rerun, since our one 96 GB card cannot hold that model.

Static serving and latency. The controller now runs inside real decoding with candidate pages in host memory, so the GPU holds 0.28-0.34x of the dense bytes and never all tiers. It has 1.7-2.9x lower KL than static selection at 3.3-3.6% of a decode step (Table 31). With a new single-pass kernel, whole decode steps are faster than dense fp16 in every row, 1.10-2.01x at batch 1 (Table 34).

If a concern remains after these results, we would be grateful to know which analysis or experiment would resolve it. We can run it and report it within the discussion period.

Thank you to the authors for the substantial experimental effort during the rebuttal period, for replacing the Python heap selector with Proposition 4's closed-form quantile (9-107 ms), and for candidly summarizing the method's limitations in the revision.

After carefully reviewing the new results across all responses, however, several findings either leave critical systems questions unanswered or empirically reinforce my core concerns regarding the practical value of the deterministic certificate apparatus. For the reasons below, I do not feel comfortable raising my score and will maintain my current rating.

1. The New Adaptive Baselines Undercut the Core Thesis for Worst-Case Certification

The central premise of the paper is that a deterministic, outward-rounded worst-case attention-error certificate (Theorem 1, Lemma 1) provides a principled advantage for post-compression memory allocation and error control. Yet the new equal-byte comparisons (tqE8 W1, FGun Q3) show the opposite:

  • Standard Rate-Distortion pricing matches or outperforms the certificate price: Computing a simple mean-square rate-distortion gain (RDKV / RateQuant) achieves lower p99 single-step attention error (0.85-0.91x) than the proposed certificate price (tqE8 W1), ties on Llama-3.1-8B (-0.02 [-0.28, +0.24]) and Qwen3-8B (-0.09 [-0.39, +0.20]) on RULER-32K, and statistically significantly outperforms the certificate price on Qwen2.5-7B RULER-32K (Certificate - rate-distortion = -0.37 [-0.68, -0.07]). Furthermore, 76-88% of the error reduction over uniform pages already comes from simple head-level differentiation (One tier per head is within 1.05-1.16x of the certificate's p99 error). Reframing rate-distortion as an alternative "mean-square price of the same retained state" effectively concedes that the paper's flagship worst-case certification machinery provides no allocation advantage over a standard variance/MSE proxy.
  • E_key(q) remains unused in allocation and requires empirical calibration for adequacy: As confirmed in Q1, no allocation decision uses E_key(q), and because E_key(q) overstates realized key error by >280x-300x (even with Hoeffding sub-Gaussian radii), it cannot arbitrate key vs. value bit splits (k4v2 vs. k5v2 had to be selected via an empirical KL sweep, confirming Weakness 2). Even with new Propositions 5 and 6, the total certificate remains 37-40x loose at the median, meaning any adequacy threshold still requires empirical calibration against dense ground truth. For post-hoc flagging of top-decile errors, the value term alone already achieves AUROC 0.94-0.97 (vs. 0.97-0.98 with E_key(q)), which is a slim justification for the key-certificate complexity.

2. Modest Downstream Task Gains in a Lightly Degraded (0.253x) Regime

In Q3, I asked whether certificate-guided allocation yields substantial gains in tighter regimes (e.g., k3v2 or k4v2 at 0.22x-0.25x dense KV) where baselines degrade by several points.

  • At the chosen 0.253x budget (k4v2 + pages, where the k4v2 base already consumes ~0.23x dense before any pages), price-blind pages lose only 1.19-1.53 RULER points to dense, and KIVI-style 3-bit on Llama-3.1-8B loses only 0.30 points. While Certificate - price-blind clears zero (+0.65 [+0.02, +1.29], +0.86, +1.20), it only ties KIVI-style 3-bit on Llama-3.1-8B (-0.06 [-0.62, +0.50]), loses slightly to rate-distortion on Qwen2.5-7B (-0.37), and resolves no gain on LongBench. Tighter budgets where uniform quantization degrades substantially (e.g., k3v2 + pages around 0.20x-0.22x) remain untested.
Reviewer_tqE8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a method to estimate an upper bound on the attention-output error caused by KV-cache quantization, without keeping the original full-precision KV cache. It stores small additional statistics, called receipts, that describe the quantization errors of keys and values and uses them to calculate this bound for each decoding query. Based on this bound, the method keeps key precision fixed and adaptively allocates additional precision to important value chunks using 2-bit correction pages.

Critical strengths
  • The paper addresses an important problem of understanding and controlling the error introduced by KV-cache quantization.

  • The theoretical analysis provides a deterministic attention-error bound, with extensive numerical checks and no observed violations under the reported audit criteria.

  • The experiments cover different model sizes and datasets, and show consistent improvements in attention-output error under the same memory budget.

  • The authors also provide a packed Triton implementation and evaluate actual autoregressive decoding.

Critical weaknesses

W1. Missing comparisons with existing adaptive KV-cache compression methods

The main experimental baselines are uniform precision allocation, simple attention-based and residual-error-based allocation heuristics, and KIVI-style quantization. While these comparisons are useful, there are several closely related methods that already study importance-aware mixed-precision KV-cache compression and are not compared against.

For example, HqeKV (Findings of ACL 2026) supports multiple quantization precision levels and uses importance-aware compression decisions under memory constraints. RDKV (2026) formulates KV-cache compression as a rate-distortion problem and allocates different bit-widths to tokens and channels based on their impact on attention. Other relevant methods include DiffKV (SOSP 2025), which distinguishes the importance of keys, values, tokens, and heads, and KVTuner (ICML 2025), which optimizes layer-wise KV precision. These methods are missing from the related work as well. Earlier methods such as MiKV and ZipCache are cited, but are not included as experimental baselines.

I think this is important because the main empirical contribution is allocating different precision to different parts of the KV cache. Without comparing against at least one or two of the existing adaptive quantization methods, it is difficult to understand how much improvement comes from the proposed certificate, rather than simply using nonuniform precision.

Also, the ablation in Table 3 only considers relatively simple heuristics. The residual-only baseline uses squared residual norms, while the attention-only baseline uses a hand-designed discount for additional pages. These do not fully isolate the advantage of the proposed attention-weighted residual reduction, and the authors acknowledge that these heuristics do not reproduce existing allocation methods. I would like to see comparisons against stronger allocation strategies, preferably using the same quantization representation and memory budget.

W2. The proposed online adaptive compression is not fully evaluated, and the controller only increases precision

One of the main motivations of the paper is that the importance of different KV-cache regions changes as decoding proceeds, so the system should adjust their precision based on the current query.

The theoretical method in Sections 2 and 3 supports query-dependent decisions, and Figure 3 evaluates a dynamic controller that adds correction pages when the value-error bound exceeds a target. However, this dynamic behavior is only evaluated by replaying recorded queries over a fixed KV cache. In the main allocation experiments, the first 1,536 tokens form a fixed cache, and the following 512 queries are evaluated without appending their own keys and values.

The paper does have an actual GPU implementation and end-to-end autoregressive decoding experiments, but these use a different setting. In the serving experiments, correction pages are selected using the last 32 prompt queries, before generation starts, and the allocation is kept fixed during decoding. Therefore, the paper does not demonstrate the benefit or cost of continuously updating precision based on new decoding queries in a real serving system.

There is also a limitation in the proposed controller itself. It only increases value precision by installing additional correction pages, and never removes previously installed pages. For example, if the model initially attends to chunk A and later switches to chunk B, the controller can increase the precision of B, but cannot reclaim the memory previously allocated to A. This makes it difficult to continuously adapt the allocation under a strict memory budget. Key precision is also predetermined and fixed throughout decoding, even though different key regions or channels might have different importance.

The method prepares correction pages in advance, so higher value precision can be recovered without retaining the original FP16 values. However, the paper does not provide a complete mechanism for storing and loading these candidate pages during online decoding. I would like to see an end-to-end experiment with a growing KV cache, online precision updates, a fixed GPU memory budget, and measurements of the associated page-loading overhead.

W3. The upper bounds are quite loose, and their practical usefulness for error control is not fully established

The proposed certificate is mathematically valid under its assumptions, and the authors perform extensive checks of its correctness. However, the bounds can be much larger than the actual attention-output error.

For example, Table 7 shows that with 5-bit keys and 2-bit values, which match the main packed serving precision, the complete certificate can be around 69–72 times larger than the actual error at the median for the representative 16K configurations. The paper explains that much of this looseness comes from the key-error term and the use of worst-case inequalities.

I understand that this does not necessarily affect the ranking of value correction pages. When increasing value precision, the key term stays fixed, so the authors can calculate the exact decrease in their certificate even if the full bound is loose. However, that decrease is not necessarily the same as the reduction in actual attention error.

I think the paper should better distinguish the usefulness of the certificate for ranking which chunks to refine from its usefulness for deciding whether the current compression is accurate enough. The dynamic controller in Figure 3 uses a target on the value-error component, rather than the complete certificate, but it is still unclear how well this target corresponds to a desired level of actual attention-output error. A comparison with an oracle allocation based on measured attention error would help quantify how much additional memory the proposed strategy needs.

Also, the memory-saving result in Table 2 depends on the static comparator being required to meet its calibrated value-error target on every decision query. Appendix D.3 shows that a less conservative, p99-calibrated static policy uses even fewer pages than the dynamic controller, although it fails to meet the target on more held-out queries. This is a reasonable tradeoff, but it would be useful to show memory usage against the fraction of queries that satisfy the error target, instead of relying mainly on the more conservative comparator.

Finally, I think the presentation of Section 2 needs improvement. The section moves through the setting, the different receipts, and the mathematical bounds too quickly, without enough intuition about what each receipt represents, why it is needed, and how it contributes to the final error bound. In particular, the roles of the key-error bounds, value reconstruction-error bounds, and original value-norm bounds should be explained more clearly before introducing the equations. A simple example and a more gradual derivation would make this section much easier to follow.

W4. Limited end-to-end efficiency evaluation

Although the authors implement GPU kernels, their latency measurements exclude important costs such as KV-cache packing, page selection, and page transfer. In Table 18, page selection alone takes 3.1 seconds for Qwen2.5-7B at 32K and 53.1 seconds for Llama-3.1-70B at 64K, which can be substantial compared with decoding time. Also, the serving comparisons are mainly against dense FP16 PyTorch eager attention, rather than optimized quantized KV-cache implementations, and are limited to batch size one. The reported speedups are mixed, with some configurations even slower than dense attention. I think a more complete end-to-end latency evaluation and comparisons against stronger serving baselines are needed to establish the practical efficiency of the method.

References

Questions for authors

Please see above.

4 comments
AuthorsOpenReview ↗

Reviewer tqE8 (1 of 2: W1 and W2)

Thank you for the thorough review and the pointers to related work, all of which the revision now discusses.

W1. Adaptive baselines, and how much comes from the certificate. On one page pool and byte budget we ran the allocation signals of ZipCache and of RDKV and RateQuant, allocation at the granularity of KVTuner (per layer) and DiffKV (per head), and two oracles, over 120 recorded windows of five models (Table 3).

p99 attention error relative to the certificate price
Price-blind pages1.55-2.25x
Saliency (below one page per chunk)1.70-1.79x
One tier per layer1.22-1.43x
One tier per head1.05-1.16x
Rate-distortion gain0.85-0.91x
Decision oraclethe certificate attains 87-93% of its gain

Head-level differentiation carries 76-88% of the gain over price-blind pages, and the placement across chunks within a head carries the rest. The rate-distortion gain has slightly lower p99 error and ties the certificate price in KL and task scores. It prices the same pages from the same receipts under an independence model, so the paper presents the two as mean-square and worst-case prices of one retained state. KVTuner's released presets, served at the same bytes, lose 1.7-4.5 points to dense where certificate pages lose 0.6-1.3. HqeKV and RDKV also evict tokens, which lies outside what the certificate prices.

W2. Online adaptation, removal of pages, page storage. The revision runs the experiment you describe inside the model's decode loop (Table 31). The cache grows from 32 to 80 chunks, the controller reprices all pages every 32 steps and swaps them under a fixed GPU budget, and every prepared page lives in pinned host memory. Static selection, the serving path of the submission, has 1.7-2.9x the KL of online swapping on two models, and loading costs 3.3-3.6% of a decode step. Removal follows from Proposition

  1. Removing a chunk's deepest page raises the bound by exactly its price, so one price list decides what to install and what to evict, and in your example chunk A's pages leave once chunk B's candidates carry higher prices. Key precision stays fixed, since a key refinement changes every softmax weight of the head (Proposition 3), and we state this as a limitation.
AuthorsOpenReview ↗

Reviewer tqE8 (2 of 2: W3, W4 and presentation)

W3. Ranking against adequacy, the oracle, and the target trade-off. The revision separates the two uses of the certificate (Appendices D.12 and D.17). For ranking, the certificate attains 87-93% of an oracle's gain, because the value term is the exact worst case given its receipts (new Proposition 5). For adequacy, the complete certificate is 66-72x the realized error, 37-40x with the tighter terms of Propositions 5 and 6, and this factor is nearly constant across instances. The certificate therefore flags the top decile of realized error with AUROC 0.97-0.98, so a target on it acts as a threshold on realized error up to a calibrated factor. Table 29 gives the curve you asked for, memory against the share of held-out queries that meet the target.

W4. End-to-end efficiency. The closed form of Proposition 4 replaces the Python heap of the submission and selects the same pages in 9-107 ms from 32K to 128K (Table 32). With a new single-pass kernel, whole decode steps are faster than dense fp16 in every row, 1.10-2.01x at batch 1 and 1.55-2.12x at batches 4 and 8 (Table 34). The kernel is faster than FlashInfer's dense decode from batch 4 on, and FlashInfer's FP8 cache at 0.5x bytes stays 1.3-1.9x faster at the kernel level (Table 33). A comparison inside an optimized serving engine remains future work.

Presentation of Section 2. We kept the structure and added what you propose. Before any equation each receipt is introduced by the question it answers, and a three-token example runs from the setting through Theorem 1 to one exact page price. A stepwise derivation in four steps is written and could replace the current text if you prefer it.

We would be glad to revise further where the paper still reads too fast, and if a concern remains after these results, we would be grateful to know which analysis or experiment would resolve it within the discussion period.

I thank the authors for additional experiments. My concerns are mostly addressed, and I will raise my score.

Thank you very much for reading our responses so carefully and for raising your score. Your suggestions on adaptive baselines and online control led to the studies that most strengthened the revision. We sincerely appreciate your time and the constructive review.

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

This paper proposes a KV-cache quantization method that uses error bounds to guide memory allocation. The method quantizes keys at a fixed precision and stores values using a low-bit base representation with additional correction pages. It also keeps a small amount of information about quantization errors, allowing it to estimate an upper bound on attention-output error without retaining the original KV cache.

Based on the estimated error reduction, the method adaptively allocates additional precision to different value chunks. The authors show that this approach reduces attention-output error compared to uniform precision allocation under the same memory budget. They also implement a packed KV-cache representation and a Triton kernel for inference.

Critical strengths
  • The method provides a way to estimate attention error after KV-cache compression. The error bound can be computed without accessing the original full-precision KV cache, which could be useful for making memory allocation decisions during inference.

  • The adaptive allocation method shows consistent improvements in attention-output error. Compared to uniform allocation, the proposed method reduces attention error by 30–67% under the same memory budget across multiple models and datasets.

  • The paper includes a practical implementation. The authors implement packed KV-cache storage and a Triton kernel, and demonstrate inference with a 70B model at 128K context length on a single GPU.

Critical weaknesses
  • The novelty of the proposed method is not sufficiently clear. Previous works such as WitCert and Calver have already explored error bounds for quantized attention. The proposed memory allocation strategy also seems closely related to existing importance-aware mixed-precision quantization methods. While the combination of error bounds and progressive value refinement is interesting, it is unclear how significant the new contribution is compared to these existing approaches.

  • The experimental comparisons with existing methods are limited. Most of the main experiments compare the proposed method against uniform allocation, which is a relatively simple baseline. Although the authors include comparisons with KIVI-style quantization and WitCert, there are limited comparisons against existing adaptive or mixed-precision KV-cache quantization methods. This makes it difficult to understand how much improvement the proposed method offers over existing techniques.

  • The proposed method does not demonstrate improvements in downstream task accuracy. Although the method significantly reduces attention-output error and improves the KL divergence to the full-precision model, these improvements do not translate into significant gains in downstream task performance. As shown in Tables 14 and 15, the proposed method achieves nearly identical task scores to uniform allocation and KIVI-style quantization across RULER and LongBench. This raises questions about the practical benefits of the improved attention accuracy, especially given the additional complexity of the proposed method. Evaluations under more aggressive compression settings, where existing methods suffer noticeable accuracy degradation, would help demonstrate its practical value.

Overall, while the method shows promising improvements in attention accuracy, I am not fully convinced that the paper demonstrates a sufficiently significant advance over existing KV-cache compression techniques.

Questions for authors
  • Could the authors clarify the main novelty compared to WitCert, Calver, and existing importance-aware KV-cache quantization methods? In particular, what capabilities does the proposed method provide that these methods cannot?

  • Could the authors include comparisons with stronger adaptive or mixed-precision KV-cache quantization baselines at the same memory budget? It would be helpful to understand whether the proposed method improves the overall memory–accuracy trade-off compared to existing methods.

  • Since the proposed method significantly reduces attention error but does not show a clear improvement in downstream task scores, could the authors evaluate it under more aggressive compression settings where existing quantization methods noticeably degrade model accuracy?

  • What is the end-to-end overhead of dynamically selecting and loading correction pages during inference? Where are the unused correction pages stored, and how does this affect total memory usage and inference latency?

4 comments
AuthorsOpenReview ↗

Reviewer DQBZ (1 of 2: Q1 and Q2)

Thank you for the careful review. We answer the four questions in two comments.

Q1. Novelty relative to WitCert, Calver and importance-aware quantization. The new capability is refinement between compressed states at an exact price on a sound bound, with no full-precision copy kept.

Per-query deterministic boundHow precision is raised after compressionWhat decides it
Calveryespromotes values to FP16 from retained originalsblock contributions
WitCertyesrestores exact blocks from a backing storea gate on the bound
Importance-aware mixed precision (MiKV, ZipCache, KVTuner, DiffKV, HqeKV, RDKV)noprecision is chosen when entries are compressedan importance, sensitivity or rate-distortion signal
Oursyesinstalls or removes nested 2-bit pages, originals discardedthe exact change of the bound (Proposition 1)

Two capabilities follow. Precision moves in both directions during decoding, and swapping pages by the exact price keeps the output 1.7-2.9x closer to dense in KL than a one-time selection (Table 31). The certificate also flags the queries with the largest realized error (AUROC 0.97-0.98, Appendix D.17), so the system can check per query whether the compressed state is adequate. On identical states our bound is tighter than WitCert's while storing about one byte of key receipt per token and head against its 32 bytes (Appendix D.8).

Q2. Stronger adaptive baselines and the memory-accuracy trade-off. We placed the allocation signals of ZipCache, RDKV and RateQuant, KVTuner and DiffKV on our page pool at equal bytes (Table 3). The certificate price has lower p99 attention error than saliency, per-layer and per-head allocation and attains 87-93% of an oracle's gain. The rate-distortion rule ties it. That rule prices the same pages from the same receipts under an independence model, so we report the two as the mean-square and worst-case prices of one retained state. For the trade-off, Figure 7 plots KL to dense against KV bytes. At 0.253x certificate pages have 2.5-3.0x lower KL than a KIVI-style cache of the same bytes, a KL that cache reaches only at about 0.29x.

AuthorsOpenReview ↗

Reviewer DQBZ (2 of 2: Q3 and Q4)

Q3. More aggressive compression. At 0.25x dense, the bytes of a KIVI-style 3-bit cache, on all 2,652 RULER-32K requests per model:

RULER-32K points, 95% intervalsQwen2.5-7BLlama-3.1-8BQwen3-8B
Certificate - price-blind pages+0.65 [+0.02, +1.29]+0.86 [+0.34, +1.39]+1.20 [+0.64, +1.77]

Certificate pages also score above the KIVI-style cache on the two Qwen models and tie it on Llama-3.1-8B, where that cache loses only 0.30 points to dense. At the submitted budget of 0.316x price-blind pages lose only 0.73 points, which left the submitted study little room to resolve a gain. On LongBench every page rule stays within 0.4 points of dense, so scores cannot rank the rules there.

Q4. Overhead of selecting and loading pages, and where unused pages live. Selection now takes 9-107 ms after pricing, and in the static path the unselected pages are discarded. In the online path every prepared page stays in pinned host memory, and the GPU holds only the base and the resident pages, 0.28-0.34x of the dense bytes. Pricing, page-table edits and host-to-GPU copies add 3.3-3.6% to a decode step (Appendix D.14).

If a concern remains after these results, we would be grateful to know which analysis or experiment would resolve it. We can run it and report it within the discussion period.

I thank the authors for providing the additional explanations and experiments. These comments have largely addressed my concerns on comparing to existing mixed-precision KV quantization methods, performance at higher compression rate and the runtime overhead.

I will still consider the novelty somewhat incremental, but I appreciate the method's ability to adjust the precision according to the its contribution to error. I will raise my score to weak accept.

Thank you very much for reading our responses and for raising your score. Your questions on mixed-precision baselines, higher compression rates and runtime overhead led to studies that strengthened the revision. We sincerely appreciate your time and the constructive review.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the response and the revision (all reviewers and the AC)

We thank the reviewers for specific and constructive reviews. The method, Theorem 1, Proposition 1 and the cache representation are unchanged. We ran each requested study, and the revised PDF reports them with new text in blue. Tables 3 and 4 are replaced by stronger versions of the same two comparisons (the submitted tables are now Tables 11 and 14), Section 2 gains the role of each receipt and a numerical example, and the new studies are in Appendices D.9 to D.18.

RequestMain findingWhere
Task scores where compression costs accuracy (FGun Q3, DQBZ Q3)At 0.25x dense, certificate pages score above price-blind pages on all three models, with intervals above zero over all 2,652 RULER-32K requests per modelTable 4, App. D.9
Published adaptive rules at equal memory (tqE8 W1, DQBZ Q2)The certificate price has lower p99 error than saliency, per-layer and per-head allocation and attains 87-93% of an oracle's gain. The rate-distortion rule ties it.Table 3, App. D.12
Online control on a growing cache (tqE8 W2, FGun W3, DQBZ Q4)Repricing and swapping pages during decoding, with pages in host memory, gives 1.7-2.9x lower KL than a one-time selection at 3.3-3.6% of a decode stepTable 31, App. D.14
Serving cost (FGun Q2, tqE8 W4)Selection takes milliseconds, and whole decode steps are faster than dense fp16 in every rowTables 33, 34
Looseness and the role of E_key (tqE8 W3, FGun)Two new propositions bring the certificate from 66-72x to 37-40x the realized error, and it flags the largest realized errors with AUROC 0.97-0.98App. A.10, A.11, D.17
Presentation of Section 2 (tqE8)Each receipt is introduced by the question it answers, with one running numerical exampleSec. 2

Limits, as the paper now states them. The task-score gains are small in absolute terms, since compression costs only 1.2-1.5 points at these budgets. The certificate price does not outrank the rate-distortion rule, and E_key is too loose to split bits between keys and values. A comparison inside an optimized serving engine remains open.

Superseded numbers. The submitted LongBench rows (now Tables 14 and 17) omitted the benchmark's first-line rule for three tasks, which affected every arm alike. The new study uses the official rule and reaches the same conclusion. The selection times of Table 20 and the latencies of Table 19 are replaced by those of the closed-form selector and the single-pass kernel.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.