Pairwise-Independent Dithering for Single-Stage Hadamard Quantization

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 [ mathbbE!left[ left|leftlangle y,widehatx-xrightrangleright|2 right] ≤ left(frac3π√32+o(1)right) fraclVert yrVert22d,4b, ] as b→∞, 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.