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~\cite{feng2026provable}. 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} |\langle y,\widehat{x}-x\rangle|^{2}
\leq
\left(\frac{3\pi\sqrt{3}}{2}+o(1)\right)
\frac{\|y\|_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, it saves approximately $3.72d$ bits
per encoded vector and reduces the leading upper-bound constant by a factor of
approximately $5.93$.