# Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Placed in KV cache quantization, one of 12 directions in Efficient LLM inference and serving.
- Builds on 27 of its 41 references that are in the map.
- First posted on arXiv 7 May 2026.

## Placed in

- Efficient LLM inference and serving / [KV cache quantization](https://mlsanity.com/inference/kv-cache-quantization/)

## Builds on (most cited first, 27 of 27)

- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [QuaRot: Outlier-Free 4-Bit Inference in Rotated LLMs](https://mlsanity.com/paper/2404.00456/) (2024)
- [QuIP#: Even Better LLM Quantization with Hadamard Incoherence and Lattice Codebooks](https://mlsanity.com/paper/2402.04396/) (2024)
- [SpQR: A Sparse-Quantized Representation for Near-Lossless LLM Weight Compression](https://mlsanity.com/paper/2306.03078/) (2023)
- [Expanding the Reach of Federated Learning by Reducing Client Resource Requirements](https://mlsanity.com/paper/1812.07210/) (2018)
- [Distributed Mean Estimation with Limited Communication](https://mlsanity.com/paper/1611.00429/) (2016)
- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [OWQ: Outlier-Aware Weight Quantization for Efficient Fine-Tuning and Inference of Large Language Models](https://mlsanity.com/paper/2306.02272/) (2023)
- [QTIP: Quantization with Trellises and Incoherence Processing](https://mlsanity.com/paper/2406.11235/) (2024)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [DoCoFL: Downlink Compression for Cross-Device Federated Learning](https://mlsanity.com/paper/2302.00543/) (2023)
- [Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2409.09913/) (2024)
- [Pushing the Limits of Large Language Model Quantization via the Linearity Theorem](https://mlsanity.com/paper/2411.17525/) (2024)
- [Quartet II: Accurate LLM Pre-Training in NVFP4 by Improved Unbiased Gradient Estimation](https://mlsanity.com/paper/2601.22813/) (2026)
- [THC: Accelerating Distributed Deep Learning Using Tensor Homomorphic Compression](https://mlsanity.com/paper/2302.08545/) (2023)
- [Optimal Quantization for Matrix Multiplication](https://mlsanity.com/paper/2410.13780/) (2024)
- [How to send a real number using a single bit (and some shared randomness)](https://mlsanity.com/paper/2010.02331/) (2020)
- [HACK: Homomorphic Acceleration via Compression of the Key-Value Cache for Disaggregated LLM Inference](https://mlsanity.com/paper/2502.03589/) (2025)
- [ScionFL: Efficient and Robust Secure Quantized Aggregation](https://mlsanity.com/paper/2210.07376/) (2022)
- [OptiReduce: Resilient and Tail-Optimal AllReduce for Distributed Deep Learning in the Cloud](https://mlsanity.com/paper/2310.06993/) (2023)
- [A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work](https://mlsanity.com/paper/2604.18555/) (2026)
- [Beyond Throughput and Compression Ratios: Towards High End-to-end Utility of Gradient Compression](https://mlsanity.com/paper/2407.01378/) (2024)
- [RaanA: A Fast, Flexible, and Data-Efficient Post-Training Quantization Algorithm](https://mlsanity.com/paper/2504.03717/) (2025)
- [Stein's method of normal approximation: Some recollections and reflections](https://mlsanity.com/paper/2104.08302/) (2021)
- [DynamiQ: Accelerating Gradient Synchronization using Compressed Multi-hop All-reduce](https://mlsanity.com/paper/2602.08923/) (2026)

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

- [Entropy-Constrained Adaptive Stochastic Quantization](https://mlsanity.com/paper/2608.18147/) (2026)
- [KV-COBRA: KV Cache Compression via Co-Optimized Bit-Rank Allocation](https://mlsanity.com/paper/2609.24298/) (2026)
- [Transforms for LLM Quantization: The Great Inversion and Format Co-Design](https://mlsanity.com/paper/2608.25188/) (2026)
- [TORQUE: Optimizing What (not) to Quantize Before and After Rotation](https://mlsanity.com/paper/2609.36032/) (2026)
- [Few Bits, One Law: Toward W2A4KV2](https://mlsanity.com/paper/2610.09202/) (2026)
- [Fast Quantized Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2610.16289/) (2026)

## Abstract (arXiv)

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 individually 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, we show that two RHTs may not be sufficient for Vector Quantization (VQ), which often requires weak correlation 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.