Why replace attention at all

Self-attention mixes every position with every other by building a score matrix A = softmax(QK^T / √d_k) of shape [N, N] and applying it as AV. That matrix is the source of both its power and its cost. Its power: every entry A_ij is computed from the actual tokens at i and j, so the mixing is data-controlled — the model decides, per input, who attends to whom. Its cost: forming and applying an N × N matrix is O(N^2) in compute and (naively) memory.

The question Hyena poses is surgical: can you keep the two properties that make attention work — global receptive field (every position can influence every other) and data-dependence (the mixing adapts to the input) — without ever materializing an N × N object? Hyena’s bet: a global filter convolution supplies the first property cheaply, multiplicative gating supplies the second, and stacking them in a short recurrence recovers enough of attention’s expressivity to compete at moderate scale.

Advertisement

The Hyena operator: convolutions and gates

Given an input u: [N, d], a Hyena layer first produces N_ord + 1 projections with a linear map (plus a short depthwise conv): a value stream v and gate streams x^1, …, x^{N_ord}, each of shape [N, d]. An order-N_ord Hyena operator is then the recurrence

z^1     = v
z^{n+1} = x^n ⊙ ( h^n * z^n )      for n = 1 .. N_ord
y       = z^{N_ord + 1}

Here * is a causal long convolution with a learned filter h^n of length N, and ⊙ is elementwise (Hadamard) multiplication by the gate x^n. Read it as an alternating stack: convolve (mix across time), then gate (modulate by the input), repeat. The order-2 case y = x^2 ⊙ (h^2 * (x^1 ⊙ (h^1 * v))) most directly parallels attention: two data-controlled projections surrounding a long-range mixing operator, echoing how Q and K surround the score matrix in softmax(QK^T)V.

Advertisement

The long convolution, made precise

The convolution is the engine. A causal discrete convolution of a signal x with filter h, both length N, is

y_t = Σ_{τ=0}^{t}  h_{t-τ} · x_τ   ,   t = 0 .. N-1

Each output y_t is a weighted sum of all inputs up to t. Because the filter length equals the sequence length, position 0 can influence position N-1: the receptive field is global, exactly what attention has and ordinary short convolutions (kernel size 3, 5, …) lack.

Written as a matrix, this is y = S_h x where S_h is the lower-triangular Toeplitz matrix whose t-th diagonal holds h_t. That is the key contrast with attention: the mixing matrix S_h is fixed (one value per diagonal, ~N free numbers) rather than data-dependent (dense, N^2 entries recomputed per input). Evaluating S_h x directly is still O(N^2) multiply-adds — which is where the FFT comes in.

Implicit filters: an MLP over positions

A filter of length N would naively be N learnable numbers per channel — and at N = 32K that is both a huge parameter count and hard to regularize. Hyena instead uses an implicitly parameterized filter: the value at time-step t is produced on demand by a small feed-forward network over a positional encoding of t,

h_t = window(t) · FFN( γ(t) )

where γ(t) is a positional embedding (e.g. sines/cosines of t), FFN is a tiny MLP shared across all t, and window(t) is a smooth modulation — typically an exponential decay exp(-α t) — that biases the filter to fade with distance. The decisive consequence: the parameter count is decoupled from the filter length. A fixed-size MLP defines a filter of any length N; doubling the context adds no filter parameters. This makes a sequence-length convolution practical and lets the filter represent smooth, long-range structure a raw N-vector would struggle to learn.

The convolution theorem and FFT evaluation

A length-N convolution is affordable because of the convolution theorem: convolution in the time domain is elementwise multiplication in the frequency domain. For circular convolution,

h * x  =  iFFT( FFT(h) ⊙ FFT(x) )

So instead of the O(N^2) Toeplitz matrix-vector product, you take two FFTs, multiply the spectra elementwise (O(N)), and take one inverse FFT — each FFT O(N log N), so the whole convolution is O(N log N).

One subtlety: the FFT computes circular convolution, which wraps around, whereas we want linear (causal) convolution. The fix is zero-padding: pad both h and x to length 2N (the next power of two), convolve circularly, and the wrap-around terms land in the discarded padding. Doubling the length keeps the cost at O(2N log 2N) = O(N log N). The filter spectrum FFT(h) can even be cached across the batch, since h does not depend on the input.

Counting the operations: O(N log N) vs O(N^2)

A radix-2 Cooley–Tukey FFT of length N costs about (N/2) log_2 N complex multiplications and N log_2 N additions — Θ(N log N). A Hyena convolution needs three such transforms plus an O(N) product. Attention’s QK^T and AV, by contrast, are ~2 N^2 d multiply-adds.

N = 8192 :
  attention   ~ N^2      = 8192^2      ≈ 6.7 × 10^7  score entries
  Hyena conv  ~ N log2 N = 8192 × 13  ≈ 1.1 × 10^5  butterflies
  ratio       ~ N / log2 N = 8192 / 13   ≈ 630 × fewer ops

The gap widens with N: the ratio N / log_2 N is ~130× at 1K, ~630× at 8K, ~5000× at 64K. A full Hyena layer runs the convolution once per order per channel, so its cost is O(N_ord · d · N log N) — linear in width and the small constant order, only log-linear in sequence length. That is the whole sub-quadratic promise.

Recovering data-dependence through gating

A fixed Toeplitz convolution alone is not attention: its matrix S_h is the same for every input, so it cannot do input-dependent routing like associative recall (“find the token that followed this key earlier”). Attention gets that from the data-dependent score matrix; Hyena gets it from the gates. Each x^n is a projection of the input, and the product x^n ⊙ (h^n * z^n) makes the effective operator input-dependent even though every filter is fixed.

Unroll the order-2 operator. Writing the gates as diagonal matrices D_{x^1}, D_{x^2} and the convolutions as Toeplitz matrices S_{h^1}, S_{h^2}, the whole layer is

y = D_{x^2} · S_{h^2} · D_{x^1} · S_{h^1} · v

The product D_{x^2} S_{h^2} D_{x^1} S_{h^1} is an N × N operator that does depend on the input (through the diagonal D factors) — but it is never formed explicitly. It is applied factor by factor: cheap FFT convolutions interleaved with cheap elementwise multiplies. That factorization is precisely how Hyena buys attention-like, data-controlled global mixing at O(N log N).