acceptodds
Under review as a conference paper at ICLR 2027

Value Channels Gaussianize Rounding Noise: Tensor Geometry of KV-Cache Quantization

Abstract

A quantized key-value cache is written once and read by many future, possibly adaptive, queries. We show that, within a factor of two, the uniform read error is governed by one invariant: the expected injective norm of a random sign tensor that pairs the attention family with the Euclidean value space. Three reductions isolate it. Convex order removes the encoder: among conditionally unbiased encoders on fixed grids, independent stochastic rounding is optimal for every convex loss. Duality replaces the query family by its convex hull, and symmetry replaces the bit budget by its orbits. A structure theorem then reduces this invariant, for every attention family and up to absolute constants, to two scalar quantities. It is a Bernoulli counterpart of Chevet's inequality for a Euclidean factor: the error is the worst fixed-query fluctuation, amplified by in value dimension , plus a flat-direction width in which the value channels Gaussianize the bounded rounding noise. When each token's values share one grid, Bernoulli and Gaussian noise models therefore differ by a factor of order at most on tokens, and softmax attention with logarithmic-dimensional keys attains this factor in every dimension. Across independent token groups, fluctuations add in and selections in . Optimal precision is a convex program, rounded within a factor of eight, whose optimum equalizes the contributions to the worst-case error of all coordinates stored above the minimum precision.

Primary area:
learning theory
Keywords:
KV cache quantization, stochastic rounding, uniform error, Bernoulli processes, injective tensor norm, Chevet inequality, precision allocation

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 3 reviews, above 85% of the others.
Reviewer_uazKOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper derives how Key tensor perturbations in the attention operations, modeled as (conditionally-) unbiased uniform quantization, interact with the attention score structure. It is shown how output error norm can be first approximated (up to a uniform constant) by random sign perturbations on the quantization grid and, later and in certain regimes, by Gaussian noise. The bounds are then used to derive optimal bitwidth allocations between tokens and channels to minimize output distortion. The derived bounds and allocations are validated on synthetic data.

Critical strengths
  • The presentation is thorough. No definitions or references appear missing.
  • The notation is consistent and I had no problem navigating the manuscript.
  • The results check out numerically on synthetic data.
Critical weaknesses
  • The text is extremely dense. Few theorems or definitions include simplified explanations or plain-text discussion of implications. It feels like the text was ruthlessly and repeatedly compressed with an LLM to make it as short as possible, leaving only bare bones of definitions, cross-references and formulaic results.
  • Numerical validation only deals with synthetic data sampled independently from Gaussian or mixture of Gaussian distributions. Since real Q and K tensors in LLMs are heavily-correlated and might be more heavy-tailed, it is not clear which results hold for real LLMs.

Since I have very limited experience with such math-heavy manuscripts, its hard for me to gauge how critical these downsides are.

The score I give ("weak accept") reflects the fact that I see no strong indications of unfairness or misrepresented results, but I might not have the expertise to independently verify or contextualize all of them.

Questions for authors
  • The scope of quantization is somewhat unclear since Sections 2 and 3 seemingly only describe Value-tensor perturbations but Proposition 5 suddenly Key-tensor perturbations too, which only ever appear in the proposition itself. Can you elaborate on which parts of the paper deal with V or KV quantizations?
  • What are the implications of the bit allocations you derive on LLM inference where the query family is not fixed but rather expands as generation goes? Is there a practical way to update allocations on the fly?
3 comments
AuthorsOpenReview ↗

Response to Reviewer uazK (1/2)

Thank you for the review; we agree with its main criticism, that the main text is too dense. The revised PDF (changes in blue) adds plain-language readings, states the scope up front, and checks the laws on trained models.

W1 (density). Within the 10-page limit, the main text gained "In words" readings after Theorem 2, Theorem 7 and Corollary 8 and a scope statement in Section 1. The decomposition figure (Figure 2 at submission) illustrates a proof step, so it now sits beside that proof (Figure 4, Appendix E). The fuller fix is in Appendix A, next to the dependency graph (Figure 3): a new list, "The results in words", with a plain statement of every main-text result. In short:

  • Theorem 2. On grids fixed in advance, rounding every coordinate independently and at random to a neighbouring grid point is the best among schemes that are unbiased given their earlier outputs, for every convex error measure; schemes that are unbiased only on average can do better (Remark 3). The best worst-input error lies between one half and one times a single quantity, B(A,h)\mathcal B(\mathcal A,h), so from there on the worst-input error depends on the grids only through their spacings.
  • Theorem 7. When each token's values share one spacing, that quantity is, up to constants, the typical error of the single worst query plus a selection term: the gain the query family gets from choosing, after the noise is drawn, the average in which the rounding errors fail to cancel. Rounding noise and Gaussian noise then give the same worst-query error up to constants once the head dimension exceeds the logarithm of the context length (Corollary 8).

On W3 and W4, for checking the results without the proofs: Figure 3 shows what each result relies on, Appendix B gives where each external theorem comes from, Appendix I.1–I.3 and I.5 check every law on synthetic data, and Appendix I.4 checks Theorem 7, Corollary 8 and the read-error bounds on real heads. The one new probabilistic ingredient of the structure theorem is Lemma 30 in Appendix E.

Q1 (which parts concern values and which keys). Apart from Proposition 5(b), every result from Theorem 2 through Corollary 14 concerns value rounding with exact keys; the keys only determine the attention family. Section 1 and the Takeaway now say so.

