acceptodds
Under review as a conference paper at ICLR 2027

Pairwise-Independent Dithering for Single-Stage Hadamard Quantization

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. Their -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 bits per coordinate and achieves as , with a dimension-free term uniform over unit inputs and fixed queries. Compared with the two-stage construction of Feng et al., it eliminates the residual-stage -bit payload and reduces the leading upper-bound constant by a factor of approximately .

Primary area:
foundation or frontier models, including LLMs
Keywords:
Randomized Hadamard Transform, Quantization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_cnSAOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper modifies a recent quantization algorithm by Feng et al, which aims at B-bit quantizing and reconstruction of a vector x. The algorithm by Feng et al. relies on multiplying x by a diagonal Radamacher matrix, followed by normalized Hadamard matrix, and flooring a dithered and compressed version of each entry. The novelty of the current paper with respect to Feng et al. is the choice of the dither, where a pairwise independent noises U_i replace a scalar noise. The authors show unbiasedness and smaller variance w.r.t Feng et al.

Critical strengths

A simple and clear improvement of an existing quantization algorithm.

Critical weaknesses
  1. I’m afraid that the authors did not do a good job in translating and simplifying this AI-generated proof. The paper is extremely jargon heavy, and would probably not mean much to readers that did not read Feng et al. very recently. Some examples:

a. I didn’t see the point of Section 1.3 (“Technical overview”). I did not mean much to me in first pass (e.g., \Phi undefined, Q_U undefined) , and all details are explained later, so second read is not helpful either. I believe it can be removed.

b. The role, definition, and intuition behind G_B in Section 2.2 are missing.

c. The term “q” in Proposition 3.2 apparently refers to something in Algorithm 1, without it being noted anywhere in that proof or in that section.

d. I could not decipher why (3.5) is true. More detailed transitions would have helped.

  1. There are no experiments to validate the performance in practice, and code is not provided for reproducibility.
Questions for authors

A few suggestions that the authors might consider in order to improve the paper’s score:

  1. Implement their algorithm in code and upload to a public Github repository.

  2. Provide a better and more self-contained introduction to Feng at al.

  3. Demonstrate improved practical performance over state-of-the-art quantizers, in particular that of Feng et al.

  4. Improve writing and notations, several suggestions are given above.

Additional space could be saved by removing Section 1.3, and avoiding unnecessary display equation (an annoying tendency of AI generated proofs), e.g., (1.1), (1.2), among others.

3 comments

We thank the reviewer for the detailed comments on presentation, and we have revised the paper accordingly.

Writing. We revised the writing to explain each object in plain terms before it is used. In particular, we rewrote the technical overview in Section 1.3 (see the general response). It now explains, in order, what we use from Feng et al., why a single stage with a shared dither fails (with the exact example x=y=e1x=y=e_1), and why pairwise-independent dithers fix it.

Section 2.2 now explains the role of GBG_B: mapping the cell midpoint back through the nonlinear F−1F^{-1} would be biased, and GBG_B corrects this bias so that averaging over the dither gives exactly tt. Appendix A recalls its construction from Feng et al. (their Lemma A.8).

The vector qq in Proposition 3.2 is now defined in the proof: q=(q1,…,qd)q=(q_1,\dots,q_d) is the vector of decoded scalars in Algorithm 1, so that qi=QUi(zi)q_i=\mathsf{Q}_{U_i}(z_i) and x^=DH⊤q/d\hat{x}=DH^\top q/\sqrt{d}.

We also expanded the derivation of Equation (3.5) in the proof of Proposition 3.3. Since D2=ID^2=I and H⊤H=IH^\top H=I, we have x=DH⊤z/dx=DH^\top z/\sqrt{d}, so x^−x=DH⊤e/d\hat{x}-x=DH^\top e/\sqrt{d} with e=q−ze=q-z. Since DD is symmetric, ⟨y,DH⊤v⟩=⟨HDy,v⟩\langle y,DH^\top v\rangle=\langle HDy,v\rangle, and (HDy)i=∥y∥2wi/d(HDy)_i=\|y\|_2w_i/\sqrt{d} by the definition of wiw_i. Together these give ⟨y,x^−x⟩=1d∑i(HDy)iei=∥y∥2d∑iwiei\langle y,\hat{x}-x\rangle=\frac{1}{\sqrt{d}}\sum_i(HDy)_ie_i=\frac{\|y\|_2}{d}\sum_i w_ie_i, which is Equation (3.5).

