Provable Quantization with Randomized Hadamard Transform

Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov · 2026

Read Provable Quantization with Randomized Hadamard Transform by Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13810.txt.

Introduction

Ying Feng and four colleagues prove fair noised rounding with a single shuffled Hadamard transform, matching the mean squared error bounds of truly random spin grids. Their rounder feeds HD to the input vector then subtracts a random scalar offset before rounding, adding extra chance at tiny cost. A noised TurboQuant hits mean squared error (pi times square root of 3 over 2 plus o(1)) times 4 to the minus b at b bits per slot.

Catalog record

CREATORYing Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68704
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13810

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Provable Quantization with Randomized Hadamard Transform Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov Abstract Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require Θ ⁡ ( d 2 ) \Theta(d^{2}) time. The randomized Hadamard transform H ​ D HD reduces this cost to O ⁡ ( d ​ log ⁡ d ) O(d\log d) , but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies H ​ D HD to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error ( π ​ 3 / 2 + o ⁡ ( 1 ) ) ⋅ 4 − b \bigl(\pi\sqrt{3}/2+o(1)\bigr)\cdot 4^{-b} at b b bits per coordinate, where the o ⁡ ( 1 ) o(1) term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows. 1 Introduction Vector quantization is a fundamental technique for compressing real-valued vectors in \mathbb{R}^{d} into compact binary representations. Given a vector x\in\mathbb{R}^{d} , a quantizer VectorQuant maps x to a sequence of b\cdot d bits \textsc{VectorQuant}(x) . The bits can then be input to another procedure VectorDequant , obtaining the decoded vector \widetilde{x}=\textsc{VectorDequant}(\textsc{VectorQuant}(x)) . The size b\cdot d of the compressed representation controls the distortion \|x-\widetilde{x}\|^{2} , or the expected distortion E[\|x-\widetilde{x}\|^{2}] if the procedures are randomized. Alternatively, instead of decoding \widetilde{x} , some function of it (e.g., the distance to another vector y ) is estimated. This primitive plays an important role in many areas of machine learning, including similarity search 8 ; 18 ; 12 ; 15 ; 14 , federated learning 28 ; 29 ; 7 , efficient transformers 32 , and model compression 16 ; 5 ; 27 . A popular and well-studied approach to vector quantization is random projection followed by scalar quantization 8 ; 12 ; 13 ; 4 ; 28 ; 29 ; 15 ; 5 ; 27 ; 14 ; 32 . Here, one computes \textsc{VectorQuant}(x)=\mathsf{quant}(Rx) , where R is a random rotation matrix and \mathsf{quant} is a scalar quantizer (e.g., the sign function) applied coordinate-wise to the vector Rx . A key advantage of this approach is that it is data-oblivious : it requires no complex preprocessing tailored to the input distribution. Moreover, this method is amenable to theoretical analysis, since each coordinate of Rx is approximately normally distributed when R is a uniformly random rotation. However, applying a dense random rotation matrix R requires \Theta(d^{2}) time, which can be prohibitively expensive for high-dimensional vectors. To overcome this bottleneck, 2 ; 23 ; 30 ; 20 ; 17 and others proposed to replace random projections with randomized Hadamard transforms . Specifically, one replaces R with the structured matrix HD , where H\in\mathbb{R}^{d\times d} is the normalized Hadamard matrix and D is a diagonal matrix with independent Rademacher ( \pm 1 ) entries on the diagonal. The resulting transform can be applied in O(d\log d) time using the fast Walsh-Hadamard algorithm, yielding a substantial speedup over dense rotations. Thanks to its low complexity and efficient parallel implementation, randomized Hadamard transform is often the method of choice in industrial deployments, see, e.g., 10 ; 1 . Unfortunately, HD is no longer a uniformly random rotation; in fact, it is not even a continuous random variable. As a consequence, the coordinates of HDx have a more complex distribution than in the dense case, and theoretical guarantees for quantization become harder to establish. Existing results are typically either empirical 4 ; 25 ; 22 or provable but with higher dimension or number of bits compared to those achievable with truly random rotations 3 ; 20 ; 26 ; 21 ; 9 ; 7 . A natural remedy is to use more general structured matrices obtained by composing multiple randomized Hadamard transforms, possibly interleaved with other (e.g., sparse diagonal) matrices 11 ; 21 ; 33 ; 19 ; 34 . In particular, the last paper independently showed that the composition of just two randomized Hadamard transforms suffices to approximate 1 1 1 They show that, for each vector x and coordinate i , (HD_{1}HD_{2}x)_{i} approximates (Rx)_{i} in Kolmogorov distance up to an error of O(d^{-1/5}) . See Related Work for further discussion. uniform random rotation in high dimensions. However, those matrices are still more complex than a single randomized transform. Furthermore, the approximation error translates into an increased bound for the expected distortion after quantization. In this paper, we study a simple alternative to composing multiple randomized Hadamard transforms, namely dithering . Specifically, we consider quantizers where each coordinate of HDx is shifted by a random amount (controlled by a parameter U ) before applying the scalar quantizer \mathsf{quant} . Such quantizers are quite simple, as they require only one application of the randomized Hadamard transform, followed by a subtraction of a random vector. At the same time, the random offset injects additional randomness into the quantization process, which facilitates the analysis. 1.1 Our results We consider the following data-oblivious vector quantization problem. For an input vector x\in\mathbb{R}^{d} , a quantizer \textsc{VectorQuant}:\mathbb{R}^{d}\rightarrow\{0,1\}^{b\cdot d} outputs a binary string of bd bits, where b is the bit-width per coordinate. The dequantizer \textsc{VectorDequant}:\{0,1\}^{b\cdot d}\rightarrow\mathbb{R}^{d} maps this string back to a vector \widetilde{x}\in\mathbb{R}^{d} . We aim to design a pair of quantizer and dequantizer such that for any desired bit-width b minimize the following expected distortion measure for any (worst-case) vectors: \sup_{x\in\mathcal{S}^{d-1}}\mathbb{E}\|x-\widetilde{x}\|_{2}^{2}, where the expectation is over the internal randomness of the quantizer. The restriction to unit vectors is only for normalization: for nonzero inputs one can store the norm separately, quantize x/\|x\|_{2} , and rescale the decoded vector. In the following, we assume that d is padded to a power of 2 , thus there exists a d\times d Hadamard matrix. Our main result shows that randomized Hadamard mappings HD , after dithering, provides compression guarantees that asymptotically match those achievable with truly random rotation matrices R . Moreover, our quantizer is unbiased, which is a desirable property for numerous applications. In particular we show that our proposed algorithm has the following guarantees: Theorem 1.1 . For every dimension d and every unit vector x\in\mathcal{S}^{d-1} , Algorithm 5 satisfies \mathbb{E}_{D,U}[\widetilde{x}]=x and \mathbb{E}_{D,U}\|x-\widetilde{x}\|_{2}^{2}\leq\frac{\pi\sqrt{3}/2+o(1)}{4^{b}},\qquad b\to\infty, (1) where the o(1) term vanishes as b\to\infty , uniformly over d and x . The scaling constant in this theorem matches the bound obtained for TurboQuant in 32 that assumed fully random rotation matrices, up to the o(1) term. Furthermore, as noted in 6 , this also provides guarantees for a special case of the EDEN quantization method 28 , also using fully random rotation matrices. Thus, Theorem 1.1 can be viewed as justifying the use a single randomized Hadamard matrix

Read the complete text