- 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
-
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)).
-
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
-
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 error by 30–67% (Table 1) and teacher-forced next-token KL divergence by (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]) andAdaptive - KIVI-style(+0.17,-0.41,+0.04,-0.03,-0.06) covers zero. Even at half the page budget (0.289xdense KV, Table 13),Adaptive - Uniformon RULER-32K is-0.09 [-1.33, +1.14]. - This highlights a critical surrogate gap: minimizing unweighted single-head attention output error across all heads/layers spends refinement budget on heads with large value norms (Figure 5) rather than the specific retrieval or reasoning heads that affect discrete downstream generation decisions.
-
The Key Certificate Is Completely Unused by the Page Allocator, Is Loose in Serving, and Dictates an Unfavorable Key-Heavy (
k5v2) Bit Allocation:- and cancel out of allocation: Because Proposition 1 subtracts from at fixed keys, , the key error bounds , and the value norm bounds cancel completely from the page price . Even the target-driven controller in Figure 3 / Table 10 thresholds only the value-error bound , ignoring . 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
k5v2serving configuration (Table 7, 16K and 32K deploy arms), the total certificate exceeds realized error by a median factor of ( at p90), and the softmax perturbation factor hits its vacuous cap of in 24.0%–30.5% of all instances (and 61.2%–64.1% without sinks). Because assumes worst-case sign alignment across all channels, and grow exponentially unless keys use bits. - Inefficient base bit split (
k5v2vs.k4v4): To keep 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,k5v2loses RULER points relative to a simple statick4v4KIVI-style baseline (Table 13), and adding pages up to thek4v4byte budget (0.316xdense) merely recovers parity withk4v4(Table 4) while incurring substantial metadata and kernel complexity.
-
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.andPackoverhead, yetBase + selected pagesis still slower than dense 16-bit serving in 4 of the 5 measured rows (1.305xon Qwen2.5-7B 16K,1.198xat 32K,1.063xon Llama-3.1-8B 32K, and1.952xon 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 to dense FP16 (Table 5, line 1134).
- 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 (
Questions for authors
Clarification Requests
- 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?
- 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?
- 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
- 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.
- 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
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.
1/2
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 (tqE8W1), 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 headis within1.05-1.16xof 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 usesE_key(q), and becauseE_key(q)overstates realized key error by>280x-300x(even with Hoeffding sub-Gaussian radii), it cannot arbitrate key vs. value bit splits (k4v2vs.k5v2had to be selected via an empirical KL sweep, confirming Weakness 2). Even with new Propositions 5 and 6, the total certificate remains37-40xloose 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 AUROC0.94-0.97(vs.0.97-0.98withE_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.253xbudget (k4v2+ pages, where thek4v2base already consumes~0.23xdense before any pages), price-blind pages lose only1.19-1.53RULER points to dense, and KIVI-style 3-bit on Llama-3.1-8B loses only0.30points. WhileCertificate - price-blindclears 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 around0.20x-0.22x) remain untested.
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.
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.