Hadamard Transform: A Deep Dive into the Lightweight Deep Learning Technique That Replaces Multiplication with Addition and Subtraction

The Multiplication Bottleneck in Deep Learning

Matrix multiplication is virtually omnipresent in deep learning models. From convolutional neural networks to today's large language models (LLMs) with hundreds of billions of parameters, massive multiply-accumulate operations form the computational backbone of both inference and training. However, it is precisely these dense multiplication operations that represent the biggest obstacle to deploying models on mobile devices, edge devices, and other resource-constrained scenarios.

In modern deep learning architectures, matrix multiplication (GEMM, General Matrix Multiply) accounts for the vast majority of computation time. Take the Transformer architecture as an example: the Q, K, V projections in its self-attention mechanism and the feed-forward network layers are essentially large-scale matrix multiplications. A single inference pass on a 70-billion-parameter LLM may involve trillions of floating-point multiply-accumulate operations. From a hardware perspective, a 32-bit floating-point multiplier requires approximately 4-5 times more transistors than an adder of the same bit width, and the energy difference is even more significant—at a typical 45nm process node, the energy consumption of a single 32-bit floating-point multiplication is over 30 times that of a single addition.

Multiplication operations not only occupy more transistor area and consume more power at the hardware level, but their execution latency is also significantly higher than addition and subtraction. This naturally raises the question: Can we maintain the expressive power of deep learning models while minimizing or even completely eliminating multiplication?

A technique that recently sparked discussion on Reddit provides an inspiring answer—by leveraging the Hadamard Transform, a large portion of heavy matrix multiplications can be replaced with operations consisting solely of addition and subtraction, dramatically reducing computational cost.

Core Principles of the Hadamard Transform: Why It Eliminates Multiplication

The Special Structure of Hadamard Matrices

The Hadamard Transform is an orthogonal transform based on Hadamard matrices. The elements of a Hadamard matrix consist of only +1 and -1, which means that when a vector is multiplied by a Hadamard matrix, it essentially involves only addition and subtraction of elements, without requiring actual floating-point multiplication.

From a detailed mathematical perspective, the Hadamard Matrix is denoted as H_n, where n is the matrix order (typically a power of 2). It satisfies the orthogonality condition H_n · H_n^T = n · I_n, meaning the product of the matrix and its transpose equals n times the identity matrix. The simplest 2nd-order Hadamard matrix is [[1,1],[1,-1]], and higher-order matrices are recursively generated using Sylvester's construction: H_{2n} = [[H_n, H_n],[H_n, -H_n]]. Orthogonality means the Hadamard transform is invertible—the transformation does not lose information, which is crucial for maintaining the expressive power of neural networks. Moreover, since its elements are only ±1, it can be implemented in digital circuits using simple XOR gates and adders, completely bypassing multipliers.

Even better, the Hadamard Transform has a fast algorithm analogous to the Fast Fourier Transform (FFT)—the Fast Walsh-Hadamard Transform (FWHT)—which reduces the original O(n²) complexity to O(n log n). The core idea of FWHT is similar to FFT, leveraging the recursive structure of Hadamard matrices to decompose the computation into multiple layers of butterfly operations. For a vector of length n, direct multiplication by a Hadamard matrix requires O(n²) additions and subtractions, while FWHT decomposes it into log₂(n) layers, each performing n/2 additions and n/2 subtractions, for a total computation of O(n·log n). For example, processing a 1024-dimensional vector requires approximately 1 million operations with the direct method, while FWHT requires only about 10,240—nearly 100x speedup. This decomposition is also naturally parallelism-friendly, making it highly suitable for SIMD instruction sets and hardware pipeline implementations.

Hadamard Transform vs. Traditional Matrix Multiplication

In traditional fully connected layers or attention layers, weight matrices contain large numbers of arbitrary real values, and every forward pass requires millions of multiply-accumulate operations. If some linear transformations are approximated or replaced with Hadamard structures, these operations degenerate into sign flips and accumulations, which are extremely hardware-friendly.

For low-power chips, DSPs, and even dedicated ASICs, eliminating multipliers means smaller chip area, lower energy consumption, and faster response times.

Practical Applications of the Hadamard Transform

Inference Acceleration on Mobile and Edge Devices

This method shows particularly outstanding acceleration potential on mobile and edge devices. Scenarios such as smartphones, wearable devices, and IoT terminals are extremely sensitive to power consumption and latency, unable to bear the burden of massive multiplication operations. By introducing the Hadamard Transform to replace some dense computations, inference efficiency can be improved with almost no additional hardware cost, enabling more complex AI models to truly run on-device.

Critical Role in Ultra-Low-Bit Quantization of Large Models

Even more noteworthy is the role of the Hadamard Transform in ultra-low-bit quantization of LLMs. To enable large models to run within limited GPU memory, the industry has been continuously exploring compressing weights to 4-bit, 2-bit, or even lower.

