How the Walsh-Hadamard Transform Powers Needle 2's Structured Attention Network

The Walsh-Hadamard transform enables Needle 2's Structured Attention Network to perform fast, deterministic orthogonal mixing in feed-forward layers and reconstruct ultra-compact quantized weights during export using fixed mathematical operations rather than learned matrices.

The cactus-compute/needle repository implements a novel transformer architecture called the Structured Attention Network (SAN) that leverages classical signal processing techniques to reduce computational overhead. At the core of this design lies the Walsh-Hadamard transform (WHT), which serves dual purposes: replacing dense layers in the MLP sub-layers and enabling compact weight encoding for quantized inference. Unlike standard transformer implementations that rely solely on learned linear projections, Needle 2's SAN utilizes this deterministic, orthogonal transformation to achieve strong feature mixing with minimal parameter count.

Fast Orthogonal Mixing in the MLP Sub-layer

The SAN's feed-forward block replaces conventional dense layers with a HadamardMLP module defined in needle/model/architecture.py. This module implements a weight-free mixing stage that operates in O(n log n) time complexity while maintaining full expressivity through learned diagonal scaling vectors.

Generating the Walsh-Hadamard Matrix

The transformation matrix H is generated on-the-fly by the _walsh_matrix function (lines 80-85 in architecture.py). This recursive construction builds an n×n normalized Walsh-Hadamard matrix without storing learned weights:

def _walsh_matrix(n: int) -> jnp.ndarray:
    """Return an n×n normalized Walsh‑Hadamard matrix."""
    H = np.array([[1.0]], dtype=np.float32)
    while H.shape[0] < n:
        H = np.block([[H, H], [H, -H]])
    return jnp.asarray(H / np.sqrt(n))

The function recursively doubles the matrix dimensions using the Sylvester construction until reaching the target size, then normalizes by √n to maintain orthogonality (H·Hᵀ = I).

The HadamardMLP Architecture

Inside HadamardMLP.__call__, the input activation x undergoes two Walsh-Hadamard multiplications sandwiching a non-linear gating mechanism. The implementation pads inputs to the next power-of-two dimension, then applies learned diagonal scalars d1, d2, and d3:

@nn.compact
def __call__(self, x):
    n = 1 << (self.d_model - 1).bit_length()
    H = _walsh_matrix(n).astype(self.dtype)
    
    # Learned diagonal parameters only

    d1 = self.param("d1", jinit.ones, (n,)).astype(self.dtype)
    d2 = self.param("d2", jinit.ones, (n,)).astype(self.dtype)
    d3 = self.param("d3", jinit.constant(0.02), (n,)).astype(self.dtype)
    
    # Pad and transform

    pad = n - self.d_model
    z = jnp.pad(x, ((0, 0), (0, 0), (0, pad))) if pad else x
    z = (d1 * z) @ H
    z = nn.silu(d2 * z) @ H
    return (d3 * z)[..., : self.d_model]

This design reduces the MLP's learned parameters to three diagonal vectors while the heavy mixing work is performed by the fixed orthogonal matrix.

Compact Weight Reconstruction During Model Export

Beyond inference-time mixing, the Walsh-Hadamard transform enables dramatic compression during model serialization. In needle/model/export.py (lines 60-61), the code reconstructs full weight tensors from compact codebook indices using a normalized Walsh-Hadamard matrix:

w_group = (codebook_bits[idx] * norm) @ H

Here, codebook_bits stores quantized indices, norm provides per-group scaling, and H is the same normalized Walsh-Hadamard matrix used in the forward pass. This approach eliminates the need to store dense weight matrices on disk—only the compact codebook representation and the fixed transform matrix are required, significantly reducing binary size while allowing exact reconstruction at runtime.

Summary

• Needle 2's SAN replaces standard MLP dense layers with HadamardMLP, utilizing the Walsh-Hadamard transform for fast O(n log n) orthogonal mixing.
• The _walsh_matrix function in needle/model/architecture.py generates normalized orthogonal matrices recursively without learned parameters.
• Only three diagonal vectors (d1, d2, d3) are learned per MLP layer, drastically reducing parameter count while preserving expressivity.
• During export, the same transform enables ultra-compact weight encoding in needle/model/export.py by reconstructing weights from codebook indices via matrix multiplication with H.
• This dual usage makes the Walsh-Hadamard transform foundational to both the computational efficiency and storage efficiency of Needle 2's architecture.

Frequently Asked Questions

What is the Walsh-Hadamard transform in Needle 2's SAN?

The Walsh-Hadamard transform is a deterministic, orthogonal linear transformation used throughout Needle 2's Structured Attention Network. Unlike learned weight matrices, it provides fixed, invertible mixing operations that run in O(n log n) time, enabling efficient feature blending in MLP layers and compact weight reconstruction during model export.

How does HadamardMLP differ from standard transformer feed-forward layers?

Standard transformer MLPs rely on two dense linear projections with non-linear activation between them. In contrast, HadamardMLP replaces these projections with multiplication by a fixed Walsh-Hadamard matrix H, learning only three diagonal scaling vectors (d1, d2, d3). This reduces parameters while maintaining strong mixing capabilities through the orthogonal properties of H.

Why does Needle 2 use the Walsh-Hadamard transform for model export?

The export pipeline in needle/model/export.py uses the Walsh-Hadamard transform to reconstruct full weight tensors from compressed codebook representations. By storing only quantized indices and applying the normalized matrix H during loading, Needle 2 achieves significant binary size reduction without sacrificing model accuracy or inference speed.

What is the computational complexity of the Walsh-Hadamard transform in Needle 2?

The Walsh-Hadamard transform operates in O(n log n) time complexity, where n is the padded dimension (next power-of-two). This is substantially faster than the O(n²) complexity of dense matrix multiplication, making it ideal for the quantized, low-bit inference pipelines targeted by the Needle 2 architecture.

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