Part of the paperValuesKeys
Sections 2–5, Theorem 2 to Corollary 14, except Proposition 5roundedexact
Proposition 5(a)roundedexact; the query family is approximated
Proposition 5(b)perturbedperturbed, any quantizer
Appendix D, first-order key error—stochastically rounded
Section 6, real heads and perplexityroundedexact

The split has a reason. The value error is linear in the value perturbation and is a norm of the error array, which is what Sections 3 and 4 compute. A key perturbation acts through the softmax, so its error does not have the form our main theorem handles; Theorem 7 still gives a first-order upper bound for it (end of Appendix D), and Proposition 5(b) gives an exact one. We have added the scope statement to Section 1, a sentence before Proposition 5, and this derivation at the end of Appendix D.

AuthorsOpenReview ↗

Response to Reviewer uazK (2/2)

W2 (synthetic data only; real Q and K are correlated and heavy-tailed). The theorems make no assumption on how queries, keys or values are distributed. The upper bounds need only that each value lies in its grid's range and that the rounding randomness is independent of the input, which per-token ranges with stochastic rounding satisfy; the optimality of Theorem 2 and the lower bound of Theorem 12, which assume grids fixed in advance, are not claimed for such ranges, nor are the statements that inherit them. Correlation and heavy tails change the attention family and the ranges, and so the numbers: an outlier value widens its token's range and coarsens that token's grid, and the error bound grows by at most that factor, and by little unless queries attend to that token (Lemma 26). On Qwen2.5-0.5B with WikiText-2 (all 48 key-value heads on 8 text chunks; values rounded, keys exact; Section 6, Appendix I.4), the ratios that Theorem 7 and Corollary 8 bound stay as close to one as on synthetic families: between 0.800 and 0.932, and between 0.989 and 1.085. At 3 bits the measured read error under stochastic rounding is 0.376–0.494 of B\mathcal B. On the larger Qwen2.5-1.5B (56 key-value heads on 4 chunks, head dimension 128; protocol fixed before its run, after the 0.5B results) the two ratios lie between 0.838 and 0.957 and between 0.994 and 1.074. At this cache length B\mathcal B is within 4% of the single-worst-query term on every head, so real heads test the laws in their simplest regime; the selection term matters on families with rare sharp queries (Section 6). The allocation result is mixed: every adapted per-token schedule lowers the 2-bit perplexity on 15 of 16 chunks, but our equal-contribution schedule is the weakest of three, and on the worst-query error of later queries it keeps almost none of the gain it has on its own calibration queries (3 bits: median 1.023 of uniform). On those calibration queries every adapted schedule cuts the median worst-query error to 0.09–0.16 of uniform, so what fails is the calibration family, not only the optimizer (general response, item 1).

Q2 (allocation when the query family grows during generation). In practice, not yet. A schedule fitted to the queries seen so far did not hold up on later queries (Section 6), and a token's bits cannot be raised after it has been rounded. What can be computed on the fly is the schedule of each newly written block, for a set of queries declared in advance: if the cache is written in blocks of many tokens, the worst-query error of the whole cache is at most the largest worst-query error of a single block, because full attention is a mixture of the block-wise attentions (Section 5; Lemma 32 in Appendix H; in expectation this costs a factor C(1+log⁡G/d)C(1+\sqrt{\log G/d}) for GG blocks, and per-block schedules are not claimed jointly optimal). That needs a query set known to cover future queries. One that provably does follows from the model weights, but it is far larger than the queries that occur (the largest observed query norm is a median 0.121 of the bound; Appendix I.4), so a set that is both valid and tight is open (Section 7), as is the propagation of read errors through later layers and generated tokens.

We hope the real-model checks (W2) and the scope statement (Q1) address your main questions, and we would welcome any remaining concerns on readability.

Reviewer_uazKOpenReview ↗

Concerns largely resolved

Thank you for the additional explanations and results.

The addition of practical LLM measurements strengthen the narrative. However, they also show the limited practical usefulness of the results, as seen from equal-contribution schedules underperforming beyond token positions they were calibrated on (Table 1, Table 9).

I appreciate the additional results, improved clarity and honesty about limitations, and maintain my positive assessment of the paper.

Reviewer_kUuFOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops a theoretical framework for characterizing the worst-case attention output error of a quantized KV cache reused by multiple future queries, using the expected injective norm of a random sign tensor. It establishes the optimality of independent stochastic rounding under conditional unbiasedness assumptions, analyzes Gaussianization through value channels, and derives a convex precision-allocation formulation with approximation guarantees. Validation consists of theoretical proofs and synthetic experiments, without evaluation on real LLMs.

Critical strengths
  1. The paper explains why small error for a fixed query does not imply small worst-query error. It also proves that, with a shared grid across each token’s value channels, Bernoulli and Gaussian error models become equivalent up to constant factors once the value dimension reaches a logarithmic scale.
  2. The objective clearly matches the cache-reuse setting, and the theoretical results form a coherent framework connecting error characterization, structural decomposition, and precision allocation.
Critical weaknesses
  1. The results have substantive scope restrictions: stochastic rounding is optimal only among conditionally unbiased encoders with fixed grids and precision schedules, while Gaussianization requires shared spacing across each token’s value channels. The paper’s example of a n\sqrt{n} improvement through correlated rounding further limits broader interpretations of optimality.
  2. It remains unclear whether the weighted transport distance of queries outside the calibration set can be effectively controlled in real models. If this distance is large, the benefits of worst-query precision allocation may not persist.
