The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

Introduction

Sequential neural networks like RNNs, including their variants such as LSTMs and GRUs , have good performance in capturing temporal dependencies and processing input step-by-step . These advantages make them effective in tasks including time-series prediction and speech recognition . Traditional RNNs and their enhanced variance, LSTMs perform well in testing because of their sequential nature, but their training times tend to be slow and suffer from vanishing or exploding gradient issues, which limit their capabilities to capture long-term dependencies . Transformers , equipped with a self-attention mechanism, provide an efficient solution to the slow training problem by enabling parallelized computations. Large Language Models (LLMs) based on the Transformer architecture, such as GPT-4 , GPT-4o , OpenAI’s o1 , Llama 3.1 , Claude , and Gemini , have become ubiquitous nowadays, and their integrations to modern technology reshaped our expectations of the limits of their capabilities. Transformers are capable of training efficiently on large datasets, but their quadratic memory and time complexity with respect to sequence length make them expensive in resources, both in terms of memory and processing power, during training and inference. Specifically, self-attention mechanisms grows $O(n^{2})$ in terms of computational complexity .

State-space models (SSMs) recently received significant attention as a potential alternative to Transformer-based architecture on inherently sequential tasks . Mamba , built on SSMs, combines the benefits from both RNNs and Transformers architectures. Mamba incorporates the efficient inference and state-tracking capabilities of RNNs and leverages the scalability and parallelizable computations of Transformers. Equipped with long-term memory embedding, Mamba balances the trade-off between training efficiency and inference performance .

As these architectures continue to express the state of modern AI, it is crucial to explore what types of problems they can solve and their limitations. Recent studies using the circuit complexity framework explain the computational capabilities of Mamba. demonstrates that a threshold circuit with constant depth and $c\log n$-precision can simulate depth $d$ SSM and Mamba. Moreover, an $\mathsf{L}$-uniform threshold circuit of constant depth can simulate such SSM and Mamba models. Another work shows Transformers are in $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ with $\operatorname{poly}n$-precision, and they present a new set of metrics to evaluate the circuit complexity of LLMs with $\operatorname{poly}n$-precision. Understanding Mamba’s computational limits with high precision is crucial because we need to know what problems it can theoretically solve and to compare Mamba with Transformers and other architectures. Without such understanding, assumptions about Mamba’s potential to surpass Transformers in terms of sequential reasoning or state tracking remain questionable.

However, from Table 1, prior work primarily focused on low-precision implementations or alternative uniformity conditions, leaving a gap in understanding Mamba’s expressiveness with $\operatorname{poly}(n)$-precision under $\mathsf{DLOGTIME}$-uniformity. This gap is significant because proving Mamba in $\mathsf{TC}^{0}$ with $\operatorname{poly}(n)$-precision reflects real-world scenarios, where higher precision is often necessary. Moreover, $\mathsf{DLOGTIME}$-uniformity is widely considered as a more realistic condition in practice. Unlike $\mathsf{L}$-uniform circuits, which may allow unrealistically complex preprocessing, $\mathsf{DLOGTIME}$-uniform circuits require the structure of the circuit to be computable by highly efficient machines, so $\mathsf{DLOGTIME}$-uniformity reflects practical constraints on constructing and applying the circuits. Therefore, it is natural to raise the question: Can Mamba, implemented with $\operatorname{poly}(n)$-precision, be proved to reside within $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$?

In this paper, we break down the fantasized superiority in Mamba by demonstrating that it falls within the same circuit complexity class $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ with $\operatorname{poly}n$-precision. This result shows SSM and Mamba have the same computational capabilities as Transformers have , indicating that SSM and Mamba, despite their stateful design, cannot solve problems outside $\mathsf{TC}^{0}$, such as arithmetic formula problem, boolean formula value problem, and permutation composition problems if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$.

Beyond and , our contributions are summarized as follows: If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, assume we have the $\operatorname{poly}(n)$-bits precision float point number, constant-depth layers, and $O(n)$ size hidden dimension, then we have

A $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family can simulate Selective SSM (Theorem 4.4).

