The Hadamard Transform underpins many SoTA LLM quantization algorithms such as @Google's TurboQuant, QuIP#, QuaRot, SpinQuant, and NestQuant. LLM quantization works best when a vector’s coordinates have similar magnitudes. If most of a vector’s mass sits in one coordinate, e.g. x = (0,0,0,1,0,0,0,0,0,0), then the quantizer faces a bad tradeoff: use a wide range and waste resolution, or use a tighter range and “clip” the outlier, which may result in significant accuracy loss of the LLM. This is the basic motivation behind random orthogonal rotations: Multiplying x by a Gaussian rotation matrix R spreads x’s mass uniformly over coordinates, while preserving inner-products: ‖Rx‖₂ = ‖x‖₂, ⟨Rw, Rx⟩ = ⟨w, x⟩. The problem with random rotation, of course, is computational cost: a dense d × d rotation costs O(d²) per vector, so cubic time for W*X. In 2006, a beautiful and influential paper by Ailon and Chazelle, proposed a faster “pseudo-random” rotation op via the randomized Hadamard transform H′ = (1/√d)HD, where H is a Hadamard matrix and D is a diagonal random sign matrix. It turns out that H’ has essentially the same effect as a fully random rotation, in the sense that it “evenly spreads the mass” of any unit vector. This is essentially the uncertainty principle of the Fourier transform (!) The upshot is that H’x and H’w can now be computed in O(d log d) time instead of O(d²), due to the recursive (FFT) structure of H. In this blog, @prlnet's 17-year old researcher @sag0li explains how how we used Agentic toos to efficiently implement a block-Hadamard kernel in CuteDSL, which allows for very fine-grained control over memory and cache management -- this is the path to ultra-fast inference!