Zoology: Measuring and Improving Recall in Efficient Language Models — part 8/14

Cleaned-text code points [108041, 123560). Bibliography omitted here; source.md includes it.

2. We again define 𝐖 := 𝟎 N × d , 𝒃 1 := 𝟏 N × d , 𝒃 2 := 𝟎 N × d {\bf W}:=\mathbf{0}^{N\times d},\bm{b}_{1}:=\mathbf{1}^{N\times d},\bm{b}_{2}:=\mathbf{0}^{N\times d} . Then, for input 𝒚 ∈ ℝ N × d \bm{y}\in\mathbbm{R}^{N\times d} , BaseConv ​ ( 𝒚 , 𝟎 N × d , 𝒆 0 , 𝟏 N × d , 𝟎 N × d ) \textsc{BaseConv}\left({\bm{y},\mathbf{0}^{N\times d},\bm{e}_{0},\mathbf{1}^{N\times d},\mathbf{0}^{N\times d}}\right) for BaseConv in Algorithm 7 is given in equation 4 as 𝐘 0 ≡ 𝒚 ⊛ 𝒆 0 . \displaystyle{\bf Y}_{0}\equiv\bm{y}\circledast\bm{e}_{0}. Now, to perform shift_up ( 𝒚 , s ) (\bm{y},s) , as before, we first apply the circular convolution to reverse the input 𝐘 0 [ : , j ] = 𝒚 [ : , j ] ⊛ 𝒆 0 \displaystyle{\bf Y}_{0}[:,j]=\bm{y}[:,j]\circledast\bm{e}_{0} = coeff ⁡ ( ∑ i = 0 N − 1 𝒚 ⁡ [ N − 1 − i , j ] ⋅ X i ) , \displaystyle=\mathrm{coeff}\left(\sum_{i=0}^{N-1}\bm{y}[N-1-i,j]\cdot X^{i}\right), We then apply 𝒀 1 ≡ shift_down ​ ( 𝒀 0 , s ) \bm{Y}_{1}\equiv\texttt{shift\_down}(\bm{Y}_{0},s) to get 𝒀 1 [ : , j ] \displaystyle\bm{Y}_{1}[:,j] ≡ coeff ⁡ ( ∑ i = s N − 1 𝒀 0 ​ [ N − 1 − ( i − s ) , j ] ⋅ X i ) , \displaystyle\equiv\mathrm{coeff}\left(\sum_{i=s}^{N-1}\bm{Y}_{0}[N-1-(i-s),j]\cdot X^{i}\right), ≡ coeff ⁡ ( ∑ i = s N − 1 𝒀 0 ​ [ N − 1 − i + s , j ] ⋅ X i ) . \displaystyle\equiv\mathrm{coeff}\left(\sum_{i=s}^{N-1}\bm{Y}_{0}[N-1-i+s,j]\cdot X^{i}\right). Finally, we apply another circular convolution with the identity filter to replace N − 1 − i N-1-i with i i to get 𝐘 2 [ : , j ] = 𝒀 1 [ : , j ] ⊛ 𝒆 0 \displaystyle{\bf Y}_{2}[:,j]=\bm{Y}_{1}[:,j]\circledast\bm{e}_{0} = coeff ⁡ ( ∑ i = 0 N − 1 𝒚 ⁡ [ i + s , j ] ⋅ X i ) , \displaystyle=\mathrm{coeff}\left(\sum_{i=0}^{N-1}\bm{y}[i+s,j]\cdot X^{i}\right), Here, we note that we can compute both of these primitives in one and three layers, respectively (see Lemma H.11 ).

∎

Now, we present a BaseConv model with two layers that implements the add n ( 𝒚 : 𝒙 , 𝑺 ) \texttt{add}_{n}({\bm{y}:\bm{x}},{\bm{S}}) , the purpose of which is to add some window of computation 𝒙 \bm{x} to a running sum 𝑺 \bm{S} .

###### Proposition H.9 (The Running Sum Primitive) .

For any 𝐱 , 𝐒 ∈ ℝ n × d \bm{x,S}\in\mathbbm{R}^{n\times d} contained in some 𝐲 ∈ ℝ N × d \bm{y}\in\mathbbm{R}^{N\times d} , there exists a ( N , 2 , d , N , d ) − BaseConv \left(N,2,d,N,d\right)-\text{{BaseConv}} that computes add n ( 𝐲 : 𝐱 , 𝐒 ) \texttt{add}_{n}({\bm{y}:\bm{x}},{\bm{S}}) for BaseConv as in Algorithm 7 .