A $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ circuit family ( Theorem 4.5) can simulate Mamba.

Selective SSM and Mamba are not capable of resolving the arithmetic formula problems, Boolean formula value problems, and permutation composition problems (Theorem 5.1).

Knowing the true computational capabilities of SSM and Mamba in $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ can inform researchers who attempt to use Mamba to solve problems outside $\mathsf{TC}^{0}$. By identifying the constraints of the current design, our work pushed the exploration of the expressiveness of neural network models.

In Section 2, introduce the works related our paper. Section 3 introduces key computational concepts and Mamba definitions that form the basis for subsequent sections. Then, we present the circuit complexity results for Selective SSM and Mamba in Section 4. Section 5 details our hardness results. Finally, Section 6 gives a conclusion.

Related Work

Circuit Complexity, a crucial set of metrics in computational complexity theory, studies the computational power of circuit families. It has valuable applications in comprehending the capabilities of machine learning models . The complexity classes include $\mathsf{AC^{0}}$ represents problems that are highly parallelizable equipped with standard logic gates, which can be solved by constant-depth circuits with unbounded fan-in $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$ gates; $\mathsf{TC^{0}}$ class extends from $\mathsf{AC^{0}}$ with additional majority gates; $\mathsf{NC^{1}}$ problems can be solved by $O(\log n)$-depth circuits with bounded fan-in. These circuit complexity classes form a hierarchy: $\mathsf{AC}^{0}\subset\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}$ . The question of whether $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$ remains an open topic of discussion. demonstrates that while Transformers can simulate nonsolvable semi-automata, their depth is influenced by the length of the input sequence. Building on this, investigates the expressive power of Transformers augmented with Chain-of-Thought (CoT) reasoning in the context of circuit complexity. They propose the following relationships:

Here, $\mathsf{T}[d(n),s(n),e(n)]$ refers to a constant-depth Transformer with an embedding size of $d(n)$, precision $s(n)$ bits, and exponent size $e(n)$ for input length $n$. Meanwhile, $\mathsf{CoT}[T(n),d(n),s(n),e(n)]$ denotes a $T(n)$-step Chain-of-Thought process using a constant-depth Transformer $\mathsf{T}[d(n),s(n),e(n)]$. They use their framework to show that Transformers equipped with CoT are capable of tackling more complex problems. Therefore, circuit complexity has shown its effectiveness in representing the computational capabilities of neural networks.

Limits on Transformers Model.

Transformers have shown outstanding performance on tasks from natural language processing, but they present limited effectiveness in mathematical computations. A series of research highlights the reasoning limitations of Transformer Model . shows that average-hard attention transformers (AHATs) and softmax-attention transformers (SMATs) are in $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ with $O(\operatorname{poly}(n))$-bit float number precision, indicating that they are equivalent to constant-depth threshold circuits with polynomial size, and their ability is limited when handling more complex reasoning tasks which require higher-depth or nonuniform computations. As a result, Transformers with SMATs or AHATs are inherently unable to solve problems outside $\mathsf{TC}^{0}$, especially those that involve many inherently sequential computations. What about Transformers with CoT? Even though Transformers with CoT can address relatively more problems than CoT, Transformers still fail to solve problems requiring reasoning beyond $\mathsf{TC}^{0}$.

Architecture of State-Space Models (SSM).

SSMs have emerged as an alternative model to the popular LLMs, such as RNNs and Transformers. SSM presents ideal performance in tasks involving long-term dependencies and sequential reasoning . The foundation of SSMs uses linear dynamical systems (LDS) or discrete-time state-space equations to represent the system’s internal state and its evolution over time. Using these mechanisms, SSMs are able to capture the sequential nature of data by updating the state iteratively, which has efficient inference and state-tracking . Compared to RNNs, SSMs have better scalability and stability when handling long sequences, and SSMs are capable of resolving the gradient-related issues inherent to RNNs .

Mamba is a recent advancement in SSM architecture, and it combines the efficient parallelizable computation from Transformers. SSMs in Mamba use kernel methods and spectral techniques to enable convolution and facilitate parallelizable computation . Mamba incorporates efficient memory embedding and long-term state representation into its architecture, making itself a strong opponent to the popular LLMs today, such as Transformers. However, despite the theoretical expectations of SSM and Mamba, it is crucial for us to understand the computational limits to conclude whether its capabilities outperform Transformers.

