# Role of the Walsh-Hadamard Transform in Needle 2's MLP: Architecture and Implementation

> Discover how the Walsh-Hadamard transform in Needle 2's MLP dramatically cuts parameters from O(n²) to O(n) using fixed orthogonal matrices and fast butterfly computations for efficient deep learning.

- Repository: [Cactus Compute, Inc./needle](https://github.com/cactus-compute/needle)
- Tags: internals
- Published: 2026-08-30

---

**The Walsh-Hadamard transform in Needle 2's MLP replaces dense weight matrices with a fixed orthogonal mixing matrix, reducing learnable parameters from O(n²) to O(n) while maintaining expressive power through fast O(n log n) butterfly computations.**

The cactus-compute/needle repository implements Needle 2, an efficient large language model that replaces conventional feed-forward layers with a structured **Walsh-Hadamard transform in Needle 2's MLP** architecture. This design, encapsulated in the `HadamardMLP` class, leverages fixed orthogonal matrices and learnable diagonal scaling to achieve hardware-friendly computation. By combining the fast Hadamard algorithm with butterfly-style operations, this approach significantly cuts memory bandwidth and parameter counts without sacrificing model capacity.

## What Is the Walsh-Hadamard Transform in Needle 2?

The **Walsh-Hadamard transform** is a linear operation defined by a recursive orthogonal matrix that mixes all input dimensions simultaneously. In Needle 2, this transform is implemented as a fixed-weight matrix generated by the `_walsh_matrix` function in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py) (lines 80-85), which produces a normalized Hadamard matrix used for structured dimension mixing.

Unlike dense linear layers that learn an O(n²) weight matrix, the Hadamard matrix is fixed and orthogonal. This property allows the transform to decorrelate inputs efficiently while remaining invertible and numerically stable.

## Three Core Functions of the HadamardMLP Layer

The `HadamardMLP` class in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py) (lines 287-303) serves three critical architectural purposes:

### Parameter-Efficient Dimension Mixing

The **Hadamard matrix** acts as a fixed, orthogonal mixing operator that interacts all input dimensions in a single operation. Instead of storing a dense O(n²) weight matrix, the layer sandwiches the transform between **learnable diagonal matrices** (`d1`, `d2`, `d3`). This structure yields dense interaction patterns while only requiring O(n) learnable parameters, dramatically reducing memory footprint for large-scale models.

### Fast O(n log n) Computation via Butterfly Operations

The recursive definition of the Walsh-Hadamard matrix enables the **fast Hadamard algorithm**, which computes the transform using a butterfly-style decomposition similar to the FFT. This reduces computational complexity from O(n²) to **O(n log n)**, minimizing memory bandwidth pressure and accelerating inference. The implementation leverages this recursive structure in `_walsh_matrix` to ensure efficient hardware utilization.

### Learnable Diagonal Scaling and Non-Linearity

The MLP applies a structured sequence of operations that mimic a traditional two-layer feed-forward network:

```python
z = (d1 * x_padded) @ H                # scale → Hadamard

z = nn.silu(d2 * z) @ H                # non-linear → Hadamard

out = (d3 * z)[..., :d_model]          # final scaling & truncate

```

Here, **H** represents the normalized Walsh-Hadamard matrix. The diagonal parameters (`d1`, `d2`, `d3`) function as per-dimension gain controls before and after each transform, while the **SiLU activation** injects non-linearity between the two Hadamard passes. This pattern replicates the expressive capacity of a conventional `Linear → Activation → Linear` stack with far fewer parameters.

## Implementation in needle/model/architecture.py

The core logic resides in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py), where the `HadamardMLP` class orchestrates the transform and diagonal scaling. You can instantiate and run the module as follows:

```python
import jax
import jax.numpy as jnp
from needle.model.architecture import HadamardMLP

# Dummy input: (batch, seq_len, d_model)

batch, seq_len, d_model = 2, 16, 128
x = jnp.ones((batch, seq_len, d_model), dtype=jnp.bfloat16)

# Initialise the module

mlp = HadamardMLP(d_model=d_model, dtype=jnp.bfloat16)

# Initialise random parameters (Flax/linen style)

key = jax.random.PRNGKey(0)
params = mlp.init(key, x)

# Forward pass

out = mlp.apply(params, x)
print(out.shape)          # → (2, 16, 128)

```

Running this snippet demonstrates that `HadamardMLP` accepts the same tensor shapes as standard feed-forward layers, but internally executes the Walsh-Hadamard mixing described above.

## Integration with the Transformer Stack

The Walsh-Hadamard MLP integrates into the full transformer pipeline through two additional key files:

- **[`needle/model/run.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/run.py)** – Executes the complete transformer stack, inserting `HadamardMLP` immediately after the attention block to process sequence representations.
- **[`needle/model/export.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/export.py)** – Handles model serialization and quantization pipelines, ensuring the Hadamard-based weights are correctly exported for efficient deployment.

Together, these components ensure the **Walsh-Hadamard transform in Needle 2's MLP** functions as a drop-in replacement for dense feed-forward layers while preserving compatibility with standard transformer inference workflows.

## Summary

- **Parameter efficiency**: The Walsh-Hadamard transform enables O(n) parameter scaling using fixed orthogonal matrices and learnable diagonal vectors (`d1`, `d2`, `d3`).
- **Computational speed**: Butterfly-style O(n log n) operations reduce memory bandwidth compared to O(n²) dense matrix multiplications.
- **Architectural compatibility**: The `HadamardMLP` class in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py) maintains the same input/output contract as conventional MLP layers.
- **Quantization friendly**: Fixed Hadamard matrices avoid gradient updates, simplifying quantization schemes handled in [`needle/model/export.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/export.py).

## Frequently Asked Questions

### How does the Walsh-Hadamard transform reduce parameters in Needle 2's MLP?

Instead of learning a dense O(n²) weight matrix, the `HadamardMLP` uses a fixed orthogonal Hadamard matrix and only learns three diagonal vectors (`d1`, `d2`, `d3`). This structure requires only O(n) learnable parameters while still achieving dense mixing of all input dimensions through the orthogonal transform.

### What is the computational complexity of the HadamardMLP layer?

The layer operates in **O(n log n)** time complexity due to the fast Hadamard algorithm, which uses a butterfly computation pattern similar to the FFT. This compares favorably to the O(n²) complexity of standard dense feed-forward layers, significantly reducing compute cost for large hidden dimensions.

### Where is the HadamardMLP class implemented in the Needle repository?

The class is defined in [`needle/model/architecture.py`](https://github.com/cactus-compute/needle/blob/main/needle/model/architecture.py) at lines 287-303. The underlying Walsh-Hadamard matrix generator function `_walsh_matrix` is located at lines 80-85 in the same file, producing the normalized transform matrix used during forward passes.

### How does the Walsh-Hadamard transform compare to a standard feed-forward layer?

A standard feed-forward layer learns two dense matrices (expansion and projection) with O(n²) parameters and O(n²) compute. The Walsh-Hadamard approach replaces these with fixed orthogonal transforms and learnable diagonal scales, achieving comparable expressive power through the non-linear SiLU activation between two Hadamard passes while requiring fewer parameters and less computation.