Zoology: Measuring and Improving Recall in Efficient Language Models โ€” part 10/14

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

Further, any ๐„ i โˆˆ ( โ„ฌโ„ฌ โˆ— ) {\bf E}_{i}\in\left(\cal{BB}^{*}\right) can be expressed as a product of 2 โ€‹ log โก e โ€‹ n โ€‹ d 2\log{end} butterfly factor matrices. Then by Lemma H.16 and Lemma H.11 we can compute ๐„ i โ€‹ ๐’™ โ€ฒ {\bf E}_{i}\bm{x^{\prime}} in by stacking 2 โ€‹ log โก e โ€‹ n โ€‹ d 2\log{end} ( n , d , L , e โ€‹ n , d ) โˆ’ BaseConv \left(n,d,L,en,d\right)-\text{{BaseConv}} models each with L = ๐’ช โก ( 1 ) L=\mathcal{O}(1) . Because ๐„ {\bf E} has width w w , Lemma H.11 implies that composing with each ๐„ i {\bf E}_{i} for 1 โ‰ค i โ‰ค w 1\leq i\leq w constructs a final model with ๐’ช โก ( w โ€‹ log โก ( e โ€‹ n โ€‹ d ) ) \mathcal{O}(w\log(end)) layers. โˆŽ

Finally, the kaleidoscope hierarchy is related to linear arithmetic circuits via the following result. We note that in [ Dao et al., 2020 ] it is assumed that w = s w=s , yet inspection of the proof yields the following stronger result:

###### Theorem H.19 ( [ Dao et al., 2020 ] ) .

Let ๐Œ {\bf M} be an n ร— n n\times n matrix such that multiplication of ๐Œ {\bf M} times an arbitrary vector ๐ฎ \bm{u} can be be represented as ( n , s , ฮ” , w ) (n,s,\Delta,w) -linear arithmetic circuit ๐’ž \mathcal{C} . Then, ๐Œ โˆˆ ( โ„ฌโ„ฌ โˆ— ) ๐’ช โก ( w / n ) ๐’ช โก ( ฮ” ) {\bf M}\in\left(\cal{BB}^{*}\right)^{\mathcal{O}(\Delta)}_{\mathcal{O}(w/n)} .

We combine Theorem H.19 and Lemma H.18 to show that BaseConv can compute any linear arithmetic circuit with polylogarithmic factors in ฮ” \Delta .

###### Corollary H.20 .

For any ( n โ€‹ d , s , ฮ” , w ) (nd,s,\Delta,w) -linear arithmetic circuit ๐’ž \mathcal{C} that can be represented by a matrix ๐Œ โˆˆ โ„ n โ€‹ d ร— n โ€‹ d {\bf M}\in\mathbbm{R}^{nd\times nd} multiplied by a vector ๐ฑ โˆˆ โ„ n โ€‹ d \bm{x}\in\mathbbm{R}^{nd} , there exists an equivalent ( n , ฮ” โ€ฒ , d , w , d ) โˆ’ BaseConv \left(n,\Delta^{\prime},d,w,d\right)-\text{{BaseConv}} with ฮ” โ€ฒ = ๐’ช โก ( ฮ” โ€‹ log โก ( w ) ) \Delta^{\prime}=\mathcal{O}(\Delta\log(w)) such that ๐Œ โ€‹ ๐ฑ = BaseConv โ€‹ ( ๐ฎ , ๐ก ) {\bf M}\bm{x}=\textsc{BaseConv}\left({\bm{u},\bm{h}}\right) where ๐ฑ \bm{x} is the row major form of ๐ฎ โˆˆ โ„ n ร— d \bm{u}\in\mathbbm{R}^{n\times d} .

### H.5 General Arithmetic Circuits

We are now ready to prove the result that yields the equivalency between arithmetic circuits and BaseConv .

###### Theorem H.21 .

For any ( n โ€‹ d , s , ฮ” , w ) (nd,s,\Delta,w) -arithmetic circuit ๐’ž \mathcal{C} , there exists an equivalent ( N , ฮ” โ€ฒ , d , N โ€ฒ , d โ€ฒ ) โˆ’ BaseConv \left(N,\Delta^{\prime},d,N^{\prime},d^{\prime}\right)-\text{{BaseConv}} with N = n , ฮ” โ€ฒ = ๐’ช โก ( ฮ” โ€‹ log โก w ) N=n,\Delta^{\prime}=\mathcal{O}(\Delta\log{w}) , N โ€ฒ = ๐’ช โก ( w ) , d โ€ฒ = d N^{\prime}=\mathcal{O}(w),d^{\prime}=d that simulates ๐’ž \mathcal{C} .