Experiments. We added experiments in Section 6 and Appendix B, following the setup of the recent arXiv version of Feng et al. (summarized in the general response). For example, at a fixed total number of bits per coordinate, our inner-product error is 24 to 43 times smaller than that of the two-stage quantizer of Feng et al. on random query–data pairs. The experiments also include a synthetic example where a shared dither fails. For x=y=e1x=y=e_1, the normalized error of our quantizer with one shared dither grows linearly in dd and reaches about 10410^4 at d=4096d=4096, while that of our quantizer with pairwise-independent dithers stays between 11 and 55. We will release the code with the final version.

I thank the authors for considering my comments and suggestion. I ask the authors to make their code publicly available to the research community via an openly available online repository. Conditioned on that\textbf{Conditioned on that}, I am raising my score to “weak accept.”

Thank you for your kind response. We have uploaded our code as supplementary material on OpenReview, where it is publicly available. Since the supplementary material stays attached to the paper, we think it is a convenient place for the community to access the code.

Reviewer_zivCOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper addresses quantisation of high-dimensional vectors, where prior work has introduced a dithered quantisation method based on the Hadamard transform. The current work improves that process by simplifying the algorithm and achieving better accuracy.

Critical strengths
  • A quantiser that achieves better accuracy with a simpler algorithm is a win-win.
  • Detailed proofs validate theoretical performance.
Critical weaknesses
  • The paper is hard to approach for researchers outside this specific field.
  • While I do understand the algorithm, it is not clear why and what, in the construction of the current method is better than the prior art.
  • It would have been nice to demonstrate the results with a few practical examples.

Minor issues:

  • The choice of the indexing letter "i" in Lemma 3.1 is unfortunate, as in Eq. (3.1) it is left unclear whether it is an index or the imaginary unit.
Questions for authors

None

2 comments

We thank the reviewer for the review and the suggestions on accessibility.

1.Presentation. We rewrote the technical overview (Section 1.3) and revised the later sections for readability. The overview now proceeds in three steps around an explicit example (see the general response). Section 2.2 gives intuition for the reconstruction map GBG_B, whose construction is recalled in Appendix A. Section 3 defines all notation used in the analysis and expands the derivation of the key identity (Equation (3.5)).

  1. Comparison with prior work. The revised technical overview (Section 1.3) explains where the improvement comes from. The main change to the construction of Feng et al. is the dither: each coordinate gets its own dither Ui=(V0+i⋅V1) mod 1U_i=(V_0+i\cdot V_1)\bmod 1 instead of one dither shared by all coordinates. With a shared dither, the quantization errors of different coordinates are correlated, and for some inputs (for example x=y=e1x=y=e_1) the inner-product error does not decrease with dd. This is why Feng et al. need a second stage that quantizes the residual. With pairwise-independent dithers, the errors of different coordinates are uncorrelated, so the 1/d1/d gain holds with a single stage. This change still leaves a technical difficulty. With a single stage, the query weights wiw_i and the input coordinates ziz_i are built from the same random signs, so the scalar bound of Feng et al. does not apply directly. Our main technical estimate (Lemma 4.2) shows that this correlation costs at most a factor of 33.

The table below compares the resulting guarantees for estimating ⟨y,x⟩\langle y,x\rangle for a fixed query yy and a unit input xx.

MethodTransformBits per coordinateUnbiasedProved bound on E⟨y,x^−x⟩2\mathbb{E}\langle y,\hat{x}-x\rangle^2
Feng et al., single stage (for vector MSE, not inner products)1 Hadamardbbyes (their App. A.3)O(∥y∥22/4b)O(\Vert y\Vert_2^2/4^b), no 1/d1/d gain
Feng et al., two-stage2 Hadamardup to b+3.72b+3.72, variable lengthyes(48.37+o(1)) ∥y∥22/(d4b)(48.37+o(1))\,\Vert y\Vert_2^2/(d4^b)
TurboQuant-proddense rotation, Θ(d2)\Theta(d^2) timebbyes17.1 ∥y∥22/(d4b)17.1\,\Vert y\Vert_2^2/(d4^b)
Ours1 Hadamardexactly bbyes(8.16+o(1)) ∥y∥22/(d4b)(\mathbf{8.16}+o(1))\,\Vert y\Vert_2^2/(d4^b)
Lower bound, any quantizer–bb–1⋅∥y∥22/(d4b)1\cdot\Vert y\Vert_2^2/(d4^b)
  1. Experiments. We added experiments on real embedding data (Section 6 and Appendix B), following the setup of Feng et al. At a fixed total number of bits per coordinate, our inner-product error is 24 to 43 times smaller than that of the two-stage quantizer of Feng et al. on random query–data pairs. The experiments also include an example where a shared dither fails. For x=y=e1x=y=e_1, the normalized error of our quantizer with one shared dither grows linearly in dd and reaches about 10410^4 at d=4096d=4096, while that of our quantizer with pairwise-independent dithers stays between 11 and 55.

  2. Notation. Thank you for pointing this out. We now write Ui=(V0+i⋅V1) mod 1U_i=(V_0+i\cdot V_1)\bmod 1 and state that ii is the integer coordinate index (Section 1.2, Equation (3.1), and Algorithm 1).

