Hyena — Long Convolutions Math

The primitive: a causal convolution over the whole sequence

Start with the definition. Given an input signal x of length N and a filter h of length N, the causal discrete convolution is

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

Output y_t is a weighted sum of every input up to t, and the weight on x_τ depends only on the distance t - τ. Two properties fall out. It is causal: no term with τ > t appears, so a token never sees the future — the same guarantee a causal attention mask provides. And it is shift-equivariant: the filter is applied identically at every position.

In a Hyena layer this runs depthwise: the input is u: [N, d], the filter bank is h: [d, N] — one length-N filter per channel — and channel c is convolved only with filter c. Mixing across channels is left to the pointwise projections around it, as in depthwise-separable convolutions.

The Toeplitz picture: a matrix with only N free numbers

Every linear operator on a length-N signal is some N × N matrix, so ask which matrix a convolution is. Expand the sum as y = S_h x:

        [ h_0   0    0    0  ]
S_h  =  [ h_1  h_0   0    0  ]      S_h[t, τ] = h_{t-τ}  if t ≥ τ, else 0
        [ h_2  h_1  h_0   0  ]
        [ h_3  h_2  h_1  h_0 ]

This is a lower-triangular Toeplitz matrix: constant along every diagonal. That single structural fact is the whole economic difference from attention. Attention’s mixing matrix A = softmax(QK^T / √d_k) has N^2 independent entries, all recomputed from the input on every forward pass; the convolution’s has just N free numbers, one per diagonal, identical for every input. A long convolution is a structured, input-independent replacement for a dense, input-dependent matrix.

That buys the global receptive field cheaply and costs you content-based routing: a fixed S_h weights ‘12 tokens ago’ the same way whatever those tokens are, so it cannot do associative recall. Hyena restores data-dependence by interleaving convolutions with elementwise gates computed from the input, y = x^2 ⊙ (h^2 ∗ (x^1 ⊙ (h^1 ∗ v))) — in matrix form D_{x^2} S_{h^2} D_{x^1} S_{h^1} v, an input-dependent N × N operator applied as cheap factors and never materialized.

Why the filter has to be long

Convolutional networks have used kernels of size 3 or 5 for decades, so why insist the filter be as long as the sequence? Because a global receptive field is what makes attention work, and short kernels reach it only slowly. Stacking L layers of kernel size k gives a receptive field of 1 + L · (k - 1) positions — linear in depth, so letting position 0 influence position 8191 with k = 3 needs about 4096 layers.

Dilated convolutions do better: doubling the dilation each layer grows the receptive field as 2^L, so log_2 N ≈ 13 layers cover 8192 positions. But the coverage is sparse — each layer skips most offsets, and which distances are representable is fixed by the dilation schedule rather than learned. A filter of length N sidesteps both problems: one layer, every offset from 1 to N-1 given its own learnable weight. The receptive field stops being a budget you spend depth on and becomes simply the sequence length. The price is that evaluating S_h x directly costs N(N+1)/2 multiply-adds — still O(N^2), which is what the FFT removes.

The convolution theorem

The escape hatch is the oldest result in signal processing: convolution in time is multiplication in frequency. For circular convolution (h ∗ x)_t = Σ_{τ} h_{(t-τ) mod N} x_τ, the length-N DFT satisfies

DFT(h ∗ x)[k]  =  DFT(h)[k] · DFT(x)[k]        for every frequency k
⇒   h ∗ x  =  iFFT( FFT(h) ⊙ FFT(x) )

The reason is one line of algebra: a DFT decomposes the signal into complex exponentials e^{2πikt/N}, and a shift by τ multiplies such an exponential by e^{-2πikτ/N}. Complex exponentials are the eigenvectors of any shift-invariant operator, so in that basis the operator is diagonal — and a diagonal matrix acts by elementwise multiplication. Instead of an O(N^2) Toeplitz product you take two forward transforms, an O(N) elementwise product, and one inverse.

That leaves an intuition worth carrying: FFT(h) is the filter’s transfer function, one complex gain per frequency. Learning a long filter is learning which frequencies to amplify, attenuate, or phase-shift — slow structure in the low bins, sharp local detail in the high ones.

Linear vs circular: the padding that preserves causality

The theorem is stated for circular convolution, which wraps: the index t - τ is taken mod N. A language model needs linear causal convolution, which does not. Getting this wrong is no small numerical error — wrap-around lets the end of the sequence leak into the beginning, an outright causality violation. Make it concrete with h = [1, 0.5, 0.25, 0.125] and x = [1, 2, 0, 0]; the linear causal result is

