DASHQuant: Provable Quantization with a Single Randomized Hadamard Transform
cs.LG, cs.DS
Submitted: 2026-05-13
Updated: 2026-11-07
Comments: Accepted at NeurIPS 2026
License: http://creativecommons.org/licenses/by/4.0/
The gist: Vector quantization via random projection followed by scalar quantization is a fundamental primitive in machine learning…
Terminology
Abstract
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 Θ(d 2) time. The randomized Hadamard transform HD reduces this cost to O(d d), but its discrete structure complicates analysis and leads to weaker or purely empirical compression guarantees. In this work, we introduce DASHQuant (Dithered Accelerated Single-Hadamard Quantization), a provable variant of this approach. Specifically, the quantizer applies HD to the input vector and adds a random dithering 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, and a special case of EDEN, achieves mean squared error (π sqrt 3 /2 + o(1)) times 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.
Sources
- A Note on TurboQuant and the Earlier DRIVE/EDEN Line of Work
- Fast Cross-Polytope Locality-Sensitive Hashing
- Fastfood: Approximate Kernel Expansions in Loglinear Time
- TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
- Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- 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