Questions for authors
  1. Can the authors clarify how the conditional unbiasedness and fixed-grid assumptions relate to practical KV-cache quantization methods, which often use deterministic rounding and input-dependent quantization scales? Which theoretical guarantees remain applicable when these assumptions are relaxed?
  2. How can the query family be specified before quantization in realistic autoregressive generation, where future queries depend on previously generated tokens?
  3. Can the authors provide experiments on real LLMs to validate whether the theoretical error characterization accurately predicts attention output errors and whether the proposed precision allocation improves over uniform or MSE-based allocation under matched bit budgets?
4 comments
AuthorsOpenReview ↗

Response to Reviewer kUuF (1/4)

Thank you for asking for the real-model validation; each of your questions is answered below, with the new material in the revised PDF (changes in blue; main-text theorem and equation numbers unchanged, appendix lemmas after Appendix C.3 shifted by 3). The main point: we ran both halves of Q3 on trained models. On Qwen2.5-0.5B at 3 bits the measured read error lies between 0.376 and 0.494 of the invariant on every head for stochastic rounding and between 0.248 and 0.464 for round-to-nearest, with medians close to a back-of-envelope value from the worst-query term of Theorem 7; worst-query allocation computed from earlier queries does not carry over to later ones, which is the risk of W2, now measured.

Notation: FA(x)=sup⁡a∈A∥a⊤x∥2F_{\mathcal A}(x)=\sup_{a\in\mathcal A}\Vert a^\top x\Vert_2 is the worst-query read error of an error array x∈Rn×dx\in\mathbb R^{n\times d}, and B(A,h)=EFA(h⊙ε)\mathcal B(\mathcal A,h)=\mathbb E F_{\mathcal A}(h\odot\varepsilon) is the invariant of Eq. (2), with hih_i the spacing of token ii when its dd value channels share one grid; rr is the largest single-query fluctuation, bd\mathfrak b_d the flat (selection) width, and G\mathcal G the Gaussian counterpart of B\mathcal B.

AuthorsOpenReview ↗

Response to Reviewer kUuF (2/4)

Q3 (real LLMs). Section 6, Table 1; Appendix I.4, Tables 8–11. The first 512 tokens of each 1024-token WikiText-2 chunk form the cache; the family of a key-value head is the set of attention vectors over the cache of the query heads that share it; spacings are per-token absmax; values are rounded and keys stay exact (no key-quantized run was done). Qwen2.5-0.5B: 48 key-value heads on 8 chunks, 384 cases (d=64d=64). Qwen2.5-1.5B: 56 heads on 4 chunks, 224 cases (d=128d=128).

Does the characterization predict the read error? Within a stable factor, yes, for a family that contains the measured queries. On Qwen2.5-0.5B the ratio B/(d r+bd)\mathcal B/(\sqrt d\thinspace r+\mathfrak b_d) of Theorem 7 lies between 0.800 and 0.932, G/B\mathcal G/\mathcal B between 0.989 and 1.085, and the measured 3-bit read error between 0.376 and 0.494 of B\mathcal B for stochastic rounding (SR) and between 0.248 and 0.464 for round-to-nearest (RTN); on Qwen2.5-1.5B the same quantities are 0.838–0.957, 0.994–1.074, 0.393–0.497 and 0.268–0.486. Theorem 2's lower bound of 12B\tfrac12\mathcal B is for the worst input, attained at midpoint inputs, so measured SR errors below 12B\tfrac12\mathcal B on these inputs are consistent with it. On these heads B\mathcal B is within 4% of d r\sqrt d\thinspace r, so the test exercises the fixed-query term; the selection term matters on families with rare sharp queries (Section 6). In this regime a back-of-envelope estimate with per-coordinate error variances h2/6h^2/6 (SR, inputs spread within cells) and h2/12h^2/12 (RTN) gives 0.408 and 0.289 of B\mathcal B, against measured medians of 0.416 and 0.303 at 3 bits on Qwen2.5-0.5B; RTN sits higher at 2 bits (0.354) and on Qwen2.5-1.5B (0.336 at 3 bits). This is the value-only read error with attention renormalized over the cache, an upper bound on the cache's contribution to the head output.

Does the allocation beat uniform and MSE-based allocation at matched budgets? For our equal-contribution schedule computed from a calibration set: better than uniform end to end at 2 bits but not distinguishable from it at 3 bits (12.81 against 12.57 with SR, 12.29 against 12.54 with RTN, within chunk-to-chunk variation), not better than squared-error allocation on later queries or end to end, and not better than uniform on the worst-case error of later queries. Setup: schedules are computed from queries at positions 512–767 and evaluated on positions 768–1023 (3 bits); perplexity is that of tokens 641–1023 of 16 chunks, with prefix values quantized and schedules from positions 512–639 (exact cache 11.77; SR averages 3 seeds).

Schedulelater queries: median B\mathcal B / uniformlowest inppl 2 bits, SRppl 2 bits, RTNppl 3 bits, SRppl 3 bits, RTN
uniform10.41119.3217.1712.5712.54
MSE-greedy0.7700.22413.0912.5812.3712.04
worst-attention0.7310.26613.2312.6712.4012.07
equal-contribution1.0230.09913.7613.1312.8112.29

