actual chunk is substantially longer in the dataset (note the ellipsis).
510(k) SUBSTANTIAL EQUIVALENCE DETERMINATION DECISION SUMMARY ASSAY ONLY
TEMPLATE A. 510(k) Number: k180209 B. Purpose for Submission: New Device C.
Measurand: 1,5-Anhydroglucitol (1,5-AG) D. Type of Test: Quantitative,
colorometric, pyranose oxidase (PROD) E. Applicant: Diazyme Laboratories Inc.
F. Proprietary and Established Names: Diazyme 1,5-AG Assay G. Regulatory
Information: 1. Regulation section: 21 CFR 864.7470; Glycosylated hemoglobin
assay 2. Classification: Class II … [1,920 tokens of context from the PDF] …
Diazyme’s 1,5-AG assay uses the enzyme pyranose oxidase (PROD) to oxidize the
2nd position hydroxyl group of 1,5-AG and to detect the generated hydrogen
peroxide by colorimetry using peroxidase (POD). Type of Test:

##### SQUAD

(Question Answering). The Stanford Question Answering Dataset (SQUAD) can be
used to evaluate the reading comprehension of language models. The model is
given a passage of text and a question whose answer is contained in the
passage.

Because the models trained in this work are relatively small-scale (up to 1.3
billion parameters trained on 10 billion tokens) and not instruction fine-
tuned, they struggle to answer questions when asked directly. To make the task
more amenable to these raw language models, we first use GPT-4 to reformat the
questions to more closely resemble the next-token-prediction task the models
were trained on:

Can you rewrite this question and answer as a statement. Ensure that the
answer is the last part of the statement. \n \n Question: {question} \n\n
Answer: {answer} \n\n Rewrite:

For example, the question and answer “Question: Which NFL team represented the
AFC at Super Bowl 50? Answer: Denver Broncos” was rewritten by GPT-4 as “The
NFL team that represented the AFC at Super Bowl 50 was the Denver Broncos.” We
verify that the rewritten sentence does indeed end with the answer, discarding
any sentences where it does not (40% of questions).

We run the reformatting on 5,000 squad questions from the validation set,
yielding a final dataset of 2,984 questions formatted as next token
predictions.

Below we include one example of a zero-shot prompt. The reformatted question
is in bold.

For the third straight season, the number one seeds from both conferences met
in the Super Bowl. The Carolina Panthers became one of only ten teams to have
completed a regular season with only one loss, and one of only six teams to
have acquired a 15–1 record, while the Denver Broncos became one of four teams
to have made eight appearances in the Super Bowl. The Broncos made their
second Super Bowl appearance in three years, having reached Super Bowl XLVIII,
while the Panthers made their second Super Bowl appearance in franchise
history, their other appearance being Super Bowl XXXVIII. Coincidentally, both
teams were coached by John Fox in their last Super Bowl appearance prior to
Super Bowl 50. The team in Super Bowl 50 that had a 15-1 record was the

##  Appendix F Theoretical Results

###  F.1 Introduction

Our focus in this section will be on the theoretical results of the paper.
Specifically, we will show the equivalence of models Based and Mamba [5] with
BaseConv, a minimal gated-convolution operator [1, Definition 4.1], and prove
lower bounds for the MQAR problem [1, Section H.7.1] in various settings. We
begin by setting notation and introducing the theoretical formulations of the
models.

##### Notation.

We will be denoting the all $1$ row vector of size $k$, given by
$\begin{bmatrix}1&1&\ldots&1&1\end{bmatrix}$, and the all $0$ row vector of
size $k$, given by $\begin{bmatrix}0&0&\ldots&0&0\end{bmatrix}$, as
$\bm{1}^{k}$ and $\bm{0}^{k}$, respectively. We will also construe the
standard basis vector $\mathbf{e}_{i}$ as a column vector in these notes, and
adhere to the following matrix indexing convention: ${\bf M}[i,j]$ is the
entry in the $i$th row and the $j$th column, ${\bf
M}[i,:]\in\mathbb{F}^{1\times n}$ denotes the $i$th row, and ${\bf
M}[:,j]\in\mathbb{F}^{m\times 1}$ denotes the $j$th column of ${\bf
M}\in\mathbb{F}^{m\times n},$ where $\mathbb{F}$ is a field and the reader can
substitute $\mathbb{F}$ for $\mathbb{R}$ for convenience. For a matrix ${\bf
M}\in\mathbb{R}^{n\times m}$, we define the pair-wise Hadamard product of
columns of ${\bf M}$ as ${\bm{M}}\circ{\bm{M}}\in\mathbb{R}^{n\times m^{2}}$ ,
where

$\displaystyle({\bm{M}}\circ{\bm{M}})[:,i]:=\mathbf{M}[:,j]\odot\mathbf{M}[:,k]\quad\text{for}\quad
i\in[m^{2}],$ (15) $\displaystyle
j=\left\lfloor\frac{i-1}{m}\right\rfloor+1,\quad k=(i-1)\mod m+1.$

Moreover, we define the element-wise exponentiation of a matrix ${\bf M}$ as
$\exp[{\bf M}]$ where $\exp[{\bf M}]_{ij}=\exp({\bf M}_{ij})$. Next, we denote
the Hadamard product of vectors ${\bf u},{\bf v}\in\mathbb{F}^{n}$ as ${\bf
u}\odot{\bf v}$; the operation can be extended to matrices accordingly, and
for vectors ${\bf u},{\bf v}\in\mathbb{F}^{n}$, we denote their linear (or
acyclic) convolution as ${\bf u}\ast{\bf v}$

##### Arithmetic Circuit Notation.

We briefly introduce the notation of arithmetic circuits [81]. An arithmetic
circuit $\mathcal{C}$ with variables
$X\triangleq\\{x_{1},x_{2},\ldots,x_{n}\\}$ over a field $\mathbb{F}$ is
interpreted as a directed acyclic graph, where the input nodes are labelled by
either the variables from $X$ or constants from $\mathbb{F}$ and the internal
nodes are labelled by $+$ or $\times$ with the output being the polynomial
computed at the output node.

We shall also refer to the size of the circuit as the number of nodes, the
depth of the circuit as the length of the longest path between an input node
and the output node, and the width of the circuit as the number of parallel
operations in the circuit, or ‘wires’ which will be intersected by a
horizontal ‘cut’ through the circuit. Moreover, the degree of a circuit is
defined as the degree of the polynomial computed by the circuit. We summarize
this with the following definition:

######  Definition F.1.

An arithmetic circuit $\mathcal{C}$ is an $(n,s,\Delta,w)$-circuit if
$\mathcal{C}$ is an $n$-variate arithmetic circuit of size $s$ and of depth at
most $\Delta$, and width $w$.

###  F.2 The Models

We now introduce the definitions of the models Based and Mamba for the
reader’s convenience. Note that we have redefined these models to ensure
consistency with the notation presented above.

####  F.2.1 Based

The Based model combines two layer types: BaseConv and LinearAttention defined
below.

######  Definition F.2 (BaseConv [1]).

Given an input sequence ${\bm{u}}\in\mathbb{R}^{N\times d},$ where $N$ is the
sequence length and $d$ is the model dimension, a learned weight matrix
${\bm{W}}^{B}\in\mathbb{R}^{d\times d}$ and biases
${\bm{B}}^{B},{\bm{B}}^{K}\in\mathbb{R}^{N\times d}$ and a matrix of
convolution filters ${\bm{K}}\in\mathbb{R}^{N\times d}$, a BaseConvlayer
computes the following:

$\bm{z}^{\texttt{BaseConv}}:=({\bm{u}}{{\bm{W}}}^{B}+{\bm{B}}^{B})\odot\left({{\bm{K}}}\ast{\bm{u}}+{\bm{B}}^{K}\right)\in\mathbb{R}^{N\times
d},$ (16)

where the convolutions are applied across the input length $N$.

######  Definition F.3 (LinearAttention [24]).

Given an input sequence ${\bm{u}}\in\mathbb{R}^{N\times d},$ where $N$ is the
sequence length and $d$ is the model dimension, a set of linear
projections666By linear projections of a matrix
${\bm{u}}\in\mathbb{R}^{m\times n},$ we mean ${\bm{u}}{\bm{W}}+{\bm{B}}$ for
some weight matrix ${\bm{W}}\in\mathbb{R}^{n\times n}$ and bias
${\bm{B}}\in\mathbb{R}^{m\times n}$.
$\texttt{Projection}_{q},\texttt{Projection}_{k}\in\mathbb{R}^{d\times
d^{\prime}},\texttt{Projection}_{v}\in\mathbb{R}^{d\times d}$, where
$d^{\prime}$ is the feature dimension, the LinearAttention layer computes the
following:

$\bm{z}^{\texttt{LinearAttention}}:=\left(\overline{{\bm{Q}}}\
\overline{{\bm{K}}}^{\top}\right){\bm{V}}\in\mathbb{R}^{N\times d},$ (17)

where
${\bm{Q}}:=\texttt{Projection}_{q}({\bm{u}}),{\bm{K}}:=\texttt{Projection}_{k}({\bm{u}}),{\bm{V}}:=\texttt{Projection}_{v}({\bm{u}})$,
and we have

$\displaystyle\overline{{\bm{Q}}}$
$\displaystyle=[\bm{1},{\bm{Q}},{\bm{Q}}\circ{\bm{Q}}]\in\mathbb{R}^{N\times(1+d^{\prime}+d^{\prime
2})},$ $\displaystyle\overline{{\bm{K}}}$
$\displaystyle=[\bm{1},{\bm{Q}},{\bm{K}}\circ{\bm{K}}]\in\mathbb{R}^{N\times(1+d^{\prime}+d^{\prime
2})}.$

####  F.2.2 Mamba

We now introduce the Mamba model from [5].

######  Definition F.4 (Mamba [5]).

Given an input sequence ${\bm{u}}\in\mathbb{R}^{N\times d},$ where $N$ is the
sequence length and $d$ is the model dimension, the Mamba layer computes the
following:

$\bm{z}^{\texttt{Mamba}}:=\texttt{SSM}(\overline{{\bm{A}}},\overline{{\bm{B}}},{\bm{C}})({\bm{u}})\in\mathbb{R}^{N\times
d},$ (18)

with the parameters,
$\overline{{\bm{A}}}\in\mathbb{R}^{\overline{d}\times\overline{d}},\overline{{\bm{B}}}\in\mathbb{R}^{\overline{d}}$,
defined as

$\displaystyle\overline{{\bm{A}}}$
$\displaystyle:=\exp\left(\Delta{\bm{A}}\right),$ (19)
$\displaystyle\overline{{\bm{B}}}$
$\displaystyle:=\left(\Delta{\bm{A}}\right)^{-1}(\exp\left(\Delta{\bm{A}}\right)-{\bm{I}})\cdot\Delta{\bm{B}},$
$\displaystyle={\bm{A}}^{-1}(\exp\left(\Delta{\bm{A}}\right)-{\bm{I}})\cdot{\bm{B}},$

where $\overline{d}$, the state dimension, and
${\bm{A}}\in\mathbb{R}^{\overline{d}\times\overline{d}}$ are parameters of the
model and do not depend on the input ${\bm{u}}$, along with the following
input-dependent parameters
${\bm{B}},{\bm{C}}\in\mathbb{R}^{N\times\overline{d}},\Delta\in\mathbb{R}^{N\times
d}$ defined as

$\displaystyle{\bm{B}}$
$\displaystyle:=\texttt{Linear}_{N\times\overline{d}}({\bm{u}})\in\mathbb{R}^{\overline{d}},$
(20) $\displaystyle{\bm{C}}$
$\displaystyle:=\texttt{Linear}_{N\times\overline{d}}({\bm{u}})\in\mathbb{R}^{\overline{d}},$
$\displaystyle\Delta$ $\displaystyle:=\texttt{Linear}_{N\times
d}({\bm{u}})\in\mathbb{R}$

for $i\in[N]$. It is important to note here that the parameters
$\overline{{\bm{B}}},{\bm{C}},\Delta$ are causal777That is,
${\bm{B}}[i,:],C[i,:]$ and $\Delta[i,:]$ depend only on ${\bm{u}}[0\cdots
i-1]$. and we denote the dependence on upto the $i$th row of the input
${\bm{u}}$ for $i\in[N]$ by adding a subscript $i$ where the dependence for
$\overline{{\bm{A}}}_{i}\in\mathbb{R}^{\overline{d}\times\overline{d}}$ is
inherited from $\Delta_{i}$ in equation 19 and we denote
$\overline{{\bm{B}}}[i,:]=:{\bm{B}}_{i},\overline{{\bm{C}}}[i,:]=:{\bm{C}}_{i}$.

Finally, the SSM in equation 18 is realized as a linear recurrence. That is,
for every $(i,j)\in[N]\times[d]$, we have

$\displaystyle\bm{h}[i,j]$
$\displaystyle=\overline{{\bm{A}}}_{i}\bm{h}[i-1,j]+\overline{{\bm{B}}}_{i}{\bm{u}}[i,j]$
(21) $\displaystyle\bm{z}[i,j]$ $\displaystyle={\bm{C}}_{i}^{\top}\bm{h}[i,j]$

where $\bm{h}[i,j]\in\mathbb{R}^{\overline{d}},\bm{z}[i,j]\in\mathbb{R}$
denote the latent state and the output of the SSM in eq. 18, respectively.

###  F.3 Equivalency to BaseConv

For a polynomial with variables $X$ over a field $\mathbb{F}$, there exists a
corresponding arithmetic circuit $\mathcal{C}$ over $X$ that computes the
output of the polynomial at its terminating node when interpreted as a
directed acyclic graph. For any such arithmetic circuit $\mathcal{C}$ of size
$s$ and depth $\Delta$, [1, Theorem 4.2] showed the existence of an equivalent
BaseConv operator that uses $\tilde{\mathcal{O}}(s\Delta)$ parameters and
$\tilde{\mathcal{O}}(\Delta)$ layers. In the sequel, we use this result by
expressing the model outputs computed in equation 17 and equation 18 as
polynomials in ${\bm{u}}$ and $\exp\left({\bm{u}}\right)$ to show the
equivalency between these disparate models. We would now like to recall [1,
Theorem 4.2]. Before doing so, we first establish the following definitions
from [1].

######  Definition F.5.

An $\left(N,0pt,d,\tilde{N},\tilde{d}\right)-\text{\text{Gated Convolution
Model}}$ is a stacked sequence to sequence model with $L$ layers such that:

  1. 1.

input and output are $N\times d$ matrices,

  2. 2.

each layer’s operations consist of element-wise gating, convolution, linear
projection, and

  3. 3.

all the individual gated convolution layers take in $\tilde{N}\times\tilde{d}$
matrices and output $\tilde{N}\times\tilde{d}$ matrices. We refer to the tuple
$(\tilde{N},\tilde{d})$ as the _inner dimension_ of the model.

We also assume that the input $\bm{u}\in\mathbb{R}^{N\times d}$ is embedded
into $\bm{u}^{\prime}\in\mathbb{R}^{\tilde{N}\times\tilde{d}}$ such that

$\bm{u}^{\prime}[n,t]=\begin{cases}\bm{u}[n,t]\ \ \text{ if }n<N,\ t<d\ \\\ 0\
\ \text{ otherwise. }\end{cases}$

The output from the last layer
${\bm{z}}\in\mathbb{R}^{\tilde{N}\times\tilde{d}}$ is transformed into output
$\bm{y}\in R^{N\times d}$ by extracting the top left $N\times d$ entries in
${\bm{z}}$.

######  Theorem F.1 ([1], Theorem 4.2).

For any $(nd,s,\Delta,w)$-arithmetic circuit $\mathcal{C}$, there exists an
equivalent
$\left(N,\Delta^{\prime},d,\tilde{N},\tilde{d}\right)-\text{{BaseConv}}$ with
$N=n,\Delta^{\prime}=\mathcal{O}(\Delta\log{w})$,
$\tilde{N}=\mathcal{O}(w),\tilde{d}=d$ that simulates $\mathcal{C}$.

######  Remark F.1.

For notational simplicity, we will use ${\bm{u}}_{i,j}$ as the symbol for the
variable in the polynomial in ${\bm{u}}$ representing the entry
${\bm{u}}[i,j]$.

We now present the results showing equivalency between the models in section
F.2 and the BaseConv layer in equation 16 using theorem F.1.

######  Proposition F.1.