###### Proof.

We will show this for d ′ = 1 d^{\prime}=1 and the general case follows as we will explain at the end. We now specify the two layers that we use 𝒛 1 \displaystyle\bm{z}^{1} ≡ BaseConv ​ ( 𝒚 , 𝟎 N × 1 , 𝒉 1 , 𝒃 1 1 , 𝟎 N × 1 ) ≡ 𝒃 1 1 ⊙ ( 𝒉 1 ∗ 𝒚 ) \displaystyle\equiv\textsc{BaseConv}\left({\bm{y},\mathbf{0}^{N\times 1},\bm{h}^{1},\bm{b}^{1}_{1},\mathbf{0}^{N\times 1}}\right)\equiv\bm{b}^{1}_{1}\odot\left(\bm{h}^{1}\ast\bm{y}\right) 𝒛 \displaystyle\bm{z} ≡ BaseConv ​ ( 𝒛 1 , 𝟎 N × 1 , 𝒉 2 , 𝒃 1 2 , 𝒃 1 2 ) ≡ 𝒃 1 2 ⊙ ( 𝒉 2 ∗ 𝒚 + 𝒃 2 2 ) , \displaystyle\equiv\textsc{BaseConv}\left({\bm{z}^{1},\mathbf{0}^{N\times 1},\bm{h}^{2},\bm{b}^{2}_{1},\bm{b}^{2}_{1}}\right)\equiv\bm{b}^{2}_{1}\odot\left(\bm{h}^{2}\ast\bm{y}+\bm{b}^{2}_{2}\right), where we will specify the kernels as we go along. Let us start by defining the kernel and the bias for the first layer as 𝒉 1 ≡ ( 𝒆 0 𝒆 0 𝟎 n ⋯ 𝟎 n ) , 𝒃 1 ≡ ( 𝟎 n 𝟏 n 𝟎 n ⋯ 𝟎 n ) . \bm{h}^{1}\equiv\begin{pmatrix}\bm{e}_{0}\\ \hline\cr\\ \bm{e}_{0}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix},\quad\quad\bm{b}_{1}\equiv\begin{pmatrix}\bm{0}^{n}\\ \hline\cr\\ \bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}. Let us first compute 𝒉 1 ∗ 𝒚 \bm{h}^{1}\ast\bm{y} as follows: 𝒉 1 ​ ( X ) ⋅ 𝒚 ​ ( X ) \displaystyle\bm{h}^{1}(X)\cdot\bm{y}(X) = ( X n + 1 ) ⋅ ( 𝑺 ⁡ ( X ) ⋅ X n + 𝒙 ⁡ ( X ) ) \displaystyle=(X^{n}+1)\cdot(\bm{S}(X)\cdot X^{n}+\bm{x}(X)) = 𝑺 ⁡ ( X ) ⋅ X 2 ​ n + ( 𝑺 + 𝒙 ) ​ ( X ) ⋅ X n + 𝒙 ⁡ ( X ) . \displaystyle=\bm{S}(X)\cdot X^{2n}+(\bm{S}+\bm{x})(X)\cdot X^{n}+\bm{x}(X). We then have 𝒛 1 ≡ 𝒃 1 1 ⊙ ( 𝒉 1 ∗ 𝒚 ) ≡ ( 𝟎 n 𝟏 n 𝟎 n ⋯ 𝟎 n ) ⊙ ( 𝒙 𝑺 + 𝒙 𝑺 ⋯ 𝟎 n ) ≡ ( 𝟎 n 𝑺 + 𝒙 𝟎 n ⋯ 𝟎 n ) \bm{z}_{1}\equiv\bm{b}_{1}^{1}\odot\left(\bm{h}^{1}\ast\bm{y}\right)\equiv\begin{pmatrix}\bm{0}^{n}\\ \hline\cr\\ \bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\odot\begin{pmatrix}\bm{x}\\ \hline\cr\\ \bm{S}+\bm{x}\\ \hline\cr\\ \bm{S}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\equiv\begin{pmatrix}\bm{0}^{n}\\ \hline\cr\\ \bm{S}+\bm{x}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}

##### Resetting for Next Phase.

