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.

Advertisement

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.

Advertisement

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.