Given an input ${\bm{u}}\in\mathbb{R}^{N\times d}$, there exists an equivalent
$\left(N,O(\log^{2}(Nd)),d,O(N(d+d^{\prime 2}),O(\max(d,d^{\prime
2}))\right)-\text{{BaseConv}}$ that computes the output of the LinearAttention
layer with feature dimension $d^{\prime}$, cf. eq. 17.

###### Proof.

For the matrices ${\bm{Q}},{\bm{K}}\in\mathbb{R}^{N\times
d^{\prime}},{\bm{V}}\in\mathbb{R}^{N\times d}$ with the corresponding
projection matrices ${\bm{W}}^{Q},{\bm{W}}^{k}\in\mathbb{R}^{d\times
d^{\prime}},{\bm{W}}^{V}\in\mathbb{R}^{d\times d}$, a single BaseConv layer
that computes each of these matrices by simply taking identical projection and
${\bm{h}}^{s},{\bm{h}}^{l},{\bm{B}}^{s}\equiv 0$ and
${\bm{B}}^{\ell}\equiv\mathbbm{1}^{N\times d}$, the all $1$ matrix. Using the
remembering primitive [1, Proposition H.10], we can compute each of these in
turn while remembering others using $O(1)$ layers and $Nd$ parameters.

Next, we derive an expression for each entry $(i,j)\in[N]\times[d^{\prime 2}]$
of ${\bm{Q}}\circ{\bm{Q}},{\bm{K}}\circ{\bm{K}}\in\mathbb{R}^{N\times
d^{\prime 2}}$. From equation 15, observe that each entry of
${\bm{M}}\circ{\bm{M}}$ can be written as the product of entries from
${\bm{M}}$. Hence we have

$\displaystyle({\bm{Q}}\circ{\bm{Q}})[i,j]$
$\displaystyle\equiv{\bm{Q}}[i,k]\cdot{\bm{Q}}[i,\ell]$ (22)
$\displaystyle({\bm{K}}\circ{\bm{K}})[i,j]$
$\displaystyle\equiv{\bm{K}}[i,k]\cdot{\bm{K}}[i,\ell]$

for $k=\left\lfloor\frac{j-1}{d^{\prime}}\right\rfloor+1,\quad\ell=(j-1)\mod
d^{\prime}+1.$ Note, however, that we can simulate the above by first
increasing the inner dimension and copying over columns of ${\bm{Q}}$ to get
${\bm{Q}}_{1},{\bm{Q}}_{2}\in\mathbb{R}^{N\times d}$ defined as
${\bm{Q}}_{1}[i,j]:={\bm{Q}}[i,k]\text{ and
}{\bm{Q}}_{2}[i,j]:={\bm{Q}}[i,\ell]$ for
$k=\left\lfloor\frac{j-1}{d^{\prime}}\right\rfloor+1,\quad\ell=(j-1)\mod
d^{\prime}+1$ so that $({\bm{Q}}\circ{\bm{Q}})={\bm{Q}}_{1}\odot{\bm{Q}}_{2}$,
which, mutatis mutandis, also applies to $({\bm{K}}\circ{\bm{K}})$ We can
achieve the copying of the columns by simply using the projection matrix
${\bm{W}}^{B}$ and another permutation matrix ${\bm{P}}$. Apart from the
multiplication by ${\bm{P}}$, we only need to use $O(1)$ layers, and moreover,
since the circuit that computes ${\bm{P}}{\bm{u}}$ simply rearranges the
input, there exists a single BaseConv layer that computes ${\bm{P}}{\bm{u}}$
[1, Corollary H.20]. By the stacking lemma [1, Lemma H.11], we can stack these
layers to get a composition of the outputs so far to get a
$\left(N,O(1),d,O(N(d+d^{\prime 2}),O(\max(d,d^{\prime
2}))\right)-\text{{BaseConv}}$ model. Moreover, the concatenated matrices
$\overline{{\bm{Q}}},\overline{{\bm{K}}}$
$\in\mathbb{R}^{N\times(1+d^{\prime}+d^{\prime 2})}$ then take the addition of
the computed components so far which again takes $O(1)$ layers of BaseConv.

Finally, we can express each entry $(i,j)\in[N]\times[d]$ of the output of
LinearAttention as a polynomial as follows:

$\displaystyle{\bm{z}}_{i,j}({\bm{u}})$
$\displaystyle\equiv\sum_{m\in[1+d^{\prime}+d^{\prime
2}],n\in[N]}\overline{{\bm{Q}}}[i,m]\cdot\overline{{\bm{K}}}[n,m]\cdot{\bm{V}}[n,j].$
(23)

Thus, we can derive the arithmetic circuit that computes
${\bm{z}}_{i,j}({\bm{u}})$ by taking in the outputs of the BaseConv layers so
far as input and compute each of the terms inside the sum by multiplying the
outputs from all three and compute the sum using additional $\log{\lceil
Nd\rceil}$ depth. Each term inside the sum requires two multiplication gates
with depth $2$, each of which serve as inputs to the circuit with size $Nd$
computing the sum. Moreover, there are $N\cdot d$ such output gates each of
which is computed in parallel resulting in a circuit of size $O(N\cdot d)$,
depth $O(\log(Nd))$ and width $O(Nd)$. O Overall, applying theorem F.1 then
results in an equivalent $\left(N,O(\log^{2}(Nd)),d,O(N(d+d^{\prime
2}),O(\max(d,d^{\prime 2}))\right)-\text{{BaseConv}}$ model that computes
${\bm{z}}$. ∎

###  F.4 The Lower Bounds

In the sequel, we consider the multiple-query associative recall problem
($\mathrm{MQAR}$) as defined in [1, Section H.7.1]. We briefly recall the
definition here.

> Suppose we are given an input sequence $\bm{u}[0\cdots
> 3N-1]\triangleq\\{\left(\bm{k}_{0},\bm{v}_{0},\bm{q}_{0}\right),\ldots,\left(\bm{k}_{N-1},\bm{v}_{N-1},\bm{q}_{N-1}\right)\\}$
> with each $\bm{k}_{i},\bm{v}_{i},\bm{q}_{i}\in C$ is a token drawn from a
> vocabulary of size $c=|C|$. Our goal is then to check, for each $1\leq i\leq
> N-1$, whether there exists $0\leq j<i$ such that
> $\bm{q}_{i}\equiv\bm{k}_{j}$, and if so, output $\bm{v}_{j}$.

####  F.4.1 The Space Complexity of AR

We will start by providing a lower bound on the space complexity of solving
the standard associative recall (AR) problem. As AR is a subclass of MQAR,
this naturally provides a lower bound on the space complexity of MQAR as well.
Here, we formally recall the associative recall problem.

> The AR problem takes key-value pairs
> $\\{\bm{k}_{i},\bm{v}_{i}\\}_{i=0}^{n-1}$ along with a query $\bm{q}$
> appended at the end as input and the goal is to output $\bm{v}_{i}$ if
> $\bm{q}=\bm{k}_{i}$ for some $i\in[0,N-1]$.

We now require a randomized communication complexity lower bound result for
the index problem:

> The index problem has two agents, Alice and Bob, where Alice has a string
> $\bm{x}\in\\{0,1\\}^{n}$ and Bob has an index $i\in[n]$, and the goal for
> the players is to output the $i$-th entry $\bm{x}_{i}$. Moreover, we also
> require the communication to be one-way: only Alice is allowed to send a
> single message to Bob and Bob needs to output the answer.

We will make use of the following lower-bound result.

######  Theorem F.2 ([82]).

The one-way randomized communication complexity888The randomized communication
complexity of function $f$ is defined as
$\min_{\pi}\left\lVert\pi\right\rVert$, where $\pi$ ranges over all randomized
protocols that can solve $f$ with probability of success at least $2/3$. of
the index problem for sending an $n$-length bit string is $\Omega(n)$.

####  F.4.2 Lower Bound for Recurrent Models

We now use theorem F.2 to first provide a lower bound on the number of bits
required by the following class of models to solve AR.

######  Definition F.6 (Recurrent Models).

A model $\mathcal{M}$ taking an input ${\bm{u}}\in\mathbb{R}^{N\times d}$,
where $N$ is the input length and $d$ is the model dimension, is termed a
_recurrent model_ if its $i$-th state, representing the output at location
$i$, ${\bm{Z}}_{\mathcal{M}}^{i}\in\mathbb{R}^{\tilde{d}}$, with $\tilde{d}$
denoting the state size, is determined exclusively by the preceding elements
of the input ${\bm{u}}[0\ldots i-1]$. The state ${\bm{Z}}_{\mathcal{M}}^{i}$
represents the accumulated information of the model depending on the inputs up
to the $i$-th element, and is distinct from learned parameters that are static
with respect to the input sequence.

Specifically, ${\bm{Z}}_{\mathcal{M}}^{i}({\bm{u}})=\phi({\bm{u}}[0\ldots
i-1])$, indicating that the state is a function of the input history but not
of the entire input sequence simultaneously. Moreover, we can express this as:

${\bm{Z}}_{\mathcal{M}}^{i}({\bm{u}})=f_{\mathcal{M}}^{i}({\bm{Z}}_{\mathcal{M}}^{i-1},{\bm{u}}[i]),$
(24)

for a sequence of functions $\\{f_{\mathcal{M}}^{i}\\}_{i\in[N]}$, where each
function is tailored to evolve the state based on the immediate past state and
the current input.

######  Remark F.2.

Note that definition F.6 excludes models that inherently require the entire
input sequence for computation at any state, such as those based on non-causal
convolutional operations over the full input.

######  Theorem F.3.

Any recurrent model $\mathcal{M}$ (definition F.6) that solves AR requires
$\max_{i}\left\lvert{\bm{Z}}_{\mathcal{M}}^{i}\right\rvert$ to be at least
$\Omega(N)$-bits.

###### Proof.

Consider an instance $(\bm{x},i)$ of the index problem with
$\bm{x}\in\\{0,1\\}^{N}$. We now describe the corresponding instance of the AR
problem:

$\\{j,\bm{x}_{j}\\}_{j=0}^{N-1},i.$ (25)

Next, consider the following one-way protocol for solving the index problem
using the regressive model $\mathcal{M}$. Alice with their access of
$\bm{x}\in\\{0,1\\}^{N}$ generate an input for AR (without the query) as in
equation 25. Alice then runs the model $\mathcal{M}$ on
$\\{i,\bm{x}_{j}\\}_{j=0}^{N-1}$ and sends the memory content of running the
model $\mathcal{M}$ to Bob. This should include the state
${\bm{Z}}^{N-1}_{\mathcal{M}}$ of size $\tilde{d}$ as we can reasonably assume
that both have access to the set of functions
$\\{f_{\mathcal{M}}^{j}\\}_{j\in[N]}$. Since we assume that this model solves
AR, the output ${\tt Out}[N,:]=\bm{x}_{i}$ should contain the associated value
of $i$. Here, Bob can compute ${\tt Out}[N,:]$ by using the memory content
sent by Alice and applying the function $f^{N}$ as follows.

$\bm{x}_{i}={\tt Out}[N,:]=f^{N}({\bm{Z}}^{N-1},\bm{u}[N]).$

That is, the total number of bits that are communicated in this protocol is
$\left\lvert{\bm{Z}}_{\mathcal{M}}^{N-1}\right\rvert$. Now, if
$\max_{j}\left\lvert{\bm{Z}}_{\mathcal{M}}^{j}\right\rvert$ is $o(N)$ bits, we
have shown that a one-way communication protocol exists for solving the index
problem exists that uses $o(N)$ communication complexity. This contradicts
theorem F.2 and hence, we conclude that the model $\mathcal{M}$ solving AR
also needs $\Omega(N)$ bits. ∎

######  Corollary F.1.

Given an input ${\bm{u}}\in\mathbb{R}^{N\times d}$ to the AR problem, a causal
Mamba model with all entries in its computation taking $O(1)$ bits needs
$d+\overline{d}\geq\Omega(N)$ to solve AR.

###### Proof.

We will first show that causal Mamba is a recurrent model. To see this, first
observe equation 21 and note the fact that the input-dependent parameters
$\overline{{\bm{A}}},\overline{{\bm{B}}},{\bm{C}},\Delta$ are causal as
mentioned in definition F.4.

Next, due to equation 21, in order to compute
${\bm{z}}_{N,:}\in\mathbb{R}^{d}$, we need
${\bm{C}}_{N}\in\mathbb{R}^{\overline{d}},\overline{{\bm{B}}}_{N}\in\mathbb{R}^{\overline{d}}$
and $\Delta_{N}\in\mathbb{R}^{d}$ along with
${\bm{h}}[N-1,:]\in\mathbb{R}^{\overline{d}}$. Here, we have the $(N-1)$-st
state ${\bm{Z}}_{\texttt{Mamba}}^{N-1}\in\mathbb{R}^{3\overline{d}+d}$ given
by

${\bm{Z}}_{\texttt{Mamba}}^{N-1}:=\\{{\bm{h}}[i-1,:],\Delta^{1}_{N},\overline{{\bm{B}}}^{1}_{N},{\bm{C}}^{1}_{N}\\},$

where $\Delta^{1}_{N},\overline{{\bm{B}}}^{1}_{N},{\bm{C}}^{1}_{N}$ are all
linear functions of ${\bm{u}}[0\cdots N-1]$ that we receive from the
$(N-1)$-st state and we compute
$\Delta^{2}_{N},\overline{{\bm{B}}}^{2}_{N},{\bm{C}}^{2}_{N}$ as linear
functions of ${\bm{u}}[N]$ so that we have
$\Delta_{N}=\Delta^{1}_{N}+\Delta^{1}_{N},\overline{{\bm{B}}}_{N}=\overline{{\bm{B}}}^{1}_{N}+\overline{{\bm{B}}}^{2}_{N},{\bm{C}}_{N}={\bm{C}}^{1}_{N}+{\bm{C}}^{2}_{N}$.
We can then define the function $f^{N}$ as follows:

$\displaystyle{\bm{Z}}_{\texttt{Mamba}}^{N}[j]$
$\displaystyle=\exp(\Delta_{N}[j]{\bm{A}})\bm{h}[N-1,j]+\overline{{\bm{B}}}_{N}{\bm{u}}[N,j]$
$\displaystyle=\overline{{\bm{A}}}_{N}\bm{h}[N-1,j]+\overline{{\bm{B}}}_{N}{\bm{u}}[N,j],$
$\displaystyle{\tt Out}[N,j]$
$\displaystyle=f^{N}({\bm{Z}}_{\texttt{Mamba}}^{N-1})[j]={\bm{C}}_{N}^{\top}{\bm{Z}}_{\texttt{Mamba}}^{N}[j].$

Thus, due to theorem F.3, we can conclude that
$\left\lvert{\bm{Z}}_{\texttt{Mamba}}^{N-1}\right\rvert$ does require
$\Omega(N)$-bits to solve AR. Finally, assuming each entry of
${\bm{Z}}_{\texttt{Mamba}}^{N-1}$ needs $O(1)$ bits to represent, the overall
state ${\bm{Z}}_{\texttt{Mamba}}^{N-1}$ needs $O(d+\overline{d})$ to
represent, which completes the proof of the claim. ∎

####  F.4.3 Lower Bound on the Number of Layers for AR

Next, we will again use theorem F.2 to provide a better bound on the number of
layers required to solve AR.

######  Theorem F.4.

Given an input ${\bm{u}}\in\\{0,1\\}^{N\times d}$ to the AR problem with any
encoding such that $\log{c}\leq d\leq 2^{(\log{N})^{1-\epsilon}}$ for
$\epsilon>0$, and $c$ possible tokens from the vocabulary with $c\leq N$, a
data-independent BaseConv model with model parameters taking $O(\log{N})$ bits
needs $\Omega(\epsilon\log\log{N})$ layers to solve AR.

###### Proof.

For a BaseConv model that solves AR using $L$ layers, by definition, there
exists a polynomial $P({\bm{u}})$ of degree at most $2^{L}$ that solves AR for
any ${\bm{u}}\in\\{0,1\\}^{N\times d}$999Since BaseConv is data independent,
note that the polynomial $P(\cdot)$ is defined once we fix $N$ and $d$.. This
is because for the output of the $i$th layer of BaseConv, given by
${\bm{Z}}_{\texttt{BaseConv}}^{i}$, we have

${\bm{Z}}_{\texttt{BaseConv}}^{i}({\bm{Y}}_{\mathcal{M}}^{i-1})\equiv
P^{i}({\bm{Z}}_{\texttt{BaseConv}}^{i-1}),\quad\deg(P^{i})\leq 2,$

for some polynomial $P^{i}$ of degree $2$ which simply takes the inner
products allowing the model to solve AR, where
${\bm{Z}}_{\texttt{BaseConv}}^{0}:={\bm{u}}$. Further, for such a model with
$L$ layers, by composition, the output of the $i$-th layer for $i\in[L]$ is
also a polynomial over the input ${\bm{u}}$ and has degree at most $2^{i}$. At
the end, we have a polynomial $P({\bm{u}})$ of degree $\leq 2^{L}$ for
${\bm{u}}\in\\{0,1\\}^{N\times d}.$ As in the proof of theorem F.3, again take
the instance instance $(\bm{x},i)$ of the index problem with
$\bm{x}\in\\{0,1\\}^{N}$ and the corresponding instance of the AR problem as
before

${\bm{u}}:=\\{j,\bm{x}_{j}\\}_{j=0}^{N-1},i.$ (26)

Next, we build the following one-way protocol for solving the index problem
using the BaseConv model from the hypothesis that it solves AR. Alice with
their access of $\bm{x}\in\\{0,1\\}^{N}$ will again generate an input $\bm{u}$
for AR (without the query) as in equation 26.

Alice first takes the values
${\bm{a}}:={\bm{u}}[0:N-2,:]\in\\{0,1\\}^{(N-1)\times d}$ and substitutes
these known $(N-1)d$ values to define the following polynomial:

$\
Q({\bm{u}}_{N-1,0},\ldots,{\bm{u}}_{N-1,d-1})=P({\bm{a}},{\bm{u}}_{N-1,0},\ldots,{\bm{u}}_{N-1,d-1}).$
(27)

Here, note that $Q$ is a polynomial in $d$ variables that correspond to the
values ${\bm{u}}[N-1,:]$ that Bob has and trivially has degree $D\leq 2^{L}$.
Now, Alice can run the model $\mathcal{M}$, retrieve the coefficients of $Q$,
and send it to Bob. Since we assume that $P$ solves AR, Bob can take the
coefficients of $Q$ and substitute ${\bm{u}}[N-1,:]$ to $Q$ to compute
$P({\bm{u}})$ which is the associated value of $i$.

Here, the polynomial $Q$ that Alice sends has at most $d^{2^{L}}$ coefficients
as each term in $Q$ can have degree at most $2^{L}$. If each such coefficient
has $B$ bits, then using theorem F.2, the total number of bits being
communicated must satisfy $B\cdot d^{2^{L}}\geq\Omega(N)$. This follows from
the fact that if $B\cdot d^{2^{L}}\leq o(N)$, then since the associated value
of $i$ in equation 26 is the answer to the indexing problem, we have shown
that a one-way communication protocol for solving the index problem uses
$o(N)$ communication complexity, which then contradicts theorem F.2. Thus, we
must have

$B\cdot d^{2^{L}}\geq\Omega(N)\implies
2^{L}\log(d)\geq\log\left(\frac{N}{B}\right)-O(1).$

Taking logarithm of both sides then yields

$\displaystyle L$
$\displaystyle\geq{\log\left(\frac{\log\left(\frac{N}{B}\right)}{\log\left(d\right)}\right)}-O(1)\geq{\log\left(\frac{\log{N}-\log{B}}{\log\left(d\right)}\right)}-O(1)$
$\displaystyle\geq{\log\left(\frac{\log{N}-\log{B}}{(\log{N})^{1-\epsilon}}\right)},$
(28)

where we use the fact that $d\leq 2^{(\log{N})^{1-\epsilon}}$ for any
$\epsilon>0$ in equation 28.

Moreover, as the model parameters are assumed to be $O(\log{N})$ bits, any
coefficient in $Q$ should have absolute value at most
$\left(2^{O(\log{N})}\cdot Nd\right)^{2^{L}}$ as each coefficient can be a
product of at most $Nd$ variables. That is, for some $\alpha>0$, we have the
following bound on each coefficient:

$2^{B}\leq(N^{\alpha+1}d)^{2^{L}}\leq(N^{(\alpha+2)2^{L}})$

where the last equality uses the fact that $d\leq N$. We thus have

$\log(B)\leq\log(\alpha+2)+L+\log\log{N}.$ (29)

Substituting equation 29 to equation 28, we get

$\displaystyle
L\geq\log\left(\frac{\log{N}-\log(\alpha+2)-L-\log\log{N}}{(\log{N})^{1-\epsilon}}\right)$
(30)

Now, if $L>\log\log{N}$, we are done. Otherwise, if $L\leq\log\log{N}$, then
we can substitute this to equation 30 to get

$\displaystyle L$
$\displaystyle\geq\log\left(\frac{\log{N}-\log(\alpha+2)-2\log\log{N}}{(\log{N})^{1-\epsilon}}\right)$
$\displaystyle=\log\left(\log{N}-\log(\alpha+2)-2\log\log{N}\right)-(1-\epsilon)\log\log{N}$
(31)

We now claim that first term in equation 31 satisfies the following:

$\log\left({\log{N}-\log(\alpha+2)-2\log\log{N}}\right)\geq(1-\frac{\epsilon}{2})\log\log{N}.$
(32)

To see this, note that, for sufficiently large enough $N$, the following
holds:

$\displaystyle\frac{\log{N}}{2}\geq\log(\alpha+2)+2\log\log{N},$

hence, we get

$\log\left({\log{N}-\log(\alpha+2)-2\log\log{N}}\right)\geq\log\left(\frac{\log{N}}{2}\right)\geq\log\log{N}-1\geq(1-\frac{\epsilon}{2})\log\log{N}.$

This proves the claim in equation 32. Finally, using equation 32, equation 31
leads to the following:

$L\geq(1-\frac{\epsilon}{2})\log\log{N}-(1-\epsilon)\log\log{N}=\frac{\epsilon}{2}\log\log{N},$

which still provides the lower bound $L=\Omega(\epsilon\log\log{N})$, as
desired. ∎

######  Remark F.3.

We remark that it is possible to extend theorem F.4 to any model whose output
from each layer is a polynomial of some degree $\Delta\geq 2$ ot get a lower
bound of $\Omega(\epsilon\log\log{N}/\log{\Delta})$.

####  F.4.4 Lower Bound on the Number of Layers for $\mathrm{MQAR}$ with
$d=\log_{2}{c}$

##### Setup.

We take $d=\log_{2}{c}$ to encode all $c$ possible tokens from $C$. That is,
all the $2^{d}$ possible $d$-bit vectors can appear as a token in the input
for $\mathrm{MQAR}$. We will show that data-independent BaseConv needs
$\Omega(\log{d})$ = $\Omega(\log{\log{c}})$-layers to solve this setting of
$\mathrm{MQAR}$, while Attention (+ReLU) can solve this in $O(1)$ layers.

We first provide the trivial solution using Attention (+ReLU).

######  Proposition F.2.

Attention (with linear biases and ReLU) followed by two layers of MLPs can
solve MQAR for an input sequence $\bm{u}\in\\{0,1\\}^{3N\times d}$ such that
$d=\log_{2}(c)$ in $O(1)$ layers.

###### Proof.

Given a row ${\bm{u}}[i,:]\in\\{0,1\\}^{d}$, we express each row as
${\bm{w}}[i,:]\in\\{-1,1\\}^{d}$ by applying the projection
${\bm{u}}{\bm{W}}+{\bm{B}}$, where
${\bm{W}}:=\operatorname{diag}(2,\ldots,2)\in\mathbb{R}^{d\times d}$ and the
bias matrix ${\bm{B}}$ is the matrix of all $-1$’s so that
${\bm{w}}[i,j]=2{\bm{u}}[i,j]-1$. Then, we can specify the query and key
projection matrices ${\bf Q},{\bf K},{\bf V}\in\mathbb{R}^{3N\times d}$ as
follows:

$\begin{aligned} {\bf
K}[i,:]&\equiv\begin{cases}{\bm{w}}[i,:]={\bm{k}}_{\lfloor
i/3\rfloor}&\text{if }i\equiv 0\mod 3\\\ \bm{0}&\text{otherwise}\end{cases}\\\
{\bf Q}[i,:]&\equiv\begin{cases}{\bm{w}}[i,:]={\bm{q}}_{\lfloor
i/3\rfloor}&\text{if }i\equiv 2\mod 3\\\ \bm{0}&\text{otherwise}\end{cases}\\\
{\bf V}[i,:]&\equiv\begin{cases}{\bm{w}}[i+1,:]={\bm{v}}_{\lfloor
i/3\rfloor}&\text{if }i\equiv 0\mod 3\\\
\bm{0}&\text{otherwise}\end{cases}\end{aligned},$

where the values are shifted to the corresponding key index. Computing the
pair-wise inner products then yields

${\bf QK}^{\top}[i,j]\equiv\begin{cases}\langle\bm{q}_{\lfloor
i/3\rfloor},\bm{k}_{\lfloor j/3\rfloor}\rangle&\text{if }i\equiv 2\mod 3\text{
and }j\equiv 0\mod 3\\\ \bm{0}&\text{otherwise}\end{cases}$

However, since both $\bm{q}_{\lfloor i/3\rfloor},\bm{k}_{\lfloor
j/3\rfloor}\in\\{-1,1\\}^{d}$, we have $\langle\bm{q}_{\lfloor
i/3\rfloor},\bm{k}_{\lfloor j/3\rfloor}\rangle\leq d$ with equality iff
$\bm{q}_{\lfloor i/3\rfloor}\equiv\bm{k}_{\lfloor j/3\rfloor}$. We then
subtract off $d-1$ from each of the $3N\times 3N$ entries by taking the bias
${\bf B}\in\mathbb{R}^{3N\times 3N}$ as the matrix with each entry $-d+1$. Let
${\bf Z}:=\textsc{ReLU}({\bf QK}^{\top}+{\bf B})$ so that we have

${\bf Z}[i,j]=\mathbbm{1}\\{\bm{q}_{\lfloor i/3\rfloor}\equiv\bm{k}_{\lfloor
j/3\rfloor}\\}.$

Next, as we may have multiple matches and we only need to return $1$, we
modify ${\bm{Z}}$ by multiplying with the matrices
${\bm{W}}_{1},{\bm{W}}_{2}\in\mathbb{R}^{d\times d}$ and adding the bias
${\bm{B}}\in\mathbb{R}^{d\times d}$ defined as follows:

${\bm{W}}_{1}[k,j]:=\begin{cases}1&\text{if }k\geq j\\\
0&\text{otherwise}\end{cases},\quad{\bm{W}}_{2}[\ell,k]:=\begin{cases}-1&\text{if
}k=0\\\ 1&\text{if }k=\ell,\ell\neq 0\\\
0&\text{otherwise}\end{cases},\quad{\bm{B}}[i,j]=1.$

For ${\bm{Z}}_{1}:={\bm{Z}}{\bm{W}}_{1}$ and
${\bm{Z}}_{2}:={\bm{Z}}{\bm{W}}_{1}{\bm{W}}_{2}$, we have:

$\displaystyle{\bm{Z}}_{1}[i,j]$
$\displaystyle=\sum_{k}{\bm{Z}}[i,k]{\bm{W}}_{1}[k,j]=\sum_{k\geq
j}{\bm{Z}}[i,k],$ $\displaystyle{\bm{Z}}_{2}[i,j]$
$\displaystyle=\sum_{k}{\bm{Z}}_{1}[i,k]{\bm{W}}_{2}[k,j]={\bm{Z}}_{1}[i,j]-{\bm{Z}}_{1}[i,0].$

That is, each entry in ${\bm{Z}}_{1}$ sums the entries in the row that are at
the same or higher column index while each column in ${\bm{Z}}_{2}$ subtracts
the first entry—the sum of all entries in the row—from each entry in the row.
Semantically, for each row in ${\bm{Z}}_{1}$, the entries from $0$ to the
index of the first match must have the same value, and thus, are the only non-
negative entries in ${\bm{Z}}_{2}$. Next, we add the bias and activate under
ReLU to get ${\bm{Z}}^{\prime}\in\mathbb{R}^{3N\times d}$:

${\bm{Z}}^{\prime}[i,k]:=\textsc{ReLU}({\bm{Z}}_{2}+{\bm{B}})[i,k]=\begin{cases}1&\text{if
}k\leq\min\\{j\lvert\ {\bm{q}}_{\lfloor i/3\rfloor}\equiv{\bm{k}}_{\lfloor
j/3\rfloor}\\}\\\ 0&\text{otherwise.}\end{cases}$

Now, we multiply by the weight matrix ${\bm{W}}_{3}\in\mathbb{R}^{3N\times d}$
defined as

${\bm{W}}_{3}[k,j]:=\begin{cases}-1&\text{if }k=j+1\\\ 1&\text{if }k=j\\\
0&\text{otherwise}\end{cases}$

This yields the retriever
$\overline{{\bm{Z}}}={\bm{Z}}^{\prime}{\bm{W}}_{3}\in\mathbb{R}^{3N\times d}$
given by

$\overline{{\bm{Z}}}[i,k]:=\sum_{\ell}{\bm{Z}}^{\prime}[i,\ell]{\bm{W}}_{3}[\ell,k]={\bm{Z}}^{\prime}[i,k]-{\bm{Z}}^{\prime}[i,k+1]=\mathbbm{1}\\{k=\min\\{j\lvert\
{\bm{q}}_{\lfloor i/3\rfloor}\equiv{\bm{k}}_{\lfloor j/3\rfloor}\\}\\}.$

Finally, we multiply with the values ${\bf V}$ to get

$(\overline{{\bm{Z}}}{\bf V})[i,:]\equiv\overline{{\bm{Z}}}[i,:]{\bf
V}\equiv\overline{{\bm{Z}}}[i,j^{*}]\cdot{\bf
V}[j^{*},:]\equiv\begin{cases}\bm{v}_{j^{*}}&\text{if }{\bm{q}}_{\lfloor
i/3\rfloor}\equiv{\bm{k}}_{\lfloor j^{*}/3\rfloor},j^{*}=\min\\{j\lvert\
{\bm{q}}_{\lfloor i/3\rfloor}\equiv{\bm{k}}_{\lfloor j/3\rfloor}\\}.\\\
\bm{0}&\text{if no such $j^{*}$ exists.}\end{cases}$

That is, the row corresponding to the query returns the value associated to
the first matching key. Thus, the model with Attention (computing ${\bm{Z}}$)
followed by two MLPs computing ${\bm{Z}}^{\prime}$ and $\overline{{\bm{Z}}}$,
respectively, solves the MQAR problem. ∎

Next, we relate the output of $L$ layers of BaseConv to the degree of the
polynomial that it computes.

######  Lemma F.1.

For any input sequence $\bm{u}$, there exists a multilinear polynomial
equivalent (over Boolean inputs) to the polynomial computed by $L$ layers of
BaseConv with degree at most $2^{L}$.

###### Proof.

Let $P(\bm{u})$ be the polynomial computed by $L$ layers of BaseConv. Since
the output of a single layer of BaseConv is equivalent to a polynomial over
the input variables with degree at most $2$, composing $L$ such layers yields
a polynomial of degree at most $2^{L}$. However, $P(\bm{u})$ need not be multi
linear, but the polynomial defined as

${Q}(\bm{u}):=(\cdots((P(\bm{u})\mod(u_{1}^{2}-u_{1}))\mod(u_{2}^{2}-u_{2}))\cdots)\mod(u_{3Nd}^{2}-u_{3Nd})$

is equivalent to $P(\bm{u})$ as $(u_{i}^{2}-u_{i})$ evaluates to $0$ for each
input var $u_{i}\in\\{0,1\\}$. However,
$\deg({Q}(\bm{u}))\leq\deg(P(\bm{u}))$, and thus, the claim holds. ∎

We now relate the MQAR (in the above setting) to the degree of the polynomial
that it computes.

######  Lemma F.2.

The MQAR problem with $d=\log_{2}(c)$ is represented by a multi-linear
polynomial of degree $2d+1$.

###### Proof.

We will start by specifying the obvious Boolean circuit that solves MQAR.
First, we take the XNOR of keys and queries bitwise as follows.

$\bm{x}^{ij}={\bm{q}_{i}\ {\tt xnor}\
\bm{k}_{j}}:=\left(\bm{q}_{i}\wedge\bm{k}_{j}\right)\vee\left(\neg\bm{q}_{i}\wedge\neg\bm{k}_{j}\right)\text{
for }i>j,$ (33)

where, for ${\bm{x}},{\bm{y}}\in\\{0,1\\}^{d}$, we have

$[{\bm{x}}\ {\tt xnor}\ {\bm{y}}][k]:=\begin{cases}1&\text{if
}{\bm{x}}[k]={\bm{y}}[k]\\\ 0&\text{othwerise}\end{cases}$

That is, each bit from $\bm{x}^{ij}$ is set to $1$ iff the corresponding bits
from $\bm{q}_{i}$ and $\bm{k}_{j}$ match. Next, we take the AND of the
$d$-bits to get

$\bm{y}^{ij}:=\bigwedge_{k\in[d]}\bm{x}^{ij}_{k},i>j.$ (34)

Thus, $\bm{y}^{ij}$ is set to $1$ iff the query $\bm{q}_{i}$ matches with the
key ${\bm{k}}_{j}$. Finally, we AND with each bit of the values to get the
output $\bm{z}^{ij}$ with the $k$th bit for $k\in[d]$ given by

$\bm{z}^{ij}_{k}:=\bm{y}_{ij}\wedge[\bm{v}_{j}]_{k}.$ (35)

Thus, the output of the circuit can be represented as

$\bm{z}^{ij}=\begin{cases}\bm{v}_{i}&\text{if
}\bm{q}_{i}\equiv\bm{k}_{j},i>j\\\ \bm{0}&\text{otherwise.}\end{cases}$

We can now directly translate the above circuit into a multi-linear
polynomial. With slight abuse of notation, we have the following
correspondence for equation 34, where
$\bm{u}_{i}\equiv\bm{q}_{i},\bm{u}_{j}\equiv\bm{k}_{j},i>j$ and we use
$\bm{u}_{ij}$ to represent the variable corresponding to the entry
$\bm{u}[i,j]$.

$\bm{x}^{ij}_{k}(\bm{u}):=\bm{u}_{ik}\bm{u}_{jk}+(1-\bm{u}_{ik})(1-\bm{u}_{jk})\quad\text{for
each }k\in[d],i>j.$

Next, we translate equation 34 as follows.

$\bm{y}^{ij}(\bm{u}):=\prod_{k\in[d]}\left(\bm{u}_{ik}\bm{u}_{jk}+(1-\bm{u}_{ik})(1-\bm{u}_{jk})\right).$

Finally, we can write the polynomial that computes MQAR as follows.

$\bm{z}^{ij}(\bm{u}):=\left(\prod_{k\in[d]}\bm{u}_{ik}\bm{u}_{jk}+(1-\bm{u}_{ik})(1-\bm{u}_{jk})\right)\bm{u}_{(i+1)k}\quad\text{for
each }k\in[d],i>j,$ (36)

where $\bm{u}[i+1,:]\equiv\bm{v}_{j}$. It is then easy to observe that
equation 36 is multi-linear and has degree $2d+1$. ∎

We are now ready to provide the lower bound.

######  Theorem F.5.

A data-independent BaseConv model needs $\log(2d)$-layers to solve
$\mathrm{MQAR}$ for an input sequence $\bm{u}\in\\{0,1\\}^{3N\times d}$ with
$d=\log_{2}(c)$.

###### Proof.

Due to Lemma F.2, we know there exists a multi-linear polynomial that solves
MQAR, and due to [83, Lecture 3, Proposition 4], it is unique. Specifically we
cannot solve MQAR with a multi-linear polynomial of degree $\leq 2d$. Now,
assume that there is a BaseConv model with $L$ layers that exactly solves
MQAR. Then, due to Lemma F.1, this yields a multilinear polynomial $P(\bm{u})$
of degree at most $2^{L}$. Here, if $L\leq\log(2d)$, then the resulting
BaseConv with $L$ layers results in a multilinear polynomial of degree $\leq
2d$. This contradicts the above claim that we cannot have a multi linear
polynomial of degree $<2d+1$ that exactly represents MQAR. Consequently, a
data-independent BaseConv model needs $\geq\log(2d)$-layers to solve
$\mathrm{MQAR}$. ∎

###  F.5 Lower Bound on the Number of Layers for $d\geq\log_{2}{c}$ with
Specific Encodings

####  F.5.1 The Equality Problem

For an input pair $\bm{u}_{1},\bm{u}_{2}$ where each $\bm{u}_{i}$ is a token
drawn from a vocabulary of size $c=|C|$ and embedded in $\\{0,1\\}^{d}$, we
define the equality problem (EQ) as checking whether the two encodings are
equal: $\bm{u}_{1}\equiv\bm{u}_{2}$.

We first note that any model that solves $\mathrm{MQAR}$ also solves EQ via
the following proposition.

######  Proposition F.3.

Any model $M_{\mathrm{MQAR}}$ that solves MQAR also solves EQ using the same
number of layers.

###### Proof.

If there exists a model $\textsc{M}_{\mathrm{MQAR}}$ that solves MQAR using
$L$ layers, then for an arbitrary input instance for EQ given by
$\bm{u}_{1},\bm{u}_{2}\in\mathbb{R}^{2\times d}$, we can produce the following
input instance for MQAR:
$\bm{u}:=\\{(\bm{u}_{1},\mathbbm{1},\bm{u}_{1}),(\bm{u}_{2},\mathbbm{1},\bm{u}_{2})\\}$
and solve EQ using $L$ layers with $\textsc{M}_{\mathrm{MQAR}}$ returning
$\mathbbm{1}$ iff there is a match. ∎

Due to Proposition F.3, we obtain the following corollary.

######  Corollary F.2.

Any lower bound $\overline{L}$ on the number of layers $L$ of BaseConv to
solving EQ is also a lower bound on the number of layers required for solving
$\mathrm{MQAR}$.

We now try to prove a lower bound for the case of $d\geq\log_{2}{c}$. First,
note that there are embeddings here where the lower bound from F.5 holds:
consider the embedding where the first $\log_{2}{c}$ has the compact binary
embedding as before but the last $d-\log_{2}{c}$ bits are the same for all the
tokens. We will instead prove a lower bound for a more interesting set of
embeddings.

####  F.5.2 The $p$-Hot Encoding for $p\geq 1$

######  Definition F.7 ((Almost) $p$-Hot Encoding).

We define the $p$-hot encoding to be the collection of embeddings for a token
$\bm{x}_{t}$ with $0\leq t<c$ such that we express $t$ in base
$\sqrt[p]{c}:(t_{0},..,t_{p-1})\in[0,\sqrt[p]{c})^{p}$ and represent each
$t_{i}$ as one hot encoding in $\\{0,1\\}^{\sqrt[p]{c}}$. That is, we take
$d=p\cdot\sqrt[p]{c}$.

Moreover, we define the almost $p$-hot encoding to be the collection of
embeddings where each $t_{i}$ is mapped in $\\{0,1\\}^{\sqrt[p]{c}-1}$
obtained by dropping the last bit of its one-hot encoding in
$\\{0,1\\}^{\sqrt[p]{c}}$.

Note that both of the encodings have $p$-many blocks derived from each of the
one-hot encodings.

######  Definition F.8 (Block-Exclusive).

We say that a polynomial $P$ with variables in
$\bm{u}:=\left(\bm{u}_{0},\ldots,\bm{u}_{p-1}\right)$ is block-exclusive if
each non-zero monomial in $P$ given by the product

$\prod_{{i\in[p],\ j\in[\sqrt[p]{c}]}}\bm{u}_{i,j}$

does not contain any product of the form $\bm{u}_{i,j}\bm{u}_{i,j^{\prime}}$
for $i\in[p],j,j^{\prime}\in[\sqrt[p]{c}]$.

######  Remark F.4.

The condition specified in Definition F.8 ensures that a block-exclusive
polynomial is necessarily multilinear, as it disallows the term
$\bm{u}_{i,j}\bm{u}_{i,j^{\prime}}$ for $j=j^{\prime}$ in any non-zero
monomial.

######  Lemma F.3.

For any Boolean function $f:\\{0,1\\}\to\\{0,1\\}$ with inputs from the almost
$p$-hot encoding or the $p$-hot encoding setting, there exists a block-
exclusive polynomial equivalent to $f$.

###### Proof.

Given an input $\bm{u}$ to $f$ from the almost $p$-hot encoding or the $p$-hot
encoding such that $\bm{u}:=\left(\bm{u}_{0},\ldots,\bm{u}_{p-1}\right)$, we
first observe that the polynomial $P(\bm{u})$ representing $f({\bm{u}})$
cannot have a non-zero monomial with variables from the same block.
Specifically, for $0\leq j<p$, any non-zero monomial in $P$ cannot have a
product of the form ${\bm{u}}_{j,k}{\bm{u}}_{j,k^{\prime}}$ for $k\neq
k^{\prime}$. To see this, assume that there exists a non-zero monomial in $P$
with at least two terms ${\bm{u}}_{j,k}{\bm{u}}_{j,k^{\prime}}$ from the same
$j$th block in ${\bm{u}}$, then monomial always evaluates to $0$ as the $j$th
block is derived from the one-hot encoding in $\\{0,1\\}^{\sqrt[p]{c}}$ or the
almost one-hot encoding in $\\{0,1\\}^{\sqrt[p]{c}-1}$, and hence, cannot have
more than one bit set to $1$.

Next, if a non-zero monomial in $P$ does contain a product of the form
${\bm{u}}_{j,k}{\bm{u}}_{j,k^{\prime}}$ for $k,k^{\prime}\in[\sqrt[p]{c}]$, we
can define the polynomial

${Q}(\bm{u}):=(\cdots((P(\bm{u})\mod(u_{0,0}^{2}-u_{0,0}))\mod(u_{0,1}^{2}-u_{0,1}))\cdots)\mod(u_{p-1,\sqrt[p]{c}-1}^{2}-u_{p-1,\sqrt[p]{c}-1}).$

Since each entry is Boolean, $Q$ is equivalent to $P$ over Boolean inputs, and
thus, $Q$ is the block-exclusive polynomial equivalent to $f$. ∎

######  Proposition F.4.

Any Boolean function $f:\\{0,1\\}\to\\{0,1\\}$ with inputs from the almost
$p$-hot encoding setting has a unique representation as a block-exclusive
polynomial.

###### Proof.

Due to [83, Proposition 4], we know that every Boolean function $f$ is
represented by a multilinear polynomial. Moreover, from Lemma F.3, we know
that the polynomial $P(\bm{u})$ representing $f({\bm{u}})$ is block-exclusive
for ${\bm{u}}$ with the almost $p$-hot encoding.

To show uniqueness, we replicate the argument from [83, Lecture 3, Proposition
4]: Given two block-exclusive polynomials $P$ and $P^{\prime}$ equivalent to
$f$ with inputs from the almost $p$-hot encoding, we have
$(P-P^{\prime})(\bm{u})\equiv 0$. Now, assume, for the sake of contradiction,
that $P-P^{\prime}\not\equiv 0$. Here, note that as $P-P^{\prime}$ is not
identically zero and we have a non-zero monomial, and since the inputs are
from the almost $p$-hot encoding, we know that this monomial cannot contain
any product of the form $\bm{u}_{j,k}\bm{u}_{j,k^{\prime}}$. Let
$S\subseteq[p]\times[\sqrt[p]{c}-1]$ be a minimal set of indices such that the
monomial $\prod_{(j,k)\in S}\bm{u}_{j,k}$ appears in $P-P^{\prime}$ with non-
zero coefficient. Note that $\chi_{S}$ forms a valid input to $f$ as each
block in $S$ can be assigned at most one non-zero entry. Then, since
$(P-P^{\prime})(\chi_{S})\neq 0$ as every other monomial will get at least one
variable that is assigned to $0$ for $\chi_{S}$ , we achieve a contradiction,
and thus, $P-P^{\prime}$ must be identically zero on inputs from the almost
$p$-hot encoding. ∎

######  Lemma F.4.

The EQ problem in the almost $p$-hot encoding setting is represented by a
block-exclusive polynomial of degree $2p$.

###### Proof.

Each input pair $\bm{u}^{1},\bm{u}^{2}$ to the EQ problem can be represented
as $\bm{u}^{i}:=(\bm{u}^{i}_{0},\ldots,\bm{u}^{i}_{p-1})$ for $i\in\\{1,2\\}$,
where for each $0<j<p$ such that we have

$\bm{u}^{i}_{j}:=(\bm{u}^{i}_{j,0},\ldots,\bm{u}^{i}_{j,\sqrt[p]{c}-2})\in\\{0,1\\}^{\sqrt[p]{c}-1}.$

The following polynomial takes the inner product of each of these one-hot
encodings:

$P^{j}(\bm{u}):=\sum_{k=0}^{\sqrt[p]{c}-2}\bm{u}^{1}_{j,k}\cdot\bm{u}^{2}_{j,k}+(1-\sum_{k=0}^{\sqrt[p]{c}-2}\bm{u}^{1}_{j,k})(1-\sum_{k=0}^{\sqrt[p]{c}-2}\bm{u}^{2}_{j,k})$

for $0<j<p$. Here, note that there can be only be at most $1$ in both
$\bm{u}^{1}_{j}$ and $\bm{u}^{2}_{j}$, and thus, $P^{j}(\bm{u})=1$ iff the
$j$th block agree.

Next, the following polynomial is equivalent to the Boolean function that
solves the EQ problem:

$P(\bm{u}):=\prod_{j=0}^{p-1}P^{j}(\bm{u}),$

and we have $P(\bm{u})=\mathbbm{1}\\{\bm{u}^{1}\equiv\bm{u}^{2}\\}$. Here,
note that $P$ is multi-linear and has degree $2p$ as each $P^{j}$ is a
degree-2 polynomial. Moreover, $P$ is block-exclusive as each $P^{j}$ is
block-exclusive and we only multiply monomials from different blocks in $P$.

∎

######  Proposition F.5.

Let $P$ be the block-exclusive polynomial that solves the EQ problem in the
$p$-hot encoding. Then, $\deg(P)\geq 2p$.

###### Proof.

For the sake of contradiction, assume that there exists a block-exclusive
polynomial $P$ that solves EQ in the $p$-hot encoding setting with degree
$\leq 2p-1$. Then, given an input
${\bm{u}}:=({\bm{u}}_{0},\ldots,{\bm{u}}_{p-1})$ from the almost $p$-hot
encoding, where each block ${\bm{u}}_{i}$ corresponds to the truncated bit
string from the one-hot encoding in $\\{0,1\\}^{\sqrt[p]{c}-1}$, we can
convert this input to the $p$-hot encoding
${\bm{v}}:=({\bm{v}}_{0},\ldots,{\bm{v}}_{p-1})$ as follows:

${\bm{v}}_{i}:=\left({\bm{u}}_{i,0},\ldots,{\bm{u}}_{i,\sqrt[p]{c}-2},1-\sum_{j=0}^{\sqrt[p]{c}-2}{\bm{u}}_{i,j}\right)$

Then, the block-wise multilinear polynomial $Q({\bm{u}})=P({\bm{v}})$ solves
the EQ problem in the almost one-hot encoding setting and has
$\deg(Q)\leq\deg(P)\leq 2p-1$ which contradicts the combination of Proposition
F.4 and Lemma F.4. ∎

######  Theorem F.6.

A data-independent BaseConv model needs at least
$\lfloor\log(2p)\rfloor$-layers to solve $\mathrm{MQAR}$ for an input sequence
$\bm{u}\in\\{0,1\\}^{3N\times d}$ in the $p$-hot encoding setting, where
$d=p\cdot\sqrt[p]{c}$.

###### Proof.

We know from Corollary F.2 that it suffices to show a lower bound for the EQ
problem. Moreover, we know from Proposition F.5 that we cannot solve the EQ
problem in the $p$-hot encoding setting with a block-exclusive polynomial of
degree $\leq 2p-1$. Now, assume that there is a BaseConv model with $L$ layers
that exactly solves EQ in the $p$-hot encoding setting. Then, due to Lemma F.1
and Proposition F.4, this yields a block-exclusive polynomial $P(\bm{u})$ of
degree at most $2^{L}$. Here, if $L<\lfloor\log(2p)\rfloor$ which , then the
resulting BaseConv with $L$ layers results in a block-exclusive polynomial of
degree $\leq 2p-1$. This contradicts the above claim that we cannot have a
block-exclusive polynomial of degree $<2p$ that exactly represents EQ.
Consequently, a data-independent BaseConv model needs
$\geq\lfloor\log(2p)\rfloor$-layers to solve EQ. ∎

Table 7: Based Training Settings | 355M | 1.4B
---|---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.95$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 27 | 36
Hidden Size | 1024 | 1792
MLP Activation | SwiGLU
MLP Width | 2
Num. Linear Attn Layers | 5 | 7
Num. Linear Attn Heads | 16
Taylor Feature Dimension | 16
Linear Attn Positional Encodings | None
Num. Sliding Window Layers | 5 | 7
Sliding Window Size | 64 | 16
Sliding Window Heads | 16
Sliding Window Positional Encodings | Rotary
Num. BaseConv Layers | 17 | 22
BaseConv Projection Expansion Factor | 4
BaseConv Filter Size | 3
BaseConv Activation | SiLU
Table 8: Attention Training Settings | 355M | 1.4B
---|---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.95$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 24 | 36
Hidden Size | 1024 | 1680
Num Heads | 16 | 24
RMSNorm | True
MLP Bias | False
Flash Attn | True
Rotary Emb. Fraction | 0.5
MLP Activation | SwiGLU
MLP Width | 4
Table 9: Mamba Training Settings | 355M | 1.4B
---|---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.95$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 46
Hidden Size | 1024 | 2048
RMSNorm | True
Norm Epsilon | $1e-5$
Dt State | $16$
Dt (Min, Max) | $(0.001,0.1)$
Dt Init. Strategy | Random
Dt Init. Floor | $1e-4$
Dt Scale | $1.0$
Dt Softplus | True
Projection Expansion Factor | 2
Short Conv Filter Size | 4
Table 10: Hyena Training Settings | 355M
---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.95$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 29
Hidden Size | 1024
Num Heads | 1
MLP Width | 2
Short Conv. Filter Size | 3
Exp. Mod. Decay (Fast, Slow) | 0.3, 1.2
Filter Sine Freq. (w) | 14
Filter Order | 64
Filter Inner MLP | 2
Table 11: Hyena Training Settings | 355M
---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.99$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 24 (No Attention Layers)
Hidden Size | 1024
Num Heads | 16
MLP Width | 4
Table 12: Hyena Training Settings | 355M
---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.99$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 19
Hidden Size | 1024
MLP Width | 3.5
Table 13: Gated Linear Attention (GLA) Training Settings | 355M
---|---
Optimizer | Adam
Optimizer momentum | $\beta_{1},\beta_{2}=0.9,0.95$
Optimizer eps | $1e-8$
Precision | BFloat16
Warmup | 1%
Learning rate decay | Cosine
Learning rate (min, base) | 8e-5, 8e-4
Global batch size | 256
Weight decay | 0.1
Num Layers | 24
Hidden Size | 1024
Num Heads | 4
MLP Width | 2