The Hadamard Transform Bug That Quietly Made Our Inverse Worse Than Returning Zeros
This title could be clearer and more informative.Try out Clickbait Shieldfor free (5 uses left this month).
A debugging story from the VeloxQuant-MLX project explains a subtle math bug in Hadamard transform-based preconditioning for KV-cache quantization. The team assumed any Hadamard matrix accepted by MLX's hadamard_transform was self-inverse (applying it twice returns the original), which holds for symmetric Walsh-Hadamard constructions but not for Paley-constructed matrices used at factors m=20 and m=28. Because those matrices are orthogonal but not symmetric, the true inverse requires the transpose, not a repeated forward pass. The error silently propagated through dimensions like 40, 56, 80, 112, 160, and 224 - including real model configurations such as Phi-2 (head_dim=80), Qwen3-4B, and Qwen2.5-7B - producing a relative reconstruction error of about 1.7, worse than simply returning zeros (error of 1.0). No crash, NaN, or exception ever signaled the problem. The fix removed m=20 and m=28 from the fast Hadamard path, falling back to a more expensive but correct QR rotation, and added a round-trip regression test asserting the actual mathematical contract (self-inverse under double application) rather than just kernel execution.
Questions this post answers
Is every orthogonal Hadamard matrix its own inverse?
No. An orthogonal matrix always satisfies H^T H equals the identity, but it only equals its own inverse when it is also symmetric, so that H^T equals H. Walsh-Hadamard matrices built from powers of two are symmetric and self-inverse, but Paley-construction Hadamard matrices, built from quadratic residues over finite fields, can be orthogonal without being symmetric, meaning the true inverse requires the transpose rather than reapplying the same transform. Developers building quantization kernels can revisit these invertibility edge cases through related breakdowns on daily.dev.
Why did applying hadamard_transform twice fail to reconstruct the original tensor for certain dimensions in MLX?
Because MLX's hadamard_transform supports dimensions built from base factors including 20 and 28, which correspond to Paley-constructed Hadamard matrices that are orthogonal but not symmetric. Code that assumed reapplying the same transform recovers the original (valid only for symmetric cases like m=1 and m=12) silently produced wrong results for m=20, m=28, and any dimension multiple of them, such as 40, 56, 80, 112, 160, and 224, with a measured relative reconstruction error around 1.7. Teams relying on MLX's fast transforms for quantization pipelines can track such edge-case pitfalls via daily.dev.
How bad was the reconstruction error from the incorrect Hadamard inverse assumption, compared to just returning zeros?
The incorrect inverse produced a relative reconstruction error of roughly 1.7, which is worse than the error of 1.0 obtained by simply returning an all-zeros tensor instead of attempting reconstruction. This occurred for dimensions derived from Paley-constructed Hadamard matrices such as 20 and 28 and their multiples, including realistic transformer widths like head_dim=80 used in Phi-2. Anyone validating numerical correctness in ML kernels can compare similar failure cases on daily.dev.
Share this post