We now use the next layer to reset for the next phase. Here, we need the first vector to be 𝟏 n \bm{1}^{n} in order to start adding the next vector. We thus use the kernel and the biases 𝒉 2 , 𝒃 1 2 , 𝒃 2 2 \bm{h}^{2},\bm{b}^{2}_{1},\bm{b}^{2}_{2} defined as 𝒉 2 ≡ ( 𝒆 0 𝟎 n 𝟎 n ⋯ 𝟎 n ) , 𝒃 1 2 ≡ ( 𝟏 n 𝟏 n 𝟎 n ⋯ 𝟎 n ) , 𝒃 2 2 ≡ ( 𝟏 n 𝟎 n 𝟎 n ⋯ 𝟎 n ) . \bm{h}^{2}\equiv\begin{pmatrix}\bm{e}_{0}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix},\quad\quad\bm{b}^{2}_{1}\equiv\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix},\quad\quad\bm{b}^{2}_{2}\equiv\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}. Explicitly, for the second layer, we compute the result of the convolution in terms of polynomials as follows: 𝒉 2 ​ ( X ) ⋅ 𝒛 1 ​ ( X ) = 1 ⋅ ( 𝑺 + 𝒙 ) ​ ( X ) ⋅ X n = ( 𝑺 + 𝒙 ) ​ ( X ) ⋅ X n . \displaystyle\bm{h}^{2}(X)\cdot\bm{z}^{1}(X)=1\cdot(\bm{S}+\bm{x})(X)\cdot X^{n}=(\bm{S}+\bm{x})(X)\cdot X^{n}. Thus, the output for the second layer is given by 𝒛 ≡ 𝒃 1 2 ⊙ ( 𝒉 2 ∗ 𝒛 1 + 𝒃 2 2 ) ≡ ( 𝟏 n 𝟏 n 𝟎 n ⋯ 𝟎 n ) ⊙ ( ( 𝟎 n 𝑺 + 𝒙 𝟎 n ⋯ 𝟎 n ) + ( 𝟏 n 𝟎 n 𝟎 n ⋯ 𝟎 n ) ) ≡ ( 𝟏 n 𝟏 n 𝟎 n ⋯ 𝟎 n ) ⊙ ( 𝟏 n 𝑺 + 𝒙 𝟎 n ⋯ 𝟎 n ) ≡ ( 𝟏 n 𝑺 + 𝒙 𝟎 n ⋯ 𝟎 n ) . \bm{z}\equiv\bm{b}_{1}^{2}\odot\left(\bm{h}^{2}\ast\bm{z}^{1}+\bm{b}^{2}_{2}\right)\equiv\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\odot\left(\begin{pmatrix}\bm{0}^{n}\\ \hline\cr\\ \bm{S}+\bm{x}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}+\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\right)\equiv\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{1}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\odot\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{S}+\bm{x}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}\equiv\begin{pmatrix}\bm{1}^{n}\\ \hline\cr\\ \bm{S}+\bm{x}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\end{pmatrix}. Therefore, we have used two BaseConv layers to add 𝒙 \bm{x} to the running sum 𝑺 \bm{S} and reset for the next phase. Here, we note that the only operations we perform and are convolutions and Hadamard product and they generalize in the obvious way to d > 1 d>1 . ∎

Next, we show that a five layer BaseConv model can perform gated convolution on windows of the input (without changing the rest of the input).

###### Proposition H.10 (The Remembering Primitive) .

For any 𝐱 ∈ ℝ n × d , 𝐯 ∈ ℝ m × d \bm{x}\in\mathbbm{R}^{n\times d},\bm{v}\in\mathbbm{R}^{m\times d} contained in some 𝐲 ∈ ℝ N × d \bm{y}\in\mathbbm{R}^{N\times d} for some n + m + s + t ≤ N n+m+s+t\leq N so that for 𝐡 ∈ ℝ n × d \bm{h}\in\mathbbm{R}^{n\times d} and 𝐩 ∈ ℝ ( n + s ) × d \bm{p}\in\mathbbm{R}^{(n+s)\times d} with 𝐱 ∗ 𝐡 ∈ ℝ ( n + s ) × d \bm{x}\ast\bm{h}\in\mathbbm{R}^{(n+s)\times d} and 𝐯 ∗ 𝐡 ∈ ℝ ( m + t ) × d \bm{v}\ast\bm{h}\in\mathbbm{R}^{(m+t)\times d} , there exists a ( N , 5 , d , N , d ) − BaseConv \left(N,5,d,N,d\right)-\text{{BaseConv}} that computes 𝚛𝚎𝚖𝚎𝚖𝚋𝚎𝚛 ( 𝐲 : 𝐱 , 𝐯 , 𝐡 , 𝐩 ) {\tt remember}(\bm{y}:\bm{x},\bm{v},\bm{h},\bm{p}) for BaseConv as in Algorithm 7 .