In detail. On their own calibration queries all adapted schedules cut the median worst-query error to 0.09–0.16 of uniform, the squared-error schedule included (Table 9, a check added after the held-out run); our greedy equal-contribution schedule is the best of the three there at 3 and 4 bits but last at 2 bits, so it is an imperfect optimizer at low budgets, and the stochastic subgradient method and certificate Eq. (21) were not run on real heads. Since every adapted schedule already reaches a median 0.09–0.16 in-sample, the later-query loss at 3 and 4 bits is a transfer failure that a better in-sample optimizer would not repair. On later queries ours keeps almost none of its gain (median 0.939–1.023 of uniform; 0.850–0.905 on Qwen2.5-1.5B), the other two keep part of it in the median, and the tail is heavy: at 3 bits the mean later-query ratio is 1.611, 1.670 and 2.076 for the three adapted schedules. End to end, every adapted schedule lowers the 2-bit perplexity on 15 of 16 chunks under both roundings; at 3 bits the squared-error and worst-case-attention schedules have post-hoc 95% intervals just below 1 under RTN, and the other differences are within chunk-to-chunk variation (Table 11). The protocol favours the adapted schedules (calibration from the start of the continuation, a 2-bit uniform grid without a zero level, about 0.05 bits per value of uncharged metadata), so the 2-bit gain over uniform is not offered as evidence for worst-query allocation. Section 7 now states the consequence: the allocation results are optimality statements for the declared family, and a calibration set of earlier queries is not such a family on these models.

AuthorsOpenReview ↗

Response to Reviewer kUuF (3/4)

W2 (transport distance outside the calibration set). Quantified, and the concern is borne out. At uniform precision the transport residual of the worst later query to the calibration set is at most a median 1.166 times the calibration-family B\mathcal B (0.153 averaged over later queries), an upper bound computed from the observed later queries against the finite set. Proposition 5(a) then bounds the later error by the calibration error plus a residual of the order of B\mathcal B, which is not informative, and the fitted schedules lose their in-sample gains (Q3). A family that needs no transport follows from the weights (Q2), but the largest observed query norm is a median 0.121 of that bound, so its radius is about eight times what the queries reach (its B\mathcal B was not computed). A family that covers future queries and is still tight is an open problem, which we state in Section 7.

Q1 (deterministic rounding, input-dependent scales). The statements about FAF_{\mathcal A}, B\mathcal B and the Gaussian width do not involve the encoder: Proposition 4(a), Theorem 7, Corollary 8, Proposition 9, Theorem 11 and the width part of Corollary 10 hold as stated, and Proposition 5(b) holds for every realized key and value perturbation. Conditional unbiasedness enters through Theorem 2 and the lower bounds that use it (Theorem 12, Corollaries 10 and 14); the allocation upper bounds and the tail bound of Proposition 4(b) are statements about SR, and for RTN they hold only through the additive-noise model. The link between B\mathcal B and the actual error (paragraph "Beyond stochastic rounding" after Remark 3; Appendix C.4):

  1. RTN, worst input: exactly d2sup⁡a∈A∑iaihi\tfrac{\sqrt d}{2}\sup_{a\in\mathcal A}\sum_ia_ih_i, half the amplitude bound of Section 4 (Lemma 24); up to the factor 2 of Theorem 2, its gap to B\mathcal B is the worst-case value of randomization.
  2. RTN under the additive-noise model (independent errors uniform on [−hi/2,hi/2][-h_i/2,h_i/2]; an assumption on the inputs): 14B≤EFA≤12B\tfrac14\mathcal B\le\mathbb E F_{\mathcal A}\le\tfrac12\mathcal B (Lemma 25), which holds in 0.984–0.997 of the Qwen2.5-0.5B cases over 2–4 bits.
  3. Input-dependent scales with fresh SR given the scales: EFA≤B(A,h(v))\mathbb E F_{\mathcal A}\le\mathcal B(\mathcal A,h(v)) and the tail bound of Proposition 4(b) hold input by input, provided the values lie in the stored range.

Not claimed for input-dependent grids: the minimax optimality of Theorem 2 and the lower bounds above.

W1 (scope restrictions). Each restriction applies to specific results.

  • Fixed grids and schedules: only the optimality and lower-bound statements need them (Q1, item 3).
  • Optimality among conditionally unbiased encoders is a worst-input statement. On real inputs the biased RTN has the lower read error in every case at 3 and 4 bits, as the error variances suggest (Q3). Under the additive-noise model the same invariant brackets both encoders (Lemma 25); on worst inputs RTN is governed by the amplitude instead (Lemma 24).
  • Shared spacing across a token's value channels: per-token value quantization with one group per head is exactly this layout; group-wise spacings follow from the last claim of Lemma 26, losing at most the ratio of group spacings (Appendix C.4), and non-uniform levels and outlier extraction are not covered. Under this layout Corollary 8 gives the Gaussian model up to absolute constants once d≥log⁡(2n)d\ge\log(2n); here dd is 64–128 against log⁡(2n)≈7\log(2n)\approx7.
  • The n\sqrt n example (Remark 3) marks the boundary of the class, and the gain depends on the family: for hard retrieval every encoder on these grids has error at least 12max⁡i∥hi⋅∥2\tfrac12\max_i\Vert h_{i\cdot}\Vert_2 at midpoint inputs, RTN attains it, and SR is within a factor 2; Remark 3 and Appendix C.4 now say so. Real heads sit in the fluctuation-dominated regime nearer the averaging example, where correlated rounding could gain; we did not test it.
AuthorsOpenReview ↗

Response to Reviewer kUuF (4/4)