Preliminaries

In Section 3.1, we introduce the float point number. In Section 3.2, we introduce the Mamba block.

1 Float Point Numbers

To compute SSM and Mamba correctly and effectively, we establish the computational framework by providing the definitions of the basic concepts of floating-point numbers and their related operations as follows.

Notably, the operations provided below are not limited to purely theoretical work; in fact, they can be effectively realized in hardware.

We can use the uniform threshold circuit, which has the size of $\operatorname{poly}(n)$ and has a constant depth, to compute all $+,\cdot$, and comparison of two $p$-bit floating-point numbers, as defined in Definition A.14.

Using the same depth uniform threshold circuit as above, we can compute the iterative multiplication of $m$ numbers of floating-point numbers with $q$ bits.

Using the same depth uniform threshold circuit as above, we can compute the iterative addition of $m$ numbers of floating-point numbers with $q$ bits.

For any positive integer $p$ such that $p\leq\operatorname{poly}(n)$, there exists a uniform threshold circuit with size $\operatorname{poly}(n)$ and constant-depth that approximates $\exp(x)$ for any $p$-bit floating-point number $x$, with a relative error not exceeding $2^{-p}$. The depth required for this computation is denoted as $d_{\exp}$.

2 Mamba Blocks

Having established the necessary mathematical foundation, this section introduces the main components of the Mamba architecture, as illustrated in Figure 1. We start by discussing the input projection within the Mamba framework.

After the input projection, Mamba used a 1-D convolution layer to capture local temporal patterns by convolving the input features with a learned kernel.

for $t\in[L]$ and $n\in[N]$, where $X_{t-k,d^{\prime}}=0$ if $t-k<0$, and zero-padding is applied for boundary cases; $W[k,d^{\prime},n]$ selects the contribution of the $d^{\prime}$-th feature at time step $t-k$ to the $n$-th output channel.

Then, the convoluted input goes through a non-linear $\mathsf{SiLU}$ activation function in Mamba.

Now we introduce the softplus activation used in Mamba selection mechanisms as $\tau_{\Delta}$.

Following this, the selection functions dynamically adapt the state-space parameters based on the input sequence, refining the model’s ability to represent sequential dependencies by modulating the state-space matrices $B$, $C$, and $\Delta$ based on learned projection.

With the selection functions implemented, we now introduce the Selective SSM in Mamba.

Finally, we introduce the Mamba output projection, which maps the processed sequence back to the original feature dimension.

Through this progression, we can now define Mamba as a series of composite functions.

Complexity of SSM and Mamba

In Section 4.1, we provide an approximation of the logarithm function within $\mathsf{TC}^{0}$. In Section 4.2, we analyze the complexity of computing Recurrent SSM. In Section 4.3, we investigate the complexity of computing Convolution SSM. In Section 4.4, we establish circuit complexity bounds for selective SSM. In Section 4.5, we present the circuit complexity bounds for Mamba computations.

In this section, we show the approximation of logarithm can be done in $\mathsf{TC}^{0}$ circuit. The logarithm function is a key component of the $\mathsf{Softplus}$ activation function, which plays a central role in the selection mechanisms of the Selective SSM within the Mamba architecture. Therefore, the ability to compute logarithm in $\mathsf{TC}^{0}$ is crucial for ensuring Selective SSM and Mamba operate within constant depth $\mathsf{TC}^{0}$.

To approximate $\log(x)$, we normalize $x=\langle m,e\rangle$ into $r\in[\frac{1}{2},1]$ or $r\in$, depending on whether $e$ is even or odd. This normalization adjusts the exponent to $k$ and can be computed by $\mathsf{TC}^{0}$ circuit in constant depth.

We use Taylor series expansion around 1 to approximate $\log(r)$, and we can get an approximation of $\log(r)$ with relative error bounded by $2^{-p-1}$.

