Provable Quantization with Randomized Hadamard Transform

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 compression. While dense random rotations yield clean theoretical guarantees, they require $\Theta (d^2)$ time. The randomized Hadamard transform $HD$ reduces this cost to $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 $HD$ to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. This approach is used by popular quantizers such as RaBitQ, and is a slight modification of others, including TurboQuant and EDEN. We prove that this approach provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. For example, we prove a dithered version of TurboQuant achieves mean squared error $(\pi \sqrt{3}/2+o(1))\cdot 4^{-b}$ at $b$ bits per coordinate, where the $o(1)$ term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.