Q2 (query family in autoregressive generation). The family must be fixed before rounding; the queries need not be. Proposition 4(b) covers every sequence of queries in the family chosen adaptively, including queries that depend on earlier outputs. Two further facts are now in the paper.

  1. A family containing every future query follows from the weights: for a head with RMSNorm, query bias and rotary embeddings, ∥q∥2≤∥Wq∥op∥g∥∞D+∥bq∥2\Vert q\Vert_2\le\Vert W_q\Vert_{\mathrm{op}}\Vert g\Vert_\infty\sqrt D+\Vert b_q\Vert_2 for every input and position (Appendix I.4). It is valid but loose (W2).
  2. Growing caches (Section 5; Lemma 32 in Appendix H). If the cache is written in blocks I1,…,IGI_1,\dots,I_G, then softmax(Kq)=∑btb(q)softmax(KIbq)\mathrm{softmax}(Kq)=\sum_bt_b(q)\mathrm{softmax}(K_{I_b}q) with t(q)t(q) a probability vector, so the read error is at most the largest block error, and with fresh SR per block and token-wise spacings EFA≤Cmax⁡bB(Ab,hb)(1+log⁡G/d)\mathbb E F_{\mathcal A}\le C\max_b\mathcal B(\mathcal A_b,h_b)(1+\sqrt{\log G/d}). A block's schedule can therefore be computed when it is written; the bound is informative for blocks of many tokens (for one-token blocks it is weaker than the trivial bound, so generated tokens must be grouped first) and claims no joint optimality.

Not covered: the propagation of read errors through later layers and generated tokens (Section 7).

We hope the real-model checks of the error law, the scope statements and the protocol-fixed negative result answer the questions, and we would appreciate it if you would take them into account in your assessment.

Reviewer_L9kHOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper performs a theoretical analysis of the worst-case error of value quantization in the KV cache of attention. They show that under conditionally unbiased grid quantization, the error can be characterized by the geometry of attention patterns and the quantization grid spacing. The main result shows that increasing the number of value channels makes the quantization error increasingly Gaussian. Based on the worst-case analysis, they introduce the equal contribution schedule, a mixed-precision bit allocation scheme that allocates bits per token given a fixed total bit budget.

Critical strengths
  • Good theoretical novelty, I haven’t seen such a worst-case quantization error analysis for attention before and the derived bounds appear surprisingly tight.
  • The assumptions on the queries and keys are fairly weak, to my understanding they are not restricted to a specific distribution or assumed to be i.i.d.. This makes the results and findings more generally applicable than many other theoretical findings or bounds in the field.
Critical weaknesses
  • The assumption on the conditional unbiasedness of the quantization function in the analysis is fairly restrictive. In practice, stochastic rounding is fairly uncommon and often expensive on HW, which may be a limitation for translating the theoretical findings to particle gains.
  • The scope of the analysis is fairly narrow and focuses mainly on value quantization. Key perturbations are briefly considered, but the main findings do not extend to key quantization which is an equally important part of the KV cache.
  • They study and analysis is purely theoretical which is of course the nature of the contribution of this paper. For the equal contribution schedule (proposition 13), it would have been though interesting to see if that can help an e2e metric on a real LLM.
  • While there theoretical analysis is very interesting and a valuable contribution to understand quantization error, I do not (yet) see how this result can be used in the future to improve quantization algorithms for the KV cache (beyond the toy mixed precision allocation of proposition 13).
Questions for authors

How would rotations like used in TurboQuant influence the findings (i.e. eq 2)?

4 comments
AuthorsOpenReview ↗

Response to Reviewer L9kH (1/3)

Thank you for the review. The main change for it: the paper now covers deterministic round-to-nearest, with the exact worst-input error and a two-sided bound under the classical noise model, checked on two trained models; a rotation of the value channels acts on the invariant B\mathcal B of Eq. (2) only through the per-token ranges; and the end-to-end comparison you asked for is in Section 6, where per-token allocation lowers 2-bit perplexity and our equal-contribution schedule is the weakest of three adapted schedules (W3). Changes are in blue; main-text theorem and equation numbers are unchanged, while in the appendix the new Lemmas 24–26 shift later lemma numbers by 3.

Notation: FA(x)=sup⁡a∈A∥a⊤x∥2F_{\mathcal A}(x)=\sup_{a\in\mathcal A}\Vert a^\top x\Vert_2 is the worst-query read error of an error array x∈Rn×dx\in\mathbb R^{n\times d}, B(A,h)=EFA(h⊙ε)\mathcal B(\mathcal A,h)=\mathbb E F_{\mathcal A}(h\odot\varepsilon) with Rademacher signs ε\varepsilon, and hih_i is the spacing of token ii when its dd value channels share one grid.

