acceptodds
Under review as a conference paper at ICLR 2027

Beyond Berry–Esseen: Loss-Aware Distortion Transfer for Randomized Hadamard Quantization

Abstract

Random rotations make scalar quantization near-optimal, and fast structured rotations are used in practice in their place. For the two-stage randomized Hadamard transform (two-RHT), which costs time and sign bits, recent work shows that each rotated coordinate is only -close to its dense-Haar law, which yields an bound on the extra distortion. We prove that the distortion itself converges much faster. For every bit-width, every symmetric nearest-centroid codebook, and every unit input, the squared-error gap between two-RHT and dense Haar is at most with an explicit constant, and this rate is attained at one bit. The proof reduces the loss to a few absolute-value kinks, shows by a zero-bias coupling that Rademacher sums match the Gaussian on every kink up to rather than , and uses that the first Hadamard stage makes for every input. The same argument explains when one stage suffices, and we prove that one undithered stage leaves a non-vanishing gap on sparse inputs. As corollaries, the known two-RHT guarantee for DRIVE sharpens from to , and the gap relative to the dense-rotation distortion is . Structured rotations are free when ; at we measure worst-case gaps of –. Exact computation on basis and sparse inputs gives up to and a relative gap of about at every . Two-RHT with the Lloyd–Max codebook has – lower worst-case distortion than a provable dithered single-stage quantizer at once , mostly because of the codebook. In million-scale retrieval two-RHT matches the dense rotation within seed noise; in LLM KV caches it tracks the dense rotation, but per-channel key statistics matter more than the rotation.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Machine Learning, Vector Quantization, Randomized Algorithms, Structured Random Transforms, High-Dimensional Geometry, Efficient Inference, Neural Network Compression, Approximate Nearest-Neighbor Search, Large Language Models

Reviews

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

The paper concerns random rotations which are used in quantization of neural networks. The theory of TurboQuant assumes that the random rotation is a dense matrix chosen according to a Haar measure, but practical implementations need to have a fast way to multiply with the random rotation matrix, so they use Hadamard-structured random matrices. Previous works have addressed this theoretical gap by bounding the distance (e.g. Wasserstein) of probability laws arising from the Hadamard-structured versus the dense random matrices. This paper instead directly bounds the resulting quantization distortion, giving an "improved" error bound for the distortion that can not be deduced from the previous results about distances of probability laws.

Critical strengths

New error bound. The paper provides a new error bound on a distortion measure, which can not be deduced from the previous bounds that focused on distance of probability laws (and not on the final distortion).

Critical weaknesses

Readability. The theory is compressed to two pages of dense theorems that are nontrivial to parse. The paper doesn't provide intuition or discussion of the results. The language in the paper also reads "claudish", and indeed the AI use statement suggests that the paper was written mainly by AI. (e.g. "yardstick", "What is not new.", "What matters more than the rotation.", "The harness is sound, and Qwen’s keys are the problem.") Specialized notation/terms are not explained (e.g. vNMSE, SIFT, etc). The formatting also breaks in places, for example many expectations are rendered lower, e.g. at the start of line 197 or in corollary 1.

Especially in times where the mathematical results themselves are discovered/proved by AI, the value comes from clearly communicating and explaining the results and putting them in context, and the paper fails at that.

Questions for authors
  • What is the purpose and context of the experiments? You label "two-RHT" as "yours", but as you say in the paper, this has been studied in previous papers, no? I generally don't understand the relation between the theory and the experiments: The theory seems to provide a new error bound for an existing method, while the experiments seem to compare different methods (?). Shouldn't the experiments focus on demonstrating that the error bound holds in practice and how it can potentially inform certain choices (e.g. of hyperparameters) in the method?
Reviewer_anEbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies scalar quantization with two‑stage randomized Hadamard transforms (two‑RHT). While prior work establishes that coordinate‑wise distributions converge to Gaussian at rate O(d−1/2)O(d^{-1/2}), it shows quantization MSE distortion converges faster at O(1/d)O(1/d). A kink lemma is derived showing quantization loss operates on absolute‑value kinks, where Rademacher sums approximate Gaussians via ∥u∥44\|u\|_4^4 instead of third‑order moments. Further analysis of single‑ and two‑stage transforms proves undithered one‑RHT produces non‑vanishing distortion gaps for sparse inputs. Empirical results on retrieval and LLM KV‑cache quantization verify the theory: two‑RHT closely matches dense‑Haar rotation when d≫4bd \gg 4^b.

Critical strengths

The paper theoretically distinguishes coordinate‑distribution convergence from quantization‑distortion convergence. With the kink lemma, it obtains a tighter O(1/d)O(1/d) distortion bound improving the prior O(d−1/2)O(d^{-1/2}) result. It analyzes one‑/two‑stage RHT, proves inherent distortion flaws of one‑stage for sparse inputs and explains the mitigation mechanism of two‑stage transforms. It combines noise‑free exact gap computation with retrieval and KV‑cache benchmarks, clarifying the practical operating regime against the dense rotation baseline.

Critical weaknesses
  1. Loose theoretical constant: The derived upper‑bound constant is much larger than empirical gaps, so the bound serves mainly for qualitative analysis instead of quantitative prediction.
  2. No high‑probability guarantee: Distortion bounds hold only in expectation over random signs. High‑probability bounds for a single fixed random matrix realization are absent for practical deployment.
  3. Limited applicable scope: Satisfactory performance is valid chiefly under d≫4bd\gg4^b. Errors become notable for small dimensions or large bit‑widths, and learned rotations are not investigated.
Questions for authors

This work analyzes quantization from the perspective of preserving vector geometric structure, which does not directly capture the influence of quantization on downstream classification tasks. The recent work [1] directly investigates the effect of quantization on feature discriminability, offering a complementary perspective from a classification standpoint. This should be noted in the related work.

[1] "Lu, Weizhi, Mingrui Chen, and Weiyu Li. "Binary and Ternary Quantization Can Enhance Feature Discrimination." arXiv preprint arXiv:2504.13792 (2025)."

Reviewer_3VdUOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper is a theoretical paper on the use of random rotations in quantization. More precisely, this paper considers the following problem: what guarantees can one have on the resulting quantization error of a given input when using a) two-random Hadamard transforms vs. b) a dense random rotation? The overall context is the following: it is known that random dense rotations result in a lower quantization error compared to random Hadamard transforms. However, random Hadamard transforms are cheaper to compute, which is why they often trump dense rotations in practice. This paper establishes a stronger bound / a more rapid rate of convergence on the quantization errors produced by two random Hadamard transforms against one dense random rotation. The paper then proceeds to validate empirically the theoretical findings.

Critical strengths
  1. The mathematical result is strong.
  2. The techniques used to obtain the final result cleverly leverage some specific aspects of quantization, as opposed to more general probability theory arguments. This is how the authors manage to improve upon the previously known rate of convergence.
  3. The result holds in general cases.
Critical weaknesses

Unfortunately, the paper is very difficult to read and to parse. Even the abstract is very dense and is hard to read. I believe this paper is substantially AI generated based on the following elements. First, the overall register of extremely compressed language and jargon. Second, some phrases or way of constructing sentences, which are very typical from Claude models. And third, the paper overall lacks the usual hand-holding and shepherding that usually appear in theoretical papers. There is unfortunately very limited explanations of the result itself, the proof techniques used to achieve the result, the conclusion of the result, etc.

Questions for authors

See weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.