For the readerโ€™s convenience, we begin with a proof sketch and then provide the details afterwards.

###### Proof Sketch of Theorem H.21 .

Let us layer ๐’ž \mathcal{C} so that each layer ๐’ž โ„“ \mathcal{C}_{\ell} for โ„“ โˆˆ [ L ๐’ž ] \ell\in[L_{\mathcal{C}}] either only has linear gates or multiplication gates, where the number of such layers L ๐’ž = ๐’ช โก ( ฮ” ) L_{\mathcal{C}}=\mathcal{O}(\Delta) . The composition of all ๐’ž โ„“ \mathcal{C}_{\ell} layers results in ๐’ž \mathcal{C} . We use ๐’› โ„“ + 1 โˆˆ โ„ w \bm{z}^{\ell+1}\in\mathbbm{R}^{w} to denote the output of the โ„“ \ell -th layer ๐’ž โ„“ \mathcal{C}_{\ell} which feeds as the input to the ( โ„“ + 1 ) (\ell+1) -th layer ๐’ž โ„“ + 1 \mathcal{C}_{\ell+1} . Here, we note that if we can simulate each ๐’ž โ„“ \mathcal{C}_{\ell} with BaseConv , then we can simulate the entire layered circuit ๐’ž \mathcal{C} due to Lemma H.11 .

Now, if the layer ๐’ž โ„“ lin \mathcal{C}_{\ell}^{\mathrm{lin}} is a linear layer (with only addition gates), then it can be represented by a matrix ๐‘ด โˆˆ โ„ w ร— w \bm{M}\in\mathbbm{R}^{w\times w} multiplied by ๐’› โ„“ โˆˆ โ„ w \bm{z}^{\ell}\in\mathbbm{R}^{w} (We can append with 0 0 s if necessary so that the input from the previous gates can be written as w w -length vector). Thus, we can apply Corollary H.20 to simulate ๐’ž โ„“ lin \mathcal{C}_{\ell}^{\mathrm{lin}} with an equivalent ( n , log โก w , d , ๐’ช โก ( log โก w ) , d ) โˆ’ BaseConv \left(n,\log{w},d,\mathcal{O}(\log{w}),d\right)-\text{{BaseConv}} model.

Next, if ๐’ž โ„“ mult \mathcal{C}_{\ell}^{\mathrm{mult}} instead consists of only the multiplication gates. Then, we note here that the output ๐’› โ„“ \bm{z}^{\ell} may not exactly equal the input to ๐’ž โ„“ mult \mathcal{C}_{\ell}^{\mathrm{mult}} . Nevertheless, we can apply a ๐’ช โก ( w ) \mathcal{O}(w) sparse linear map ๐‘ โˆˆ โ„ w ร— w {\bf R}\in\mathbbm{R}^{w\times w} so that ๐‘ โ€‹ ๐’› โ„“ {\bf R}\bm{z}^{\ell} yields vectors ๐’— 1 , ๐’— 2 , \bm{v}^{1},\bm{v}^{2}, and ๐’— 3 \bm{v}^{3} , where ๐’— 1 \bm{v}_{1} constitutes the โ€œfirstโ€ input to all the multiplication gates and ๐’— 2 \bm{v}_{2} constitutes all the โ€œsecondโ€ inputs while ๐’— 3 \bm{v}^{3} consists of all entries needed as inputs in the subsequent layers. That is, for the i i th gate in ๐’ž โ„“ mult \mathcal{C}_{\ell}^{\mathrm{mult}} , we compute ๐’— i 1 โ‹… ๐’— i 2 \bm{v}^{1}_{i}\cdot\bm{v}^{2}_{i} . This implies that for all the gates in ๐’ž โ„“ mult \mathcal{C}_{\ell}^{\mathrm{mult}} , we can simply compute ๐’— 1 โŠ™ ๐’— 2 \bm{v}_{1}\odot\bm{v}_{2} . To this end, we use the ๐š›๐šŽ๐š–๐šŽ๐š–๐š‹๐šŽ๐š› {\tt remember} primitive with constant number of layers from Proposition H.10 to define a ( n , ๐’ช โก ( log โก w ) , d , w , d ) โˆ’ BaseConv \left(n,\mathcal{O}(\log{w}),d,w,d\right)-\text{{BaseConv}} model that remembers ๐’— 3 \bm{v}^{3} while performing the Hadamard product of ๐’— 1 \bm{v}^{1} with ๐’— 2 \bm{v}^{2} .

