Hyena Hierarchy Math

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.

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.

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

A worked numeric example

Take a length-4 causal convolution with values v = [1, 0, 2, 1] and implicit filter h = [1, 0.5, 0.25, 0.125] (a decaying window, as the MLP would produce). Direct evaluation of y_t = Σ_{τ≤t} h_{t-τ} v_τ:

y_0 = h_0 v_0                       = 1·1                     = 1.00
y_1 = h_1 v_0 + h_0 v_1            = 0.5·1 + 1·0            = 0.50
y_2 = h_2 v_0 + h_1 v_1 + h_0 v_2 = 0.25·1 + 0 + 1·2       = 2.25
y_3 = h_3 v_0 + h_2 v_1 + h_1 v_2 + h_0 v_3 = 0.125 + 0 + 1 + 1 = 2.125

That is 1+2+3+4 = 10 multiply-adds — the N(N+1)/2 lower-triangular count that grows as O(N^2). The FFT route computes identical numbers by padding to length 8, transforming h and v, multiplying the spectra point-by-point, and inverse-transforming; the causal outputs land in the first four slots. At N = 4 the FFT is not worth it — the crossover is a few hundred positions — but the numbers are exactly equal, and past it the FFT wins by the 630×-and-climbing margins above.

Hyena vs SSMs vs attention

Hyena is one corner of a triangle of sequence mixers. Attention forms a dense, fully data-dependent N × N matrix — maximum flexibility, O(N^2) cost. State-space models (S4, and the selective SSM in Mamba) also reduce to a long convolution, but their filter is not a free MLP: it is the impulse response K = (CB, CAB, CA^2 B, …) of a linear recurrence with matrices (A, B, C). S4 evaluates that convolution with the same FFT trick, so it too is O(N log N).

The distinctions are sharp. Filter origin: Hyena parameterizes the filter directly and implicitly (MLP over positions); SSMs derive it from a structured recurrence. Data-dependence: vanilla Hyena’s filter is input-independent, data-dependence coming only from the gates; Mamba instead makes the SSM parameters themselves input-dependent (selective scan). Decoding: an SSM carries a compact recurrent state, giving O(1) work per token; Hyena’s implicit filter has no such small state natively, so causal generation is its weak spot unless the filter is distilled into a recurrence. All three chase global, adaptive mixing — but only attention pays quadratically for it.

Practical and CPU-SLM implications, and pitfalls

For a small model on a CPU, Hyena’s dominant primitive is the FFT — memory-friendly and well-optimized (FFTW, MKL, pocketfft) rather than a giant dense matmul — and it sheds the ballooning KV cache that makes long-context attention decode memory-bound. But the constants bite. FFT overhead: below the crossover (a few hundred to ~1K tokens) attention or a plain matmul is faster, so Hyena only pays off at long context. Power-of-two padding can nearly double work just past a boundary — a 4100-token input pads to 8192. Numerical care: the decay window must keep the floating-point filter stable. And autoregressive inference is the real pitfall: naively re-convolving the whole prefix per token is O(N log N) per step, i.e. O(N^2 log N) for a sequence — worse than attention with a KV cache — unless you exploit an SSM-style recurrent form. Hyena wins cleanly on long, parallel workloads; token-by-token generation is the case needing extra engineering.