Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven

2026-05-07 · Source: Takara TLDR - Daily AI Papers · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Mathematics & Computational Sciences · Depth: Expert, medium

Summary

This research proves the efficacy of randomized Hadamard transforms (RHTs) as a fast, orthogonal alternative to uniform random rotations (URRs) in quantization schemes. While URRs ensure individual coordinates converge to a Gaussian distribution in high dimensions, a single RHT does not. The study demonstrates that composing two RHTs on a $d$-sized input vector ensures the marginal distribution of each coordinate is within $O(d^{-1/2})$ of a standard Gaussian, both in Kolmogorov and $1$-Wasserstein distances. This two-RHT composition asymptotically matches URRs in modern compression schemes like DRIVE and QUIC-FL. For Vector Quantization (VQ), which requires weak correlation across coordinate blocks, three RHTs are shown to lead to decaying coordinate covariance, ensuring similar expected error to URRs. The authors also propose an $O(d)$ runtime check to dynamically adjust the number of RHTs based on input moments.

Key takeaway

For AI Engineers optimizing model quantization, this work provides a robust, provable alternative to computationally intensive uniform random rotations. If you are implementing gradient compression or inference acceleration, using two randomized Hadamard transforms can achieve comparable performance with faster execution. For Vector Quantization, three RHTs are necessary to ensure error consistency. Consider integrating the proposed $O(d)$ runtime check to dynamically adapt RHT usage, balancing performance and computational cost for diverse inputs.

Key insights

Composing multiple randomized Hadamard transforms effectively approximates uniform random rotations for quantization.

Principles

• Two RHTs suffice for marginal Gaussian convergence.
• Three RHTs ensure decaying coordinate covariance for VQ.

Method

The proposed method involves composing two or three randomized Hadamard transforms (RHTs) to achieve statistical properties similar to uniform random rotations (URRs) for various quantization tasks, with an optional $O(d)$ runtime check to adapt the number of RHTs.

In practice

• Use two RHTs for gradient compression.
• Employ three RHTs for Vector Quantization.
• Implement dynamic RHT count based on input moments.

Topics

• Randomized Hadamard Transforms
• Uniform Random Rotations
• Quantization
• Vector Quantization
• Gradient Compression

Code references

• vantaa89/qwha

Best for: AI Engineer, NLP Engineer, Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Quantization robustness from dense representations of sparse functions in high-capacity kernel associative memory — KLR-trained Hopfield networks achieve quantization robustness via a "sparse function, dense representation" principle.
• Efficient Test-Time Finetuning of LLMs via Convex Reconstruction and Gradient Caching — HullFT uses convex reconstruction and gradient caching to make test-time finetuning of LLMs faster and more efficient.
• Non-asymptotic quantisation of spherically symmetric distributions — This paper addresses the challenge of optimal quantisation in high dimensions ($d$), where Zador's theorem requires an astronomically large sample size ($n$) for its asymptotic behavior to be observed.
• HARP: Hadamard-Preconditioned Adaptive Rotation Processor for Extreme LLM Quantization — HARP adaptively rotates LLM weights for extreme low-bit quantization, improving accuracy and inference speed over fixed methods.
• KVarN: Variance-Normalized KV-Cache Quantization [R] — KVarN efficiently quantizes KV-caches using Hadamard rotations and variance-normalization, achieving high compression with minimal accuracy loss.
• Shift-and-Sum Quantization for Visual Autoregressive Models — A novel post-training quantization framework significantly reduces reconstruction errors and aligns sampling frequencies for visual autoregressive models.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Takara TLDR - Daily AI Papers.