We use the same technique, we can approximate $\log(2)$. Lastly, we compute $\log(x)$ as $\log(x)=\log(r)+k\cdot\log(2)$.

The $\mathsf{TC}^{0}$ circuit in constant depth can compute all operations. ∎

In this section, we show recurrent SSM is in $\mathsf{TC}^{0}$.

From Definition A.17, the Recurrent SSM computation is given by:

$d_{h}$ to compute $\mathcal{H}(X,A,B,\Delta)$ (Lemma B.6),

$d_{\oplus}$ to compute $\sum_{i=1}^{n}\overline{C}_{d,i}\cdot\mathcal{H}(X,A,B,\Delta)_{t,i}$ (Lemma 3.1)

In this section, we show convolution SSM is in $\mathsf{TC}^{0}$.

From Definition A.19, the convolution output sequence is given by:

It can be computed as follows. Using a threshold circuit, we can perform

matrix multiplication to compute $\sum_{d=1}^{D}\overline{K}[d^{\prime},d,k]\cdot X_{t-k,d}$ (Lemma 3.5) and

iterated addition to compute $\sum_{k=0}^{L-1}\sum_{d=1}^{D}\overline{K}[d^{\prime},d,k]\cdot X_{t-k,d}$ (Lemma 3.1),

4 Circuit Complexity Bound for Selective SSM

In this section, we formulate the circuit complexity bound for Selective SSM.

The Selective SSM combines the selection functions, discretization, and state-space dynamics, which we have already proved to be in $\mathsf{TC}^{0}$.

To compute Selective SSM, we can follow the following. Using a threshold circuit, we can compute

5 Circuit Complexity Bound for Mamba

In this section, we formulate the circuit complexity bound for Mamba.

Using a threshold circuit, we can compute

input projections (Lemma 3.5) using matrix multiplication and addition,

output projection (Lemma 3.5) using matrix multiplications and additions,

Therefore, we can get the desired result. ∎

Hardness

In this section, we present the hardness result: Selective SSM and Mamba, which are constrained in $\mathsf{TC}^{0}$, cannot solve problems residing in $\mathsf{NC}^{1}$, such as arithmetic formula evaluation, Boolean formula value problems, and permutation composition. These results show the limitations of Selective SSM and Mamba in their expressive power.

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the Selective SSM and Mamba are not capable of resolving the arithmetic formula evaluation problems, boolean formula value problem, and permutation composition problems.

To show Selective SSM and Mamba cannot solve arithmetic formula evaluation problems, Boolean formula value problems, and permutation composition problems. We leverage the difference between the complexity classes $\mathsf{TC}^{0}$ and $\mathsf{NC}^{1}$, under the assumption $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$.

Arithmetic formula evaluation problems, Boolean formula value problems, and permutation composition problems are defined to be $\mathsf{NC}^{1}$ problems in Section C.1, C.2, and C.3.

From previous proof, we show Selective SSM and Mamba are both in $\mathsf{TC}^{0}$. Therefore, they cannot solve those $\mathsf{NC}^{1}$ problems. ∎

Conclusion

In this paper, we conducted a rigorous mathematical analysis of the computational limits of SSM and Mamba. We use the framework of circuit complexity and demonstrate that Mamba and SSMs, despite their stateful designs, fall into $\mathsf{DLOGTIME}$-uniform $\mathsf{TC}^{0}$ with $\operatorname{poly}(n)$-precision. These results show that SSM and Mamba are fundamentally equivalent to Transformers in terms of computational expressiveness, as their architectures are all constrained by the complexity class $\mathsf{TC}^{0}$. As a result, Mamba cannot solve problems outside $\mathsf{TC}^{0}$, such as arithmetic formula evaluation and Boolean formula value problems, unless $\mathsf{TC}^{0}=\mathsf{NC}^{1}$.

Our contributions include formal proofs of the circuit complexity bounds for Mamba and SSMs, and we show that their computational performances are equivalent to constant-depth uniform threshold circuits. Additionally, we provide hardness results. The hardness results show that these architectures cannot resolve sequential and state-dependent tasks that require higher computational depth. These new findings challenge the assumption that Mamba has higher computational capabilities than Transformers.