W1 (conditional unbiasedness; stochastic rounding is uncommon and costly). Agreed: deployed caches round deterministically, so results that held only for stochastic rounding (SR) would limit practical use. Conditional unbiasedness enters through Theorem 2 and the lower bounds that use it (Theorem 12, Corollaries 10 and 14). For round-to-nearest (RTN), which is biased and outside Theorem 2, the paper now gives (paragraph "Beyond stochastic rounding" after Remark 3; Appendix C.4):

  • Worst input: exactly d2sup⁡a∈A∑iaihi\tfrac{\sqrt d}{2}\sup_{a\in\mathcal A}\sum_i a_ih_i (Lemma 24), half the amplitude bound of Section 4. On worst-case inputs RTN is governed by this amplitude, not by B\mathcal B: it can be worse than SR by order n\sqrt n (one uniform average), and it is never better by more than a factor 2 (approached, for example, for hard retrieval when log⁡n≫d\log n\gg d).
  • Typical inputs: under the additive-noise model (independent errors uniform on [−hi/2,hi/2][-h_i/2,h_i/2]; an assumption on the inputs), the expected read error lies between 14B\tfrac14\mathcal B and 12B\tfrac12\mathcal B (Lemma 25). Subtractive dither, a seeded pseudo-random offset per coordinate added before rounding and subtracted after reading, makes the model exact; it needs pseudo-random numbers at write and at read time, so it does not remove the cost you raise. On Qwen2.5-0.5B the measured RTN read error is a median 0.303 of B\mathcal B at 3 bits, inside the bracket in 0.984–0.997 of the cases over 2–4 bits.
  • Why RTN beats SR on real inputs (in every case at 3 and 4 bits): on these heads B\mathcal B is within 4% of the single-worst-query term d r\sqrt d\thinspace r, and a back-of-envelope estimate from that term, with a per-coordinate error standard deviation of h/12h/\sqrt{12} for RTN and h/6h/\sqrt6 for SR on inputs spread within cells, gives 0.289 and 0.408 of B\mathcal B; the measured medians at 3 bits are 0.303 and 0.416 (Appendix I.4). Theorem 2 ranks encoders on the worst input only.

We also re-ran every allocation schedule with RTN (W3).

AuthorsOpenReview ↗

Response to Reviewer L9kH (2/3)

Q1 (rotations as in TurboQuant, Eq. (2)). A rotated cache that stores Q(VΠ)\mathsf Q(V\Pi) and reads Q(VΠ)Π⊤\mathsf Q(V\Pi)\Pi^\top has read error FA(Q(VΠ)−VΠ)F_{\mathcal A}(\mathsf Q(V\Pi)-V\Pi), because ∥a⊤xΠ∥2=∥a⊤x∥2\Vert a^\top x\Pi\Vert_2=\Vert a^\top x\Vert_2 for orthogonal Π\Pi. So every result applies with spacings measured in the rotated basis, and the rotation enters Eq. (2) only through those spacings: at equal bits, min⁡iRi′/Ri≤B(A,h′)/B(A,h)≤max⁡iRi′/Ri\min_i R_i'/R_i\le\mathcal B(\mathcal A,h')/\mathcal B(\mathcal A,h)\le\max_i R_i'/R_i for per-token ranges RiR_i before and Ri′R_i' after (Lemma 26). It helps when it shrinks the per-token ranges, as when outlier channels inflate them, and it does not change the geometry of the attention family; when some ranges grow and others shrink, the effect depends on the data, which we have not measured. For keys, rotating the post-RoPE keys and queries jointly leaves every logit unchanged. TurboQuant's non-uniform codebooks and residual stage are outside the uniform-grid encoders of Definition 1.

W2 (keys). Correct: apart from Proposition 5(b), every result from Theorem 2 through Corollary 14 concerns value rounding with exact keys, and Section 1 and the Takeaway now say so. Proposition 5(b) holds deterministically for every realized pair (ΔK,ΔV)(\Delta K,\Delta V), so it covers deterministic and input-dependent key quantizers. Theorem 7 does not apply to keys directly: to first order a key perturbation moves the output by ∑iai(q)⟨Δki,q⟩(vi−o(q))\sum_i a_i(q)\langle\Delta k_i,q\rangle(v_i-o(q)), which is linear in ΔK\Delta K but indexed by arrays that couple weights, value deviations and the query, not by the product set {a⊗u}\lbrace a\otimes u\rbrace. For stochastically rounded keys and queries in a ball, Theorem 7 applied to an enclosing product set gives a first-order upper bound; the second-order remainder is not bounded. We have added a scope statement to Section 1, a sentence before Proposition 5, and this derivation at the end of Appendix D.

W3 (end-to-end metric). We ran it (Section 6, Table 1; Appendix I.4, Tables 9–11). At 2 bits the equal-contribution schedule lowers perplexity, as every adapted schedule does, but it is the weakest of the three adapted schedules in every column. Setting: Qwen2.5-0.5B on WikiText-2, values of a 512-token prefix cache quantized per token with keys exact, schedules computed from the first 128 continuation queries of an unquantized pass, perplexity of the following tokens (exact cache 11.77; SR averages 3 seeds).

Schedule2 bits, SR2 bits, RTN3 bits, SR3 bits, RTN
uniform19.3217.1712.5712.54
MSE-greedy13.0912.5812.3712.04
worst-attention13.2312.6712.4012.07
equal-contribution13.7613.1312.8112.29

At 2 bits every adapted schedule lowers perplexity on 15 of 16 chunks under both roundings. At 3 bits the squared-error and worst-case-attention schedules have post-hoc 95% intervals just below 1 under RTN, and the remaining differences, including ours above uniform with SR (12.81 against 12.57), are within chunk-to-chunk variation (Table 11). At the attention level, on its own calibration queries our greedy implementation (contributions re-estimated from 256 draws every 32 added bits) has the lowest worst-query error in 0.589 and 0.706 of the 384 head-chunk cases at 3 and 4 bits, but at 2 bits it does not reach the equal-contribution point even there (lowest in 0.060; a check added after the held-out run), so the 2-bit rows test that greedy rather than Proposition 13; at 3 and 4 bits, where it is best in-sample, the later-query loss is a transfer failure. On later queries at 3 bits it keeps none of its gain (median 1.023 of uniform), the other two keep part of it in the median (0.770, 0.731) with a heavy tail (each more than doubles the uniform error in 0.281 and 0.286 of the cases, ours in 0.357), and uniform precision is lowest in 0.411 of the cases. Three features of the protocol favour the adapted schedules: calibration from the start of the continuation, a 2-bit uniform baseline without a zero level, and uncharged bit-width metadata (Appendix I.4). Section 7 now says that a calibration set of earlier queries is not a family that covers later ones on this model; a covering family that is also tight is open, and the allocation results apply today where the queries of interest can be declared, such as known retrieval queries.