Reviewer_zivCOpenReview ↗

All my concerns have been adressed

All my critical concerns have now been addressed.

Reviewer_pnpxOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This work is motivated by recent results on the problem of data-oblivious vector quantization. In particular, the model is as follows. The quantizer consists of an encoding function ENC and a decoding function DEC. ENC maps a vector x∈Rd→{0,1}bdx \in \mathbb{R}^d \to \lbrace 0, 1\rbrace ^{bd} for some bit budget bb. DEC attempts to reconstruct xx from ENC(xx) so as to minimize some objective function. The encoder and decoder may share randomness. Apart from optimizing the objective, a natural goal of the quantizer is to minimize the runtime of the encoder and decoder.

Previous work has established the usefulness of random rotations as a pre-processing step. That is, by applying a random rotation to the input vector xx, the encoder and decoder can then be designed for a Gaussian-looking input vector (in some sense, converting a worst-case instance to an average case instance). However, such a pre-processing step requires dense matrix vector multiplication which results in Θ(d2)\Theta(d^2) runtime. The work of Feng et al. sidesteps this by showing that similar error bounds can be achieved via randomized Hadamard transforms. When the objective function is MSE, the work of Feng et al. establishes that randomized Hadamard transforms can achieve the same error as the best random protocol comprising of an orthogonal transformation + scalar quantizer (even matching the constants). However, when the objective function is MSE over inner products with a worst case vector yy, their work loses a large constant factor in the error bound.

The algorithm of Feng et al. used a second randomized Hadamard transform to ensure that the residual vector looked isotropic. A priori, the residual vector is fixed once the randomness in diagonal matrix DD and dither UU are drawn. The errors in the residual vector could be correlated and result in no dependence on 1/d1/d in the final inner product MSE bound. Using a second randomized Hadamard transform requires additional shared randomness between the encoder and decoder, and the analysis in Feng et al. turns out to give additional constant factors in the inner product MSE bound.

This work observes that both problems can be alleviated by introducing pairwise independent dithers for each coordinate. The algorithmic framework and machinery is largely the same as that of the preceding work (Feng et al.). Intuitively, the core idea of pairwise independent dithers makes the residual vector isotropic, giving rise to the 1/d1/d dependence in the error bound without the need for an extra randomized transformation.

Critical strengths
  1. The core theoretical contribution is sound and elegant. The writing quality and mathematical clarity are both high.
  2. The paper studies a topic of wide importance and presents a valuable theoretical contribution to our understanding of data-oblivious unbiased quantization.
Critical weaknesses
  1. The scope of the paper is limited to improving the constant in the error bound of inner product MSE data-oblivious quantization. The techniques are largely the same as the preceding work (Feng et al.), with a small (yet consequential) observation that achieves the tighter bound.
  2. The second half of the technical overview was largely opaque to me. In general, the writing of the introduction and preliminaries assumes much prior knowledge about previous work. I had to read parts of Feng et al. to gain a better understanding of this work. I recommend putting more effort into making the paper more self-contained.
  3. Although previous papers in this line of work did not demonstrate empirical results, the algorithms seem simple enough to implement and test on real-world data. Even just one such experiment comparing the performance against prior work would be interesting to see. I see this as a minor weakness
  4. The only point of comparison provided is the bound achieved by preceding work. Are there known lower bounds on achievable inner product MSE for data-oblivious quantization? What if we restrict to unbiased quantization schemes and/or quantization schemes that take the form of an orthogonal transformation followed by a scalar quantizer?
Questions for authors

Clarification questions: See (4) in weaknesses.

Suggestions for future work: It might be interesting to consider the setting where both vectors xx and yy must be quantized with independent bit budgets. Perhaps the algorithms optimizing the inner product MSE in this setting may look very different. Applications of this setting include ANN index construction.

2 comments

