Pairwise-Independent Dithering for Single-Stage Hadamard Quantization
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors discuss improving a method for compressing high-dimensional vectors used in tasks like similarity search and distributed learning. They build on previous work by Feng and colleagues, who created a two-step process involving randomized transforms to estimate inner products but with higher communication costs. The authors show that a single-step approach using pairwise-independent dithers on Hadamard coordinates works just as well, reducing communication needs and tightening the error bound. They also highlight that the proof of this improvement was initially generated by an automated system and later checked and clarified by the authors.
quantizationhigh-dimensional vectorssimilarity searchrandomized Hadamard transforminner-product estimatorditheringdistributed learningmodel compressionerror boundsautomated proof systems
Authors
Honghao Lin, Vahab Mirrokni, David P. Woodruff
Abstract
Quantizing high-dimensional vectors is fundamental to similarity search, distributed learning, and model compression. Feng, Indyk, Kapralov, Krachun, and Prokhorov established sharp guarantees for an unbiased dithered quantizer based on a randomized Hadamard transform [FIK+26]. Their $1/d$-scale inner-product estimator, however, uses a second randomized transform and residual quantization, increasing both communication and the leading constant in the proved bound. We show that this extra stage is unnecessary: pairwise-independent dithers across Hadamard coordinates suffice. The resulting unbiased single-stage estimator uses $b$ bits per coordinate and achieves \[ \mathbb{E}\!\left[ \left|\left\langle y,\widehat{x}-x\right\rangle\right|^2 \right] \leq \left(\frac{3π\sqrt{3}}{2}+o(1)\right) \frac{\lVert y\rVert_2^2}{d\,4^b}, \] as $b\to\infty$, with a dimension-free $o(1)$ term uniform over unit inputs and fixed queries. Compared with the two-stage construction of Feng et al., it eliminates the residual-stage $O(d)$-bit payload and reduces the leading upper-bound constant by a factor of approximately $5.93$. The proof was first obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors have verified the proof and edited it for clarity of presentation.