Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven
cs.LG, cs.AI, cs.DS, cs.NI
Submitted: 2026-05-07
Updated: 2026-11-02
Comments: Accepted at NeurIPS 2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression…
Terminology
Abstract
Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches used for gradient compression, inference acceleration, KV-cache compression, model weight quantization, and approximate nearest-neighbor search in vector databases. In practice, URRs are often replaced by randomized Hadamard transforms (RHTs), which preserve orthogonality while admitting fast implementations. The remaining issue is the performance for worst-case inputs. With a URR, each coordinate is distributed as a shifted beta distribution, which converges to a Gaussian distribution in high dimensions. Generally, one RHT is not suitable in the worst case, as individual coordinates can be far from these distributions. We show that after composing two RHTs on any d-sized input vector, the marginal distribution of every fixed coordinate of the normalized rotated vector is within O(d-1/2) of a standard Gaussian both in Kolmogorov distance and in 1-Wasserstein distance. We then plug these bounds into the analyses of modern compression schemes, namely DRIVE and QUIC-FL, and show that two RHTs achieve performance that asymptotically matches URRs. However, while two RHTs suffice for scalar quantization, they may be insufficient for Vector Quantization (VQ), which depends on the joint distribution across fixed-size blocks of coordinates (as opposed to only marginal distribution convergence for single coordinates). We prove that a composition of three RHTs leads to decaying coordinate covariance. This ensures that any fixed, bounded, multi-dimensional VQ codebook optimized for URRs has the same expected error when using three RHTs, up to an additive term that vanishes with the dimension. Finally, because practical inputs are rarely adversarial, we propose a linear-time O(d) check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.
Sources
- A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work
- Expanding the Reach of Federated Learning by Reducing Client Resource Requirements
- SpQR: A Sparse-Quantized Representation for Near-Lossless LLM Weight Compression
- DynamiQ: Accelerating Gradient Synchronization using Compressed Multi-hop All-reduce
- Federated Learning: Strategies for Improving Communication Efficiency
- Quartet II: Accurate LLM Pre-Training in NVFP4 by Improved Unbiased Gradient Estimation
- A multivariate central limit theorem for Lipschitz and smooth test functions
- New estimates of the convergence rate in the Lyapunov theorem
- RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithm
- TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
Related papers
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis
- (Mis)generalization of Helpful-Only Fine-tuning