We thank the reviewer for the detailed and constructive comments, which we address below.

  1. Constant-factor improvement and lower bound. The order ∥y∥22/(d4b)\|y\|_2^2/(d4^b) is optimal: by the lower bound of Zandieh et al. (2026), every quantizer with bb bits per coordinate has error at least 1/(d4b)1/(d4^b) on some pair of unit vectors (now stated in Section 1.2). The remaining room is thus in the constant and the algorithm, and we improve both: a single randomized Hadamard transform with exactly bb bits per coordinate, no second stage, and a proved constant of 8.168.16 instead of 48.3748.37. Removing the second stage also requires a new and sharp estimate (Lemma 4.2), since the query weights and the input coordinates then share the same random signs.

  2. Technical overview. We rewrote Section 1.3 in the revised version (see the general response). It now (i) uses the exact example x=y=e1x=y=e_1 to show why a dither shared by all coordinates gives no 1/d1/d gain, which is why Feng et al. need a second stage, (ii) shows in a few lines why pairwise-independent dithers remove every cross term, and (iii) explains why the weighted estimate of Lemma 4.2 is needed and sketches its proof.

  3. Experiments. We have added Section 6 and Appendix B for experiments in our revised version (summarized in the general response). In particular, at a fixed total number of bits per coordinate, our inner-product error is 24 to 43 times smaller than that of the two-stage quantizer of Feng et al. on random query–data pairs.

Thank you to the authors for addressing my main concerns. After reviewing the changes, I believe weaknesses 2, 3, 4 in my original review have been adequately addressed. I maintain my score of 3 for the paper only because the technical contribution is limited to the observation that pairwise independent dithers suffice to remove the second stage in Feng et al.'s algorithm. I believe the result is still a solid contribution to our theoretical understanding of the problem.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Changes and Rebuttal

We thank all reviewers for their careful reading and constructive feedback. We have uploaded a revised PDF. Revised and new text is in blue. The main changes are as follows.

  1. Rewritten technical overview (Section 1.3). The overview now follows three steps. (i) The quantizer of Feng et al. We give an overview of their quantizer and list the two properties of its scalar quantizer that we need: it is unbiased, and its variance is at most (π/2+o(1))B−2et2/3(\pi/2+o(1))B^{-2}e^{t^2/3} for ∣t∣≤5log⁡B|t|\le\sqrt{5\log B}. (ii) From two stages to one. We write the inner-product error as a weighted sum of coordinate errors and show, with the exact example x=y=e1x=y=e_1, that a dither shared by all coordinates gives no 1/d1/d gain. This is why Feng et al. need a second stage. (iii) Pairwise-independent dithers. Pairwise independence removes every cross term, so a single stage suffices. The remaining step is our weighted estimate E[Y2eX2/3]≤33\mathbb{E}[Y^2e^{X^2/3}]\le 3\sqrt{3} for Rademacher sums that share their signs.

  2. Experiments (new Section 6 and Appendix B). We noticed that the recent arXiv version of Feng et al. (v2) added experiments, and we follow their setup: GloVe-200 and the DBpedia OpenAI3 embeddings with d=1536d=1536 and d=3072d=3072, with 100,000 database vectors and 1,000 queries each. We compare with the two-stage quantizer of Feng et al., TurboQuant-MSE, TurboQuant-prod, and an ablation of our quantizer with one shared dither. For the reconstruction error E∥x^−x∥22\mathbb{E}\|\hat{x}-x\|_2^2 of a single vector, our quantizer has the same guarantee as that of Feng et al. (Corollary 5.1), so we focus on inner products.

  • The two-stage quantizer spends 2.1 to 2.3 extra bits per coordinate on its residual. At a fixed total number of bits, our inner-product error is 24 to 43 times smaller on random query–data pairs, 18 to 27 times smaller on pairs of a query and its nearest neighbor, and 10 to 16 times smaller for y=xy=x.

  • On random and nearest-neighbor pairs, our quantizer is more accurate than TurboQuant-prod, the unbiased variant of TurboQuant, at every bit budget, with one Hadamard transform instead of a dense rotation. The biased TurboQuant-MSE has a smaller reconstruction error, but its bias makes it unreliable on correlated pairs (normalized error 905 for y=xy=x at b=2b=2 on DBpedia-3072, compared with 9.3 for ours).

  • Pairwise independence matters on structured inputs. For x=y=e1x=y=e_1, the normalized error of the shared-dither ablation grows linearly in dd and reaches about 10410^4 at d=4096d=4096, while ours stays between 1 and 5.

  • The constant in Theorem 1.1 is nearly attained. For y=xy=x and b≥4b\ge 4, the normalized error d4b E⟨y,x^−x⟩2d4^b\,\mathbb{E}\langle y,\hat{x}-x\rangle^2 of our quantizer lies between 7.3 and 8.0, compared with 3π3/2≈8.163\pi\sqrt{3}/2\approx 8.16.

  1. Clarity. We added intuition for the reconstruction map GBG_B (Section 2.2) and recall its construction from Feng et al. in Appendix A for self-containedness. We clarified the notation raised by the reviewers (Ui=(V0+i⋅V1) mod 1U_i=(V_0+i\cdot V_1)\bmod 1 with ii the integer coordinate index, and the vector qq in Proposition 3.2), expanded the derivation of Equation (3.5).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.