###### Proof.

We will again show this for d ′ = 1 d^{\prime}=1 and the general case should follow. We now specify the first two layers that we use 𝒛 1 \displaystyle\bm{z}^{1} ≡ BaseConv ​ ( 𝒚 , 𝟎 N × 1 , 𝒉 1 , 𝒃 1 1 , 𝟎 N × d ) ≡ 𝒃 1 1 ⊙ ( 𝒉 1 ∗ 𝒚 ) \displaystyle\equiv\textsc{BaseConv}\left({\bm{y},\mathbf{0}^{N\times 1},\bm{h}^{1},\bm{b}^{1}_{1},\mathbf{0}^{N\times d}}\right)\equiv\bm{b}^{1}_{1}\odot\left(\bm{h}^{1}\ast\bm{y}\right) 𝒛 2 \displaystyle\bm{z}^{2} ≡ BaseConv ​ ( 𝒛 1 , 𝟎 N × 1 , 𝒉 2 , 𝒃 1 2 , 𝟎 N × d ) ≡ 𝒃 1 2 ⊙ ( 𝒉 2 ∗ 𝒚 ) , \displaystyle\equiv\textsc{BaseConv}\left({\bm{z}^{1},\mathbf{0}^{N\times 1},\bm{h}^{2},\bm{b}^{2}_{1},\mathbf{0}^{N\times d}}\right)\equiv\bm{b}^{2}_{1}\odot\left(\bm{h}^{2}\ast\bm{y}\right), The kernel 𝒉 1 \bm{h}^{1} and the bias 𝒃 1 1 \bm{b}^{1}_{1} for the first layer are then given by 𝒉 1 ≡ ( 𝒉 𝟎 m 𝒆 s + t 𝟎 n 𝟎 n ⋯ 𝟎 n ) , 𝒃 1 1 ≡ ( 𝒑 𝟎 m + t 𝟎 n 𝟎 s 𝟏 m ⋯ 𝟎 n ) . \bm{h}^{1}\equiv\begin{pmatrix}\bm{h}\\ \hline\cr\\ \bm{0}^{m}\\ \hline\cr\\ \bm{e}_{s+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\\ \end{pmatrix},\quad\quad\bm{b}_{1}^{1}\equiv\begin{pmatrix}\bm{p}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{s}\\ \hline\cr\\ \bm{1}^{m}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\\ \end{pmatrix}. where recall that 𝒙 ∗ 𝒉 ∈ ℝ ( n + s ) × d \bm{x}\ast\bm{h}\in\mathbbm{R}^{(n+s)\times d} and 𝒗 ∗ 𝒉 ∈ ℝ ( m + t ) × d \bm{v}\ast\bm{h}\in\mathbbm{R}^{(m+t)\times d} .

We now want to first specify the result of applying the first kernel: ( 𝒉 1 ∗ 𝒚 ) \displaystyle\left(\bm{h}^{1}\ast\bm{y}\right) = coeff ⁡ ( ( 𝒉 ⁡ ( X ) + X n + m + s + t ) ⋅ ( 𝒗 ⁡ ( X ) ⋅ X n + s + 𝒙 ⁡ ( X ) ) ) \displaystyle=\mathrm{coeff}\left((\bm{h}(X)+X^{n+m+s+t})\cdot\left(\bm{v}(X)\cdot X^{n+s}+\bm{x}(X)\right)\right) = coeff ⁡ ( 𝒉 ∗ 𝒗 ⁡ ( X ) ⋅ X n + s + 𝒉 ∗ 𝒙 ⁡ ( X ) + 𝒗 ⁡ ( X ) ⋅ X 2 ​ n + 2 ​ s + m + t + 𝒙 ⁡ ( X ) ⋅ X n + m + s + t ) \displaystyle=\mathrm{coeff}\left(\bm{h}\ast\bm{v}(X)\cdot X^{n+s}+\bm{h}\ast\bm{x}(X)+\bm{v}(X)\cdot X^{2n+2s+m+t}+\bm{x}(X)\cdot X^{n+m+s+t}\right) We then have 𝒛 1 ≡ 𝒃 1 1 ⊙ ( 𝒉 1 ∗ 𝒚 ) ≡ ( 𝒑 𝟎 m + t 𝟎 n 𝟎 s 𝟏 m ⋯ 𝟎 n ) ⊙ ( 𝒉 ∗ 𝒙 𝒉 ∗ 𝒗 𝒙 𝟎 s 𝒗 ⋯ 𝟎 n ) ≡ ( 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) 𝟎 m + t 𝟎 n 𝟎 s 𝒗 ⋯ 𝟎 n ) . \bm{z}_{1}\equiv\bm{b}_{1}^{1}\odot\left(\bm{h}^{1}\ast\bm{y}\right)\equiv\begin{pmatrix}\bm{p}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{s}\\ \hline\cr\\ \bm{1}^{m}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\\ \end{pmatrix}\odot\begin{pmatrix}\bm{h}\ast\bm{x}\\ \hline\cr\\ \bm{h}\ast\bm{v}\\ \hline\cr\\ \bm{x}\\ \hline\cr\\ \bm{0}^{s}\\ \hline\cr\\ \bm{v}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\\ \end{pmatrix}\equiv\begin{pmatrix}\bm{p}\odot(\bm{h}\ast\bm{x})\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{0}^{s}\\ \hline\cr\\ \bm{v}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}^{n}\\ \end{pmatrix}. We now describe the second kernel 𝒉 2 \bm{h}^{2} and the bias matrix 𝒃 1 2 \bm{b}^{2}_{1} as follows: 𝒉 2 ≡ ( 𝒆 0 𝟎 m + t 𝒆 0 𝟎 n + s 𝟎 m ⋯ 𝟎 ) , 𝒃 1 2 ≡ ( 𝟎 n + s 𝟎 m + t 𝟎 n 𝟏 n + s 𝟏 m ⋯ 𝟎 ) \bm{h}^{2}\equiv\begin{pmatrix}\bm{e}_{0}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{e}^{0}\\ \hline\cr\\ \bm{0}^{n+s}\\ \hline\cr\\ \bm{0}^{m}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix},\quad\quad\bm{b}_{1}^{2}\equiv\begin{pmatrix}\bm{0}^{n+s}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{1}^{n+s}\\ \hline\cr\\ \bm{1}^{m}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix} This yields the following convolution computation: 𝒉 2 ⊙ 𝒛 1 \displaystyle\bm{h}^{2}\odot\bm{z}^{1} ≡ coeff ⁡ ( ( X m + n + s + t + 1 ) ⋅ ( 𝒗 ⁡ ( X ) ⋅ X 2 ​ n + 2 ​ s + m + t + ( 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) ) ​ ( X ) ) ) \displaystyle\equiv\mathrm{coeff}\left(\left(X^{m+n+s+t}+1\right)\cdot\left(\bm{v}(X)\cdot X^{2n+2s+m+t}+\left(\bm{p}\odot(\bm{h}\ast\bm{x})\right)(X)\right)\right) ≡ coeff ⁡ ( 𝒗 ⁡ ( X ) ⋅ X 3 ​ n + 3 ​ s + 2 ​ m + 2 ​ t + 𝒗 ⁡ ( X ) ⋅ X 2 ​ n + 2 ​ s + m + t CLOSE \displaystyle\equiv\mathrm{coeff}(\bm{v}(X)\cdot X^{3n+3s+2m+2t}+\bm{v}(X)\cdot X^{2n+2s+m+t} + ( 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) ) ( X ) ⋅ X m + n + s + t + ( 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) ) ( X ) ) \displaystyle\quad+\left(\bm{p}\odot(\bm{h}\ast\bm{x})\right)(X)\cdot X^{m+n+s+t}+\left(\bm{p}\odot(\bm{h}\ast\bm{x})\right)(X)) Thus we have 𝒛 2 ≡ 𝒃 2 1 ⊙ ( 𝒉 2 ∗ 𝒛 1 ) ≡ ( 𝟎 n + s 𝟎 m + t 𝟎 n 𝟏 n + s 𝟏 m ⋯ 𝟎 ) ⊙ ( 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) 𝟎 m + t 𝟎 n 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) 𝒗 ⋯ 𝟎 ) ≡ ( 𝟎 n + s 𝟎 m + t 𝟎 n 𝒑 ⊙ ( 𝒉 ∗ 𝒙 ) 𝒗 ⋯ 𝟎 ) \bm{z}^{2}\equiv\bm{b}_{2}^{1}\odot\left(\bm{h}^{2}\ast\bm{z}^{1}\right)\equiv\begin{pmatrix}\bm{0}^{n+s}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{1}^{n+s}\\ \hline\cr\\ \bm{1}^{m}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix}\odot\begin{pmatrix}\bm{p}\odot(\bm{h}\ast\bm{x})\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{p}\odot(\bm{h}\ast\bm{x})\\ \hline\cr\\ \bm{v}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix}\equiv\begin{pmatrix}\bm{0}^{n+s}\\ \hline\cr\\ \bm{0}^{m+t}\\ \hline\cr\\ \bm{0}^{n}\\ \hline\cr\\ \bm{p}\odot(\bm{h}\ast\bm{x})\\ \hline\cr\\ \bm{v}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix} We now shift this up by 2 ​ n + s + m + t 2n+s+m+t entries using the primitive operation defined in Proposition H.8 that costs three additional layers so that we end up with 𝒛 ≡ ( 𝒑 ⊙ ( 𝒉 ∗ 𝒖 ) 𝒗 ⋯ 𝟎 ) \bm{z}\equiv\begin{pmatrix}\bm{p}\odot(\bm{h}\ast\bm{u})\\ \hline\cr\\ \bm{v}\\ \hline\cr\\ \cdots\\ \hline\cr\\ \bm{0}\end{pmatrix} Again, we note that the only operations we perform and are convolutions and Hadamard product and they generalize in the obvious way to d > 1 d>1 . ∎

