# Pairwise-Independent Dithering for Single-Stage Hadamard Quantization

arXiv: https://arxiv.org/abs/2608.02564 · HTML: https://mlsanity.com/paper/2608.02564/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2026.

## Built on by (most cited first, 1 of 1)

- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)

## Abstract (arXiv)

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.