Overall, we can then collect all the resulting BaseConv layers and compose them as in Lemma H.11 to simulate ๐’ž \mathcal{C} . Overall, the number of layers used is given by ๐’ช โก ( ฮ” โ€‹ log โก w ) \mathcal{O}(\Delta\log{w}) while the internal dimension remains fixed at w w . โˆŽ

Using the outline in the proof sketch, we now delve into a detailed analysis of the arithmetic circuit ๐’ž \mathcal{C} to an equivalent BaseConv model.

###### Proof of Theorem H.21 .

Let ๐’– โˆˆ โ„ n โ€‹ d \bm{u}\in\mathbbm{R}^{nd} be the input to the arithmetic circuit ๐’ž \mathcal{C} with depth ฮ” \Delta and width w w . We begin by rearranging the circuit into layers of addition and multiplication gates. That is, each layer ๐’ž โ„“ \mathcal{C}^{\ell} has either all addition gates or all multiplication gates. This allows us to readily apply the results from Section H.4 . Note here that we can assert that the number of such layers L ๐’ž = ๐’ช โก ( ฮ” ) L_{\mathcal{C}}=\mathcal{O}(\Delta) . Moreover, we construe the input to each such circuit as a vector of length w {w} by appending with extra 0s if necessary so that the composition of the layers results in a circuit equivalent to ๐’ž \mathcal{C} . See Fig. 8 for an example of such decomposition

Let ๐’› โ„“ โˆˆ โ„ w \bm{z}^{\ell}\in\mathbbm{R}^{w} denote the input to each layer ๐’ž โ„“ \mathcal{C}_{\ell} for โ„“ โˆˆ [ L ๐’ž ] \ell\in[L_{\mathcal{C}}] with ๐’› 1 โ‰ก ( ๐’– , ๐ŸŽ w โˆ’ n โ€‹ d ) \bm{z}^{1}\equiv(\bm{u},\bm{0}^{w-nd}) . It is important to note here that we may not have ๐’› โ„“ + 1 โ‰ก ๐’ž โ„“ โ€‹ ( ๐’› โ„“ ) \bm{z}^{\ell+1}\equiv\mathcal{C}_{\ell}(\bm{z}^{\ell}) since the inputs for gates at the ( โ„“ + 1 ) (\ell+1) -th layer may come from any of the previous layers. We now handle the case of layers with addition gates, multiplication gates, and the intermediate stage separately.

##### Addition Gates.