By building the theoretical limits of Mamba and SSMs, our work contributes to the broader understanding of the computational power of modern neural network models. We emphasize the need for future innovations to solve problems beyond $\mathsf{TC}^{0}$ so they can solve more complex and inherently sequential problems. We hope our study can inspire more research on designing newer architectures that can balance efficiency, scalability, and enhanced expressiveness.

References

Appendix A Preliminaries

In this section, we introduce more definitions related to our work. In Section A.1, we introduce the circuit complexity classes. In Section A.2, we introduce more float point numbers and their operations. In Section A.3, we define the components of Recurrent SSM. In Section A.4, we define the components of Convolution SSM.

We begin by introducing the notations used in this paper.

A.1 Circuit Complexity

In this section, we provide an introduction to the fundamental concepts of circuit complexity classes.

Let $x$ be an arbitrary element in $\{0,1\}^{*}$. Let $L$ be a subset of $\{0,1\}^{*}$ called a language.

If there is $C_{|x|}\in\mathcal{C}$ (a Boolean circuit) satisfying $C_{|x|}(x)=1$ iff $x\in L$, then we say $L$ is recognized by a family $\mathcal{C}$ of Boolean circuits.

We now introduce $\mathsf{NC}^{i}$ class.

$\mathsf{NC}^{i}$ consists of languages that can be decided by Boolean circuits with a size of $O(\text{poly}(n))$, depth $O((\log n)^{i})$, and utilizing ${\sf OR}$, ${\sf AND}$, and ${\sf NOT}$ gates with bounded fan-in.

When Boolean circuits are allowed to use ${\sf AND}$ and ${\sf OR}$ gates with unbounded fan-in, they become capable of recognizing a broader class of languages. The $\mathsf{AC}^{i}$ class is defined as follows.

$\mathsf{AC}^{i}$ refers to the set of languages that Boolean circuits can recognize with size $O(\operatorname{poly}(n))$, depth $O((\log n)^{i})$, and utilizing ${\sf AND}$, ${\sf OR}$, and ${\sf NOT}$ gates with unbounded fan-in.

Since these three gates may be simulated by ${\sf MAJORITY}$ gates, we arrive at a broader complexity class, $\mathsf{TC}^{i}$.

$\mathsf{TC}^{i}$ includes languages that can be recognized by Boolean circuits with size $O(\operatorname{poly}(n))$, depth $O((\log n)^{i})$, and unbounded fan-in gates for ${\sf OR}$, ${\sf AND}$, ${\sf NOT}$, and ${\sf MAJORITY}$. A ${\sf MAJORITY}$ gate outputs $1$ if more than half of its inputs are $1$.

In Definition A.5, ${\sf THRESHOLD}$ gates or ${\sf MOD}$ gates configured for prime values can replace ${\sf MAJORITY}$ gates. A Boolean circuit that includes any of these gates is referred to as a threshold circuit.

A deterministic Turing machine in polynomial time with respect to the size of the input can recognize the languages in class $\mathsf{P}$.

We define $\mathsf{DLOGTIME}$-uniformity and discuss the relationships between this definition and $\mathsf{L}$-uniformity as follows.

A.2 Float Point Numbers

In this section, we introduce the float point numbers.

With floating points $\langle m_{1},e_{1}\rangle$, $\langle m_{2},e_{2}\rangle$ having $p$-bits, we define the following operations:

A.3 Discretization: Recurrent SSM

In this section, we define and formalize the discretization of recurrent SSMs and their associated components. We provide a structured foundation for understanding their functionality and computation. We begin by introducing the discrete transformation technique that transforms the continuous state-space representations into discrete ones.

Transitioning from the discretization step, we proceed to the hidden state recurrence in recurrent SSM, which is the core update mechanism for hidden states across timesteps.

Finally, we are able to formalize recurrent SSMs, which combine the hidden state update mechanism with the output projection step.

A.4 Discretization: Convolutional SSM

In this section, we extend the formulation of SSM by presenting its convolutional implementations after discretization. These are the core mechanisms that enable its parallel computations. We first show the kernel computation.

