Fast Vector Quantization with Provable Guarantees via Randomized Hadamard Transform

Paper: 2605.13810 Authors: Ying Feng, Piotr Indyk, Michael Kapralov, Dmitry Krachun, Boris Prokhorov Categories: cs.LG, cs.DS

The Gap

Vector quantization compresses high-dimensional vectors by projecting them randomly and then quantizing each coordinate. Dense random rotations (like Gaussian random matrices) give clean theoretical guarantees: unbiased reconstruction with predictable mean squared error. But they cost Θ(d²) time—prohibitive for modern applications where d can be thousands or millions.

The randomized Hadamard transform HD (a diagonal random sign matrix times a Hadamard matrix) drops this to O(d log d), making it practical. It’s widely used in similarity search, federated learning, and KV cache compression. But its discrete structure—it only permutes and flips signs, never truly “mixes” like a dense rotation—breaks the analysis techniques that work for Gaussian matrices. Existing guarantees for HD are either weaker (larger error bounds) or purely empirical.

The gap: Can we prove that HD-based quantization achieves the same asymptotic error rates as dense rotations, despite its discrete structure?

Problem: Need O(d log d) quantization with dense-rotation guarantees
   |
   v
Obstacle: HD's discrete structure resists standard analysis
   |
   v
Insight: Add scalar dithering (random offset before quantizing)
   |
   v
Method: HD + dither + scalar quantization
   |
   v
Evidence: Prove MSE matches dense rotations asymptotically
   |
   v
Conclusion: Fast quantization with provable optimal rates

The Increment

One sentence: Before this paper, fast O(d log d) quantization via randomized Hadamard transform lacked provable guarantees matching dense rotations; after, we know that adding scalar dithering closes the gap completely.

Core Mechanism

The method has three stages. First, apply the randomized Hadamard transform HD to the input vector x. This is a structured random rotation: multiply by a Hadamard matrix (which recursively splits and combines coordinates with ±1 weights), then flip each coordinate’s sign independently with probability 1/2. Second, subtract a random scalar offset u (drawn uniformly from [0, Δ] where Δ is the quantization bin width) from each coordinate. Third, round each coordinate to the nearest quantization level.

The key is the dithering step. Without it, HD’s discrete structure creates pathological cases: vectors aligned with HD’s structure get quantized poorly. The random offset u breaks this alignment. Since u is scalar (same value subtracted from all coordinates), it costs almost nothing—just d subtractions. But it injects enough randomness to “smooth out” the discrete artifacts of HD.

The analysis proves two things: (1) the quantizer is unbiased (expected reconstruction equals the input), and (2) the mean squared error decays as 4^(-b) where b is bits per coordinate, with a constant factor (π√3/2) that matches the best possible for any rotation-based quantizer. The o(1) term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.

Input vector x (d dimensions)
   |
   v
[HD transform: O(d log d)]
   |
   v
Rotated vector HDx
   |
   v
[Subtract scalar dither u from each coordinate]
   |
   v
Dithered vector HDx - u*1
   |
   v
[Scalar quantization: round each coordinate]
   |
   v
Quantized vector q
   |
   v
[Reconstruction: add back u, apply (HD)^-1]
   |
   v
Reconstructed x_hat

Think of it like shuffling a deck of cards. A dense random rotation is like a perfect riffle shuffle—every card can end up anywhere with equal probability. The Hadamard transform is like a deterministic shuffle that only swaps pairs and flips them—fast, but predictable. If you always shuffle the same deck the same way, certain patterns survive. The dithering is like cutting the deck at a random position before shuffling. It’s a tiny intervention (one random number), but it breaks the predictability. Now even though the shuffle itself is deterministic, the outcome looks random because you don’t know where the cut happened. The quantization error, which depends on how coordinates align with bin boundaries, gets “averaged out” by this randomness.

Key Concepts

• Randomized Hadamard Transform (HD): Start with the Hadamard matrix, which is defined recursively. For dimension 2, it’s [[1,1],[1,-1]]. For dimension 2^k, it’s the 2^(k-1) Hadamard matrix in each quadrant, with the bottom-right quadrant negated. Multiplying a vector by this matrix costs O(d log d) via the Fast Hadamard Transform (like FFT but simpler). Then multiply each coordinate by an independent random sign (±1 with equal probability). This gives a random orthogonal matrix that’s fast to apply but has discrete structure—it only permutes and flips signs, never creates “new” directions by mixing coordinates with arbitrary weights.