Let ๐’ž โ„“ lin \mathcal{C}_{\ell}^{\mathrm{lin}} denote an arbitrary linear layer which only contains the addition gates that takes in ๐’› โ„“ \bm{z}^{\ell} as input. We know that there exists a matrix ๐Œ โˆˆ โ„ w ร— w โ€ฒ {\bf M}\in\mathbbm{R}^{w\times w^{\prime}} such that we have ๐’ž โ„“ lin โ€‹ ( ๐’› โ„“ ) โ‰ก ๐Œ โ€‹ ๐’› โ„“ . \mathcal{C}_{\ell}^{\mathrm{lin}}(\bm{z}^{\ell})\equiv{\bf M}\bm{z}^{\ell}. Here, note here that we may need entries from the vector ๐’› โ„“ \bm{z}^{\ell} in subsequent layers. Let s s be the total number of such entries, then for at each index for such entries i โˆˆ [ w ] i\in[w] , we have the corresponding index i s โˆˆ [ s ] i_{s}\in[s] . We then append the i i th standard row vector into the matrix ๐Œ {\bf M} to get the matrix ๐Œ โ€ฒ โˆˆ โ„ w ร— ( w โ€ฒ + s ) {\bf M}^{\prime}\in\mathbbm{R}^{w\times(w^{\prime}+s)} so that we have ( ๐Œ โ€ฒ โ€‹ ๐’› โ„“ ) โ€‹ [ j ] = { ( ๐Œ โ€‹ ๐’› โ„“ ) โ€‹ [ j ] if โ€‹ j < w โ€ฒ ๐’› โ„“ โ€‹ [ i ] if โ€‹ j = w โ€ฒ + i s \left({\bf M}^{\prime}\bm{z}^{\ell}\right)[j]=\begin{cases}\left({\bf M}\bm{z}^{\ell}\right)[j]&\text{if }j<w^{\prime}\\ \bm{z}^{\ell}[i]&\text{if }j=w^{\prime}+i_{s}\end{cases} Here, note that we must have w โ€ฒ + s โ‰ค w w^{\prime}+s\leq w as w w is the width of the circuit. If needed, we then append the matrix ๐Œ โ€ฒ {\bf M}^{\prime} with all-zero rows ๐ŸŽ w \bm{0}^{w} so that we get the matrix ๐Œ โ€ฒโ€ฒ โˆˆ โ„ w ร— w {\bf M}^{\prime\prime}\in\mathbbm{R}^{w\times w} . Note here that we have thus preserved all entries needed in subsequent layers and incorporated the output of the โ„“ \ell th layer with the output ๐Œ โ€ฒโ€ฒ โ€‹ ๐’› โ„“ โ‰ก ๐’› โ„“ + 1 {\bf M}^{\prime\prime}\bm{z}^{\ell}\equiv\bm{z}^{\ell+1} serving as the input of the ( โ„“ + 1 ) (\ell+1) -th layer. Applying Corollary H.20 then yields an equivalent ( n , ๐’ช โก ( log โก w ) , d , w , d ) โˆ’ BaseConv \left(n,\mathcal{O}(\log{w}),d,w,d\right)-\text{{BaseConv}} model.

##### Multiplication Gates.

Next, we deal with the layer ๐’ž mult โ„“ \mathcal{C}^{\ell}_{\mathrm{mult}} of multiplication gates by collecting the two inputs to each multiplication gates as ๐’— 1 โ„“ , ๐’— 2 โ„“ \bm{v}_{1}^{\ell},\bm{v}_{2}^{\ell} . Note that for the input ๐’› โ„“ โˆˆ โ„ w \bm{z}^{\ell}\in\mathbbm{R}^{w} from the previous layer, we will again have entries that need to be used in the subsequent layers that we will denote as ๐’— 3 โ„“ \bm{v}_{3}^{\ell} . We thus need to permute the entries of ๐’› โ„“ \bm{z}^{\ell} to get the vector [ ๐’— 1 โ„“ : : ๐’— 2 โ„“ : : ๐’— 3 โ„“ ] [\bm{v}_{1}^{\ell}::\bm{v}_{2}^{\ell}::\bm{v}_{3}^{\ell}] so that we can remember ๐’— 3 โ„“ \bm{v}_{3}^{\ell} while taking the Hadamard product ๐’— 1 โ„“ โŠ™ ๐’— 2 โ„“ \bm{v}_{1}^{\ell}\odot\bm{v}_{2}^{\ell} . To this end, we can achieve this permutation of entries using a ๐’ช โก ( w ) \mathcal{O}(w) -sparse linear matrix 12 12 12 Each row of ๐‘ โ„“ {\bf R}^{\ell} has exactly one non-zero entry. ๐‘ โ„“ โˆˆ โ„ w ร— w {\bf R}^{\ell}\in\mathbbm{R}^{w\times w} with which is equivalently represented by an ( w , w , 1 , w ) (w,w,1,w) -linear arithmetic circuit that simply moves the appropriate wires from the previous layer. This can again be achieved by a equivalent ( n , ๐’ช โก ( log โก w ) , d , w , d ) โˆ’ BaseConv \left(n,\mathcal{O}(\log{w}),d,w,d\right)-\text{{BaseConv}} model. That is, ๐‘ โ„“ โ€‹ ๐’› โ„“ {\bf R}^{\ell}\bm{z}^{\ell} has the following form: ๐‘ โ„“ โ€‹ ๐’› โ„“ โ‰ก ( ๐’— 1 โ„“ ๐’— 2 โ„“ ๐’— 3 โ„“ ) . {\bf R}^{\ell}\bm{z}^{\ell}\equiv\begin{pmatrix}\bm{v}_{1}^{\ell}\\ \hline\cr\\ \bm{v}_{2}^{\ell}\\ \hline\cr\\ \bm{v}_{3}^{\ell}\end{pmatrix}. Next, we can now define a ( n , 1 , d , n , d ) โˆ’ BaseConv \left(n,1,d,n,d\right)-\text{{BaseConv}} which extracts ๐’— 1 โ„“ \bm{v}_{1}^{\ell} as the projection with the input to the remember primitive given by ๐’š โ„“ โ‰ก ( ๐’— 2 โ„“ , ๐’— 3 โ„“ , ๐ŸŽ ) \bm{y}^{\ell}\equiv(\bm{v}_{2}^{\ell},\bm{v}_{3}^{\ell},\bm{0}) . We then specify the remember primitive as ๐š›๐šŽ๐š–๐šŽ๐š–๐š‹๐šŽ๐š› ( ๐’š โ„“ : ๐’— 2 โ„“ , ๐’— 3 โ„“ , ๐’† 0 , ๐’— 1 โ„“ ) {\tt remember}\left(\bm{y}^{\ell}:\bm{v}_{2}^{\ell},\bm{v}_{3}^{\ell},\bm{e}_{0},\bm{v}_{1}^{\ell}\right) which computes the following ๐’› โ„“ + 1 \displaystyle\bm{z}^{\ell+1} โ‰ก ( ๐’— 1 โ„“ โŠ™ ( ๐’† 0 โˆ— ๐’— 2 โ„“ ) ๐’— 3 โ„“ ๐ŸŽ ) \displaystyle\equiv\begin{pmatrix}\bm{v}_{1}^{\ell}\odot(\bm{e}_{0}\ast\bm{v}_{2}^{\ell})\\ \hline\cr\\ \bm{v}_{3}^{\ell}\\ \hline\cr\\ \bm{0}\end{pmatrix} โ‰ก ( ๐’— 1 โ„“ โŠ™ ๐’— 2 โ„“ ๐’— 3 โ„“ ๐ŸŽ ) \displaystyle\equiv\begin{pmatrix}\bm{v}_{1}^{\ell}\odot\bm{v}_{2}^{\ell}\\ \hline\cr\\ \bm{v}_{3}^{\ell}\\ \hline\cr\\ \bm{0}\end{pmatrix} โ‰ก ๐’ž mult โ„“ โ€‹ ( ๐’› โ„“ ) โˆˆ โ„ w . \displaystyle\equiv\mathcal{C}^{\ell}_{\mathrm{mult}}(\bm{z}^{\ell})\in\mathbbm{R}^{w}. Using Proposition H.10 , we know that this requires a ( n , ๐’ช โก ( log โก w ) , d , w , d ) โˆ’ BaseConv \left(n,\mathcal{O}(\log{w}),d,w,d\right)-\text{{BaseConv}} which remembers the entries that will serve as inputs in subsequent layers while performing the Hadamard product ๐’— 1 โŠ™ ๐’— 2 \bm{v}^{1}\odot\bm{v}^{2} .

Overall, we can now stack all the resulting BaseConv layers and compose them as in Lemma H.11 to simulate ๐’ž \mathcal{C} . Overall, the number of layers blows up by ๐’ช โก ( ฮ” โ€‹ log โก w ) \mathcal{O}(\Delta\log{w}) while the internal dimension remains fixed at w w . โˆŽ

### H.6 The Retnet Reduction and Space Complexity for AR

We are now in a position to show that there exists an equivalent BaseConv model that can simulate a Retnet layer from Algorithm 6 . Recall that for an input sequence ๐’– โˆˆ โ„ N ร— d \bm{u}\in\mathbbm{R}^{N\times d} , we project the input using weight matrices ๐– A , ๐– C , ๐– V โˆˆ โ„ d ร— d {\bf W}_{A},{\bf W}_{C},{\bf W}_{V}\in\mathbbm{R}^{d\times d} to ๐€ , ๐‚ , ๐• โˆˆ โ„ N ร— d {\bf A},{\bf C},{\bf V}\in\mathbbm{R}^{N\times d} and compute the following recurrence (see line 6 in Algorithm 6 ): ๐’› n โ‰ก ฮณ ๐’› n โˆ’ 1 + ( ๐€ [ n , : ] ) โŠค ๐• [ n , : ] , \bm{z}^{n}\equiv\gamma\bm{z}^{n-1}+\left({\bf A}[n,:]\right)^{\top}{\bf V}[n,:], (6) where ๐’› n โˆˆ โ„ d ร— d \bm{z}^{n}\in\mathbbm{R}^{d\times d} . We unroll this recurrence to express each state ๐’› n \bm{z}^{n} in terms of ๐’– \bm{u} with coefficients given by ฮณ \gamma and the weight matrices ๐– A , ๐– C , ๐– V {\bf W}_{A},{\bf W}_{C},{\bf W}_{V} as follows: ๐’› 0 \displaystyle\bm{z}^{0} โ‰ก ( ( ๐’– ๐– A ) [ 0 , : ] ) โŠค ( ๐’– ๐– V ) [ 0 , : ] \displaystyle\equiv\left(\left(\bm{u}{\bf W}_{A}\right)[0,:]\right)^{\top}\left(\bm{u}{\bf W}_{V}\right)[0,:] โ‰ก ( ๐’– [ 0 , : ] ๐– A ) โŠค ( ๐’– [ 0 , : ] ) ๐– V \displaystyle\equiv\left(\bm{u}[0,:]{\bf W}_{A}\right)^{\top}\left(\bm{u}[0,:]\right){\bf W}_{V} โ‰ก ๐– A โŠค ( ๐’– [ 0 , : ] ) โŠค ( ๐’– [ 0 , : ] ) ๐– V \displaystyle\equiv{\bf W}_{A}^{\top}\left(\bm{u}[0,:]\right)^{\top}\left(\bm{u}[0,:]\right){\bf W}_{V} โ‰ก ๐– A โŠค ( ๐’– โŠค [ : , 0 ] ๐’– [ 0 , : ] ) ๐– V . \displaystyle\equiv{\bf W}_{A}^{\top}\left(\bm{u}^{\top}[:,0]\bm{u}[0,:]\right){\bf W}_{V}. Similarly, we have ๐’› 1 \displaystyle\bm{z}^{1} โ‰ก ฮณ ๐’› 0 + ๐– A โŠค ( ๐’– โŠค [ : , 1 ] ๐’– [ 1 , : ] ) ๐– V \displaystyle\equiv\gamma\bm{z}^{0}+{\bf W}_{A}^{\top}\left(\bm{u}^{\top}[:,1]\bm{u}[1,:]\right){\bf W}_{V} โ‰ก ฮณ ( ๐– A โŠค ( ๐’– โŠค [ : , 1 ] ๐’– [ 0 , : ] ) ๐– V ) + ๐– A โŠค ( ๐’– โŠค [ : , 1 ] ๐’– [ 1 , : ] ) ๐– V \displaystyle\equiv\gamma\left({\bf W}_{A}^{\top}\left(\bm{u}^{\top}[:,1]\bm{u}[0,:]\right){\bf W}_{V}\right)+{\bf W}_{A}^{\top}\left(\bm{u}^{\top}[:,1]\bm{u}[1,:]\right){\bf W}_{V} โ‰ก ๐– A โŠค ( ฮณ ( ๐’– โŠค [ : , 0 ] ๐’– [ 0 , : ] ) + ๐’– โŠค [ : , 1 ] ๐’– [ 1 , : ] ) ๐– V \displaystyle\equiv{\bf W}_{A}^{\top}\left(\gamma\left(\bm{u}^{\top}[:,0]\bm{u}[0,:]\right)+\bm{u}^{\top}[:,1]\bm{u}[1,:]\right){\bf W}_{V} We can then generalize this to n โˆˆ [ N ] n\in[N] to get ๐’› n โ‰ก ๐– A โŠค ( โˆ‘ i = 0 n ฮณ n โˆ’ i ๐’– โŠค [ : , i ] ๐’– [ i , : ] ) ๐– V . \bm{z}^{n}\equiv{\bf W}_{A}^{\top}\left(\sum_{i=0}^{n}\gamma^{n-i}\bm{u}^{\top}[:,i]\bm{u}[i,:]\right){\bf W}_{V}. (7) The above helps us infer that ๐’› n \bm{z}^{n} can be expressed as a polynomial in { ๐’– โก [ 0 , 0 ] , ๐’– โก [ 0 , 1 ] , โ€ฆ , ๐’– โก [ N โˆ’ 1 , d โˆ’ 1 ] } \{\bm{u}[0,0],\bm{u}[0,1],\ldots,\bm{u}[N-1,d-1]\} . For each polynomial, there exists an arithmetic circuit that computes the polynomial in a natural way, whence we can apply Theorem H.21 to get an equivalent BaseConv model.

###### Corollary H.22 .

For a RetNet model with ๐’ช โก ( d 2 ) \mathcal{O}(d^{2}) parameters and N N layers, there exists an equivalent BaseConv model that uses ๐’ช โก ( N โ€‹ d ) \mathcal{O}(Nd) parameters and ๐’ช โก ( N โ€‹ log โก d ) \mathcal{O}(N\log{d}) layers.

###### Proof.