where $d^{\prime}\in[D^{\prime}]$ is the output feature dimension index, $d\in[D]$ is the input feature dimension index, and $k\in[M]$ is the time offset index, and $M$ is the length of the kernel.

By using this kernel $\overline{K}$, we can compute the final output sequence through convolution.

Appendix B Complexity of SSM and Mamba

In this section, we provide additional proofs to support our theorem.

In Section B.1, we show the Hadamard product is in $\mathsf{TC}^{0}$. In Section B.2, we show the discretization in SSM is in $\mathsf{TC}^{0}$. In Section B.3, we show approximating logarithm can be done in $\mathsf{TC}^{0}$. In Section B.4, we show the $\mathsf{Softplus}$ Activation is in $\mathsf{TC}^{0}$. In Section B.5, we show the $\mathsf{SiLU}$ Activation is in $\mathsf{TC}^{0}$. In Section B.6, we show the hidden state update function is in $\mathsf{TC}^{0}$. In Section B.7, we show the computation of kernel in Convolution SSM is in $\mathsf{TC}^{0}$. In Section B.8, we show the convolution indexing is in $\mathsf{TC}^{0}$. In Section B.9, we show the 1-D convolution layer in Mamba is in $\mathsf{TC}^{0}$. In Section B.10, we show the selective functions are in $\mathsf{TC}^{0}$.

Now, we present computing entrywise matrix multiplication.

The circuit’s size stays polynomial in $n$ because both $n$ and $d$ are bounded by $\operatorname{poly}(n)$, and each multiplication is implemented using a circuit of poly size. ∎

B.2 Computing Discretization

In this section, we prove computing discretization is in $\mathsf{TC}^{0}$.

The computation involves three main steps: computing $\exp(\Delta A)$, inverting $\Delta A$, and performing matrix multiplications.

The circuit’s size stays polynomial in $n$ because both $n$ and $d$ are bounded by $\operatorname{poly}(n)$, and each operation is implemented using a circuit of poly size. ∎

In this Section, we present the formal proof for approximating logarithm in $\mathsf{TC}^{0}$

Let $p\in O(\operatorname{poly}(n))$. For $\log(x)$ where $x=\langle m,e\rangle$: If $e$ is even, let $r=m\cdot 2^{-p}\in[\frac{1}{2},1)$ and $k=e+p$; otherwise, let $r=m\cdot 2^{-p+1}\in[1,2)$ and $k=e+p-1$.

Compute $\log(r)$ using the Taylor series about 1:

Since $|r-1|<1$, there is an $N\in O(p)$ that makes the relative error at most $2^{-p-1}$. Then we compute $\log(x)$ as follows:

To compute $\log(2)$, use the Taylor series:

Since $N\in O(p)$, the total error is less than or equal to $2^{-p}$.

B.4 Computing the 𝖲𝗈𝖿𝗍𝗉𝗅𝗎𝗌𝖲𝗈𝖿𝗍𝗉𝗅𝗎𝗌\mathsf{Softplus} Activation

In this section, we show the proof for Computing the $\mathsf{Softplus}$ Activation is in $\mathsf{TC}^{0}$

B.5 Computing the 𝖲𝗂𝖫𝖴𝖲𝗂𝖫𝖴\mathsf{SiLU} Activation

In this section, we show the proof of $\mathsf{SiLU}$, used in Mamba is in $\mathsf{TC}^{0}$.

From Definition 3.8, $\mathsf{SiLU}$ is given as

where $\sigma(z)$ denotes the sigmoid function, defined as:

In this section, we prove the hidden state update in Recurrent SSM is in $\mathsf{TC}^{0}$.

From Definition A.16, the hidden state recurrence is given by:

The computation of $\mathcal{H}(X,A,B,\Delta)$ involves two steps: iterative addition, multiplication, and addition:

The total depth of the circuit for computing $\mathcal{H}(X,A,B,\Delta)$ is given by:

Since the circuit size is polynomial in $n$ and the depth $d_{h}$ is constant, we get our desired result. ∎

In this section, we show the computation of Kernel in $\mathsf{TC}^{0}$.

