DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform

arXiv:2605.13810 · cs.LG, cs.DS · Submitted 2026-05-13 · Read on arXiv

cs.LG, cs.DS

Submitted: 2026-05-13

Updated: 2026-11-07

Comments: Accepted at NeurIPS 2026

License: http://creativecommons.org/licenses/by/4.0/

The gist: Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning…

Terminology

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) time. The randomized Hadamard transform HD reduces this cost to O(d d), but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we introduce DASHQuant (Dithered Accelerated Single-Hadamard Quantization), a provable variant of this approach. Specifically, the quantizer applies HD to the input vector and adds a random dithering 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, and a special case of EDEN, achieves mean squared error (π sqrt 3 /2 + o(1)) times 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.

Sources

Related papers