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

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 (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 (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:

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, where the HadamardMLP class orchestrates the transform and diagonal scaling. You can instantiate and run the module as follows:

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 – Executes the complete transformer stack, inserting HadamardMLP immediately after the attention block to process sequence representations.
• 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 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.

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 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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}