From Definition A.18, the convolution kernel computation is given by:

Since $\overline{A}$ is a diagonal matrix, each entry $(\overline{A}^{k})_{i,i}$ can be computed as $(\overline{A}_{i,i})^{k}$. By part 2 of Lemma 3.1, iterated multiplication can be computed by a threshold circuit with constant depth $d_{\otimes}$. The computations of $(\overline{A}_{i,i})^{k}$ for all $i$ are independent, so $\overline{A}^{k}$ can be computed in depth $d_{\otimes}$.

In this section, we prove the indexing operation in 1-D Convolution is in $\mathsf{TC}^{0}$.

The indexing operation has two primary operations: checking the boundary and retrieving the value.

To compute boundary checking for each time step $t\in[L]$, kernel offset $k\in[K]$, and feature $d\in[D]$, we need to check if $t-k<0$ for the zero-padding. We define $\mathsf{BoundaryCheck}(t,k)$ function as follows:

To compute value retrieval, we can establish the following:

where if $\mathsf{BoundaryCheck}(t,k)=1$, $X_{t-k,d}$ will be evaluated to so we apply zero padding.

In this section, we show the 1-D convolution layer in Mamba is in $\mathsf{TC}^{0}$.

The 1-d convolution from Definition 3.7 is the following:

this convolution has three primary operations: matrix indexing, entry-wise multiplications, and summation.

In this section, we show selective functions computation are in $\mathsf{TC}^{0}$.

The selection mechanisms from Definition 3.10 are the following $s_{B}(X)=W^{B}XP^{B},s_{C}(X)=W^{C}XP^{C},s_{\Delta}(X)=\tau_{\Delta}\cdot\mathsf{Broadcast}_{D}(W^{\Delta}XP^{\Delta}),$.

These computations have three main operations: matrix multiplications, broadcasting, and non-linear activations.

Appendix C Our Hardness Results

We present the problems about the arithmetic formula in Section C.1. We analyze the Boolean formula value problem in Section C.2. We introduce the permutation composition problem in Section C.3. In Section C.4, we state our four hardness results.

Now, we show the following definition from .

For $i\in[n]$, $X_{i}$ is an arithmetic formula.

An arithmetic formula $A$ with indeterminates $X_{1},\ldots,X_{n}$ is denoted by $A(X_{1},\ldots,X_{n})$.

After defining the arithmetic formula, we then present its computational implications.

In , they have shown that the problem defined in Definition C.2 belongs to $\mathsf{NC}^{1}$.

C.2 The Second Problem

In this section, we show the second problem.

We have $\Sigma=\{0,1,\land,\lor,\lnot,(,)\}$. We define the Boolean formula by the following:

We have and $1$ being the Boolean formulas.

Suppose we have $\beta,\alpha$ being the Boolean formulas. Then, we can get that $(\alpha\land\beta)$, $(\lnot\alpha)$, and $(\alpha\lor\beta)$ being the Boolean formulas.

We define $|\alpha|$ to be the amount of symbols from $\alpha$ (which is a string).

We define the Boolean formula by the following:

We have and $1$ being the Boolean formulas.

Suppose we have $\beta$ being the Boolean formulas. Then, we can get that $(\alpha\lnot)$ being the Boolean formulas.

Suppose we have $\beta,\alpha$ being the Boolean formulas. Suppose $|\alpha|$ is greater than or equal to $|\beta|$. Then, we can get that $\alpha\beta\land$ and $\alpha\beta\lor$ are the Boolean formulas.

We use 0 to denote False and 1 to denote True.

Consider a problem that decides the Boolean formula’s true value. This problem falls in $\mathsf{NC}^{1}$.

C.3 Permutation Composition Problem

In this section, we present the permutation composition problem as established in and its computational implications.

A permutation is a bijection $\pi:[n]\to[n]$, where $[n]=\{1,2,\ldots,n\}$ . The set of all permutations on $[n]$ forms a group $S_{n}$, called the symmetric group. A permutation $\pi\in S_{n}$ may be represented in standard forms such as cycle notation or pointwise mapping.