Finally, we show that these primitives may be composed by ’stacking’ models with matching inner dimension ( N ′ , d ′ ) (N^{\prime},d^{\prime}) .

###### Lemma H.11 .

For f , g : ℝ N × d → ℝ N × d f,g:\mathbbm{R}^{N\times d}\to\mathbbm{R}^{N\times d} that have ( N , L 1 , d , N ′ , d ′ ) (N,L_{1},d,N^{\prime},d^{\prime}) and ( N , L 2 , d , N ′ , d ′ ) (N,L_{2},d,N^{\prime},d^{\prime}) BaseConv models then their composition f ∘ g f\circ g has an ( N , L 1 + L 2 , d , N ′ , d ′ ) (N,L_{1}+L_{2},d,N^{\prime},d^{\prime}) BaseConv model which can be computed by performing their models in succession, or ’stacking’.

###### Proof.

This result follows from noting that for any f ⁡ ( 𝒖 ) f(\bm{u}) which requires L 1 L_{1} layers to compute and that we can compute f ∘ g ⁡ ( 𝒖 ) = g ⁡ ( f ⁡ ( 𝒖 ) ) f\circ g(\bm{u})=g(f(\bm{u})) using the BaseConv model with L 2 L_{2} layers, yielding L 1 + L 2 L_{1}+L_{2} layers in total. ∎

#### H.3.1 BaseConv -Hyena Equivalence

We show that the equivalence between BaseConv and Hyena by showing that each layer can simulate the other’s computation using a constant number of layers.

###### Proposition H.12 .

For any input 𝐮 ∈ ℝ N × d \bm{u}\in\mathbbm{R}^{N\times d} and ( N , L , d , N ′ , d ) − (N,L,d,N^{\prime},d)- Hyena such that 𝐳 Hyena ≡ Hyena ⁡ ( 𝐮 ) \bm{z}_{\mathrm{Hyena}}\equiv\mathrm{Hyena}(\bm{u}) with a set of filters 𝐡 ℓ \bm{h}^{\ell} and linear projections 𝐩 ℓ \bm{p}^{\ell} as per Definition H.3 for ℓ ∈ [ L ] \ell\in[L] , there exists a ( N , 5 ​ L , d , N ′ + N , d ) (N,5L,d,N^{\prime}+N,d) - BaseConv model such that 𝐳 Hyena ≡ BaseConv ​ ( 𝐮 ) \bm{z}_{\mathrm{Hyena}}\equiv\textsc{BaseConv}(\bm{u}) .