# Provable Quantization with Randomized Hadamard Transform

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

## Key facts

- Cited by 8 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 18 of its 34 references that are in the map.
- First posted on arXiv 13 May 2026.

## Placed in

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

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

- [A Survey of Quantization Methods for Efficient Neural Network Inference](https://mlsanity.com/paper/2103.13630/) (2021)
- [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)
- [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)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [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)
- [Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2409.09913/) (2024)
- [Optimal Quantization for Matrix Multiplication](https://mlsanity.com/paper/2410.13780/) (2024)
- [HadaCore: Tensor Core Accelerated Hadamard Transform Kernel](https://mlsanity.com/paper/2412.08832/) (2024)
- [Uniform Approximations for Randomized Hadamard Transforms with Applications](https://mlsanity.com/paper/2203.01599/) (2022)
- [A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work](https://mlsanity.com/paper/2604.18555/) (2026)
- [Faster Binary Embeddings for Preserving Euclidean Distances](https://mlsanity.com/paper/2010.00712/) (2020)
- [Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions](https://mlsanity.com/paper/2604.23418/) (2026)
- [Fast Cross-Polytope Locality-Sensitive Hashing](https://mlsanity.com/paper/1602.06922/) (2016)

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

- [Contraction-Gauge Preconditioning for Quantized Matrix Multiplication](https://mlsanity.com/paper/2607.18745/) (2026)
- [Stellar Colosseum: A Many-Agent Harness for Long-Horizon Research in Mathematics and Theoretical Computer Science](https://mlsanity.com/paper/2609.15983/) (2026)
- [Fast-TurboQuant: A Multiplier-Free Online Vector Quantization Approach](https://mlsanity.com/paper/2606.21448/) (2026)
- [VQ-bench: A Composable Vector Quantization Framework](https://mlsanity.com/paper/2608.11240/) (2026)
- [Transforms for LLM Quantization: The Great Inversion and Format Co-Design](https://mlsanity.com/paper/2608.25188/) (2026)
- [Exact Minimax One-Bit Unbiased Compression: Heavy-Tail Necessity and Finite-Randomness Approximation](https://mlsanity.com/paper/2609.27860/) (2026)
- [TORQUE: Optimizing What (not) to Quantize Before and After Rotation](https://mlsanity.com/paper/2609.36032/) (2026)
- [Fast Quantized Johnson-Lindenstrauss Transforms](https://mlsanity.com/paper/2610.16289/) (2026)

## Abstract (arXiv)

Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning, with applications ranging from similarity search to federated learning and KV cache compression. While dense random rotations yield clean theoretical guarantees, they require Theta(d2) time. The randomized Hadamard transform HD reduces this cost to O(d log d), but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we study a variant of this approach: dithered quantization with a single randomized Hadamard transform. Specifically, the quantizer applies HD to the input vector and subtracts a random scalar offset before quantizing, injecting additional randomness at negligible cost. We prove that this approach is unbiased and provides mean squared error bounds that asymptotically match those achievable with truly random rotation matrices. In particular, we prove that a dithered version of TurboQuant achieves mean squared error bigl(π√3/2 + o(1)bigr) · 4-b at b bits per coordinate, where the o(1) term vanishes uniformly over all unit vectors and all dimensions as the number of quantization levels grows.