• Dithered Quantization: Standard scalar quantization rounds each coordinate to the nearest multiple of Δ (the bin width). This introduces error up to Δ/2 per coordinate. Dithering means subtracting a random offset u (uniform in [0,Δ]) before rounding, then adding it back after. This makes the quantizer unbiased: the expected reconstruction equals the input. Without dithering, quantization has systematic bias (e.g., small values always round to zero). The cost is one random number and d additions—negligible compared to the HD transform.

• Mean Squared Error (MSE) Bound: For b bits per coordinate, you have 2^b quantization levels. The paper proves MSE ≤ (π√3/2 + o(1)) · 4^(-b). The 4^(-b) term is fundamental: doubling bits quarters the error. The constant π√3/2 ≈ 2.72 matches the best achievable with any rotation-based quantizer (proven in prior work for dense rotations). The o(1) term vanishes as 2^b grows, uniformly over all unit vectors and all dimensions. This means HD + dithering is asymptotically optimal.

Framework Shift

Before (dense random rotation):        After (HD + dithering):

Input x                                 Input x
   |                                       |
   v                                       v
[Gaussian random matrix]                [Hadamard + random signs]
[Cost: O(d^2)]                          [Cost: O(d log d)]
   |                                       |
   v                                       v
Rotated vector                          Rotated vector
   |                                       |
   v                                       v
[Scalar quantization]                   [Subtract scalar dither u]
   |                                       |
   v                                       v
Quantized vector                        [Scalar quantization]
   |                                       |
   v                                       v
MSE ~ 4^-b (provable)                   [Add back dither u]
                                           |
                                           v
                                        Quantized vector
                                           |
                                           v
                                        MSE ~ 4^-b (provable)

From “pay O(d²) for provable guarantees” to “pay O(d log d) with one extra random number and get the same guarantees,” the core shift is recognizing that scalar dithering can compensate for structural randomness deficits.

Expert Assessment

Problem choice: Real gap. The Hadamard transform is already deployed in production systems (FAISS, federated learning frameworks) precisely because O(d²) is intolerable. But practitioners either accept weaker empirical performance or lack theoretical justification for their hyperparameters. Closing the theory-practice gap here has immediate impact.

Method maturity: Elegant insight, not brute force. Dithering is a classical technique in signal processing, but applying it to rescue a structured transform’s theoretical guarantees is non-obvious. The analysis is sophisticated—they extend concentration inequalities to handle the interplay between HD’s discrete structure and the dithering randomness. No simpler approach is being overlooked; prior work tried to analyze HD directly and failed to get tight bounds.

Experimental integrity: The paper is theory-focused, with experiments validating the asymptotic predictions. Baselines are fair (comparing to dense rotations and prior HD-based methods). One minor gap: they don’t test on real-world data distributions (e.g., embeddings from language models), only synthetic vectors. The uniform-over-unit-sphere analysis is clean but may miss structure in practice.

Writing quality: Section 3 (main theorem) is dense—too many lemmas front-loaded before the intuition. Rewriting it to lead with the proof sketch (why dithering helps, what goes wrong without it) would make the paper more accessible. The related work section undersells how much prior work tried and failed to analyze HD tightly.

Verdict: strong accept — Solves a real problem with a clean method and rigorous proof, directly impacting deployed systems.

Takeaways

Scalar dithering as a universal fix: When you have a fast but structured randomization (like HD, or sparse random projections, or any deterministic transform with random parameters), and you need unbiased estimates, try adding scalar dithering. It’s almost free (one random number, d additions) but can eliminate bias and tighten error bounds. This pattern transfers beyond quantization—anywhere you’re trading off speed for randomness quality.

Asymptotic analysis for hyperparameter selection: The o(1) term vanishing as 2^b grows tells you that for small b (say, 2-4 bits), the constant factor matters more than the asymptotic rate. But for b ≥ 6, you’re in the regime where HD + dithering matches dense rotations. Practitioners can use this to decide when the speedup is worth it.

Fast Hadamard Transform as a building block: If you’re implementing any rotation-based algorithm (Johnson-Lindenstrauss projection, random features, sketching), consider HD as a drop-in replacement for Gaussian matrices. This paper gives you the theoretical cover to do so without sacrificing guarantees, as long as you add dithering where needed.