AuthorsOpenReview ↗

Response to Reviewer L9kH (3/3)

W4 (use for quantization algorithms). The paper does not propose a new quantizer. What it changes for design:

  • Value layout. With one grid per token, Corollary 8 makes the Gaussian error model accurate up to absolute constants once d≥log⁡(2n)d\ge\log(2n), so Gaussian error calculations apply to such value caches; channel-dependent spacings can break this.
  • A closed-form error model. On these heads B\mathcal B is within 4% of dmax⁡a∥a⊙h∥2\sqrt d\max_a\Vert a\odot h\Vert_2, so the read error of a spacing profile is a median 0.416 (SR) or 0.303 (RTN) times that quantity at 3 bits on Qwen2.5-0.5B (per head 0.376–0.494 and 0.248–0.464), computed from recorded attention weights and spacings without sampling. It predicts read error, not perplexity rankings.
  • Rotations act only through the per-token ranges (Q1).
  • Allocation against a declared family, with the certificate Eq. (21) as a lower bound on that family; Proposition 5(a) bounds the cost of using a calibration set for other queries, and on Qwen2.5 that cost is of the order of B\mathcal B itself (Appendix I.4, Table 8).

Presentation. The main text now has plain-language readings after Theorem 2, Theorem 7 and Corollary 8, and Appendix A states every main-text result in words; the decomposition figure (Figure 2 at submission) moved to Appendix E to make room.

We hope the RTN analysis, the rotation lemma and the real-model results, including the negative allocation result, make the reach and the limits of the contribution clear, and we would appreciate it if you would take them into account in your assessment.

I thank the authors for their detailed response and addressing my concerns. I appreciate the additional discussion related to RTN, while this doesn't fully resolve the limitation of SR (W1), though the change does put the paper better in context. Thanks for the additional e2e results, while on a small scale I think this is appropriate for a theoretical paper and mostly resolves W3. While W2 mainly remains and W4 partly, I want to keep my overall positive assessment of the paper.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response (1/2)

We thank the three reviewers. Where the paper stands after the revision (PDF uploaded; every change in blue):

  • The bounds hold on two trained models, in the regime where the fixed-query term dominates. On all key-value heads of Qwen2.5-0.5B and Qwen2.5-1.5B the tensor-law ratio of Theorem 7 lies in 0.800–0.957 and G/B\mathcal G/\mathcal B in 0.989–1.085 (Section 6; Appendix I.4, Table 8). At a 512-token cache B\mathcal B is within 4% of d r\sqrt d\thinspace r, so the worst-query error is the typical error of the single worst query; the selection term of Theorem 7 and the d≳log⁡nd\gtrsim\log n threshold are exercised only on the synthetic families of Section 6. The new estimate behind the structure theorem is Lemma 30 (Appendix E); the lemmas added in the revision (24–26, 32) are short consequences of Lemma 23 and Appendix C.3.
  • Consequences for practice, each under its condition. With one grid per token the Gaussian error model holds up to constants once d≥log⁡(2n)d\ge\log(2n); computed from recorded attention, B≈dmax⁡a∥a⊙h∥2\mathcal B\approx\sqrt d\max_a\Vert a\odot h\Vert_2, and the measured read error on that family is 0.376–0.494 of B\mathcal B for stochastic rounding and 0.248–0.464 for round-to-nearest (3 bits, Qwen2.5-0.5B); the worst-case error of round-to-nearest is known exactly (Lemma 24); rotations act only through the per-token ranges; and for a query set declared in advance, appended blocks can be allocated as they are written (Lemma 32), though a set that covers later queries and is still tight is open (item 3).
  • Narrowed. Theorem 12, Proposition 13 and Corollary 14 are optimality statements for a declared query family. On Qwen2.5 a family of earlier queries does not cover later ones; per-token allocation still lowers 2-bit perplexity, but our equal-contribution schedule is the weakest of three adapted schedules. Section 7 now says so.
  • Not covered. Keys beyond Proposition 5(b) and a first-order upper bound, and error propagation through later layers and generated tokens.

Main-text theorem and equation numbers are unchanged. The new Lemmas 24–26 shift later appendix lemmas by 3; the decomposition figure (Figure 2 at submission) is now Figure 4 in Appendix E, the numerics figure is Figure 2, the dependency graph is Figure 3, and appendix tables shift by one.

1. Real attention heads (Reviewer L9kH W3, Reviewer kUuF Q3, Reviewer uazK W2). The first 512 tokens of each 1024-token WikiText-2 chunk form the cache; the family of a key-value head is the set of attention vectors over the cache of the query heads that share it; spacings are per-token absmax; values are rounded and keys stay exact. Qwen2.5-0.5B: 48 key-value heads on 8 chunks (384 cases, d=64d=64); Qwen2.5-1.5B: 56 heads on 4 chunks (224 cases, d=128d=128).