y_0 = h_0 x_0                        = 1                      = 1.000
y_1 = h_1 x_0 + h_0 x_1             = 0.5 + 2               = 2.500
y_2 = h_2 x_0 + h_1 x_1 + h_0 x_2   = 0.25 + 1 + 0          = 1.250
y_3 = h_3 x_0 + h_2 x_1 + h_1 x_2 + h_0 x_3 = 0.125 + 0.5   = 0.625

A length-4 circular convolution instead gives y~_0 = h_0 x_0 + h_3 x_1 = 1 + 0.25 = 1.25: token 1, which lies in the future of position 0, has contaminated it by wrapping around. The fix is zero-padding — pad h and x to length 2N (rounded up to a power of two), convolve circularly, and every wrapped term lands in the padding you discard, leaving the first N outputs exactly linear and causal at a still-O(N log N) cost.

Counting the cost, and where the crossover sits

A radix-2 Cooley–Tukey FFT of length N uses about (N/2) log_2 N complex multiplies and N log_2 N adds. One long convolution needs three such transforms plus an O(N) spectral product. Against the direct Toeplitz product:

N = 4096 :
  direct conv  ~ N^2/2   = 4096^2 / 2   ≈ 8.4 × 10^6  multiply-adds
  FFT conv     ~ N log2N = 4096 × 12   ≈ 4.9 × 10^4  butterflies
  asymptotic ratio  N / log2 N = 4096 / 12   ≈ 341 ×

The ratio N / log_2 N is roughly 100× at N = 1024, 341× at 4K, and about 4000× at 64K — the advantage compounds exactly where long context lives. Across the layer the cost is O(d · N log N): linear in width, log-linear in length, versus attention’s O(N^2 d). The caveat is constants — FFTs have poor arithmetic intensity, need complex arithmetic, and require padding, so below roughly a thousand positions a direct convolution or plain matmul is faster.

Implicit filters: an MLP over positions

There is still a parameter problem. A length-N filter per channel means d · N learnable numbers — at d = 768 and N = 32768 that is 25 million weights for one layer’s filters, and it grows every time you extend the context. Hyena never stores the filter; it generates it:

h_t = window(t) · FFN( γ(t) )        FFN : R^m → R^d,  shared over all t

Here γ(t) is a positional encoding of the time index (sines and cosines at several frequencies, plus t) and FFN is a small MLP evaluated once per position to emit that position’s tap for all d channels. The consequence is decisive: parameter count is decoupled from filter length — a fixed-size MLP defines a filter of any length, and doubling the context adds zero filter parameters. It also changes what is easy to learn: because h_t is a smooth function of a continuous index, the filter is smooth in t — a strong regularizer against the noisy filters N free parameters would happily fit.

The decay window, and why it is not optional

The window(t) factor looks cosmetic and is not. An unconstrained MLP emits values of roughly constant magnitude for arbitrarily large t — a filter that never fades, where position 30000 contributes as strongly as position 3. That is bad statistics (language is overwhelmingly local) and bad conditioning (y_t accumulates thousands of same-scale terms, inflating activation variance and gradient noise).

The standard choice is an exponential envelope with a learnable per-channel rate,

window(t) = exp(-α_c · t),    α_c ≥ 0

which imposes a timescale. A channel with large α has an effective memory of order 1 / α steps and behaves like a short local kernel; a channel with α → 0 keeps a nearly flat filter and integrates the whole prefix. Initializing α across a spread of values gives a layer a bank of memories from a few tokens to the full context — the same idea state-space models express through the spectrum of their state matrix A.

On a CPU, and in autoregressive decoding

For a small model on a CPU the long convolution has an attractive profile. Its inner loop is an FFT, and FFTs are among the most heavily optimized routines in existence (FFTW, MKL, pocketfft), with cache-friendly access and no giant intermediate matrix. Prefill is O(d N log N) and never allocates an N × N score block. Nor is there a KV cache: the per-layer state is the filter, whose size does not grow with context.

The frictions are real too. Padding to the next power of two can nearly double the work just past a boundary — 4100 tokens pad to 8192. FFTs want floating-point complex arithmetic, so int8/int4 quantization does not apply cleanly to the convolution itself. And the sharp edge is token-by-token generation: re-convolving the whole prefix per new token costs O(N log N) per step — worse than cached attention — unless the filter is distilled into an equivalent recurrence with O(1) per-token state, which is what state-space models get for free.