The composition of two permutations $\pi_{1},\pi_{2}\in S_{n}$ is the permutation $\pi=\pi_{2}\circ\pi_{1}$ , defined by $\pi(x)=\pi_{2}(\pi_{1}(x))$ for all $x\in[n]$ . The composition of a sequence of permutations $\pi_{1},\pi_{2},\ldots,\pi_{k}\in S_{n}$ is given by:

The permutation composition problem is defined as if there is a sequence of permutations $\pi_{1},\pi_{2},\ldots,\pi_{k}\in S_{n}$ represented in a standard form, then the result of the composition $Pi=\pi_{k}\circ\pi_{k-1}\circ\cdots\circ\pi_{1}$ is expressed in the same representation.

A specific instance of the permutation composition problem is the word problem for permutations. This problem is defined as if there is a sequence of permutations $\pi_{1},\pi_{2},\ldots,\pi_{k}\in S_{n}$, then we need to determine whether $\Pi=\pi_{k}\circ\pi_{k-1}\circ\cdots\circ\pi_{1}$ equals the identity permutation $e$, where $e(x)=x$ for all $x\in[n]$.

The following theorems highlight the significance of the permutation composition problem within computational complexity:

Any language recognized by a fan-in 2 Boolean circuit of depth $d=O(\log n)$ can be recognized by a width-5 permutation branching program (PBP) of polynomial size. Consequently, the class of languages recognized by polynomial-size PBPs of bounded width equals $\mathsf{NC}^{1}$.

The word problem for the group $S_{5}$, which involves determining whether a composition of permutations equals the identity, is $\mathsf{NC}^{1}$-complete under $\mathsf{AC}^{0}$ reductions.

C.4 Results About Hardness

We introduce the hardness results for arithmetic formula evaluation problems.

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have that Definition C.2 cannot be solved by the SSM.

It is by Theorem 4.4, Lemma C.3, and Fact A.8. ∎

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have that Definition C.2 cannot be solved by the Mamba.

It is by Theorem 4.5, Lemma C.3, and Fact A.8. ∎

We introduce the hardness results for the Boolean formula problem.

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have that Definition C.6 cannot be solved by the SSM.

It is by Theorem 4.4, Lemma C.7, and Fact A.8. ∎

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have that Definition C.6 cannot be solved by the Mamba.

It is by Theorem 4.5, Lemma C.7, and Fact A.8. ∎

We introduce the hardness results for permutation composition problems.

Here, we show SSM and Mamba cannot solve Width-5 PBPs from Lemma C.12.

If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the SSM cannot solve the Width-5 PBPs.

It is by Theorem 4.4, Lemma C.12, and Fact A.8. ∎

If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the Mamba cannot solve the Width-5 PBPs.

It is by Theorem 4.5, Lemma C.12, and Fact A.8. ∎

Here, we show SSM and Mamba cannot solve the word problem from Lemma C.13.

If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the SSM cannot solve the word problem.

It is by Theorem 4.4, Lemma C.13, and Fact A.8. ∎

If $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the Mamba cannot solve the word problem.

It is by Theorem 4.5, Lemma C.13, and Fact A.8. ∎

if $\mathsf{TC}^{0}\neq\mathsf{NC}^{1}$, float point number is $\operatorname{poly}(n)$-bits precision, layers are constant-depth, and hidden dimension is $O(n)$ size, then we can have the Selective SSM and Mamba cannot solve the arithmetic formula evaluation problems, boolean formula value problem, and permutation composition problems.

Based on Lemma C.14, C.15, C.16, C.17, C.18, C.19, C.20, and C.21.

We conclude the Selective SSM and Mamba cannot solve the Definition C.6 and Definition C.2, and permutation composition problems.

Appendix D More Related Work

Besides Mamba, various techniques have been developed to optimize the approximation of attention computation in the transformer architecture, aiming to address the quadratic complexity. Both Mamba and Transformer are LLMs. Attention optimization includes methods for optimizing attention-related regression problems , multi-layer attention optimization , cross-attention mechanisms , applications of Hopfield Models , and approaches to enhance the tensor-based attention approximation .