Quantity, Qwen2.5-0.5BMedianMinMax
tensor law B/(d r+bd)\mathcal B/(\sqrt d\thinspace r+\mathfrak b_d) (Theorem 7)0.8860.8000.932
G/B\mathcal G/\mathcal B (Corollary 8)1.0050.9891.085
measured SR read error / B\mathcal B, 3 bits0.4160.3760.494
measured RTN read error / B\mathcal B, 3 bits0.3030.2480.464

When one query dominates, a back-of-envelope estimate (read error about d\sqrt d times that query's error norm, with a per-coordinate standard deviation of h/6h/\sqrt6 for stochastic rounding (SR) on inputs spread within cells and h/12h/\sqrt{12} for round-to-nearest (RTN)) gives 0.408 and 0.289 of B\mathcal B. The measured medians are 0.416 and 0.303 at 3 bits on Qwen2.5-0.5B; RTN sits higher at 2 bits (0.354) and on Qwen2.5-1.5B (0.336 at 3 bits). RTN has the lower read error in every case at 3 and 4 bits, consistent with the variance ratio; Theorem 2 ranks encoders on the worst input, and RTN, which is biased, lies outside its class.

Allocation. Schedules computed from queries at positions 512–767 were evaluated on positions 768–1023 (3 bits); perplexity is that of tokens 641–1023 of 16 chunks, with the prefix values quantized and schedules from positions 512–639 (exact cache 11.77; SR averages 3 seeds).

Schedulelater queries: median B\mathcal B / uniformlowest inppl 2 bits, SRppl 2 bits, RTNppl 3 bits, SRppl 3 bits, RTN
uniform10.41119.3217.1712.5712.54
MSE-greedy0.7700.22413.0912.5812.3712.04
worst-attention0.7310.26613.2312.6712.4012.07
equal-contribution1.0230.09913.7613.1312.8112.29
AuthorsOpenReview ↗

General Response (2/2)

On its own calibration queries every adapted schedule cuts the median worst-query error to 0.09–0.16 of uniform (Table 9, a check added after the held-out run); our greedy equal-contribution schedule is the best of the three there at 3 and 4 bits but not at 2 bits, where it does not reach the equal-contribution point. On later queries it keeps almost none of its gain (median 0.939–1.023 of uniform on Qwen2.5-0.5B, 0.850–0.905 on Qwen2.5-1.5B), and every adapted schedule has a heavy tail: each more than doubles the uniform error in 0.281–0.357 of the cases at 3 bits. End to end, every adapted schedule, ours included, lowers the 2-bit perplexity on 15 of 16 chunks under both roundings; at 3 bits the squared-error and worst-case-attention schedules have post-hoc 95% intervals just below 1 under RTN, and the other differences, including ours above uniform with SR (12.81 against 12.57), are within chunk-to-chunk variation (Table 11). The protocol favours the adapted schedules: calibration queries come from the start of the continuation, the 2-bit uniform baseline has no zero level, and bit-width metadata (about 0.05 bits per value) is not charged. The "In practice" paragraph of Section 7 is rewritten: the submission recommended a calibration set of recorded queries as the family, and the revision states that this works only when later queries stay close to it in the transport metric of Proposition 5(a).

2. Beyond stochastic rounding (Reviewer L9kH W1, Reviewer L9kH Q1, Reviewer kUuF W1, Reviewer kUuF Q1; Appendix C.4). Conditional unbiasedness is used for the optimality of SR (Theorem 2), the lower bound of Theorem 12, and the statements that inherit them (the D1\mathcal D_1 part of Corollary 10, the lower bound of Corollary 14); the allocation upper bounds are statements about SR. Otherwise, each under the condition stated: RTN has worst-input error exactly half the amplitude bound of Section 4 with token-wise spacings (Lemma 24), so up to a factor 2 the worst-case value of randomization is the gap between the amplitude and B\mathcal B that Theorem 7 computes; under the additive-noise model RTN's expected read error lies between 14B\tfrac14\mathcal B and 12B\tfrac12\mathcal B (Lemma 25; in 0.984–0.997 of the Qwen2.5-0.5B cases); with per-token absmax scales and SR given the scales the upper bounds hold input by input; a rotation of the value channels acts on B\mathcal B only through the per-token ranges (Lemma 26); and the gain of correlated rounding (Remark 3) is order n\sqrt n for one uniform average but at most a factor 2 for hard retrieval, where RTN is exactly minimax.

3. Query families during generation (Reviewer kUuF Q2, Reviewer kUuF W2, Reviewer uazK Q2). The family must be fixed before rounding, the queries need not be (Proposition 4(b)). For a cache written in blocks of many tokens, the worst-query error is at most the largest per-block worst-query error, so each block can be allocated when it is written (Section 5; Lemma 32 in Appendix H). A family that provably contains every future query follows from a weight-derived bound on the query norm, but the largest observed query norm is a median 0.121 of that bound (Appendix I.4). A family that is both valid and tight is open.

4. Scope and presentation (Reviewer L9kH W2, Reviewer uazK Q1, Reviewer uazK W1). Apart from Proposition 5(b), every result from Theorem 2 through Corollary 14 concerns value rounding with exact keys; Section 1 and the Takeaway now say so, and Appendix D derives the first-order key error. The main text gained plain-language readings after Theorem 2, Theorem 7 and Corollary 8, and Appendix A states every main-text result in words.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.