← 研踪 PaperTrailarXiv:2605.13810 · v2
DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform
首次提交 2026-05-14 01:38
版本更新 2026-11-07 08:31
雷达观测 2026-11-10 10:11
摘要
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 \log 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 $\bigl(π\sqrt{3}/2 + o(1)\bigr) \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.
作者备注：Accepted at NeurIPS 2026
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-07 08:31 · 最新观测版本
DASHQuant: Provable Quantization with a Single 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 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 \log 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 $\bigl(π\sqrt{3}/2 + o(1)\bigr) \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.
查看此版本解读 →查看此版本原文 ↗