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

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 $O(d\log d)$ time and $2d$ sign bits, recent work shows that each rotated coordinate is only $O(d^{-1/2})$-close to its dense-Haar law, which yields an $O(d^{-1/2})$ 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 $C{B}_b/d$ 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 $\Vert u{\Vert }_4^4$ rather than $\Vert u{\Vert }_3^3$, and uses that the first Hadamard stage makes $E\Vert u{\Vert }_4^4\le 3/d$ 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 $O(d^{-1/2})$ to $O(1/d)$, and the gap relative to the dense-rotation distortion is $O(B_b{4}^b/d)$. Structured rotations are free when $d\gg 4^b$; at $d\le 4^b$ we measure worst-case gaps of $4$–$41\%$. Exact computation on basis and sparse inputs gives $|\mathrm{gap}|\cdot d\le 0.96$ up to $d=16384$ and a relative gap of about $0.6\cdot 4^b/d$ at every $b\le 4$. Two-RHT with the Lloyd–Max codebook has $1.2$–$2\times$ lower worst-case distortion than a provable dithered single-stage quantizer at $b\le 4$ once $d\ge 256$, 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.