However, extreme quantization often leads to accuracy collapse due to outliers. In LLM quantization, outliers refer to extreme values in activation tensors or weights that far exceed the normal range. Research has found that in Transformer models, activations in certain specific channels can be more than 100 times larger than those in other channels. When using uniform quantization to map floating-point numbers to low-bit integers, these outliers "monopolize" most of the quantization range, causing values in the normal range to be compressed into very few quantization levels, producing enormous quantization errors. For example, if a channel's value range is [-1, 100] and 4-bit quantization has only 16 levels, then the large number of normal values in the [-1, 1] range can only be assigned to 1-2 quantization levels, resulting in severe information loss.

The Hadamard Transform plays a clever role here: it can perform a rotation on activations and weights, "dispersing" and smoothing outliers in the distribution, making the post-quantization distribution more uniform, thereby significantly reducing quantization error. The mathematical intuition is that the Hadamard Transform, as an orthogonal transform, essentially rotates vectors in high-dimensional space. When outliers exist in activations, it means energy is concentrated in a few dimensions. The Hadamard rotation redistributes each dimension's values across all dimensions—specifically, each output element after transformation is an equally-weighted sum/difference of all input elements. Following the intuition of the Central Limit Theorem, this mixing operation causes the transformed distribution to trend toward uniformity and symmetry, with outlier energy being "diluted" across all dimensions. Since orthogonal transforms preserve vector norms, no information is lost, but the distribution becomes more suitable for uniform quantization.

Cutting-edge quantization methods such as QuaRot and SpinQuant leverage precisely this idea of Hadamard rotation to achieve high-quality low-bit LLM inference. Specifically, QuaRot (Quantization with Rotation) uses a fixed Hadamard matrix as the rotation matrix, applicable without additional training. It exploits a key observation: inserting an orthogonal matrix R between consecutive linear layers in a Transformer, since W₂·R·R^T·W₁ = W₂·W₁ (the inverse of an orthogonal matrix equals its transpose), the rotation can be "absorbed" into adjacent weight matrices without changing model output. SpinQuant goes further by searching for optimal rotations in the orthogonal matrix space through Cayley optimization, using a small amount of calibration data to fine-tune the rotation matrix for better quantization results than fixed Hadamard matrices. The two represent different engineering trade-offs between "zero-cost fixed rotation" and "lightweight optimized rotation."

Technical Trade-offs and Engineering Considerations

Trade-offs in Model Expressiveness

Replacing freely learnable weights with fixed-structure Hadamard matrices eliminates multiplication but also sacrifices some model flexibility. Hadamard matrices are fixed orthogonal structures that cannot arbitrarily fit data like ordinary weights. Therefore, in practice, the Hadamard Transform often needs to be combined with a small number of learnable parameters (such as scaling factors and diagonal matrices) to achieve a balance between efficiency and accuracy.

Hardware Adaptation and Engineering Challenges

Although addition and subtraction are theoretically cheaper than multiplication, truly leveraging this advantage requires cooperation from underlying hardware and operator libraries. The multiply-accumulate units (MACs) in general-purpose GPUs are already highly optimized, and simply replacing algorithms may not immediately yield multi-fold speedups on existing hardware.

Modern GPUs (such as NVIDIA's A100 and H100) integrate large numbers of Tensor Cores—specialized compute units deeply optimized for matrix multiply-accumulate operations that can complete multiple multiply-accumulate operations in a single clock cycle. On these hardware platforms, the throughput difference between multiplication and addition has been greatly narrowed by hardware design. Furthermore, GPU memory bandwidth is often the bigger bottleneck—even if computation becomes faster, overall performance improvement is limited if data transfer speed cannot keep up. Therefore, the speedup from the Hadamard Transform on general-purpose GPUs is often below theoretical expectations, with its real advantages more reflected in reducing data precision (combined with quantization) to decrease memory bandwidth requirements, and on lightweight chips that lack dedicated multipliers.

The true dividends often appear in dedicated accelerators, edge chips, and memory-bandwidth-constrained quantized inference scenarios.

Conclusion: The Hadamard Transform Provides a Pragmatic Path for AI Lightweighting

"Multiplication-free deep learning" may sound like a bold slogan, but the underlying Hadamard Transform concept actually represents a pragmatic and effective path in AI lightweighting research. It can be used for on-device inference acceleration and has already shown promise in ultra-low-bit quantization of large models.

As large model scales continue to expand and deployment costs rise accordingly, how to do more with less compute will remain a core long-term challenge. Techniques like the Hadamard Transform that "replace multiplication with addition and subtraction" may not completely replace traditional matrix multiplication, but they provide a toolbox worth deep exploration for efficient AI design. For engineers focused on model compression, edge deployment, and quantized inference, understanding and mastering such transformation techniques is becoming increasingly important.